机器学习与高维信息检索 - Note 5 - (深度）前馈神经网络（(Deep) Feedforward Neural Networks）及基于CVXOPT的相关实例

Note 5 - (深度）前馈神经网络（(Deep) Feedforward Neural Networks）及相关实例

5.1 FNN的定义和动机

粗略地说，前馈神经网络（FNN）是一种特殊的函数类，在最小化任何一种预期损失方面都非常强大，但代价是要训练大量的参数。更确切地说，考虑一个输入变量$\mathcal{X}\in {\mathbb{R}}^p$ 和一个函数类$\mathcal{F}$，我们想从中找出一个函数$f$，使某个损失函数$L$的期望值最小。例如，考虑简单的损失函数$L(f(\mathcal{X}))=\Vert f(\mathcal{X})?\mathcal{X}{\Vert }_2^2$，用于旨在重建$\mathcal{X}$样本的自动编码器。这里，$f$由编码器函数（映射到一个低维空间）和解码器函数（映射回原始数据空间）的连接组成。

监督学习的另一个例子是回归，我们有一个输入和输出变量的联合分布$(\mathcal{X},\mathcal{Y})$，目的是在$\mathcal{F}$中找到最佳$f$，使$L(f(\mathcal{X}),\mathcal{Y})=\Vert f(\mathcal{X})?\mathcal{Y}{\Vert }_2^2$的期望最小。我们在本节后面讨论多级分类。

如果$\mathcal{F}$中的所有函数都可以用一组参数来描述，比如说$\Theta \in {\mathbb{R}}^N$，如果给定一些训练用的样本，比如说$n$，那么这些学习问题就会产生一个最小化过程

$$\hat{\Theta }=\arg \underset{\Theta \in {\mathbb{R}}^N}{\min }\frac{1}{n}\sum _{i}L\left(f_{\Theta }\left({\mathbf{x}}_i\right)\right).\text{\hspace{1em}(5.)}$$

许多应用中非常重要的一类函数是所谓的前馈神经网络$(FNN)$。前馈神经网络是线性函数${}^1$的串联。

$${\phi }_{\mathbf{W}}:{\mathbb{R}}^p\to {\mathbb{R}}^m,\mathbf{h}?\mathbf{W}\mathbf{h}\text{\hspace{1em}(5.)}$$

${}^1$ 这也包括仿射函数，因为我们可以简单地将额外的分量1附加到我们的输入向量上。

后面是所谓的激活函数，对一个向量进行分量操作。激活函数的例子有：线性整流函数(Rectified Linear Unit, ReLU)
σ(t):=max?{0,t},(5.)\sigma(t):=\max \{0, t\},\tag{5.} σ(t):=max{ 0,t},(5.)

和其他一些激活函数，见维基百科。通过对符号的轻微滥用，我们也用以下方式表示向量激活函数
$$\sigma :{\mathbb{R}}^m\to {\mathbb{R}}^m,\mathbf{x}??\begin{array}{c}\sigma \left(x_1\right)\\ ?\\ \sigma \left(x_m\right)\end{array}?\text{\hspace{1em}(5.)}$$

一个前馈神经网络是一个函数
$$f:{\mathbb{R}}^p\to {\mathbb{R}}^o,\mathbf{x}?{\sigma }_l?{\phi }_{{\mathbf{W}}_l}???{\sigma }_1?{\phi }_{{\mathbf{W}}_1}(\mathbf{x}),\text{\hspace{1em}(5.)}$$

其中，像往常一样，$?$表示函数的连接，不同的函数类$\mathcal{F}$由不同的激活函数、层数$l$和矩阵的尺寸 ${\mathbf{W}}_i\in {\mathbb{R}}^{n_i\times m_i}$定义。如果层数超过三层，我们通常称这样的FNN为深度前馈神经网络。注意，输出维度$o$是由损失函数决定的，因为FNN的输出可以作为损失的输入。

5.2 训练FNNs

在实践中训练FNN本身就是一门艺术，有许多技巧和正则化技术决定了学习一个强大的FNN的失败或成功。在这一节中，我们重点讨论为一般问题（5.1）寻找最佳FNN的基本方法，即在给定的FNN类别中寻找最佳权重$\hat{\Theta }=\left({\mathbf{W}}_1,\dots {\mathbf{W}}_L\right)$。事实上，它是一种迭代更新权重的梯度下降方法，该方法在文献中被称为反向传播（backpropagation）。在下文中，我们将描述它的工作原理。

在这里，我们在本科数学课程中需要的最重要的工具是链式法则和雅可比矩阵。回顾一下，如果$g：{\mathbb{R}}^k?{\mathbb{R}}^l$ 和$h:{\mathbb{R}}^l\to {\mathbb{R}}^m$是两个函数，$g$在$\mathbf{x}$处可微，$h$在$\mathbf{y}=g(\mathbf{x})$处可微，雅可比矩阵${\mathbf{J}}_g(\mathbf{x})$和${\mathbf{J}}_h(\mathbf{y})$。那么关于$\mathbf{x}$的函数$h?g:{\mathbb{R}}^k\to {\mathbb{R}}^m$在雅可比矩阵${\mathbf{J}}_{h?g}(\mathbf{x})={\mathbf{J}}_h(g(\mathbf{x})?{\mathbf{J}}_g(\mathbf{x})$处是可微的。

Examples

• (导数的线性)如果在上述介绍的背景中，$h$是一个简单的线性变换，由矩阵乘以$\mathbf{W}$得到，那么

$${\mathbf{J}}_{\mathbf{W}?g}(\mathbf{x})=\mathbf{W}?{\mathbf{J}}_g(\mathbf{x})$$

• 由于第$i$次输出只取决于$x_i$，(5.4)中$\sigma$的雅可比矩阵是一个平方对角矩阵，其形式为
  $${\mathbf{J}}_{\sigma }(\mathbf{x})=?\begin{array}{lll}{\sigma }^{\prime }\left(x_1\right)& & \\ & ?& \\ & & {\sigma }^{\prime }\left(x_m\right)\end{array}?$$

• 为了定义函数的雅可比矩阵，与右边的一个矢量相乘
  $$\mathrm{mult}(\mathbf{x}):{\mathbb{R}}^{m\times n}\to {\mathbb{R}}^m,\mathbf{W}?\mathbf{W}\mathbf{x},$$
  我们首先需要将$mn$变量（这里以矩阵结构给出）嵌入${\mathbb{R}}^{mn}$。这可以通过各种方式实现，但如果我们选择一行接一行地嵌入，即
  $$\pi :\mathbf{W}=?\begin{array}{c}{\mathbf{w}}_1^{?}\\ ?\\ {\mathbf{w}}_m^{?}\end{array}???\begin{array}{c}{\mathbf{w}}_1\\ ?\\ {\mathbf{w}}_m\end{array}?\in {\mathbf{R}}^{mn}$$

注意：$\pi$是将$m\times n$维的矩阵映射成一个单一维度的向量，该向量的长度为$m?n$.

那么雅可比矩阵具有良好的排列形式

$${\mathbf{J}}_{\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}(\mathbf{x})}=?\begin{array}{ccc}{\mathbf{x}}^{?}& & \\ & ?& \\ & & {\mathbf{x}}^{?}\end{array}?\in {\mathbb{R}}^{m\times mn}.$$

注意，由于$\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}(\mathbf{x})$的线性，雅可比矩阵不依赖于W。

为了计算成本函数（5.1）相对于权重的梯度$\Theta =\left({\mathbf{W}}_l,\dots {\mathbf{W}}_1\right)$，我们注意到它是一个输入数据$\mathbf{x}$的损失函数梯度的平均值，即
$$F\left({\mathbf{W}}_l,\dots ,{\mathbf{W}}_1\right):=L?{\sigma }_l?{\phi }_{{\mathbf{W}}_l}???{\sigma }_1?{\phi }_{{\mathbf{W}}_1}(\mathbf{x}).$$

因此，只需计算取决于一个输入信号的$F$的梯度，然后对所有训练数据${\mathbf{x}}_i$进行平均。为方便起见，我们表示为

$${\mathbf{h}}_j:={\sigma }_j?{\phi }_{{\mathbf{W}}_j}???{\sigma }_1?{\phi }_{{\mathbf{W}}_1}(\mathbf{x})$$

是FNN的第$j$层后的输出。对于$0<j<l$，${\mathbf{h}}_j$被称为FNN的第$j$隐藏层，${\mathbf{h}}_l$被称为输出层，${\mathbf{h}}_0:=\mathbf{x}$为FNN的输入。

我们定义函数的雅克比矩阵通过${}^2$$\frac{?}{?{\mathbf{W}}_j}F\in {\mathbb{R}}^{1\times m_j{n}_j}$

$${\mathbf{W}}_j?F\left({\mathbf{W}}_l,\dots ,{\mathbf{W}}_j,\dots ,{\mathbf{W}}_1\right).\text{\hspace{1em}(5.13)}$$

${}^2$ 由于$F$是实值的，这也是梯度的转置。

利用链式规则和上一节的例子，关于不同权重矩阵${\mathbf{W}}_i$的导数由以下公式给出
$$\begin{array}{rl}\frac{?}{?{\mathbf{W}}_l}F& ={\mathbf{J}}_L\left({\mathbf{h}}_l\right)?{\mathbf{J}}_{{\sigma }_l}\left({\mathbf{W}}_l{\mathbf{h}}_{l?1}\right)?{\mathbf{J}}_{\mathbf{m}\mathbf{u}\mathbf{l}\mathbf{t}\left({\mathbf{h}}_{l?1}\right)}\\ \frac{?}{?{\mathbf{W}}_{l?1}}F& ={\mathbf{J}}_L\left({\mathbf{h}}_l\right)?{\mathbf{J}}_{{\sigma }_l}\left({\mathbf{W}}_l{\mathbf{h}}_{l?1}\right)?{\mathbf{W}}_1?{\mathbf{J}}_{{\sigma }_{l?1}}\left({\mathbf{W}}_{l?1}{\mathbf{h}}_{l?2}\right)?{\mathbf{J}}_{\text{mult }\left({\mathbf{h}}_{l?2}\right)}\\ & \dots \\ \frac{?}{?{\mathbf{W}}_j}F& ={\mathbf{J}}_L\left({\mathbf{h}}_l\right)?{\mathbf{J}}_{{\sigma }_l}\left({\mathbf{W}}_l{\mathbf{h}}_{l?1}\right)?{\mathbf{W}}_1?{\mathbf{J}}_{{\sigma }_{l?1}}\left({\mathbf{W}}_{l?1}{\mathbf{h}}_{l?2}\right)?{\mathbf{J}}_{l?1}??{\mathbf{J}}_{\text{mult }\left({\mathbf{h}}_{j?1}\right)},\end{array}$$

在实践中，初始权重通常从正态分布中随机选择，然后用上述梯度和步长$\alpha >0$单独更新。选择步长的算法和方法已经超出了本讲座的范围。注意，我们必须 "重塑(reshape) "梯度(即$\frac{?}{?{\mathbf{W}}_i}F$的转置)成矩阵形式通过将（5.9）中的矩阵嵌入${\pi }_j$进行倒置。我们最后得到了更新规则
$${\mathbf{W}}_j\leftarrow {\mathbf{W}}_j?\alpha {\pi }_j^{?1}{\left(\frac{?}{?{\mathbf{W}}_j}F\right)}^{?}.\text{\hspace{1em}(5.14)}$$

5.3 用FNNs进行多类分类

多类分类考虑的问题是将输入的$\mathcal{X}\in {\mathbb{R}}^p$分配给多个（比如$C$）类中的一个。我们通过随机变量$(\mathcal{X},\mathcal{Y})$对该问题进行建模，其中$\mathcal{X}\in {\mathbb{R}}^p$和Y∈{e1,…,eC}\mathcal{Y} \in\left\{\mathbf{e}_{1}, \ldots, \mathbf{e}_{C}\right\}Y∈{ e1?,…,eC?}是${\mathbb{R}}^C$中的$C$标准基向量之一。一个实现$\mathbf{y}={\mathbf{e}}_c$意味着属于$c$类的事件是真的。这种对输出变量的建模也被称为独热码（one-hot-encoding）。

用FNN进行多类分类的思路是：$\mathcal{X}$作为网络的输入，输出是${\mathbb{R}}^C$中的一个向量，应该反映给定$\mathcal{X}$的类分布的概率。更确切地说，如果$\mathbf{x}$是$\mathcal{X}$的实现，如果$f$表示FNN，那么输出向量${\mathbf{h}}_l:=f(\mathbf{x})$的第$c$分量应该是$\mathcal{Y}$属于$c$类的概率，给定$\mathrm{x}$，即
$${\mathbf{h}}_l\approx ?\begin{array}{c}\mathrm{Pr}\left(\mathcal{Y}={\mathbf{e}}_1\mid \mathcal{X}=\mathbf{x}\right)\\ ?\\ \mathrm{Pr}\left(\mathcal{Y}={\mathbf{e}}_C\mid \mathcal{X}=\mathbf{x}\right)\end{array}?$$
因此，最后一个激活函数${\sigma }_l$的动机是为$C$类输出一个概率分布，实际上意味着输出向量的条目在0和1之间，并且它们加起来是1。这里一个突出的选择是softmax函数，由以下公式给出
$$\sigma :{\mathbb{R}}^C\to {\mathbb{R}}^C,?\begin{array}{c}{a}_1\\ ?\\ a_C\end{array}??\frac{1}{{\sum }_c\exp a_c}?\begin{array}{c}\exp a_1\\ ?\\ \exp a_C\end{array}?$$

练习：计算softmax函数的Jacobi-Matrix

我们训练网络所需要的损失函数必须衡量预测的分布与通过我们的训练集观察到的分布的对应程度 $\left({\mathbf{x}}_i,{\mathbf{y}}_i\right),i=1,\dots ,n$。注意，这些观察到的分布是确定的，也就是说，如果${\mathbf{x}}_i$被标记为$c$或0类，那么$y_c:=\mathrm{Pr}\left(\mathcal{Y}={\mathbf{e}}_c\mid \mathcal{X}={\mathbf{x}}_i\right)=1$。一般来说，比较两个概率分布$\mathbb{P}=\left(p_1,\dots p_C\right)$和$\mathbb{Q}=\left(q_1,\dots q_C\right)$在同一基础的$C$事件集合的一种常见方法是使用交叉熵，见维基百科。

$$H(\mathbb{P},\mathbb{Q})=?\sum _{c=1}^C{p}_c\log q_c.$$

在我们的案例中，有一个分布是确定性的，这可以简化为损失函数
$$L\left(f(\mathcal{X}),{\mathbf{y}}_c\right)=?\log f(\mathcal{X}{)}_c$$

其中$f$是一个以softmax为输出的FNN，$f(\mathcal{X}{)}_c$表示其$c$的条目。对于训练，像往常一样，我们使用训练数据上的损失的经验期望值，这导致了优化问题
$$\left({\hat{\mathbf{W}}}_l,\dots ,{\hat{\mathbf{W}}}_1\right)=\arg \underset{\left({\mathbf{W}}_l,\dots ,{\mathbf{W}}_1\right)}{\min }\left\{?\frac{1}{n}\sum _i\log f_{\left({\mathbf{W}}_{l,\dots },{\mathbf{W}}_1\right)}{\left({\mathbf{x}}_i\right)}_{c_i}\right\}$$

5.4 CVXOPT 实例

机器学习任务通常被认为是优化问题，例如，最小化误差函数或最大化概率。理想情况下，优化问题是凸的，这意味着任何局部最小值都是配方的全局最小值。假设已经有一些关于凸优化的基本知识。这个任务的目的是让我们熟悉CVXOPT，这是一个使用最广泛的凸优化工具箱。注意：如果CVXOPT不接受NumPy数组，请尝试将其转换为double。

1. 进入cvxopt.org，按照发行版本的安装说明进行安装。对于conda，需要运行
   conda install -c conda-forge crxopt
2. 浏览cvxopt.org上的例子部分，了解CVXOPT不同求解器的功能概况。
3. 实现一个函数minsq，它输入一个形状为(m, n)的NumPy数组A，和一个形状为(m,)的NumPy数组y作为参数，并返回一个形状为(n,)的NumPy数组$x$，解决以下问题。
   $$\underset{\mathbf{x}}{\min }\Vert \mathbf{A}\mathbf{x}?\mathbf{y}\Vert$$
   用适当的输入来测试函数，并将结果与使用np.linalg.pinv得到的结果进行比较。通过向y添加白高斯噪声来进行实验。

5.4.1 CVXOPT 简介

5.4.1.1 创建矩阵

CVXOPT 具有分离的密集和稀疏矩阵对象。此示例说明了创建密集和稀疏矩阵的不同方法。

使用该matrix()函数创建一个密集矩阵；它可以从列表（或迭代器）创建：

>>> from cvxopt import matrix
>>> A = matrix([1.0, 2.0, 3.0, 4.0, 5.0, 6.0], (2,3))
>>> print(A)
[ 1.00e+00  3.00e+00  5.00e+00]
[ 2.00e+00  4.00e+00  6.00e+00]
>>> A.size
(2, 3)

或来自列表列表，其中每个内部列表表示矩阵的一列：

>>> B = matrix([ [1.0, 2.0], [3.0, 4.0] ])
>>> print(B)
[ 1.00e+00  3.00e+00]
[ 2.00e+00  4.00e+00]

更广泛地说，内部列表可以代表块状列。

print(matrix([ [A] ,[B] ]))
[ 1.00e+00  3.00e+00  5.00e+00  1.00e+00  3.00e+00]
[ 2.00e+00  4.00e+00  6.00e+00  2.00e+00  4.00e+00]

更多的，参考文档。

5.4.1.2 矩阵索引

索引稠密矩阵和稀疏矩阵有两种方法：单参数索引和双参数索引。在双参数索引中，使用两个索引集I和J对矩阵进行索引 。

>>> from cvxopt import matrix
>>> A = matrix(range(16),(4,4))
>>> print(A)
[  0   4   8  12]
[  1   5   9  13]
[  2   6  10  14]
[  3   7  11  15]
>>> print(A[[0,1,2,3],[0,2]])
[  0   8]
[  1   9]
[  2  10]
[  3  11]

索引集可以是整数、列表、整数矩阵或切片。

>>> print(A[1,:])
[  1   5   9  13]
>>> print(A[::-1,::-1])
[ 15  11   7   3]
[ 14  10   6   2]
[ 13   9   5   1]
[ 12   8   4   0]

在单参数索引中，通过按列优先顺序考虑矩阵（即，通过从左到右堆叠列）以向量形式对矩阵进行索引。

>>> A[::5] = -1
>>> print(A)
[ -1   4   8  12]
[  1  -1   9  13]
[  2   6  -1  14]
[  3   7  11  -1]

这对于访问不是子矩阵的矩阵部分非常有用，例如，矩阵的对角线部分。

5.4.1.3 求解线性规划

可以通过该solvers.lp()函数指定线性程序。举个例子，我们可以解决这个问题

$$\begin{array}{ll}\text{minimize}& 2x_1+x_2\\ \text{subject to}& ?x_1+x_2\le 1\\ & x_1+x_2\ge 2\\ & x_2\ge 0\\ & x_1?2x_2\le 4\end{array}$$

如下：

>>> from cvxopt import matrix, solvers
>>> A = matrix([ [-1.0, -1.0, 0.0, 1.0], [1.0, -1.0, -1.0, -2.0] ]) # the factors of the bounds
>>> b = matrix([ 1.0, -2.0, 0.0, 4.0 ]) # constants
>>> c = matrix([ 2.0, 1.0 ]) # minimized function
>>> sol=solvers.lp(c,A,b)pcost       dcost       gap    pres   dres   k/t0:  2.6471e+00 -7.0588e-01  2e+01  8e-01  2e+00  1e+001:  3.0726e+00  2.8437e+00  1e+00  1e-01  2e-01  3e-012:  2.4891e+00  2.4808e+00  1e-01  1e-02  2e-02  5e-023:  2.4999e+00  2.4998e+00  1e-03  1e-04  2e-04  5e-044:  2.5000e+00  2.5000e+00  1e-05  1e-06  2e-06  5e-065:  2.5000e+00  2.5000e+00  1e-07  1e-08  2e-08  5e-08
>>> print(sol['x'])
[ 5.00e-01]
[ 1.50e+00]

5.4.1.4 求解二次规划

二次规划可以通过该solvers.qp()函数求解。例如，我们可以解决 QP

$$\begin{array}{ll}\text{minimize}& 2x_1^2+x_2^2+x_1{x}_2+x_1+x_2\\ \text{subject to}& x_1\ge 0\\ & x_2\ge 0\\ & x_1+x_2=1\end{array}$$
如下：

>>> from cvxopt import matrix, solvers
>>> Q = 2*matrix([ [2, .5], [.5, 1] ])
>>> p = matrix([1.0, 1.0])
>>> G = matrix([[-1.0,0.0],[0.0,-1.0]])
>>> h = matrix([0.0,0.0])
>>> A = matrix([1.0, 1.0], (1,2))
>>> b = matrix(1.0)
>>> sol=solvers.qp(Q, p, G, h, A, b)pcost       dcost       gap    pres   dres0:  0.0000e+00  0.0000e+00  3e+00  1e+00  0e+001:  9.9743e-01  1.4372e+00  5e-01  4e-01  3e-162:  1.8062e+00  1.8319e+00  5e-02  4e-02  5e-163:  1.8704e+00  1.8693e+00  6e-03  2e-03  1e-154:  1.8749e+00  1.8748e+00  2e-04  6e-05  6e-165:  1.8750e+00  1.8750e+00  2e-06  6e-07  7e-166:  1.8750e+00  1.8750e+00  2e-08  6e-09  1e-15
>>> print(sol['x'])
[ 2.50e-01]
[ 7.50e-01]

5.4.2 实例的解决方法

实现一个函数minsq，它输入一个形状为(m, n)的NumPy数组A，和一个形状为(m,)的NumPy数组y作为参数，并返回一个形状为(n,)的NumPy数组$x$，解决以下问题。
$$\underset{\mathbf{x}}{\min }\Vert \mathbf{A}\mathbf{x}?\mathbf{y}\Vert$$
用适当的输入来测试函数，并将结果与使用np.linalg.pinv得到的结果进行比较。通过向y添加白高斯噪声来进行实验。

from cvxopt import matrix, solvers
import numpy as npdef minsq(A, y):P=matrix(np.dot(A.T,A).astype('double'))q=matrix(-np.dot(A.T,y).astype('double'))x=solvers.qp(P,q)return np.array(x['x'])A=np.array([[10, 40],[20, 0],[-30, 40]])
y=np.array([50,20,10])+np.random.randn(3,)print('A:', A)
print('y:', y)
print('x:', minsq(A,y).squeeze())
print('np.dot(pinv(A),y):', np.dot(np.linalg.pinv(A),y))

结果如下

A: [[ 10  40][ 20   0][-30  40]]
y: [49.88665691 19.21406554  9.38923507]
x: [0.99519146 0.98974651]
np.dot(pinv(A),y): [0.99519146 0.98974651]