自动微分

在数学和计算机代数中，自动微分有时称作演算式微分，是一种可以借由计算机程序计算一个函数导数的方法。两种传统做微分的方法为：

• 对一个函数的表示式做符号上的微分，并且计算其在某一点上的值。
• 使用差分。

使用符号微分最主要的缺点是速度慢及将计算机程序转换成表示式的困难。此外，很多函数在要计算更高阶微分时会变得复杂。 使用差分的两个重要的缺点是舍弃误差及数值化过程和相消误差。此两者传统方法在计算更高阶微分时，都有复杂度及误差增加的问题。自动微分则解决上述的问题。

自动微分使用这个事实：任何实作一个向量函数 y=F(x)的计算机程序，一般而言，可以被分解成由基本指定运算所成的序列，而其中每一个都可以借由查表而轻易地微分。这些计算某一特定项的 "基本偏微分" 是依照微积分中的复合函数求导法则来合并成某个 F 的微分资讯（如梯度、切线、雅可比矩阵等）。这个过程会产生确实(数值上准确)的导数。因为只在最基础的层面做符号转换，自动微分避免了复杂的符号运算的问题。

复合函数求导法则，前向和反向积累

自动微分的基础是，根据复合函数求导法则来合并微分值。以$f(x)=g(h(x))$为例，根据复合函数求导法则，我们有：

${\frac {df}{dx}}={\frac {dg}{dh}}{\frac {dh}{dx}}$

通常有两个不同的模式：“前向积累”（或“前向模式”）和“反向积累”（或反向模式）。 前向积累由右到左地使用复合函数求导法则，即先计算 $dh/dx$ ，然后才$dg/dh$。 反向积累则是由左到右。

前向积累

前向积累式的自动微分是最容易理解和实作的。 $f(x_{1},x_{2})=x_{1}x_{2}+\sin(x_{1})$这个函数是可被电脑（或程序员） 解释成一连串对变数$w_{i}$的运算。 前向积累式自动微分的工具则会增加相对应的作用于第二项上的运算。

原本程式码叙述	为导数而新增的叙述
$w_{1}=x_{1}$	$w'_{1}=1$ (种子)
$w_{2}=x_{2}$	$w'_{2}=0$ (种子)
$w_{3}=w_{1}w_{2}$	$w'_{3}=w'_{1}w_{2}+w_{1}w'_{2}=1x_{2}+x_{1}0=x_{2}$
$w_{4}=\sin(w_{1})$	$w'_{4}=\cos(w_{1})w'_{1}=\cos(x_{1})1$
$w_{5}=w_{3}+w_{4}$	$w'_{5}=w'_{3}+w'_{4}=x_{2}+\cos(x_{1})$

计算$f(x_{1},x_{2})=x_{1}x_{2}+\sin(x_{1})$的导数需要初始化， 以区别是要对$x_{1}$或$x_{2}$来求导数。 上述表格则以$w'_{1}=1$和$w'_{2}=0$来初始化， 并且我们可以看到其结果$x_{2}+\cos(x_{1})$正是对$x_{1}$的导数。 注意，虽然表格列出了符号微分， 但以电脑的角度而言，电脑总是储存数值。图2则以图形表明上述的叙述。

为了计算这个例子的导数，其分别为$\partial f/\partial x_{1}$和$\partial f/\partial x_{2}$， 需要计算两次，一次是以$w'_{1}=1$和$w'_{2}=0$做初始值， 另一次则以$w'_{1}=0$和$w'_{2}=1$做为初始值。

前向积累的计算复杂度则正比于原来程式的计算复杂度。

对于函数$f:\mathbb {R} \rightarrow \mathbb {R} ^{m}$且 $m\gg 1$来说， 前向积累只要计算一次，优于需要计算 m 次的反向积累。

前向式积累自动微分的由来与二元数

前向式积累自动微分可借由扩充实数中的代数并得到一个新的算术系统来达成。 每一个数都会新增另一数，用来表示一函数在这数上导数的数。 而每一个算术运算都被扩充于此新的代数。 这个扩充后的代数就是二元数的代数。

将每一个数$\,x$替换成数$x+x'\varepsilon$，其中$x'$是一个实数，但$\varepsilon$则只是一个据有$\varepsilon ^{2}=0$这个特性的符号。 使用这特性，我们可以有运算

$(x+x'\varepsilon )+(y+y'\varepsilon )=x+y+(x'+y')\varepsilon$

$(x+x'\varepsilon )\cdot (y+y'\varepsilon )=xy+xy'\varepsilon +yx'\varepsilon +x'y'\varepsilon ^{2}=xy+(xy'+yx')\varepsilon$

减法和除法则类似。

现在，我们可以计算多项式。 如果$P(x)=p_{0}+p_{1}x+p_{2}x^{2}+\cdots +p_{n}x^{n}$，则

$P(x+x'\varepsilon )$	$=\,$	$p_{0}+p_{1}(x+x'\varepsilon )+\cdots +p_{n}(x+x'\varepsilon )^{n}$
	$=\,$	$p_{0}+p_{1}x+\cdots +p_{n}x^{n}$
		$\,{}+p_{1}x'\varepsilon +2p_{2}xx'\varepsilon +\cdots +np_{n}x^{n-1}x'\varepsilon$
	$=\,$	$P(x)+P^{(1)}(x)x'\varepsilon$

其中 $P^{(1)}$ 表示 $P$ 对第一个参数的导数。 而 $x'$ 则称作“种子”，可以任意选择。

新的算术是由有序对、写成$\langle x,x'\rangle$ 及对第一项的运算和对第二项的第一阶微分运算所组成。 将上述结果应用于多项式的解析函数上， 我们可以得到一系列关于基本算术和一些标准函数的新算术：

$\langle u,u'\rangle +\langle v,v'\rangle =\langle u+v,u'+v'\rangle$

$\langle u,u'\rangle -\langle v,v'\rangle =\langle u-v,u'-v'\rangle$

$\langle u,u'\rangle *\langle v,v'\rangle =\langle uv,u'v+uv'\rangle$

$\langle u,u'\rangle /\langle v,v'\rangle =\left\langle {\frac {u}{v}},{\frac {u'v-uv'}{v^{2}}}\right\rangle \quad (v\neq 0)$

$\sin \langle u,u'\rangle =\langle \sin(u),u'\cos(u)\rangle$

$\cos \langle u,u'\rangle =\langle \cos(u),-u'\sin(u)\rangle$

$\exp \langle u,u'\rangle =\langle \exp u,u'\exp u\rangle$

$\log \langle u,u'\rangle =\langle \log(u),u'/u\rangle \quad (u>0)$

$\langle u,u'\rangle ^{k}=\langle u^{k},ku^{k-1}u'\rangle \quad (u\neq 0)$

$\left|\langle u,u'\rangle \right|=\langle \left|u\right|,u'{\mbox{sign}}u\rangle \quad (u\neq 0)$

并且，一般而言，对于一个函数 $g$，我们会有

$g(\langle u,u'\rangle ,\langle v,v'\rangle )=\langle g(u,v),g^{(1)}(u,v)u'+g^{(2)}(u,v)v'\rangle$

其中$g^{(1)}$和$g^{(2)}$分别是$g$对其第一项和第二项的导数。

对一个二元算术运算作用于混合的参数时（数对$\langle u,u'\rangle$和实数$c$）， 实数会先被转成$\langle c,0\rangle$。 函数$f:\mathbb {R} \rightarrow \mathbb {R}$在$x_{0}$上的导数 则为以上述算术计算$f(\langle x_{0},1\rangle )$，其结果为$\langle f(x_{0}),f'(x_{0})\rangle$。

向量参数和函数

借由采取方向导数的运算， 多变数函数也可以同单变数函数的效率和机制来处理。 亦即，函数$f:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{m}$在$x\in \mathbb {R} ^{n}$这点， 和$x'\in \mathbb {R} ^{n}$这个方向上的方向导数$y'\in \mathbb {R} ^{m}$， 可以使用上述相同的算术来计算 $(\langle y_{1},y'_{1}\rangle ,\ldots ,\langle y_{m},y'_{m}\rangle )=f(\langle x_{1},x'_{1}\rangle ,\ldots ,\langle x_{n},x'_{n}\rangle )$ 而求得。

更高阶微分

以上的算术可以被一般化，以用于二阶及三阶导数。 然而，此算术的规则将会迅速变得复杂。 其复杂度将与最高阶导数阶数成平化。 取而代之的是使用限缩泰勒级数。 这是可行的，因为函数的泰勒级数中的通项为己知系数和函数导数的乘积。 使用自动微分来计算黑塞矩阵在某些最佳化已被证明是可行的。

实作

前向式积累是由对程式的非标准化转译程序来实作。 即将实数替换成二元数，常数则换成有第二项为零系数的二元数。 而数值上基本运算则被换成二元数的运算。 非标准化转译程序一般使用两者策略之一：程式码转换和运算符重载。

程式码转换

Figure 4: Example of how source code transformation could work

一个函数的程式码会被自动产生的程式码所替换， 新生成用来计算导数的程式码则会插入原程式码中。

程式码转换可实作在所有的编程语言上，且它对编译器而言，是容易最佳化的。 然而，实作自动微分的工具则是比较困难的。

例子：

• ADIC (C/C++, 前向积累)
• ADIFOR (Fortran77)
• OpenAD (Fortran77, Fortran95, C/C++)
• TAPENADE (Fortran77, Fortran95)

运算符重载

Figure 5: Example of how operator overloading could work

如果所使用的编程语言支持，运算符重载是个可行的方法。 实数的物件跟基本数学运算必须重载以满足上述 augmented 算术。 这不须要改变要被微分的函数的程式码。

运算符重载对前向积累是容易实作的，并且可能对反向积累亦如此。 然而，与前向积累相比，现有的编译器在最佳化程式码方面则是较为落后。

例子：

• ADC Version 4.0 (C/C++)
• ADF Version 4.0 (Fortran 77, Fortran 95)
• ADOL-C (C/C++)
• FADBAD++ (C/C++)
• CppAD (C/C++)
• MAD (Matlab)
• Sacado (Trilinos的一部分) (C++, forward/reverse)

参考文献

• Rall, Louis B. Automatic Differentiation: Techniques and Applications. Lecture Notes in Computer Science 120. Springer. 1981. ISBN 978-3-540-10861-0. 
• Griewank, Andreas. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. Frontiers in Applied Mathematics 19. SIAM. 2000. ISBN 0-89871-451-6. 

外部链接

• www.autodiff.org （页面存档备份，存于互联网档案馆）, An "entry site to everything you want to know about automatic differentiation"
• Automatic Differentiation of Parallel OpenMP Programs
• Automatic Differentiation, C++ Templates and Photogrammetry
• Automatic Differentiation, Operator Overloading Approach （页面存档备份，存于互联网档案馆）
• Compute analytic derivatives through a web-based interface Automatic differentiation of nonlinear models
• Compute analytic derivatives of any Fortran77 or Fortran95 through a web-based interface （页面存档备份，存于互联网档案馆） Automatic Differentiation of Fortran programs