[ML从入门到入门] 初识人工神经网络、感知机算法以及反向传播算法
前言
人工神经网络（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 经过这些样本的训练，得到模型如下图：
可以看到，上图三条直线两两相交，将 M 码的样本包围在一个三角形区域内。显然，这三条直线分别代表着该 ANN 第一层中三个神经元各自的决策边界，决策边界是不同样本之间的分界线，如果顾客输入的身高体重落在三角形区域内，那么该 ANN 模型将会认为这个顾客适合购买 M 码，反之亦然。同时也可以进一步推出，如果我们增加神经元的数量，或者非线性激活函数，最终将围出一个更加精细、更加拟合训练样本的区域。
在这个例子中，ANN 的工作过程可以总结为：顾客输入身高体重后，第一层的三个神经元各自判断数据落在自身决策边界的哪一侧，然后三个判断结果传递给第二层，第二层的神经元再进一步判断数据是否落在三角区域内，如果在三角区域内则推荐顾客购买 M 码，否则输出不推荐。
感知机
在正式介绍多层神经网络前，我们先来了解一下 感知机（Perceptron）。
感知机由 Frank Rosenblatt 在 1957 年提出，这是最早尝试用线性函数解决二分类问题的算法，后来出现的 SVM 可以看作是它的加强版。
感知机使用的线性函数如下：
$f\left(X\right)=\omega^{T}X+b$
$X$ 是输入的特征向量；$\omega$ 是权重，它的维度和 $X$ 相同；$b$ 是偏置。和 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 模型，且各层使用的激活函数都相同。相较于单层感知机，MLP 必须加入非线性激活函数，否则增加再多的层数也和单层的效果是相同的。
前面我们浅析了 ANN 的结构和工作原理，相信各位读者已经有了基本的概念，MLP 在严格定义上属于 ANN 的一种，但在很多语境下都使用 ANN 指代 MLP。下面借助一个简单的 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$ 的值。
接着来分析梯度下降的收敛原理。
我们知道，从微分角度分析一个函数可以得到如下关系：
将 $\omega_{k+1}$ 代入上面的公式可得：
可以看到，随着迭代次数的增加，$f\left(\cdot\right)$ 的值将越来越小，如果函数连续可导且存在极值点，理论上经过有限次迭代后可求得极值点。
让我们重新回归本节的重点，BP 算法。
确切来说，BP 算法分为两个阶段，初始化 $\omega$ 和 $b$ 后，第一阶段是前向传递，先计算出最后的输出值，第二阶段才是反向传递，从输出层开始往反方向计算调整各层的权重 $\omega$ 和偏置 $b$，这两个阶段重复多次后，$\omega$ 和 $b$ 将收敛至一个合适的区间。
第二阶段，梯度下降法对 MLP 各个节点进行求导时，在链式法则的作用下，我们不得不从后往前计算各层的节点，并且计算产生的值在层与层之间传递，所以被称为“反向传播”或“后向传播”。
下面拆解 MLP 网络的一部分来做分析，以达到见微知著的效果：
现在只关注图中深色的节点。
结合上图，BP 算法使用梯度下降对每个 $b$ 和 $\omega$ 进行更新的过程，可以记作：
根据链式法则，分别对 $b^{(m)}_{i}$ 和 $\omega^{(m)}_{ij}$ 进行求偏导：
令：
综上所述，可得：
最终，BP 算法每轮迭代的每个分量更新过程可以记作：
可以看到，求任意一个权重时，都需要依赖后一层的计算结果，这就导致了 BP 算法需要从输出层开始，由后往前进行计算。
前向前向传播算法
深度学习领域的著名学者 Geoffrey Hinton，于 2022 年提出了一种新的神经网络学习算法，前向前向传播算法（Forward-Forward Algorithm），详细见此论文，相关实现参考该git项目。