三、算法实现

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

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

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

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

   这种方法用于Torch和Caffe之类的库中。

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

   这种方法用于Theano和TensorFlow之类的库中。

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

   

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

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

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

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

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

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

3.2 算法框架

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

   根据前面介绍的张量的链式法则， ，则张量的链式法则为：

   

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

3.2.1 三个子过程

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

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

   • 该对象有个 f方法，该方法给出了父节点到 的函数： 。

     其中 为 的父节点集合：

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

     如果考虑 的所有子节点集合 ，则 它们的梯度贡献之和就是总的梯度：

     

2. ：返回图 中节点 的子节点列表，也就是节点 的子节点集合： 。

3. ：返回图 中节点 的父节点列表，也就是 的父节点集合： 。

4. op.bprop方法总是假定其输入节点各不相同。

   如果定义了一个乘法操作，而且每条输入节点都是x，则op.bprop方法也会认为它们是不同的：

   op.bprop会认为其输入分别为y和z，然后求出表达式之后再代入y=x,z=x 。

5. 大多数反向传播算法的实现都提供了operation对象以及它的bprop方法。

   如果希望添加自己的反向传播过程，则只需要派生出op.bprop方法即可。

3.2.2 反向传播过程

1. build_grad 过程采用符号-符号方法 ，用于求解单个结点 的梯度 。

2. build_grad 在求解过程中会用到裁剪的计算图 ， 会剔除所有与 梯度无关的节点，保留与 梯度有关的节点。

3. build_grad 过程：

   • 输入：

     • 待求梯度的节点
     • 计算图
     • 被裁减的计算图
     • 梯度表

   • 输出：

   • 算法步骤：

     • 如果 已经就在 中，则直接返回 。

       这样可以节省大量的重复计算

     • 初始化 。

     • 在图 中， 迭代遍历 的子节点的集合 ：：

       • 获取计算 的操作：

       • 获取该子节点的梯度，这是通过递归来实现的： 。

         因为子节点更靠近输出端，因此子节点 的梯度一定是先于 的梯度被计算。

       • 计算子节点 对于 的贡献： 。

       • 累加子节点 对于 的贡献： 。

     • 存储梯度来更新梯度表： 。

     • 在 中插入节点 来更新计算图 。插入过程不仅增加了节点 ，还增加了 的父节点到 的边。

     • 返回 。

4. 反向传播过程：

   • 输入：

     • 计算图
     • 目标变量
     • 待计算梯度的变量的集合

   • 输出：

   • 算法步骤：

     • 裁剪 为 ，使得 仅包含 的祖先之中，那些同时也是 的后代的节点。

       因为这里只关心 中节点的梯度

     • 初始化 ，它是一个表，各表项存储的是 对于对应节点的偏导数。

     • 初始化 （因为 ）。

     • 迭代：对每个 ，执行 。

     • 返回 。

3.3.3 算法复杂度

1. 算法复杂度分析过程中，我们假设每个操作的执行都有大概相同的时间开销。

   实际上每个操作可能包含多个算术运算，如：将矩阵乘法视为单个操作的话，就包含了很多乘法和加法。因此每个操作的运行时间实际上相差非常大。

2. 在具有 个节点的计算图中计算梯度，不会执行超过 的操作，也不会执行超过 个存储。

   因为最坏的情况下前向传播将遍历执行图中的全部 个节点，每两个节点之间定义了一个梯度。

3. 大多数神经网络的代价函数的计算图是链式结构，因此不会执行超过 的操作。

   从 降低到 是因为：并不是所有的两个节点之间都有数据通路。

4. 如果直接用梯度计算公式来求解则会产生大量的重复子表达式，导致指数级的运行时间。

   反向传播过程是一种表填充算法，利用存储中间结果（存储子节点的梯度） 来对表进行填充。计算图中的每个节点对应了表中的一个位置，该位置存储的就是该节点的梯度。

   通过顺序填充这些表的条目，反向传播算法避免了重复计算公共表达式。这种策略也称作动态规划。

3.4、应用

1. 考虑只有单个隐层的最简单的深度前馈网络，使用小批量（minibatch）随机梯度下降法训练模型。反向传播算法用于计算单个minibatch上的代价函数的梯度。

2. 取训练集上的一组minibatch实例，记做输入矩阵 ，矩阵的每一行就是一个实例，其中 为样本数量， 为特征数量。同时给出标记 ，它是每个样本的真实标记。

   设激活函数为 ReLU 激活函数，设模型不包含偏置。设输入层到隐层的权重矩阵为 ，则隐层的输出为： 。设隐层到输出层的权重矩阵为 ，则分类的非归一化对数概率为 。

   假设程序包含了cross_entropy操作，用于计算未归一化对数概率分布定义的交叉熵 ，该交叉熵作为代价函数 。引入正则化项，总的代价函数为： 。

   交叉熵为 。最小化交叉熵就是最大化似然估计

   其计算图如下所示：

   

3. 目标是通过小批量随机梯度下降法求解代价函数的最小值，因此需要计算 。

   从图中看出有两种不同的路径从 回退到 ：

   • 一条路径是通过正则化项。

     这条路径对于梯度的贡献相对简单，它对于 的梯度贡献为 。

   • 一条路径是通过交叉熵。

     • 对于 ，这条分支其梯度的贡献为 ，其中 为 ，将 替换为

     • 对于 ，这条分支对于梯度的贡献计算为：

       • 首先计算 。
       • 然后根据relu操作的反向传播规则：根据 中小于零的部分，对应地将 对应位置清零，记清零后的结果为 。
       • 分支的梯度贡献为： 。

4. 该算法的计算成本主要来源于矩阵乘法：

   • 前向传播阶段（为了计算对各节点求值）：乘-加运算的数量为 ，其中 为权重的数量。
   • 在反向传播阶段：具有相同的计算成本。

5. 算法的主要存储成本是：需要存储隐层非线性函数的输入。因此存储成本是 ，其中 为 minibatch中样例的数量， 是隐单元的数量。

6. 这里描述的反向传播算法要比现实中实际使用的实现更简单。

   • 这里定义的operation限制为返回单个张量的函数，大多数软件实现支持返回多个张量的operation 。

   • 这里未指定如何控制反向传播的内存消耗。反向传播经常涉及将许多张量加在一起。

     • 朴素算法将分别计算这些张量，然后第二步中将所有张量求和，内存需求过高。
     • 可以通过维持一个buffer，并且在计算时将每个值加到buffer中来避免该瓶颈。

   • 反向传播的具体实现还需要处理各种数据类型，如32位浮点数、整数等。

   • 一些operation具有未定义的梯度，需要跟踪这些情况并向用户报告。