反向传播算法

反向传播（Backpropagation，意为误差反向传播，缩写为BP）是对多层人工神经网络进行梯度下降的算法，也就是用链式法则以网络每层的权重为变数计算损失函数的梯度，以更新权重来最小化损失函数。

## 动机

任何监督式学习算法的目标是找到一个能把一组输入最好地映射到其正确的输出的函数。例如一个简单的分类任务，其中输入是动物的图像，正确的输出将是动物的名称。一些输入和输出模式可以很容易地通过单层神经网络（如感知器）学习。但是这些单层的感知机只能学习一些比较简单的模式，例如那些非线性可分的模式。例如，人可以通过识别动物的图像的某些特征进行分类，例如肢的数目，皮肤的纹理（无论是毛皮，羽毛，鳞片等），该动物的体型，以及种种其他特征。但是，单层神经网络必须仅仅使用图像中的像素的强度来学习一个输出一个标签函数。因为它被限制为仅具有一个层，所以没有办法从输入中学习到任何抽象特征。多层的网络克服了这一限制，因为它可以创建内部表示，并在每一层学习不同的特征。第一层可能负责从图像的单个像素的输入学习线条的走向。第二层可能就会结合第一层所学并学习识别简单形状（如圆形）。每升高一层就学习越来越多的抽象特征，如上文提到的用来图像分类。每一层都是从它下方的层中找到模式，就是这种能力创建了独立于为多层网络提供能量的外界输入的内部表达形式。

反向传播算法的发展的目标和动机是找到一种训练的多层神经网络的方法，于是它可以学习合适的内部表达来让它学习任意的输入到输出的映射。

## 概括

反向传播算法（BP 算法）主要由两个阶段组成：激励传播与权重更新。

### 第1阶段：激励传播

每次迭代中的传播环节包含两步：

- （前向传播阶段）将训练输入送入网络以获得预测结果。
- （反向传播阶段）对预测结果同训练目标求差(损失函数)。

### 第2阶段：权重更新

对于每个突触上的权重，按照以下步骤进行更新：

- 将输入激励和响应误差相乘，从而获得权重的梯度。
- 将这个梯度乘上一个比例并取反后加到权重上。

这个比例（百分比）将会影响到训练过程的速度和效果，因此成为“训练因子”。梯度的方向指明了误差扩大的方向，因此在更新权重的时候需要对其取反，从而减小权重引起的误差。

第 1 和第 2 阶段可以反复循环迭代，直到网络对输入的响应达到满意的预定的目标范围为止。

## 算法

### 数学推导

假设多层人工神经网络的第 $l$ 层是由线性算子 $W^l:\mathbb{R}^{n_{l-1}} \to \mathbb{R}^{n_l}$ 和激活函数 $f^l:\mathbb{R} \to \mathbb{R}$ 所构成，也就是说，第 $l$ 层的输入是 $n_{l-1}$ 维实数向量

$$y^{l-1} = (x_1,\,x_2,\,\cdots,\,x_{n_{l-1}})$$

输出则为$n_l$ 维实向量

$$y^{l} = (y_1,\,y_2,\,\cdots,\,y_{n_l})$$

换句话说，第 $l-1$ 层的输出 $y^{l-1}$ 就是第 $l$ 层的输入。

而 $y^{l}$ 和 $y^{l-1}$ 的具体(以第 $i$ 分量表示)递回关系为

${y^{l}}_i = f^l\{\,[W^l(y^{l-1}) ]_i\,\} = f^l \left[\, \sum^{n_{l-1}}_{j=1}y^{l-1}_{j} W^l_{ji} \,\right]$ （$1 \leq i \leq n_l$）

上式通常会简写为

$$y^{l} = f^l[\,W^l(y^{l-1})\,]$$

若这个多层人工神经网络总共有 $L$ 层，也就是说，$y^{0}$ 是最一开始的输入，而 $y^{L}$ 是最后一层的输出，那跟损失函数 $g$ 是以最后一层输出 $y^{L}$ 的各分量 ${y^{L}}_i$ (与真实值)为变数。依据上面的递回关系，可以把 $g$ 进一步的转成以第 $L$ 层的输入 $y^{L-1}$ 与权重因子 ${W^{m}}_{ij}$ 为变数的函数 $g^{L}$

$g^{L}(W^{L}_{ij},\,{y^{L-1}_k}) = g\left[\, f^{L}\left( \sum^{n_{L-1}}_{a = 1} y^{L-1}_{a} W^L_{ab} \right) \,\right]$ （$1 \leq k \leq n_{L-1}$ , $1 \leq b \leq n_L$）

由此可以归纳到 $1 \leq l <L$ 的情况(注意到前几层的权重因子不会消失在表达式中)

$g^{l}(W^{l}_{ij},\,\cdots,\,W^{L}_{ij},\,{y^{l-1}_k}) = g^{l+1}\left[\, W^{l+1}_{ij},\,\cdots,\,W^{L}_{ij},\, f^{l}\left( \sum^{n_{l-1}}_{a=1}y^{l-1}_a W^l_{ab} \right) \,\right]$ （$1 \leq k \leq n_{l-1}$ , $1 \leq b \leq n_l$）

那这样如果假设适当的可微分条件，由链式法则会有以下的递回关系 ( 若取 $g^{L+1} := g$ 和 $1 \leq l \leq L$ )

$$\frac{\partial g^l}{\partial W^l_{cd}} = \frac{\partial g^{l+1}}{\partial {y^l}_d}\bigg|_{{y^l}_d = f^l(x)} \times\frac{df^{l}}{dx}\bigg|_{x = \sum {y^{l-1}}_a W^l_{ad}} \times {y^{l-1}}_c$$

$$\frac{\partial g^l}{\partial {y^{l-1}}_c}= \sum^{n_l}_{i=1} \left[\, \frac{\partial g^{l+1}}{\partial {y^l}_i}\bigg|_{{y^l}_i = f^l(x)} \times\frac{df^{l}}{dx}\bigg|_{x = \sum{y^{l-1}}_a W^l_{ai}} \times W^l_{ci} \,\right]$$

这样就可以依据这个递回关系进行梯度下降，因为计算上是由 ${y^{L}}_i$ 对 损失函数 $g$ 的偏微分出发，一层层向后递推出前面各层的权重因子梯度，所以被称为反向传播。

注意到可将输入设为

$$y^{l-1} = (1, \,x_1,\,x_2,\,\cdots,\,x_{n_{l-1}})$$

并多加一行权重因子 $W^l_{i0}$ 为偏移，就可以把有偏移的多层网络纳入刚刚讨论的范围内。

### 实际范例

三层网络算法（只有一个隐藏层）：

```
  初始化网络权值（通常是小的随机值）
  '''do'''
     '''forEach''' 训练样本 ex
        prediction = <u>neural-net-output</u>(network, ex)  ''// 正向传递''
        actual = <u>teacher-output</u>(ex)
        计算输出单元的误差 (prediction - actual)
        计算 <math>\Delta w_h</math>  对于所有隐藏层到输出层的权值                           ''// 反向传递''
        计算 <math>\Delta w_i</math>  对于所有输入层到隐藏层的权值                           ''// 继续反向传递''
        更新网络权值 ''// 输入层不会被误差估计改变''
  '''until''' 所有样本正确分类或满足其他停止标准
  '''return''' 该网络
```

这个算法的名称意味着误差会从输出结点反向传播到输入结点。严格地讲，反向传播算法对网络的可修改权值计算了网络误差的梯度。这个梯度会在简单随机梯度下降法中经常用来求最小化误差的权重。通常“反向传播”这个词使用更一般的含义，用来指涵盖了计算梯度以及在随机梯度下降法中使用的整个过程。在适用反向传播算法的网络中，它通常可以快速收敛到令人满意的极小值。

## 直观理解

### 学习作为一个优化问题

在给出反向传播算法的数学推导之前，我们举一个例子来培养关于神经元的真实输出与正确输出间的直观感受。考虑一个有两个输入单元、一个输出单元、没有隐藏单元的简单神经网络。每个神经元都使用输入的加权作为人工神经元。

<image>

在训练之前，我们将随机分配权重$w_{1}, w_{2}$。之后神经元根据训练实例进行学习。在此例中，训练集为 ($x_{1}$, $x_{2}$, $t$)，其中 $x_{1}$ 与 $x_{2}$ 是网络的输入，$t$ 为正确输出（在给定相同的输入时网络最终应当产生的输出）。网络在给定 $x_{1}$ 和 $x_{2}$ 时，会计算一个输出 $y$，很可能与 $t$ 不同（因为权重最初是随机的）。为了衡量期望输出 $t$ 与实际输出 $y$ 之间的差异，一个常用的方法是采用平方误差测度：

$E=(t-y)^2 \,$,

其中 $E$ 为误差。

举例来讲，考虑单一训练实例的网络：$(1, 1, 0)$，输入 $x_{1}$ 与 $x_{2}$ 均为1，正确输出 $t$ 为 0。现在若将实际输出 $y$ 画在x轴，误差 $E$ 画在 $y$ 轴，得出的是一条抛物线。抛物线的极小值对应输出 $y$，最小化了误差 $E$。对于单一训练实例，极小值还会接触到 $x$ 轴，这意味着误差为零，网络可以产生与期望输出 $t$ 完全匹配的输出 $y$。因此，把输入映射到输出的问题就化为了一个找到一个能产生最小误差的函数的最佳化问题。

<image>

然而，一个神经元的输出取决于其所有输入的加权总和：

$y=x_1w_1 + x_2w_2$,

其中 $w_1$ 和 $w_2$ 是从输入单元到输出单元相连的权重。因此，误差取决于输入到该神经元的权重，也是网络要学习最终需要改变的。若每个权重都画在一个水平的轴上，而误差画在垂直轴上，得出的就是一个抛物面（若一个神经元有 $k$ 个权重，则误差曲面的维度就会是 $k+1$，因而就是二维抛物线的 $k+1$ 维等价）。

<image>

反向传播算法的目的是找到一组能最大限度地减小误差的权重。寻找抛物线或任意维度中的任何函数的极大值的方法有若干种。其中一种方法是通过求解方程组，但这依赖于网络是一个线性系统，而目标也需要可以训练多层非线性网络（因为多层线性网络与单层网络等价）。在反向传播中使用的方法是梯度下降法。

### 运用类比理解梯度下降法

梯度下降法背后的直观感受可以用假设情境进行说明。一个被卡在山上的人正在试图下山（即试图找到极小值）。大雾使得能见度非常低。因此，下山的道路是看不见的，所以他必须利用局部信息来找到极小值。他可以使用梯度下降法，该方法涉及到察看在他当前位置山的陡峭程度，然后沿着负陡度（即下坡）最大的方向前进。如果他要找到山顶（即极大值）的话，他需要沿着正陡度（即上坡）最大的方向前进。使用此方法，他会最终找到下山的路。不过，要假设山的陡度不能通过简单地观察得到，而需要复杂的工具测量，而这个工具此人恰好有。需要相当长的一段时间用仪器测量山的陡峭度，因此如果他想在日落之前下山，就需要最小化仪器的使用率。问题就在于怎样选取他测量山的陡峭度的频率才不致偏离路线。

在这个类比中，此人代表反向传播算法，而下山路径表示能使误差最小化的权重集合。山的陡度表示误差曲面在该点的斜率。他要前行的方向对应于误差曲面在该点的梯度。用来测量陡峭度的工具是微分（误差曲面的斜率可以通过对平方误差函数在该点求导数计算出来）。他在两次测量之间前行的距离（与测量频率成正比）是算法的学习速率。参见限制一节中对此类型“爬山”算法的限制的讨论。

## 限制

- 结果可能会收敛到极值。如果只有一个极小值，梯度下降的“爬山”策略一定可以起作用。然而，往往是误差曲面有许多局部最小值和最大值。如果梯度下降的起始点恰好介于局部最大值和局部最小值之间，则沿着梯度下降最大的方向会到达局部最小值。

<image>

- 从反向传播学习获得的收敛很慢。
- 在反向传播学习的收敛性不能保证。
- 然而，收敛到全局最小值据说使用自适应终止条件得到保证。
- 反向传播学习不需要输入向量的标准化（normalization）；然而，标准化可提高性能。

## 历史

弗拉基米尔·瓦普尼克在他的书《支持向量机》中首次发表反向传播算法。在1969年阿瑟·E·布莱森和何毓琦将其描述为多级动态系统优化方法。直到1974年以后在神经网络的背景下应用，并由保罗·维波斯、大卫·鲁梅尔哈特、杰弗里·辛顿和罗纳德·J·威廉斯的著作，它才获得认可，并引发了一场人工神经网络的研究领域的“文艺复兴”。在21世纪初人们对其失去兴趣，但在2010年后又拥有了兴趣，如今可以通过GPU等大型现代运算器件用于训练更大的网络。例如在2013年，顶级语音识别器现在使用反向传播算法训练神经网络。

## 外部链接

- A Gentle Introduction to Backpropagation - An intuitive tutorial by Shashi Sathyanarayana The article contains pseudocode ("Training Wheels for Training Neural Networks") for implementing the algorithm.
- Neural Network Back-Propagation for Programmers (a tutorial)
- Backpropagation for mathematicians
- Chapter 7 The backpropagation algorithm of Neural Networks - A Systematic Introduction by Raúl Rojas (ISBN 978-3540605058)
- Implementation of BackPropagation in C++
- Implementation of BackPropagation in C#
- Implementation of BackPropagation in Java
- Another Implementation of BackPropagation in Java
- Implementation of BackPropagation in Ruby
- Implementation of BackPropagation in Python
- Implementation of BackPropagation in PHP
- Quick explanation of the backpropagation algorithm
- Graphical explanation of the backpropagation algorithm
- Concise explanation of the backpropagation algorithm using math notation by Anand Venkataraman
- Backpropagation neural network tutorial at the Wikiversity