反向传播算法

  1. 前向传播 forward propagation 过程: 当前馈神经网络接收输入 并产生输出 时,信息前向流动。

    输入 提供初始信息,然后信息传播到每一层的隐单元,最终产生输出

  2. 反向传播算法back propagation允许来自代价函数的信息通过网络反向流动以便计算梯度。

    • 反向传播并不是用于学习整个神经网络的算法,而是仅用于计算梯度的算法。

      神经网络的学习算法是随机梯度下降这类基于梯度的算法。

    • 反向传播不仅仅适用于神经网络,原则上它适用于计算任何函数的导数。

  1. 计算图computational graph

    • 图中的每个节点代表一个变量(可以是标量、向量、矩阵或者张量)。

    • 操作:operation为一个或者多个变量的简单函数。

      • 多个操作组合在一起可以描述一个更复杂的函数。
      • 一个操作仅返回单个输出变量(可以是标量、向量、矩阵或者张量)。
    • 如果变量 是变量 通过一个操作计算得到,则在图中绘制一条从 的有向边。

    如: 的计算图:

一、链式法则

  1. 反向传播算法是一种利用链式法则计算微分的算法。

  2. 在一维的情况下,链式法则为:

  3. 在多维情况下,设: 的映射且满足 的映射且满足 。则有:

    使用向量记法,可以等价地写作:

    其中: 阶雅可比矩阵, 的梯度, 的梯度:

    反向传播算法由很多这样的雅可比矩阵与梯度的乘积操作组成。

1.1 张量链式法则

  1. 链式法则不仅可以作用于向量,也可以应用于张量:

    • 首先将张量展平为一维向量。
    • 然后计算该向量的梯度。
    • 然后将该梯度重新构造为张量。
  2. 对张量 的梯度。 现在有多个索引(如:二维张量有两个索引),可以使用单个变量 来表示 的索引元组(如 表示:一个二维张量的索引,每个维度三个元素)。

    这就与向量中的索引方式完全一致:

    如:

    则有:

  3. ,用单个变量 来表示 的索引元组。则张量的链式法则为:

    如:

    则有:

    .

1.2 重复子表达式

  1. 给定计算图以及计算图中的某个标量 ,根据链式法则可以很容易地写出 对于产生 的任意节点的梯度的数学表达式。

    但是在计算该表达式的时候,许多子表达式可能在计算整个梯度表达式的过程中重复很多次。

    如图中:

    可以看到 被计算多次。

    • 在复杂的计算图中,可能存在指数量级的重复子表达式,这使得原始的链式法则几乎不可实现。

    • 一个解决方案是:计算 一次并将它存储在 中,然后采用 来计算梯度。

      这也是反向传播算法采用的方案:在前向传播时,将节点的中间计算结果全部存储在当前节点上。其代价是更高的内存开销。

  2. 有时候必须重复计算子表达式。这是以较高的运行时间为代价,来换取较少的内存开销。

二、反向传播

2.1 前向传播

  1. 考虑计算单个标量 的计算图:

    • 假设有 个输入节点: 。它们对应的是模型的参数和输入。
    • 假设 为中间节点。
    • 假设 为输出节点,它对应的是模型的代价函数。
    • 对于每个非输入节点 ,定义其双亲节点的集合为
    • 假设每个非输入节点 ,操作 与其关联,并且通过对该函数求值得到:

    通过仔细排序(有向无环图的拓扑排序算法),使得可以依次计算

  2. 前向传播算法:

    • 输入:

      • 计算图
      • 初始化向量
    • 输出: 的值

    • 算法步骤:

      • 初始化输入节点:

      • 根据计算图,从前到后计算 。对于 计算过程为:

        • 计算 的双亲节点集合
        • 计算
      • 输出

2.2 反向传播

  1. 计算 时需要构造另一张计算图 : 它的节点与 中完全相同,但是计算顺序完全相反。

    计算图 如下图所示:

  2. 对于图中的任意一非输出节点 (非 ),根据链式法则:

    其中 表示图 中的边

    • 若图 中存在边 ,则在图 中存在边 ,则 的子节点。
    • 设图 的子节点的集合为 ,则上式改写作:
  3. 反向传播算法:

    • 输入:

      • 计算图
      • 初始化参数向量
    • 输出:

    • 算法步骤:

      • 运行计算 的前向算法,获取每个节点的值。

      • 给出一个 grad_table表,它存储的是已经计算出来的偏导数。

        对应的表项存储的是偏导数

      • 初始化

      • 沿着计算图 计算偏导数。遍历

        • 计算 。其中: 是已经存储的 为实时计算的。

          中的边 定义了一个操作,而该操作的偏导只依赖于这两个变量,因此可以实时求解

        • 存储

      • 返回

  1. 反向传播算法计算所有的偏导数,计算量与 中的边的数量成正比。

    其中每条边的计算包括计算偏导数,以及执行一次向量点积。

  2. 上述反向传播算法为了减少公共子表达式的计算量 ,并没有考虑存储的开销。这避免了重复子表达式的指数级的增长。

    • 某些算法可以通过对计算图进行简化从而避免更多的子表达式。
    • 有些算法会重新计算这些子表达式而不是存储它们,从而节省内存。

2.3 反向传播示例

  1. 对于 ,将公式拆分成 ,则有:

    根据链式法则,有

    假设 ,则计算图如下。其中:绿色为前向传播的值,红色为反向传播的结果。

    • 前向传播,计算从输入到输出(绿色);反向传播,计算从尾部开始到输入(红色)。

    • 在整个计算图中,每个单元的操作类型,以及输入是已知的。通过这两个条件可以计算出两个结果:

      • 这个单元的输出值。
      • 这个单元的输出值关于输入值的局部梯度比如

      每个单元计算这两个结果是独立完成的,它不需要计算图中其他单元的任何细节。

      但是在反向传播过程中,单元将获取整个网络的最终输出值(这里是 )在单元的输出值上的梯度,即回传的梯度。

      链式法则指出:单元应该将回传的梯度乘以它对其输入的局部梯度,从而得到整个网络的输出对于该单元每个输入值的梯度。如:

  2. 在多数情况下,反向传播中的梯度可以被直观地解释。如:加法单元、乘法单元、最大值单元。

    假设: ,前向传播的计算从输入到输出(绿色),反向传播的计算从尾部开始到输入(红色)。

    • 加法单元 ,则 。如果 ,则有:

      这表明:加法单元将回传的梯度相等的分发给它的输入。

    • 乘法单元 ,则 。如果 ,则有:

      这表明:乘法单元交换了输入数据,然后乘以回传的梯度作为每个输入的梯度。

    • 取最大值单元 ,则:

      如果 ,则有:

      这表明:取最大值单元将回传的梯度分发给最大的输入。

  3. 通常如果函数 的表达式非常复杂,则当对 进行微分运算,运算结束后会得到一个巨大而复杂的表达式。

    • 实际上并不需要一个明确的函数来计算梯度,只需要如何使用反向传播算法计算梯度即可。
    • 可以把复杂的表达式拆解成很多个简单的表达式(这些表达式的局部梯度是简单的、已知的),然后利用链式法则来求取梯度。
    • 在计算反向传播时,前向传播过程中得到的一些中间变量非常有用。实际操作中,最好对这些中间变量缓存。

2.4 深度前馈神经网络应用

  1. 给定一个样本,其定义代价函数为 ,其中 为神经网络的预测值。

    考虑到正则化项,定义损失函数为: 。其中 为正则化项,而 包含了所有的参数(包括每一层的权重 和每一层的偏置 )。

    这里给出的是单个样本的损失函数,而不是训练集的损失函数。

  2. 计算 的计算图为:

  3. 前向传播用于计算深度前馈神经网络的损失函数。算法为:

    • 输入:

      • 网络层数

      • 每一层的权重矩阵

      • 每一层的偏置向量

      • 每一层的激活函数

        也可以对所有的层使用同一个激活函数

      • 输入 和对应的标记

      • 隐层到输出的函数

    • 输出:损失函数

    • 算法步骤:

      • 初始化

      • 迭代:,计算:

      • 计算

  4. 反向传播用于计算深度前馈网络的损失函数对于参数的梯度。

    梯度下降算法需要更新模型参数,因此只关注损失函数对于模型参数的梯度,不关心损失函数对于输入的梯度

    • 根据链式法则有:

      考虑到 ,因此雅可比矩阵 为对角矩阵,对角线元素 表示 的第 个元素。

      因此 ,其中 表示Hadamard积。

    • 因为 ,因此:

      上式仅仅考虑从 传播到 中的梯度。 考虑到损失函数中的正则化项 包含了权重和偏置,因此需要增加正则化项的梯度。则有:

    • 因为 ,因此:

  5. 反向传播算法:

    • 输入:

      • 网络层数
      • 每一层的权重矩阵
      • 每一层的偏置向量
      • 每一层的激活函数
      • 输入 和对应的标记
    • 输出:梯度

    • 算法步骤:

      • 通过前向传播计算损失函数 以及网络的输出

      • 计算输出层的导数:

        这里等式成立的原因是:正则化项 与模型输出 无关。

      • 计算最后一层隐单元的梯度:

      • 迭代: ,迭代步骤如下:

        每一轮迭代开始之前,维持不变式:

        • 计算

        • 令:

        • 计算对权重和偏置的偏导数:

        • 计算

        • 令:

三、算法实现

3.1 符号-数值 / 符号-符号方法

  1. 代数表达式和计算图都是对符号symbol进行操作,这些基于代数的表达式或者基于图的表达式称作符号表达式。

    当训练神经网络时,必须给这些符号赋值。如:对于符号 赋予一个实际的数值,如

  2. 符号到数值的方法:给定计算图,以及图的一组输入的数值,然后返回在这些输入值处的梯度。

    这种方法用于TorchCaffe之类的库中。

  3. 符号到符号的方法:给定计算图,算法会添加额外的一些节点到计算图中,这些额外的节点提供了所需的导数的符号描述。

    这种方法用于TheanoTensorFlow之类的库中。

    下图左侧为 的计算图,右侧添加了若干节点从而给出了计算 的计算图。

  4. 符号到符号的方法的优点:导数可以使用与原始表达式相同的编程语言来描述。

    导数只是另外一张计算图,因此可以再次运行反向传播算法对导数再进行求导,从而获取更高阶的导数。

  5. 推荐使用符号到符号的方法来求导数。一旦构造出了添加导数后的计算图,那么随后如果给出了输入的数值,可以对图中的任意子节点求值。

    目前通用的计算图求解引擎的做法是:任意时刻,一旦一个节点的父节点都求值完毕,那么该节点将能够立即求值。

  6. 事实上符号到数值的方法与符号到符号的方法执行了同样的计算过程,区别在于:

    • 符号到数值的方法并没有暴露内部的计算过程。
    • 符号到符号的方法将各种求导运算暴露出来,添加到计算图中成为了节点。

3.2 算法框架

  1. 假设计算图 中的每个节点对应一个变量。这里将变量描述为一个张量 ,它可以具有任意维度并且可能是标量、向量、矩阵。

    根据前面介绍的张量的链式法则, ,则张量的链式法则为:

    其中 为张量 展平为一维向量后的索引, 为张量 展平为一维向量之后的第 个元素。

3.2.1 三个子过程

  1. :返回用于计算 的操作operation 。它就是tensorflow 中的Operation 对象。

    该函数通常返回一个操作对象

    • 该对象有个 f方法,该方法给出了父节点到 的函数:

      其中 的父节点集合:

    • 该操作对象有个bprop方法。给定 的某个子节点 ,该方法用于已知 的梯度 ,求解 对于 的梯度的贡献: