原理

当我们使用前馈神经网络接收输入x并产生输出\(\hat{y}\)时，信息通过网络向前流动。输入x提供初始信息，然后传播到每一层的隐藏单元，最终产生输出\(\hat{y}\)。这称之为前向传播（forward propagation）。在训练过程中，前向传播可以持续向前直到它产生一个标量代价函数\(J(\theta)\)。反向传播（back propagation）算法（Rumelhart et al., 1986），经常简称backprop，允许来自代价函数的信息通过网络向后流动，以便计算梯度。

计算梯度的解析表达式是很直观的，但是数值化地求解这样的表达式在计算上的代价可能很大。反向传播算法使用简单和廉价的程序来实现这个目标。

反向传播这个术语经常被误解为用于多层神经网络的整个学习算法。实际上，反向传播仅指用于计算梯度的方法，而另一种算法，例如随机梯度下降，使用该梯度来进行学习。此外，反向传播经常被误解为仅适用于多层神经网络，但原则上它可以计算任何函数的导数（对于一些函数，正确的响应是报告函数的导数是未定义的）。特别地，我们会描述如何计算一个任意函数f的梯度\(\nabla_x f(x,y)\)，其中x是一组变量，我们需要它们的导数，而y是函数的另外一组输入变量，但我们并不需要它们的导数。在学习算法中，我们最常需要的梯度是代价函数关于参数的梯度，即\(\nabla_\theta J(\theta)\)。许多机器学习任务需要计算其他导数，来作为学习过程的一部分，或者用来分析学得的模型。反向传播算法也适用于这些任务，不局限于计算代价函数关于参数的梯度。通过在网络中传播信息来计算导数的想法非常普遍，它还可以用于计算诸如多输入函数f的Jacobian的值。我们这里描述的是最常用的情况，其中f只有单个输出。

赫布理论（Hebbian theory）是一个神经科学理论，解释了在学习的过程中脑中的神经元所发生的变化。赫布理论描述了突触可塑性的基本原理，即突触前神经元向突触后神经元的持续重复的刺激，可以导致突触传递效能的增加。

计算图

为了更精确地描述反向传播算法，使用更精确的计算图（computational graph）语言是很有帮助的。

将计算形式化为图形的方法有很多。

这里，我们使用图中的每一个节点来表示一个变量。变量可以是标量、向量、矩阵、张量、或者甚至是另一类型的变量。

为了形式化我们的图形，我们还需引入操作（operation）这一概念。操作是指一个或多个变量的简单函数。我们的图形语言伴随着一组被允许的操作。我们可以通过将多个操作复合在一起来描述更为复杂的函数。

不失一般性，我们定义一个操作仅返回单个输出变量。这并没有失去一般性，是因为输出变量可以有多个条目，例如向量。反向传播的软件实现通常支持具有多个输出的操作，但是我们在描述中避免这种情况，因为它引入了对概念理解不重要的许多额外细节。

如果变量y是变量x通过一个操作计算得到的，那么我们画一条从x到y的有向边。我们有时用操作的名称来注释输出的节点，当上下文很明确时，有时也会省略这个标注。

微积分中的链式法则

微积分中的链式法则（为了不与概率中的链式法则相混淆）用于计算复合函数的导数。反向传播是一种计算链式法则的算法，使用高效的特定运算顺序。

设x是实数，f和g是从实数映射到实数的函数。假设\(y = g(x)\)并且\(z = f(g(x)) = f(y)\)。那么链式法则是说

\[\frac{dz}{dx} = \frac{dz}{dy} \frac{dy}{dx}\]

我们可以将这种标量进行扩展。假设\(x \in R^m, y \in R^n\)，g是从\(R^m\)到\(R^n\)的映射，f是从\(R^n\)到\(R\)的映射。如果y=g(x)并且z=f(y)，那么

\[\frac{\partial z}{\partial x_i} = \sum_j \frac{\partial z}{\partial y_j} \frac{\partial y_J}{\partial x_i}\]

使用向量记法，可以等价地写成

\[\bigtriangledown_x z = (\frac{\partial y}{\partial x})^T \bigtriangledown_y z\]

这里\(\frac{\partial y}{\partial x}\)是g的\(n \times m\)的Jacobian矩阵。

从这里我们看到，变量x的梯度可以通过Jacobian矩阵\(\frac{\partial y}{\partial x}\)和梯度\(\bigtriangledown_y z\)相乘来得到。反向传播算法由图中每一个这样的Jacobian梯度的乘积操作所组成。

通常我们将反向传播算法应用于任意维度的张量，而不仅仅用于向量。从概念上讲，这与使用向量的反向传播完全相同。唯一的区别是如何将数字排列成网络以形成张量。我们可以想象，在运行反向传播之前，将每个张量变平为一个向量，计算一个向量值梯度，然后将该梯度重新构造成一个张量。从这种重新排列的观点上看，反向传播仍然只是将Jacobian乘以梯度。

为了表示值z关于张量X的梯度，我们记为\(\bigtriangledown_X z\)，就像X是向量一样。X的索引现在有多个坐标——例如，一个3维的张量由3个坐标索引。我们可以通过使用单个变量i来表示完整的索引元组，从而完全抽象出来。对所有可能的元组i，\((\bigtriangledown_X z)_i\)给出\(\frac{\partial z}{\partial X_i}\)。这与向量中索引的方式完全一致，\((\bigtriangledown_x z)_i\)给出\(\frac{\partial z}{\partial x_i}\)。使用这种记法，我们可以写出适用于张量的链式法则。如果Y=g(X)并且z=f(Y)，那么

\[\bigtriangledown_X z = \sum_j (\bigtriangledown_X Y_j) \frac{\partial z}{\partial Y_j}\]

递归地使用链式法则来实现反向传播

使用链式规则，我们可以直接写出某个标量关于计算图中任何产生该标量的节点的梯度的代数表达式。然而，实际在计算机中计算该表达式时会引入一些额外的考虑。

具体来说，许多子表达式可能在梯度的整个表达式中重复若干次。任何计算梯度的程序都需要选择是存储这些子表达式还是重新计算它们几次。在某些情况下，计算两次相同的子表达式纯粹是浪费。在复杂图中，可能存在指数多的这种计算上的浪费，使得简单的链式法则不可实现。在其他情况下，计算两次相同的子表达式可能是以较高的运行时间为代价来减少内存开销的手段。

我们首先给出一个版本的反向传播算法，它指明了梯度的直接计算方式，按照它实际完成的顺序并且递归地使用链式法则。我们可以直接执行这些计算或者将算法的描述视为用于计算反向传播的计算图的符号表示。然而，这些公式并没有明确地操作和构造用于计算梯度的符号图。

基于梯度的优化

大多数深度学习算法都涉及某种形式的优化。优化指的是改变x以最小化或最大化某个函数f(x)的任务。我们通常以最小化f(x)指代大多数最优化问题。最大化可经由最小化算法最小化-f(x)来实现。

我们把要最小化或最大化的函数称为目标函数（objective function）或准则（criterion）。当我们对其进行最小化时，也把它称为代价函数（cost function）、损失函数（loss function）或误差函数（error function）。

我们通常使用个一个上标*表示最小化或最大化函数的x值，如记\(x^* = arg min f(x)\)。

这里简要回顾微积分概念如何与优化联系。

假设有一个函数\(y=f(x)\)，其中x和y是实数。这个函数的导数（derivative）记为\(f'(x)\)或\(\frac{dy}{dx}\)。导数\(f'(x)\)代表f(x)在点x处的斜率。换句话说，它表明如何缩放输入的小变化才能在输出获得相应的变化：\(f(x+\epsilon) \approx f(x) + \epsilon f'(x)\)。

因此导数对于最小化一个函数很有用，因为它告诉我们如何更改x来略微地改善y。例如，我们知道对于足够小的\(\epsilon\)来说，\(f(x-\epsilon (f'(x)))\)是比f(x)小的。因此我们可以将x往导数的反方向移动一小步来减小f(x)。这种技术称为梯度下降（gradient descent）。

当\(f'(x)=0\)时，导数无法提供往哪个方向移动的信息。\(f'(x)=0\)的点称为临界点(critical point)或驻点(stationary point)。一个局部极小点(local minimum)意味着这个点的f(x)小于所有邻近点，因此不可能通过移动无穷小的步长来减小f(x)。一个局部极大点（local maximum）意味着这个点的f(x)大于所有邻近点，因此不可能通过移动无穷小的步长来增大f(x)。有些临界点既不是最小点也不是最大点，这些点称为鞍点(saddle point)。

使f(x)取得绝对的最小值（相对所有其他值）的点是全局最小点（global minimum）。函数可能只有一个全局最小点或存在多个全局最小点，还可能存在不是全局最优的局部极小点。在深度学习的背景下，我们要优化的函数可能含有许多不是最优的局部极小点，或者还有很多处于非常平坦的区域内的鞍点。尤其是当输入是多维的时候，所有这些都将使优化变得困难。因此，我们通常寻找使f非常小的点，但这在任何形式意义下不一定是最小。

我们经常最小化具有多维输入的函数：\(f:R^n \to R\)。为了使“最小化”的概念有意义，输出必须是一维的（标量）。

针对具有多维输入的函数，我们需要用到偏导数（partial derivative）的概念。偏导数\(\frac{\partial}{\partial x_i} f(x)\)衡量点x处只有\(x_i\)增加时f(x)如何变化。梯度(gradient)是相对一个向量求导的导数：f的梯度是包含所有偏导数的向量，记为\(\nabla_x f(x)\)。梯度的第i个元素是f关于\(x_i\)的偏导数。在多维情况下，临界点是梯度中所有元素都为零的点。

在u（单位向量）方向的方向导数（directional derivative）是函数f在u方向的斜率。换句话说，方向导数是函数\(f(x + \alpha u)\)关于\(\alpha\)的导数（在\(\alpha=0\)时取得）。使用链式法则，我们可以看到当\(\alpha=0\)时，\(\frac{\partial}{\partial \alpha} f(x + \alpha u) = u^T \nabla_x f(x)\)。

为了最小化f，我们希望找到使f下降得最快的方向。计算方向导数：

\[min_{u, u^T u=1} u^T \nabla_x f(x) = min_{u, u^T u=1} |u|_2 |\nabla_x f(x)|_2 cos \theta\]
其中\(\theta\)是u与梯度的夹角。将$$ u 2 =1\(代入，并忽略与u无关的项，就能简化得到\)min{u} cos \theta$$。这在u与梯度方向相反时取得最小。换句话说，梯度向量指向上坡，负梯度向量指向下坡。我们在负梯度方向上移动可以减小f。这被称为最速下降法（method of steepest descent）或梯度下降（gradient descent）。

最速下降建议新的点为

\[x' = x - \epsilon \nabla_x f(x)\]

其中\(\epsilon\)为学习率（learning rate），是一个确定步长大小的正标量。我们可以通过几种不同的方式选择\(epsilon\)。普遍的方式是选择一个小常数。有时我们通过计算，选择使方向导数消失的步长。还有一种方法是根据几个\(\epsilon\)计算\(f(x - \epsilon \nabla_x f(x))\)，并选择其中能产生最小目标函数值的\(\epsilon\)。这种策略称为在线搜索。

最速下降在梯度的每一个元素为零时收敛（或在实践中，很接近零时）。在某些情况下，我们也许能够避免运行该迭代算法，并通过解方程\(\nabla f(x) = 0\)直接跳到临界点。

虽然梯度下降被限制在连续空间中的优化问题，但不断向更好的情况移动一小步（即近似最佳的小移动）的一般概念可以推广到离散空间。递增带有离散参数的目标函数称为爬山（hill climbing）算法。

梯度之上：Jacobian和Hessian矩阵

有时我们需要计算输入和输出都为向量的函数的所有偏导数。包含所有这样的偏导数的矩阵被称为Jacobian矩阵。具体来说，我们有一个函数\(f:R^m \to R^n\)，f的Jacobian矩阵\(J \in R^{n \times m}\)定义为\(J_{i,j} = \frac{\partial}{\partial x_j} f(x)_i\)。

有时，我们也对导数的导数感兴趣，即二阶导数（second derivative）。例如，有一个函数\(f:R^m \to R\)，f的一阶导数（关于\(X_j\)）关于\(x_i\)的导数记为\(\frac{\partial^2}{\partial x_i \partial x_j}f\)。在一维情况下，我们可以将\(\frac{\partial^2}{\partial x_i \partial x_j}f\)记为\(f''(x)\)。二阶导数告诉我们，一阶导数将如何随着输入的改变而改变。它表示只基于梯度信息的梯度下降步骤是否会产生如我们预期那样大的改善，因此它是重要的。我们可以认为，二阶导数是对曲率的衡量。假设我们有一个二次函数（虽然很多实践中的函数都不是二次的，但至少在局部可以很好地用二次近似），如果这样的函数具有零二阶导数，那就没有曲率，也就是一条完全平坦的线，仅用梯度就可以预测它的值。我们使用沿负梯度方向大小为\(\epsilon\)的下降步，当该梯度是1时，代价函数下降\(\epsilon\)。如果二阶导数是负的，函数曲线向下凹陷（向上凸出），因此代价函数将下降得比\(\epsilon\)多。如果二阶导数是正的，函数曲线是向上凹陷（向下凸出），因此代价函数将下降得比\(\epsilon\)少。

当我们的函数具有多维输入时，二阶导数也有很多。我们可以将这些导数合并成一个矩阵，称为Hessian矩阵。Hessian矩阵H(f)(x)定义为

\[H(f)(x)_{i,j} = \frac{\partial^2}{\partial x_i \partial x_j}f(x)\]

Hessian等价于梯度的Jacobian矩阵。

微分算子在任何二阶偏导连续的点处可交换，也就是它们的顺序可以互换：

\[\frac{\partial^2}{\partial x_i \partial x_j}f(x) = \frac{\partial^2}{\partial x_j \partial x_i}f(x)\]

这意味着\(H_{i,j} = H_{j,i}\)，因此Hessian矩阵在这些点上是对称的。在深度学习背景下，我们遇到的大多数函数的Hessian几乎处处都是对称的。因为Hessian矩阵是实对称的，我们可以将其分解成一组特征值和一组特征向量的正交基。在特定方向d上的二阶导数可以写成\(d^T H d\)。当d是H的一个特征向量时，这个方向的二阶导数就是对应的特征值。对于其他的方向d，方向二阶导数是所有特征值的加权平均，权重在0和1之间，且与d夹角越小的特征向量的权重越大。最大特征值确定最大二阶导数，最小特征值确定最小二阶导数。

我们可以通过（方向）二阶导数预期一个梯度下降步骤表现得多好。我们在当前点\(x^{(0)}\)处做函数f(x)的近似二阶泰勒级数：

\[f(x) \approx f(x^{(0)}) + (x-x^{(0)})^T g + \frac{1}{2} (x - x^{(0)})^T H(x - x^{(0)})\]

其中g是梯度，H是\(x^{(0)}\)点的Hessian。如果我们使用学习率\(\epsilon\)，那么新的点x将会是\(x^{(0)} - \epsilon g\)。代入上述的近似，可得

\[f(x^{(0)} - \epsilon g) \approx f(x^{(0)}) - \epsilon g^T g + \frac{1}{2} \epsilon^2 g^T H g\]

其中有3项：函数的原始值、函数斜率导致的预期改善和函数曲率导致的校正。当最后一项太大时，梯度下降实际上是可能向上移动的。当\(g^T H g\)为零或负时，近似的泰勒级数表明增加\(\epsilon\)将永远使f下降。在实践中，泰勒级数不会在\(\epsilon\)大的时候也保持准确，因此在这种情况下我们必须采取更具启发式的选择。当\(g^T H g\)为正时，通过计算可得，使近似泰勒级数下降最多的最优步长为

\[\epsilon^* = \frac{g^T g}{g^T H g}\]

最坏的情况下，g与H最大特征值\(\lambda_{max}\)对应的特征向量对齐，则最优步长是\(\frac{1}{\lambda_{max}}\)。当我们要最小化的函数能用二次函数很好地近似的情况下，Hessian的特征值决定了学习率的量级。

二阶导数还可以用于确定一个临界点是否是局部极大点、局部极小点或鞍点。回想一下，在临界点处\(f'(x)=0\)。而\(f''(x)>0\)意味着\(f'(x)\)会随着我们移向右边而增加，移向左边而减小，也就是\(f'(x-\epsilon) < 0\)和\(f'(x +\epsilon)>0\)对足够小的\(\epsilon\)成立。换句话说，当我们移向右边，斜率开始指向右边的上坡；当我们移向左边，斜率开始指向左边的上坡。因此我们得出结论，当\(f'(x) = 0 且 f''(x-\epsilon) > 0\)时，x是一个局部极小点。同理，当\(f'(x) = 0且f''(x)< 0\)时，x是一个局部极大点。这就是所谓的二阶导数测试（second derivative test）。不幸的是，当\(f''(x) = 0\)时，测试是不确定的。在这种情况下，x可能是一个鞍点或平坦区域的一部分。

在多维情况下，我们需要检测函数的所有二阶导数。利用Hessian的特征值分解，我们可以将二阶导数测试拓展到多维情况。在临界点出\((\nabla_x f(x)=0)\)，我们通过检测Hessian的特征值来判断该临界点是一个局部极大点、局部极小点还是鞍点。当Hessian是正定的（所有特征值都是正的），则该临界点是局部极小点。因为方向二阶导数在任意方向都是正的，参考单变量的二阶导数测试就能得出此结论。同样的，当Hessian是负定的（所有特征值都是负的），这个点就是局部极大点。在多维情况下，实际上我们可以找到确定该点是否为鞍点的积极迹象（某些情况下）。如果Hessian的特征值中至少一个是正的且至少一个是负的，那么x是f某个横截面的局部极大点，却是另一个横截面的局部极小点。最后，多维二阶导数测试可能像单变量版本那样是不确定的。当所有非零特征值是同号的且至少有一个特征值是0时，这个检测就是不确定的。这是因为单变量的二阶导数测试在零特征值对应的横截面上是不确定的。

多维情况下，单个点处每个方向上的二阶导数是不同的。Hessian的条件数衡量这些二阶导数的变化范围。当Hessian的条件数很差时，梯度下降法也会表现得很差。这是因为一个方向上的导数增加得很快，而在另一个方向上增加得很慢。梯度下降不知道导数的这种变化，所以它不知道应该优先探索导数长期为负的方向。病态条件也导致很难选择合适的步长。步长必须足够小，以免冲过最小而向具有较强正曲率的方向上升。这通常意味着步长太小，以至于在其他较小的曲率的方向上进展不明显。

我们可以使用Hessian矩阵的信息来指导搜索，以解决这个问题。其中最简单的方法是牛顿法（Newton’s method）。牛顿法基于一个二阶泰勒展开来近似\(x^{(0)}\)附近的f(x):

\[f(x) \approx f(x^{(0)}) + (x-x^{(0)})^T \nabla_x f(x^{(0)}) + \frac{1}{2}(x-x^{(0)})^T H(f) (x^{(0)}) (x - x^{(0)})\]

接着通过计算，我们可以得到这个函数的临界点：

\[x^* = x^{(0)} - H(f)(x^{(0)})^{-1} \nabla_x f(x^{(0)})\]

如果f是一个正定二次函数，牛顿法只要应用一次上式就能直接跳到函数的最小点。如果f不是一个真正二次但能在局部近似为正定二次，牛顿法则需要多次迭代上式。迭代地更新近似函数和跳到近似函数的最小点可以比梯度下降更快地到达临界点。这在接近局部极小点时是一个特别有用的性质，但是在鞍点附近是有害的。当附近的临界点是最小点（Hessian的所有特征值都是正的）时牛顿法才适用，而梯度下降不会被吸引到鞍点（除非梯度指向鞍点）。

仅使用梯度信息的优化算法称为一阶优化算法（first-order optimization algorithms），如梯度下降。使用Hessian矩阵的优化算法称为二阶最优化算法（second-order optimization algorithms），如牛顿法。

本书大多数上下文中使用的优化算法适用于各种各样的函数，但几乎都没有理论保证。因为在深度学习中使用的函数族是相当复杂的，所以深度学习算法往往缺乏理论保证。在许多其他领域，优化的主要方法是为有限的函数族设计优化算法。

在深度学习的背景下，限制函数满足Lipschitz连续（Lipschitz continuous）或其导数Lipschitz连续可以获得一些保证。Lipschitz连续函数的变化速度以Lipschitz常数（Lipschitz constant）\(L\)为界：

\forall x, \forall y, \mid f(x) - f(y) \mid \leq L x - y _2$$

这个属性允许我们量化自己的假设——梯度下降等算法导致的输入的微小变化将使输出只产生微小变化，因此是很有用的。Lipschitz连续性也是相当弱的约束，并且深度学习中很多优化问题经过相对较小的修改后就能变得Lipschitz连续。

最成功的特定优化领域或许是凸优化（Convex optimization）。凸优化通过更强的限制提供更多的保证。凸优化算法只对凸函数适用，即Hessian处处半正定的函数。因为这些函数没有鞍点而且其所有局部极小点必然是全局最小点，所以表现很好。然而，深度学习中的大多数问题都难以表示成凸优化的形式。凸优化仅用作一些深度学习算法的子程序。凸优化中的分析思路对证明深度学习算法的收敛性非常有用，然而一般来说，深度学习背景下凸优化的重要性大大减少。

随机梯度下降

几乎所有的深度学习算法都用到了一个非常重要的算法：随机梯度下降（stochastic gradient descent，SGD）。随机梯度下降是梯度下降算法的一个扩展。

机器学习中反复出现的一个问题是好的泛化需要大的训练集，但大的训练集的计算代价也更大。

机器学习算法中的代价函数通常可以分解成每个样本的代价函数的总和。例如，训练数据的负条件对数似然可以写出

\[J(\theta) = E_{x,y \sim \hat{p}_{data}} L(x,y,\theta) = \frac{1}{m} \sum_{i=1}^m L(x^{(i)}, y^{(i)}, \theta)\]

其中L是每个样本的损失\(L(x,y,\theta) = -log p(y \mid x; \theta)\)

对于这些相加的代价函数，梯度下降需要计算

\[\nabla_\theta J(\theta) = \frac{1}{m} \sum_{i=1}^m \nabla_\theta L(x^{(i)}, y^{(i)}, \theta)\]

这个运算的计算代价是\(O(m)\)。随着训练集规模增长为数十亿的样本，计算一步梯度也会消耗相当长的时间。

随机梯度下降的核心是，梯度是期望。期望可以使用小规模的样本近似估计。具体而言，在算法的每一步，我们从训练集中均匀抽出一小批量（minibatch）样本\(B={x^{(1)},..., x^{(m')}}\)。小批量的数目\(m'\)通常是一个相对较小的数，从一到几百。重要的是，当训练集大小m增长时，\(m'\)通常是固定的。我们可能在拟合几十亿的样本时，每次更新计算只用到几百个样本。

梯度的估计可以表示成

\[g = \frac{1}{m'} \nabla_\theta \sum_{i=1}^{m'} L(x^{(i)}, y^{(i)}, \theta)\]

使用来自小批量B的样本。然后，随机梯度下降算法使用如下的梯度下降估计：

\[\theta \leftarrow \theta - \epsilon g\]

其中，\(\epsilon\)是学习率。

梯度下降往往被认为很慢或不可靠。以前，将梯度下降应用到非凸优化问题被认为很鲁莽或没有原则。现在，我们知道梯度下降用于训练时效果不错。优化算法不一定能保证在合理的时间内达到一个局部最小值，但它通常能及时地找到代价函数一个很小的值，并且是有用的。

随机梯度下降在深度学习之外有很多重要的应用。它是在大规模数据上训练大型线性模型的主要方法。对于固定大小的模型，每一步随机梯度下降更新的计算量不取决于训练集的大小m。在实践中，当训练集大小增长时，我们通常会使用一个更大的模型，但这并非是必须的。达到收敛所需的更新次数通常会随训练集规模增大而增加。然而，当m趋向于无穷大时，该模型最终会在随机梯度下降抽样完训练集上的所有样本之前收敛到可能的最优测试误差。继续增加m不会延长达到模型可能的最优测试误差的时间。从这点来看，我们可以认为用SGD训练模型的渐近代价是关于m的函数的O(1)级别。

在深度学习兴起之前，学习非线性模型的主要方法是结合核技巧的线性模型。很多核学习算法需要构建一个\(m \times m\)的矩阵\(G_{i,j} = k(x^{(i)}, x^{(j)})\)。构建这个矩阵的计算量是\(O(m^2)\)。当数据集是几十亿个样本时，这个计算量是不能接受的。在学术界，深度学习从2006年开始受到关注的原因是，在数以万计样本的中等规模数据集上，深度学习在新样本上比当时很多热门算法泛化得更好。不久后，深度学习在工业界受到了更多的关注，因为其提供了一种训练大数据集上的非线性模型的可扩展方式。

Reference