这里回顾dlsys第四讲，本讲内容是自动微分。

课程主页：

大纲

不同微分方法的介绍；
反向模式自动微分；

不同微分方法的介绍

微分在机器学习的那个步骤起作用

回顾：每个机器学习算法都包含三个不同的元素。计算关于假设类参数的损失函数梯度是机器学习中最常见的操作：

数值微分

数值微分是根据定义直接计算梯度：

$\frac{\partial f(\theta)}{\partial \theta_i}=\lim _{\epsilon \rightarrow 0} \frac{f\left(\theta+\epsilon e_i\right)-f(\theta)}{\epsilon}$

一种更精确的近似梯度的方法：

$\frac{\partial f(\theta)}{\partial \theta_i}=\frac{f\left(\theta+\epsilon e_i\right)-f\left(\theta-\epsilon e_i\right)}{2 \epsilon}+o\left(\epsilon^2\right)$

数值微分的问题有数值误差，并且计算效率较低。

数值误差检查

然而，数值微分是测试自动微分算法实现的强大工具：

$\delta^T \nabla_\theta f(\theta)=\frac{f(\theta+\epsilon \delta)-f(\theta-\epsilon \delta)}{2 \epsilon}+o\left(\epsilon^2\right)$

其中$\delta$是单位球上的点，如果自动微分算法实现正确，则上式成立。

符号微分

写下公式，通过求和、乘积和链式法则推导出梯度（即最朴素的方式，利用定义求导）：

$\begin{aligned} \frac{\partial(f(\theta)+g(\theta))}{\partial \theta}&=\frac{\partial f(\theta)}{\partial \theta}+\frac{\partial g(\theta)}{\partial \theta}\\ \frac{\partial(f(\theta) g(\theta))}{\partial \theta}&={g}(\theta) \frac{\partial f(\theta)}{\partial \theta}+{f}(\theta) \frac{\partial g(\theta)}{\partial \theta} \\ \frac{\partial f(g(\theta))}{\partial \theta}&=\frac{\partial f(g(\theta))}{\partial g(\theta)} \frac{\partial g(\theta)}{\partial \theta} \end{aligned}$

这样实现会导致浪费计算，例如：

$\begin{aligned} f(\theta)&=\prod_{i=0}^n \theta_i\\ \frac{f(\theta)}{\partial \theta_k}&=\prod_{j \neq k}^n \theta_j \end{aligned}$

计算全部梯度需要$n(n-1)$次乘法。

计算图

每个节点代表计算中的一个（中间）值，边表示输入输出关系：

自动微分的前向模式

考虑计算：

$\dot{v}_i=\frac{\partial v_i}{\partial x_1}$

我们可以按照计算图的拓扑排序顺序计算$\dot{v}_i$，这被称为自动微分的前向模式：

$\begin{aligned} & \dot{v}_1=1 \\ & \dot{v}_2=0 \\ & \dot{v}_3=\dot{v}_1 / v_1=0.5 \\ & \dot{v}_4=\dot{v}_1 v_2+\dot{v}_2 v_1=1 \times 5+0 \times 2=5 \\ & \dot{v}_5=\dot{v}_2 \cos v_2=0 \times \cos 5=0 \\ & \dot{v}_6=\dot{v}_3+\dot{v}_4=0.5+5=5.5 \\ & \dot{v}_7=\dot{v}_6-\dot{v}_5=5.5-0=5.5 \end{aligned}$

因此：

$\frac{\partial y}{\partial x_1}=v_7=5.5$

前向模式的局限性

对于$f:\mathbb R^n \to \mathbb R^k$，我们需要$n$次前向AD传递来获得关于每个输入的梯度。在深度学习中，我们主要关心$k=1$和$n$很大的情况。为了高效地解决问题，我们需要使用另一种AD。

反向模式自动微分

实例

依然是之前的例子，我们计算：

$\bar{v}_i=\frac{\partial y}{\partial v_i}$

然后我们可以按照计算图的反向拓扑顺序迭代计算$\bar{v}_i$：

$\begin{aligned} & \overline{v_7}=\frac{\partial y}{\partial v_7}=1 \\ & \overline{v_6}=\bar{v}_7 \frac{\partial v_7}{\partial v_6}=\overline{v_7} \times 1=1 \\ & \overline{v_5}=\bar{v}_7 \frac{\partial v_7}{\partial v_5}=\overline{v_7} \times(-1)=-1 \\ & \overline{v_4}=\overline{v_6} \frac{\partial v_6}{\partial v_4}=\overline{v_6} \times 1=1 \\ & \overline{v_3}=\overline{v_6} \frac{\partial v_6}{\partial v_3}=\overline{v_6} \times 1=1 \\ & \overline{v_2}=\overline{v_5} \frac{\partial v_5}{\partial v_2}+\overline{v_4} \frac{\partial v_4}{\partial v_2}=\overline{v_5} \times \cos v_2+\bar{v}_4 \times v_1=-0.284+2=1.716 \\ & \overline{v_1}=\bar{v}_4 \frac{\partial v_4}{\partial v_1}+\overline{v_3} \frac{\partial v_3}{\partial v_1}=\overline{v_4} \times v_2+\bar{v}_3 \frac{1}{v_1}=5+\frac{1}{2}=5.5 \end{aligned}$

multiple path情形

$v_1$被用于计算图的多条路径上（$v_2$和$v_3$）：

即$y=f(v_2, v_3)$，那么：

$\overline{v_1}=\frac{\partial y}{\partial v_1}=\frac{\partial f\left(v_2, v_3\right)}{\partial v_2} \frac{\partial v_2}{\partial v_1}+\frac{\partial f\left(v_2, v_3\right)}{\partial v_3} \frac{\partial v_3}{\partial v_1}=\overline{v_2} \frac{\partial v_2}{\partial v_1}+\overline{v_3} \frac{\partial v_3}{\partial v_1}$

定义伴随：

$\overline{v_{i \rightarrow j}}=\bar{v}_j \frac{\partial v_j}{\partial v_i}$

那么：

$\bar{v}_i=\sum_{j \in \text { next }(i)} \overline{v_{i \rightarrow j}}$

总结后即可得到反向AD算法。

反向AD算法

通过扩展计算图的反向AD

我们可以通过拓展计算图来实现反向AD：

张量上的反向模式

对于高维情形，利用向量微积分即可，考虑下例：

前向计算为：

$\begin{aligned} Z&=X W \\ v&=f(Z) \end{aligned}$

对于反向模式，定义（伴随）：

$\bar{Z}=\left[\begin{array}{ccc} \frac{\partial y}{\partial z_{1,1}} & \ldots & \frac{\partial y}{\partial z_{1, n}} \\ \vdots & \ldots & \vdots \\ \frac{\partial y}{\partial z_{m, 1}} & \ldots & \frac{\partial y}{\partial z_{m, n}} \end{array}\right]$

那么：

$\overline{X_{i, k}}=\sum_j \frac{\partial z_{i, j}}{\partial X_{i, k}} \bar{Z}_{i, j}=W_{k, j} \bar{Z}_{i, j}$

即：

$\bar{X}=\bar{Z} W^T$

反向AD vs 反向传播

反向传播：

特点：

在同一个前向图中运行反向操作；
用于第一代深度学习框架（caffe、cuda-convnet）；

特点：

为伴随构造单独的图节点；
由现代深度学习框架使用；
反向模式AD的结果仍然是一个计算图；
我们可以通过组合更多操作进一步扩展该图，并在梯度上再次运行反向模式AD；
可以计算梯度的梯度；

在其他数据结构上的反向AD

要点：

通常在与前向值和伴随传播规则相同的数据类型中定义“伴随值”，然后之前的算法就可以起作用；
在我们的框架中不需要支持一般形式，但我们可能会支持“元组值”；