自动求导

前言

求导概念：数值求导，符号求导，自动求导

模式：正向传播，反向求导。雅可比原理

实现：表达式计算图，操作符重载，源码转换AST

求导

符号求导

通过求导法则将原式展开，转换为导数表达式

优势：精确数值结果

劣势：表达式膨胀

数值求导

利用有限差分与极限进行近似

优势：实现简单

劣势：由于浮点数范围导致计算不精确，计算复杂度高，对近似所用的极小数要求高

会引起截断误差与舍入误差

自动求导

所有的数值计算都由有限的基本运算组成，基本运算的导数表达式都是已知的，通过链式求导法则将数值计算各部分组合成整体。

优势：数值精度高，无表达式膨胀。

劣势：需要存储中间结果，内存占用大

要实现自动求导，需要表达式追踪，用于追踪记录计算过程的中间变量。

如，对于下列公式：

有：

正向传播

以下为正向地计算函数值的过程，按照计算法则进行计算。

根据这个过程，我们可以将原函数的计算过程转换为一个有向无环图，其中每一个节点都是一个中间结果，每一个（组）边都是一个运算。

要通过链式法则将 f 对 x1 的导数展开，需要计算 x1 到 f 的所有路径，并将其相加。

第一条路径为
$$x_1\to v_{-1}\to v_1\to v_4\to v_5\to f$$
第二条路径为
$$x_1\to v_{-1}\to v_2\to v_4\to v_5\to f$$
现在计算第一条路径
$$\begin{array}{rl}\frac{\partial v_{-1}}{\partial x_1}& =1\\ \frac{\partial v_1}{\partial v_{-1}}& =\frac{1}{v_{-1}}=\frac{1}{x_1}\\ \frac{\partial v_4}{\partial v_1}& =1\\ \frac{\partial v_5}{\partial v_4}& =1\\ \frac{\partial f}{\partial v_5}& =1\\ \therefore {\frac{\partial f}{\partial x_1}}_1& =1\ast 1\ast 1\ast \frac{1}{x_1}\ast 1=\frac{1}{x_1}\end{array}$$
第二条路径
$$\begin{array}{rl}\frac{\partial v_{-1}}{\partial x_1}& =1\\ \frac{\partial v_2}{\partial v_{-1}}& =v_0=x_2\\ \frac{\partial v_4}{\partial v_2}& =1\\ \frac{\partial v_5}{\partial v_4}& =1\\ \frac{\partial f}{\partial v_5}& =1\\ \therefore {\frac{\partial f}{\partial x_1}}_2& =1\ast 1\ast 1\ast x_2\ast 1=x_2\end{array}$$
最后的结果等于两条路径相加
$$\frac{\partial f}{\partial x_1}=\frac{1}{x_1}+x_2$$
其中可以观察到两条路径中仅有$v_{-1}\to v_5$之间的内容不同，故可以简化计算为
$$\frac{\partial f}{\partial x_1}=1\ast 1\ast 1\ast (\frac{1}{x_1}+x_2)\ast 1$$
这样就完成了对$x_1$的一次正向传播，对$x_2$的过程与之相似。

总结：正向传播通过对每一个输入变量按照计算图顺序进行跟踪，计算图中每个节点对前一个节点的导数，以计算对每个变量的导数。

反向传播

计算过程如下：

1. 初始化
$$\frac{\partial f}{\partial f}=1$$

2. 梯度反向传播
$$\begin{array}{rl}& \text{传播到 }{v}_5:\frac{\partial f}{\partial v_5}=\frac{\partial v_5}{\partial v_5}=1\\ & \text{从 }{v}_5\text{ 传播到 }{v}_4:\frac{\partial f}{\partial v_4}=\frac{\partial v_5}{\partial v_4}\cdot \frac{\partial f}{\partial v_5}=1\\ & \text{从 }{v}_5\text{ 传播到 }{v}_3:\frac{\partial f}{\partial v_3}=\frac{\partial v_5}{\partial v_3}\cdot \frac{\partial f}{\partial v_5}=-1\\ & \text{从 }{v}_4\text{ 传播到 }{v}_1:\frac{\partial f}{\partial v_1}=\frac{\partial v_4}{\partial v_1}\cdot \frac{\partial f}{\partial v_4}=1\\ & \text{从 }{v}_4\text{ 传播到 }{v}_2:\frac{\partial f}{\partial v_2}=\frac{\partial v_4}{\partial v_2}\cdot \frac{\partial f}{\partial v_4}=1\end{array}$$

3. 梯度累加 (针对输入变量)

关于 $v_{-1}$ (即 $x_1$) 的梯度：
$$\begin{array}{rl}& \text{来自 }{v}_1:\frac{\partial v_1}{\partial v_{-1}}\cdot \frac{\partial f}{\partial v_1}=\frac{1}{x_1}\cdot 1=\frac{1}{x_1}\\ & \text{来自 }{v}_2:\frac{\partial v_2}{\partial v_{-1}}\cdot \frac{\partial f}{\partial v_2}=v_0\cdot 1=x_2\\ & \therefore \frac{\partial f}{\partial v_{-1}}=\frac{1}{x_1}+x_2\end{array}$$

关于 $v_0$ (即 $x_2$) 的梯度：
$$\begin{array}{rl}& \text{来自 }{v}_2:\frac{\partial v_2}{\partial v_0}\cdot \frac{\partial f}{\partial v_2}=v_{-1}\cdot 1=x_1\\ & \text{来自 }{v}_3:\frac{\partial v_3}{\partial v_0}\cdot \frac{\partial f}{\partial v_3}=\cos (v_0)\cdot (-1)=-\cos (x_2)\\ & \therefore \frac{\partial f}{\partial v_0}=x_1-\cos (x_2)\end{array}$$

4. 最终梯度
$$\frac{\partial f}{\partial x_1}=\frac{1}{x_1}+x_2,\frac{\partial f}{\partial x_2}=x_1-\cos (x_2)$$
这样就完成了一次反向传播。

总结：反向传播通过从输出开始需要计算结果对图中每个节点的导数，以计算对每个变量的导数。

雅可比矩阵

在反向传播时，对于函数
$$\vec{y}=f(\vec{x})$$
其中
$$f:{\mathbf{R}}^n\to {\mathbf{R}}^m$$
那么向量$y$关于向量$x$的梯度可以表示为雅可比矩阵：
$${\mathbf{J}}_f=\left[\begin{array}{lll}\frac{\partial \mathbf{y}}{\partial x_1}& \cdots & \frac{\partial \mathbf{y}}{\partial x_n}\end{array}\right]=\left[\begin{array}{ccc}\frac{\partial y_1}{\partial x_1}& \cdots & \frac{\partial y_1}{\partial x_n}\\ ⋮& \ddots & ⋮\\ \frac{\partial y_m}{\partial x_1}& \cdots & \frac{\partial y_m}{\partial x_n}\end{array}\right]$$
每一行为一个输出值$y$，每一列为一个输入$x$。行数为$m$，列数为$n$

将向量$v$设置为关于以下函数的梯度
$$\begin{gathered} l=g(\vec{y}) \\ \vec{\mathbf{v}}={\left[\begin{array}{c}\frac{\partial l}{\partial y_1}\cdots \frac{\partial l}{\partial y_m}\end{array}\right]}^T \end{gathered}$$
那雅可比矩阵与向量$v$的乘积就是函数l中关于x的梯度
$${\mathbf{J}}^T\cdot \vec{\mathbf{v}}={\left[\begin{array}{ccc}\frac{\partial y_1}{\partial x_1}& \cdots & \frac{\partial y_1}{\partial x_n}\\ ⋮& \ddots & ⋮\\ \frac{\partial y_m}{\partial x_1}& \cdots & \frac{\partial y_m}{\partial x_n}\end{array}\right]}^T\cdot \left[\begin{array}{c}\frac{dl}{d{y}_1}\\ ⋮\\ \frac{dl}{d{y}_m}\end{array}\right]=\left[\begin{array}{c}\frac{\partial y_1}{\partial x_1}\cdot \frac{dl}{d{y}_1}+\cdots +\frac{\partial y_m}{\partial x_1}\cdot \frac{dl}{d{y}_m}\\ ⋮\\ \frac{\partial y_1}{\partial x_n}\cdot \frac{dl}{d{y}_1}+\cdots +\frac{\partial y_m}{\partial x_n}\cdot \frac{dl}{d{y}_m}\end{array}\right]$$
最终得到的结果为
$$\left[\begin{array}{c}\frac{\partial l}{\partial x_1}\\ ⋮\\ \frac{\partial l}{\partial x_n}\end{array}\right]$$
其中每个元素代表损失函数对每个输入变量的总梯度。

正向传播时对雅可比矩阵再转置。

综上，当$m>n$，即输出比输入多时，适合用正向传播。

当$m<n$，即输入比输出多时，适合用反向传播。

而在神经网络中，输入数据集规模极大，故更常用反向传播。

自动求导的实现方法

表达式法

封装基本的表达式及其求导表达式作为库函数；

运行时记录基本表达式和相应的组合关系；

链式法则对基本表达式的求导结果进行组合。

例如：

实现以下表达式计算
$$f(x,y,z)=\frac{(x+y)}{z}$$
手动将表达式函数分解为库函数中的基本表达式组合
$$\begin{gathered} a=x+y \\ b=\frac{x}{y} \end{gathered}$$
利用库函数中定义对应表达式的数学求导法则和链式法则
$$\begin{gathered} \partial a=\partial x+\partial y \\ \partial b=\frac{\partial x}{y}-\partial y\ast \frac{x}{y^2} \end{gathered}$$
优势：实现简单，可用任意编程语言

劣势：使用库函数进行编程，无法使用原语言运算表达式

操作符重载法

利用语言多态特性，使用操作符重载基本运算表达式；

运行时将表达式和相应的组合关系记录到$tape$中；

遍历$tape$，对其中的基本运算操作进行求导；

链式法则对基本表达式的求导结果进行组合。

优势：实现简单，语言具有多态性，易用性高

劣势：显式的构造$tape$数据结构和对$tape$进行读写；额外数据结构和操作的引入，不利于高阶求导；if、while等控制流表达式难以通过操作符重载。

源码转换法

分析获得语言程序的AST表达式；

基于AST完成基本表达式的分解和求导；

遍历AST得到基本表达式的依赖关系；

链式法则对基本表达式的求导结果进行组合。

优势：丰富数据类型与语言原生操作；无额外数据结构，易于实现高阶求导；求导结果以代码形式存在，方便分布式系统计算。

劣势：代码理解难，复杂度高