李宏毅机器学习笔记——反向传播算法

反向传播算法

反向传播（Backpropagation）是一种用于训练人工神经网络的算法，它通过计算损失函数相对于网络中每个参数的梯度来更新这些参数，从而最小化损失函数。反向传播是深度学习中最重要的算法之一，通常与梯度下降等优化算法结合使用。

反向传播的基本原理

反向传播的核心思想是利用链式法则（Chain Rule）来高效地计算损失函数相对于每个参数的梯度。以下是反向传播的基本步骤：

1. 前向传播（Forward Pass）：

   • 输入数据通过神经网络进行传播，计算出每一层的输出，直到得到最终的预测结果。
   • 计算损失函数，评估预测结果与真实标签之间的差异。

2. 计算损失函数的梯度：

   • 从输出层开始，计算损失函数相对于输出的梯度。
   • 通过链式法则，将梯度逐层向后传播，计算每一层的梯度。

3. 更新参数：

   • 使用计算得到的梯度更新网络中的权重和偏置，通常使用梯度下降法或其变种（如 Adam、RMSprop 等）。

反向传播的数学细节

假设我们有一个简单的神经网络，包含输入层、隐藏层和输出层。设定损失函数为 $L$，网络的参数为 $W$ 和 $b$（权重和偏置），反向传播的步骤如下：

1. 前向传播：

   • 计算输出：
     $$y_{\text{pred}}=f(W\cdot x+b)$$
   • 计算损失：
     $$L=\text{Loss}(y_{\text{true}},y_{\text{pred}})$$

2. 反向传播：

   • 计算输出层的梯度：
     $$\frac{\partial L}{\partial y_{\text{pred}}}$$
   • 计算隐藏层的梯度：
     $$\frac{\partial L}{\partial W}=\frac{\partial L}{\partial y_{\text{pred}}}\cdot \frac{\partial y_{\text{pred}}}{\partial W}$$
   • 继续向前传播，直到输入层。

3. 更新参数：

   • 使用学习率 $\eta$ 更新参数：
     $$W=W-\eta \cdot \frac{\partial L}{\partial W}$$
     $$b=b-\eta \cdot \frac{\partial L}{\partial b}$$

反向传播的优点

• 高效性：反向传播算法通过链式法则高效地计算梯度，避免了对每个参数单独计算梯度的高昂成本。
• 适应性：可以应用于各种类型的神经网络，包括全连接网络、卷积神经网络（CNN）、递归神经网络（RNN）等。

反向传播是训练神经网络的核心算法，通过计算损失函数的梯度并更新网络参数，使得模型能够逐步提高预测的准确性。它是深度学习的基础，使得复杂的神经网络能够有效地学习和优化。

链式法则

1. 反向传播算法是一种利用链式法则计算微分的算法。
2. 在一维的情况下，链式法则为: $\frac{dz}{dx}=\frac{dz}{dy}\times \frac{dy}{dx}$ 。
3. 在多维情况下，设： $\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^m,\overrightarrow{\mathbf{y}}\in {\mathbb{R}}^n，g$ 为 ${\mathbb{R}}^m$ 到 ${\mathbb{R}}^n$ 的映射且满足 $\overrightarrow{\mathbf{y}}=g(\overrightarrow{\mathbf{x}})，f$ 为 ${\mathbb{R}}^n$ 到 $\mathbb{R}$ 的映射且满 足 $z=f(\overrightarrow{\mathbf{y}})$ 。则有:
   $$\frac{\partial z}{\partial x_i}=\sum _{j=1}^n\frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_i},i=1,2,\cdots ,m$$
   使用向量记法，可以等价地写作:
   $${\nabla }_{\overrightarrow{\mathbf{x}}}z={\left(\frac{\partial \overrightarrow{\mathbf{y}}}{\partial \overrightarrow{\mathbf{x}}}\right)}^T{\nabla }_{\overrightarrow{\mathbf{y}}z}$$
   其中: $\frac{\partial \overrightarrow{\mathbf{y}}}{\partial \overrightarrow{\mathbf{x}}}$ 为 $g$ 的 $n\times m$ 阶雅可比矩阵， ${\nabla }_{\overrightarrow{\mathbf{x}}}z$ 为 $z$ 对 $\overrightarrow{\mathbf{x}}$ 的梯度， ${\nabla }_{\overrightarrow{\mathbf{y}}}z$ 为 $z$ 对 $\overrightarrow{\mathbf{y}}$ 的梯度:
   $${\nabla }_{\overrightarrow{\mathbf{x}}}z=\left[\begin{array}{c}\frac{\partial z}{\partial x_1}\\ \frac{\partial z}{\partial x_2}\\ ⋮\\ \frac{\partial z}{\partial x_m}\end{array}\right]{\nabla }_{\overrightarrow{\mathbf{y}}}z=\left[\begin{array}{c}\frac{\partial z}{\partial y_1}\\ \frac{\partial z}{\partial y_2}\\ ⋮\\ \frac{\partial z}{\partial y_n}\end{array}\right]\frac{\partial \overrightarrow{\mathbf{y}}}{\partial \overrightarrow{\mathbf{x}}}=\left[\begin{array}{cccc}\frac{\partial y_1}{\partial x_1}& \frac{\partial y_1}{\partial x_2}& \cdots & \frac{\partial y_1}{\partial x_{ns}}\\ \frac{\partial y_2}{\partial x_1}& \frac{\partial y_2}{\partial x_2}& \cdots & \frac{\partial y_2}{\partial x_m}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{\partial y_n}{\partial x_1}& \frac{\partial y_n}{\partial x_2}& \cdots & \frac{\partial y_n}{\partial x_m}\end{array}\right]$$

张量链式法则

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

• 首先将张量展平为一维向量。
• 然后计算该向量的梯度。
• 然后将该牱度重新构造为张量。

2. 记 ${\nabla }_{\mathbf{X}}z$ 为 $z$ 对张量 $\mathbf{X}$ 的梯度。 $\mathbf{X}$ 现在有多个索引 (如：二维张量有两个索引)，可以使用单个变量 $i$ 来表 示 $\mathbf{X}$ 的索引元组（如 $i=1\sim 9$ 表示: 一个二维张量的系引，每个维度三个元素）。
   这就与向量中的系引方式完全一致: $(\nabla \mathbf{X}z{)}_i=\frac{\theta z}{\partial x_i}$ 。
   奴:
   $$\mathbf{X}=\left[\begin{array}{lll}{x}_1& x_2& x_3\\ x_4& x_5& x_6\\ x_7& x_8& x_9\end{array}\right]$$
   则有:
   $${\nabla }_{\mathbf{X}}z=\left[\begin{array}{ccc}\frac{\partial z}{\partial x_1}& \frac{\partial z}{\partial x_2}& \frac{\partial z}{\partial x_3}\\ \frac{\partial z}{\partial x_4}& \frac{\partial z}{\partial x_5}& \frac{\partial z}{\partial x_6}\\ \frac{\partial z}{\partial x_{w_q}}& \frac{\partial z}{\partial z_g}& \frac{\partial z}{\partial x_9}\end{array}\right]$$
3. 设 $\mathbf{Y}=g(\mathbf{X}),z=f(\mathbf{Y})$ ，用单个变量 $j$ 来表示 $\mathbf{Y}$ 的索引元組。则张量的链式法则为:
   $$\frac{\partial z}{\partial x_i}=\sum _j\frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_i}\Rightarrow {\nabla }_{\mathbf{X}}z=\sum _j\left({\nabla }_{\mathbf{X}}{y}_j\right)\frac{\partial z}{\partial y_j}$$
   如：
   $$\mathbf{X}=\left[\begin{array}{lll}{x}_1& x_2& x_3\\ x_4& x_5& x_6\\ x_7& x_8& x_9\end{array}\right]$$
   则有:
   $${\nabla }_{\mathbf{X}}z=\left[\begin{array}{llll}{\sum }_j\frac{\partial z}{\partial y_j}& \frac{\partial y_j}{\partial x_1}& {\sum }_j\frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_2}& {\sum }_j\frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_j}\\ {\sum }_j\frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_4}& {\sum }_j\frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_j}& {\sum }_j\frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_0}& \\ {\sum }_j\frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_7}& {\sum }_j\frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_8}& {\sum }_j\frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_j}& \end{array}\right]$$

反向传播算法

3. 反向传播算法:

• 输入:
• 计算图 $\mathcal{G}$
• 初始化参数向量 ${\vec{u}}^{\ast }$
  。 输出: $\frac{\partial u_n}{\partial u_j},j=1,2,\cdots ,n_i$
• 运行计算 $u_n$ 的前向算法，获取每个节点的值。
• 给出一个 grad_table 表，它存储的是已经计算出来的偏导数。
  $u_i$ 对应的表项存储的是偏导数 $\frac{\partial u_n}{\partial u_i}$ 。
• 初始化 grad_table $\left[u_n\right]=1$ 。
• 沿着计算图 $\mathcal{B}$ 计算偏导数。遍历 $j$ 从 $n-1$ 到 1 :
• 计算 $\frac{\partial u_{u_n}}{\partial u_j}={\sum }_{u_i\in {\mathbb{C}}_j}\frac{\partial u_n}{\partial u_i}\frac{\partial u_i}{\partial u_j}$ 。其中： $\frac{\partial u_n}{\partial u_i}$ 是已经存储的 grad_table[ui $]$, $\frac{\partial u_i}{\partial u_j}$ 为实时计算的。
  图 $\mathcal{G}$ 中的边 $u_j\to u_i$ 定义了一个操作，而该操作的偏导只依赖于这两个变量，因此可以实时求 解 $\frac{\partial u_i}{\partial u_j}$ 。
• 存储 $\mathrm{grad}$ _able ${\left[u_j\right]}_{\text{。 }}$
• 逅回 $\mathrm{grad}\mathrm{table}\left[u_j\right],j=1,2,\cdots ,n_{\hat{j}}$ 。

4. 反向传播算法计算所有的偏导数，计算量与 $\mathcal{G}$ 中的边的数量成正比。
   其中每条边的计算包括计算偏导数，以及执行一次向量点积。
5. 上述反向传播算法为了减少公共子表达式的计算量，并没有考虑存储的开销。这避免了重复子表达式的指数 级的增长。
   。 某些算法可以通过对计算图进行简化从而避免更多的子表达式。
   。 有些算法会重新认算这些子表达式而不是存储它们，从而节省内存。

参考

DataWhale
http://www.huaxiaozhuan.com/