反向传播算法

维基百科,自由的百科全书
跳转至: 导航搜索

反向传播英语:Backpropagation,缩写为BP)是“误差反向传播”的简称,是一种与最优化方法(如梯度下降法)结合使用的,用来训练人工神经网络的常见方法。该方法计算对网络中所有权重计算损失函数英语loss function的梯度。这个梯度会反馈给最优化方法,用来更新权值以最小化损失函数。

反向传播要求有对每个输入值想得到的已知输出,来计算损失函数梯度。因此,它通常被认为是一种監督式學習方法,虽然它也用在一些无监督网络(如自动编码器英语autoencoder)中。它是多层前馈网络Delta规则英语delta rule的推广,可以用链式法则对每层迭代计算梯度。反向传播要求人工神经元英语artificial neuron(或“节点”)的激励函数英语activation function可微

动机[编辑]

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

概括[编辑]

反向传播算法(BP算法)主要由两个阶段:激励传播、和权重更新。

第1阶段:激励传播[编辑]

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

  1. (前向传播阶段)将训练输入送入网络以获得激励响应;
  2. (反向传播阶段)将激励响应同训练输入对应的目标输出求差,从而获得隐层和输出层的响应误差。

第2阶段:权重更新[编辑]

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

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

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

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

算法[编辑]

三层网络算法(只有一个隐藏层):

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

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

BP网络都是多层感知机(通常都会有一个输入层、一个隐藏层及一个输出层)。为了使隐藏层能够适合所有有用的函数,多层网络必须具有用于多个层的非线性激活函数:仅用线性激活函数的多层网络会与相当于单层线性网络。常用的非线性激活函数有邏輯函數柔性最大函数英语softmax activation function高斯函数

用反向传播算法求梯度已被重新发现多次,是更加一般的自動微分技术在反向积累模式的特例。

它也与高斯-牛顿算法英语Gauss–Newton algorithm密切相关,也是继续研究神经反向传播英语neural backpropagation的一部分。

直观理解[编辑]

学习作为一个优化问题[编辑]

在给出反向传播算法的数学推导之前,培养关于神经元的真实输出与特定的训练情况的正确输出间的直观感受是很有帮助的。考虑一个有两个输入单元、一个输出单元、没有隐藏单元的简单神经网络。每个神经元都使用输入的加权和作为线性输出英语Artificial neuron[note 1]

具有2个输入单元和1个输出单元的一个简单的神经网络

最初在训练之前,会随机分配权重。之后神经元根据训练实例英语Training set进行学习,在此情况下包含元组 (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。因此,把输入映射到输出的问题就化为了一个找到一个能产生最小误差的函数的最佳化問題

单一训练实例的线性神经元的误差曲面。

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

y=x_1w_1 + x_2w_2,

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

两个输入误差的神经元的误差曲面

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

运用类比理解梯度下降法[编辑]

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

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

推导[编辑]

由于反向传播使用梯度下降法,需要计算平方误差函数对网络权重的导数。假设对于一个输出神经元,[note 2] 平方误差函数为:

E = \tfrac{1}{2}(t - y)^2

其中

E 为平方误差,
t 为训练样本的目标输出,
y 为输出神经元的实际输出。

加入系数 \textstyle\frac{1}{2} 是为了抵消微分出来的指数。之后,该表达式会乘以一个任意的学习速率,因此在这里乘上一个常系数是没有关系的。 对每个神经元 j,它的输出 o_{j} 定义为

o_{j} = \varphi(\mbox{net}_{j}) = \varphi\left(\sum_{k=1}^{n}w_{kj}x_k\right).

通向一个神经元的输入 \mbox{net}_{j} 是之前神经元的输出 o_k 的加权和。若该神经元输出层后的第一层,输入层的输出 o_k 就是网络的输入 x_k。该神经元的输入数量是 n。变量 w_{ij} 表示神经元 ij 之间的权重。

激活函数英语activation function \varphi 一般是非線性可微函数。常用作激活函数的是邏輯函數

 \varphi(z) = \frac{1}{1+e^{-z}}

其导数的形式很好:

 \frac {\partial\varphi}{\partial z} = \varphi(1-\varphi)

求误差的导数[编辑]

计算误差对权重 w_{ij}偏导数是两次使用链式法则得到的:

\frac{\partial E}{\partial w_{ij}} = \frac{\partial E}{\partial o_j} \frac{\partial o_j}{\partial\mathrm{net_j}} \frac{\partial \mathrm{net_j}}{\partial w_{ij}}

在右边的最后一项中,只有加权和 \mathrm{net_j} 取决于 w_{ij},因此

\frac{\partial \mathrm{net_j}}{\partial w_{ij}} = \frac{\partial}{\partial w_{ij}}\left(\sum_{k=1}^{n}w_{kj}x_k\right) = x_i.

神经元 j 的输出对其输入的导数就是激活函数的偏导数(这里假定使用逻辑函数):

\frac{\partial o_j}{\partial\mathrm{net_j}} = \frac {\partial}{\partial \mathrm{net_j}}\varphi(\mathrm{net_j}) = \varphi(\mathrm{net_j})(1-\varphi(\mathrm{net_j}))

这就是为什么反向传播需要的激活函数是可微的

如果神经元在输出层中,因为此时 o_j = y 以及

\frac{\partial E}{\partial o_j} = \frac{\partial E}{\partial y} = \frac{\partial}{\partial y} \frac{1}{2}(t - y)^2 = y - t

所以第一项可以直接算出。

但如果 j 是网络中任一内层,求 E 关于 o_j 的导数就不太简单了。

考虑 E 为接受来自神经元 j 的输入的所有神经元 L = {u, v, \dots, w} 的输入的函数,

\frac{\partial E(o_j)}{\partial o_j} = \frac{\partial E(\mathrm{net}_u, \mathrm{net}_v, \dots, \mathrm{net}_w)}{\partial o_j}

并关于 o_j全微分,可以得到该导数的一个递归表达式:

\frac{\partial E}{\partial o_j} = \sum_{l \in L} \left(\frac{\partial E}{\partial \mathrm{net}_l}\frac{\partial \mathrm{net}_l}{\partial o_j}\right) = \sum_{l \in L} \left(\frac{\partial E}{\partial o_{l}}\frac{\partial o_{l}}{\partial \mathrm{net}_l}w_{jl}\right)

因此,若已知所有关于下一层(更接近输出神经元的一层)的输出 o_l 的导数,则可以计算 o_j 的导数。

把它们放在一起:

\dfrac{\partial E}{\partial w_{ij}} = \delta_{j} x_{i}

其中

\delta_{j} = \frac{\partial E}{\partial o_j} \frac{\partial o_j}{\partial\mathrm{net_j}} = \begin{cases}
(o_{j}-t_{j})\varphi(\mbox{net}_{j})(1-\varphi(\mbox{net}_{j})) & \mbox{if } j \mbox{ is an output neuron,}\\
(\sum_{l\in L} \delta_{l} w_{jl})\varphi(\mbox{net}_{j})(1-\varphi(\mbox{net}_{j}))  & \mbox{if } j \mbox{ is an inner neuron.}
\end{cases}

要使用梯度下降法更新 w_{ij},必须选择一个学习速率 \alpha。要加在原本的权重上的权重的变化,等于学习速率与梯度的乘积,乘以 -1

 \Delta w_{ij} = - \alpha \frac{\partial E}{\partial w_{ij}}

之所以要乘以 \textstyle -1 是因为要更新误差函数极小值而不是极大值的方向。

对于单层网络,这个表达式变为Delta规则英语Delta Rule。 要想更好地理解反向传播是如何起作用的,下面是一个例子来说明它:The Back Propagation Algorithm,20页。

学习模式[编辑]

有可供选择的三种学习模式(Mode):在线英语Online machine learning,批量和随机英语Stochastic gradient descent。在在线和随机学习,每次传播后被立即做一个权重的更新。在批量学习模式,权重更新前有许多传播发生。在线学习被用于提供新的型态(pattern)的连续流的动态环境。随机学习和批量学习都使用静态型态(pattern)的一个训练集合。随机学习以一个随机的顺序经过数据集合,以减少陷入局部极小值的机会。随机学习也比批量学习更快,因为权重在每次传播后被立即更新。然而批量学习将产生一个更加稳定下降到一个局部最小值,因为每次更新都是基于所有型态被进行的。

限制[编辑]

  • 结果可能会收敛到极值。如果有只有一个极小值,梯度下降的“爬山”策略一定可以起作用。然而,往往是误差曲面有许多局部最小值和最大值。如果梯度下降的起始点恰好介于局部最大值和局部最小值之间,则沿着梯度下降最大的方向会到达局部最小值。
    梯度下降法可以找到局部最小值,而不是全局最小值。
  • 从反向传播学习获得的收敛很慢。
  • 在反向传播学习的收敛性不能保证。
    • 然而,收敛到全局最小值据说使用自适应终止条件得到保证[3]
  • 反向传播学习不需要输入向量的正常化(normalization);然而,正常化可提高性能[4]

历史[编辑]

Vapnik引用(Bryson, A.E.; W.F. Denham; S.E. Dreyfus. Optimal programming problems with inequality constraints. I: Necessary conditions for extremal solutions. AIAA J. 1, 11 (1963) 2544-2550)在他的书《支持向量机》中首次发表反向传播算法。在1969年Arthur E. Bryson何毓琦将其描述为多级动态系统优化方法。[5][6] 直到1974年以后在神经网络的背景下应用,并由Paul Werbos[7]David E. Rumelhart杰弗里·辛顿Ronald J. Williams[1][8]的著作,它才获得认可,并引发了一场人工神经网络的研究领域的“文艺复兴”。在21世纪初人们对起失去兴趣,但在2010年后又拥有了兴趣,如今可以通过GPU等大型现代运算器件用于训练更大的网络。例如在2013年,顶级语音识别器现在使用反向传播算法训练神经网络。

注释[编辑]

  1. ^ One may notice that multi-layer neural networks use non-linear activation functions, so an example with linear neurons seems obscure. However, even though the error surface of multi-layer networks are much more complicated, locally they can be approximated by a paraboloid. Therefore, linear neurons are used for simplicity and easier understanding.
  2. ^ There can be multiple output neurons, in which case the error is the squared norm of the difference vector.

参见[编辑]

参考文献[编辑]

  1. ^ 1.0 1.1 1.2 Rumelhart, David E.; Hinton, Geoffrey E.; Williams, Ronald J. Learning representations by back-propagating errors. Nature. 8 October 1986, 323 (6088): 533–536. doi:10.1038/323533a0. 
  2. ^ Paul J. Werbos (1994). The Roots of Backpropagation. From Ordered Derivatives to Neural Networks and Political Forecasting. New York, NY: John Wiley & Sons, Inc.
  3. ^ Lalis, Jeremias; Gerardo, Bobby; Byun, Yung-Cheol. An Adaptive Stopping Criterion for Backpropagation Learning in Feedforward Neural Network (PDF). International Journal of Multimedia and Ubiquitous Engineering. 2014, 9 (8): 149–156 [17 March 2015]. doi:10.14257/ijmue.2014.9.8.13. 
  4. ^ ISBN 1-931841-08-X,
  5. ^ Stuart Russell; Peter Norvig. Artificial Intelligence A Modern Approach. : 578. The most popular method for learning in multilayer networks is called Back-propagation. It was first invented in 1969 by Bryson and Ho, but was largely ignored until the mid-1980s. 
  6. ^ Arthur Earl Bryson, Yu-Chi Ho. Applied optimal control: optimization, estimation, and control. Blaisdell Publishing Company or Xerox College Publishing. 1969: 481. 
  7. ^ Paul J. Werbos. Beyond Regression: New Tools for Prediction and Analysis in the Behavioral Sciences. PhD thesis, Harvard University, 1974
  8. ^ Alpaydın, Ethem. Introduction to machine learning 2nd ed. Cambridge, Mass.: MIT Press. 2010: 250. ISBN 978-0-262-01243-0. ...and hence the name backpropagation was coined (Rumelhart, Hinton, and Williams 1986a). 

外部链接[编辑]