标签：opt right 入门感知机算法 vec omega left

前言

人工神经网络（Artificial neural networks，ANNs）被广泛认为诞生于 20 世纪四五十年代，其核心理论可以追溯到 19 世纪初 Adrien-Marie Legendre 发明的最小二乘法，而在今天，经过了半个世纪互联网和计算机技术的迅猛发展，这片耕耘良久的沃土重新掀起了机器学习的研究热潮。

本文主要介绍感知器算法、多层神经网络及其后向传播算法，推导过程主要参考自胡浩基教授的机器学习公开课程。

文章面向有一定基础的读者，至少要对二分类问题和线性分类有一定了解，如果是零基础的读者，建议先阅读上一篇关于支持向量机的文章。

什么是人工神经网络

神经元是神经系统功能的基本单位，大量的神经元构成了我们的大脑，电化学信号在这些神经元之间传递，赋予了我们思考的能力。人类为了在计算机上重现生物神经元的功能，对其进行数学建模，然后这些 人工神经元（Artificial neuron）被组合起来，形成人工神经网络，用以处理复杂问题。

和上一篇文章介绍的支持向量机一样，我们将大量的训练样本输入到人工神经网络中，每个人工神经元中的权重值将在训练过程中被不断修正，最终使人工神经网络具备对样本的判别能力。这就像是人类的学习过程，先根据自己的判断得出答案，再参考正确答案，对比差异，调整解题思路，经过大量训练后，解题能力将得到提升。

人工神经元

下图展示的是生物多极神经元的结构，图中可以看到，多个信号从树突（Dendrite）输入，在胞体（Soma）进行汇总处理，经由轴突（Axon），最后在轴突末梢输出信号。

1943年，Warren McCulloch 和 Walter Pitts 基于生物神经元的生理特征，建立了单个生物神经元的数学模型，如下图：

多个信号 $x$ 乘以其相应的权重 $\omega$ 之后进行求和，最后传入激活函数 $\varphi$ 得到输出结果。激活函数是一个非线性函数，这是模拟了胞体处理电化学信号的过程，也即当胞体的电势达到一定阈值时，才会向轴突传递信号脉冲。这个过程记作：

$y_{k}=\varphi\left(\sum \limits ^{m}_{i=0} \omega_{ki}x_{i}+b_{k}\right)$

事实上，这个数学模型并没有太多生物方面的依据，是否准确描述了生物神经元的工作过程，我们无从知晓。

但从数学角度来分析，非线性的特点让激活函数能更好地拟合训练样本。在上一篇文章介绍 SVM 处理非线性样本时，我们深刻地认识到线性函数的局限性。ANN 虽然不如 SVM 那么优雅，但非线性函数的优势让它可以应对更复杂的场景。

初识人工神经网络结构

人工神经网络（接下来简称为 ANN）由多个人工神经元组成，下图是一个简单的三层 ANN：

ANN 的结构可以划分为输入层、隐藏层和输出层，根据不同的任务场景，需要适当调整隐藏层的层数以及各层的神经元个数，如上图展示的就是一个 3 层 ANN，输入层一般不计入层数。

ANN 的训练过程与 SVM 异曲同工，区别是 SVM 每次需要输入所有样本，而 ANN 则是将训练样本逐一输入，通过优化调整隐藏层中的 $\omega$ 和 $b$，使输出结果和训练样本标签之间的差异不断缩小。

如果你了解过 SVM 的话，应该知道 SVM 的工作原理是通过线性函数来区分两种样本，那 ANN 又是如何工作的呢？

一个应用例子

这是吴恩达在公开课上举的一个例子，它非常通俗易懂地展现了 ANN 的工作原理。

网购衣服时会发现，只要输入身高和体重，就可以得到推荐尺码。假设某服装厂即将推出一款新品，现需知道 M 码适合哪种身高体重的消费者，在经过试验性地投放和调研后，得到了一批 M 码购买者的数据，绘制到一个二维特征空间中如下图：

我们仍然使用上一小节的三层 ANN 来解决厂家的需求，为了帮助理解，我们暂时忽略激活函数 $\varphi$。假设该 ANN 经过这些样本的训练，得到模型如下图：

可以看到，上图三条直线两两相交，“切割”出了一个三角形区域。显然，这三条直线分别代表着该 ANN 第一层中三个神经元各自的决策边界，决策边界是不同样本之间的分界线，如果顾客输入的身高体重落在三角形区域内，那么该 ANN 模型将会认为这个顾客适合购买 M 码，反之亦然。同时也可以进一步推出，如果我们增加神经元的数量，最终将“切割”出一个更加精细、更加拟合训练样本的区域。

在这个例子中，ANN 的工作过程可以总结为：顾客输入身高体重后，第一层的三个神经元各自判断数据落在自身决策边界的哪一侧，然后三个判断结果传递给第二层，第二层的神经元再进一步判断数据是否落在三角区域内，如果在三角区域内则推荐顾客购买 M 码，否则输出不推荐。

感知机

在正式介绍多层神经网络前，我们先来了解一下 感知机（Perceptron）。

感知机由 Frank Rosenblatt 在 1957 年提出，这是最早尝试用线性函数解决二分类问题的算法，后来出现的 SVM 可以看作是它的加强版。

感知机使用的线性函数如下：

$f\left(X\right)=\omega^{T}X+b$

$X$ 是输入的特征向量；$\omega$ 是权重，它的维度和 $X$ 相同；$b$ 是偏置。PLA 和 SVM 一样，通常定义 $f\left(X\right)=0$ 作为决策边界（暂且认为是一条直线），被这条直线分割开的两侧，分别代表不同的类别。

对于二分类问题，样本标签还是设为 $y_{i} \in \left\{+1,-1\right\}$，$N$ 个训练样本集合记作：

$\left\{ \left( X_{i},y_{i}\right)\right\} _{i=1}^{N}$

训练目标是使所有训练样本被正确分类，可以用不等式表示：

$y_{i}f\left(X_{i}\right)\ge 0\ \left(i=1,2,\cdots,N\right)$

训练算法

感知机的训练算法被称为 感知机学习算法（Perceptron Learning Algorithm，PLA）。

训练过程很简单，其实就是不断调整这条直线的斜率（调整 $\omega$）以及对直线进行平移（调整 $b$），直到直线准确分隔开两种训练样本，具体过程如下：

PLA 与 SVM 最大的区别是，PLA 每轮迭代只输入一个 $X_{i}$，而 SVM 每轮迭代所有 $X_{i}$ 都会参与运算。

收敛证明

在证明算法收敛前，为了方便推导，我们重新对 $\omega$ 和 $X$ 进行定义，改用增广向量的形式来表示：

$\vec{X}_{i}=\begin{bmatrix}y_{i}X_{i}\\ y_{i}\end{bmatrix}$

$\vec{\omega}=\begin{bmatrix}\omega \\ b \end{bmatrix}$

训练过程的书写方式可以简化为：

在上一篇文章推导 SVM 时就已经提到，对线性方程进行缩放并不会改变它的性质：

$\vec{\omega}^{T}\vec{X}_{i} = 0$

$\Updownarrow$

$\alpha\vec{\omega}^{T}\vec{X}_{i} = 0$

当然，这里的 $\alpha$ 要取大于零的实数（$\alpha \in R^{+}$），如果小于零会违背前面定义的优化目标 $\vec{\omega}^{T}\vec{X}_{i} \ge 0$。

了解了以上前提后，接下来开始证明收敛，当然，以下推导的前提是训练样本线性可分。

假设存在 $\vec{\omega}_{opt}$，使 $\vec{\omega}_{opt}^{T}\vec{X}_{i} \ge 0\ \left(i=1,2,\cdots,N\right)$ 成立，那么 $\vec{\omega}_{opt}$ 同样可以进行 $\alpha$ 倍的缩放：

$\vec{\omega}_{opt}^{T}\vec{X}_{i} = 0$

$\Updownarrow$

$\alpha\vec{\omega}_{opt}^{T}\vec{X}_{i} = 0$

假设在第 $k$ 轮迭代，仍然有 $X_{i}$ 使 $\vec{\omega}_{k}^{T}\vec{X}_{i} < 0$。又根据前面训练过程可知，两次相邻迭代存在如下关系：

可以进一步推出，当 $\alpha$ 足够大时，存在：

$\left\|\vec{X}_{i}\right\|^{2}+2\vec{\omega}_{k}^{T}\vec{X}_{i}-2\alpha\vec{\omega}_{opt}\vec{X}_{i}<0$

于是可以得到：

$\left \| \vec{\omega}_{k+1}-\alpha\vec{\omega}_{opt} \right \|^{2}<\left \| \vec{\omega}_{k}-\alpha\vec{\omega}_{opt} \right \|^{2}$

上面的不等式可以看出，随着迭代次数的增加，$\omega_{k}$ 逐渐趋近于 $\alpha\omega_{opt}$。但这不足以证明 $\omega_{k}$ 收敛，因为在逼近 $\alpha\omega_{opt}$ 的过程中，收敛速度也可能逐渐变小直到忽略不计，所以接下来我们要做的是去定量分析其收敛速度。

设：

$\beta=\max \limits_{i=1,2,\cdots,N} \left\{\|\vec{X}_{i}\|\right\}$

$\gamma=\min \limits_{i=1,2,\cdots,N} \left\{\vec{\omega}_{opt}^{T}\vec{X}_{i}\right\}$

取：

$\alpha=\frac{\beta^{2}+1}{2\gamma}$

可得：

则：

$\left \| \vec{\omega}_{k+1}-\alpha\vec{\omega}_{opt} \right \|^{2}<\left \| \vec{\omega}_{k}-\alpha\vec{\omega}_{opt} \right \|^{2} - 1$

设 $D=\left \| \vec{\omega}_{0}-\alpha\vec{\omega}_{opt} \right \|$，根据上面的不等式可知，当 $\alpha=\frac{\beta^{2}+1}{2\gamma}$ 时，最多经过 $D^{2}$ 轮迭代，$\vec{\omega}$ 收敛至 $\alpha\vec{\omega}_{opt}$。

另一种收敛证明

这个证明思路参考自康奈尔大学的公开课程，原文见链接。

与上一种证明方法取指定的 $\alpha$ 值类似，首先是取：

$\left \| \vec{\omega}_{opt} \right \|=1$

$0<\left \| \vec{X}_{i} \right \| \le 1$

$\vec{\omega}_{opt}$ 和 $\vec{X}_{i}$ 是向量，所以他们的模可以随意取值。

然后，我们在所有样本向量中，选一个到决策边界距离最小的样本，该样本向量到决策边界的距离使用 $\gamma$ 来表示：

接下来分别分析 $\vec{\omega}^{T}\vec{\omega}_{opt}$、$\vec{\omega}^{T}\vec{\omega}$ 与 $\gamma$ 的关系。

先来分析 $\vec{\omega}^{T}\vec{\omega}_{opt}$：

显然，在经过 $M$ 轮迭代后，有：

$\vec{\omega}_{M+1}^{T}\vec{\omega}_{opt} \ge M\gamma$

接着来分析 $\vec{\omega}^{T}\vec{\omega}$：

同理，在经过 $M$ 轮迭代后，有：

$\vec{\omega}_{M+1}^{T}\vec{\omega}_{M+1} \le M$

再来看一下 $\vec{\omega}^{T}\vec{\omega}_{opt}$ 和 $\vec{\omega}^{T}\vec{\omega}$ 之间的关系：

$\vec{\omega}_{M+1}^{T}\vec{\omega}_{opt}=\|\vec{\omega}_{M+1}\|\cos \theta\le\|\vec{\omega}_{M+1}\|=\sqrt{\vec{\omega}_{M+1}^{T}\vec{\omega}_{M+1}}$

这里的 $\theta$ 是 $\vec{\omega}_{M+1}$ 和 $\vec{\omega}_{opt}$ 之间的角度。

联立以上所有条件可以得到结论：

由上面不等式可知，当 $\left \| \vec{\omega}_{opt} \right \|=1$ 且 $0<\left \| \vec{X}_{i} \right \| \le 1$ 时，最多经过 $\frac{1}{\gamma^{2}}$ 轮迭代，$\vec{\omega}$ 收敛至 $\vec{\omega}_{opt}$。

多层感知机

前面我们仅分析了单层感知机，顾名思义，多层感知机（Multi-Layer Perception，MLP）由多层神经元的叠加组成，上一层神经元的输出做为输入传递给下一层神经元，MLP 一般是指拥有至少一个隐藏层的全连接 ANN 模型，且各层使用的激活函数都相同。

前面我们浅析了 ANN 的结构和工作原理，相信各位读者已经有了基本的概念，MLP 在严格定义上属于 ANN 的一种，但通常认为两者是等同的。下面借助一个简单的 3 层 MLP 来理解其工作原理：

训练目标是使 MLP 模型尽可能地拟合训练样本，可以量化为下面的目标函数：

最小化：$E=\frac{1}{2}\left\|y-Y\right\|^{2}$

$y$ 代表输出层输出的向量；$Y$ 代表训练样本的标签。显然，MLP 的输出 $y$ 和样本标签 $Y$ 越接近越好，所以我们将两者相减，最终是要使 $E$ 取得最小值。科学家们构造了各种各样的目标函数，但为减少计算难度，一般都是易于求导的函数。

训练算法

接下来介绍的训练算法，将解答 ANN 如何调整 $\omega$ 和 $b$ 来使 $E$ 的值达到最小。

反向传播算法

我们常用 反向传播算法（Backpropagation，BP）训练 ANN，它也是一种启发式算法，顾名思义，该算法从输出层开始，将计算结果一层层地由后往前反向传递。

不同于 PLA 算法简单粗暴地进行加减操作，BP 算法的本质是 梯度下降法（Gradient Descent），梯度下降法用于求函数的极值点。例如求某函数 $f\left(\omega\right)$ 的极小值点，首先是赋予 $\omega$ 一个初始值，然后通过下面的计算得到新的 $\omega$，重复此过程，直到 $\omega$ 不再变化或变化极小为止，此时的 $\omega$ 即可认为是极小值点，迭代过程记作：

$\omega_{k+1}=\omega_{k}-\left.\eta\ \frac{\mathrm{d} f\left(\omega\right)}{\mathrm{d} \omega}\right|_{\omega_{k}}$

这里的 $\eta$ 是一个大于零的自定义值，称为 学习率（Learning Rate），代表梯度下降的步长，其取值将影响收敛的效率，它可以是一个固定值，但如果取值太大可能会导致无法收敛，为避免这种情况发生，可以随着迭代次数的增加不断减小 $\eta$ 的值。

接着来分析梯度下降的收敛原理。

我们知道，从微分角度分析一个函数可以得到如下关系：