查看“︁自動微分”︁的源代码

在[[數學]]和[[計算機代數]]中，'''自動微分'''有時稱作'''演算式微分'''，是一種可以藉由電腦程式計算一個函數[[導數]]的方法。兩種傳統做微分的方法為：
* 對一個函數的表示式做符號上的微分，並且計算其在某一點上的值。
* 使用[[差分]]。

使用符號微分最主要的缺點是速度慢及將電腦程式轉換成表示式的困難。此外，很多函數在要計算更高階微分時會變得複雜。
使用差分的兩個重要的缺點是[[捨棄誤差]]及[[數值化]]過程和相消誤差。此兩者傳統方法在計算更高階微分時，都有複雜度及誤差增加的問題。自動微分則解決上述的問題。

自動微分使用這個事實：任何實作一個向量函數 '''y'''=F('''x''')的電腦程式，一般而言，可以被分解成由基本指定運算所成的序列，而其中每一個都可以藉由查表而輕易地微分。這些計算某一特定項的 "基本偏微分" 是依照微積分中的[[复合函数求导法则]]來合併成某個 F 的微分資訊（如[[梯度]]、[[切線]]、[[雅可比矩陣]]等）。這個過程會產生確實(數值上準確)的導數。因為只在最基礎的層面做符號轉換，自動微分避免了複雜的符號運算的問題。

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

自動微分的基礎是，根據[[复合函数求导法则]]來合併微分值。以<math>f(x)=g(h(x))</math>為例，根據[[复合函数求导法则]]，我們有：

:<math>\frac{df}{dx} = \frac{dg}{dh} \frac{dh}{dx}</math>

通常有兩個不同的模式：“前向積累”（或“前向模式”）和“反向積累”（或反向模式）。
前向積累由右到左地使用[[复合函数求导法则]]，即先計算 <math>dh/dx</math> ，然後才<math>dg/dh</math>。
反向積累則是由左到右。

===前向積累===

前向積累式的自動微分是最容易理解和實作的。
<math>f(x_1,x_2) = x_1 x_2 + \sin(x_1)</math>這個函數是可被電腦（或程式設計師）
解釋成一連串對變數<math>w_i</math>的運算。
前向積累式自動微分的工具則會增加相對應的作用於第二項上的運算。
{| class="wikitable"
|-
! 原本程式碼敘述
! 為導數而新增的敘述
|-
| <math>w_1 = x_1</math>
| <math>w'_1 = 1</math> (種子)
|-
| <math>w_2 = x_2</math>
| <math>w'_2 = 0</math> (種子)
|-
| <math>w_3 = w_1 w_2</math>
| <math>w'_3 = w'_1 w_2 + w_1 w'_2 = 1  x_2 + x_1  0 = x_2</math>
|-
| <math>w_4 = \sin(w_1)</math>
| <math>w'_4 = \cos(w_1)w'_1 = \cos(x_1)  1</math>
|-
| <math>w_5 = w_3 + w_4</math>
| <math>w'_5 = w'_3 + w'_4 = x_2 + \cos(x_1)</math>
|}

計算<math>f(x_1,x_2) = x_1 x_2 + \sin(x_1)</math>的導數需要初始化，
以區別是要對<math>x_1</math>或<math>x_2</math>來求導數。
上述表格則以<math>w'_1=1</math>和<math>w'_2=0</math>來初始化，
並且我們可以看到其結果<math>x_2 + \cos(x_1)</math>正是對<math>x_1</math>的導數。
注意，雖然表格列出了符號微分，
但以電腦的角度而言，電腦總是儲存數值。圖2則以圖形表明上述的敘述。

為了計算這個例子的導數，其分別為<math>\partial f/\partial x_1</math>和<math>\partial f / \partial x_2</math>，
需要計算兩次，一次是以<math>w'_1 = 1</math>和<math>w'_2 = 0</math>做初始值，
另一次則以<math>w'_1 = 0</math>和<math>w'_2 = 1</math>做為初始值。

前向積累的[[計算複雜性理論|計算複雜度]]則正比於原來程式的計算複雜度。

對於函數<math>f:\mathbb{R} \rightarrow \mathbb{R}^m</math>且 <math>m \gg 1</math>來說，
前向積累只要計算一次，優於需要計算 m 次的反向積累。

===反向積累===

== 前向式積累自動微分的由來與二元數 ==

前向式積累自動微分可藉由擴充[[實數]]中的[[代數]]並得到一個新的[[算術]]系統來達成。
每一個數都會新增另一數，用來表示一函數在這數上導數的數。
而每一個算術運算都被擴充於此新的代數。
這個擴充後的代數就是[[二元數]]的代數。


將每一個數<math>\,x</math>替換成數<math>x+x'\varepsilon</math>，其中<math>x'</math>是一個實數，但<math>\varepsilon</math>則只是一個據有<math>\varepsilon^2=0</math>這個特性的符號。
使用這特性，我們可以有運算
:<math>(x + x'\varepsilon) + (y + y'\varepsilon) = x + y + (x' + y')\varepsilon</math>
:<math>(x + x'\varepsilon) \cdot (y + y'\varepsilon) = xy + xy'\varepsilon + yx'\varepsilon + x'y'\varepsilon^2 = xy + (x y' + yx')\varepsilon</math>
減法和除法則類似。

現在，我們可以計算[[多項式]]。
如果<math>P(x) = p_0 + p_1 x + p_2x^2 + \cdots + p_n x^n</math>，則

{| class="wikitable",border=0
|-
|<math>P(x + x'\varepsilon) </math>
|<math>=\,</math>
|<math>p_0 + p_1(x + x'\varepsilon) + \cdots + p_n (x + x'\varepsilon)^n</math>
|-
| 
|<math>=\,</math>
|<math>p_0 + p_1 x + \cdots + p_n x^n</math>
|-
|
|
|  <math>\, {} + p_1x'\varepsilon + 2p_2xx'\varepsilon + \cdots + np_n x^{n-1} x'\varepsilon</math>
|-
|
|<math>=\,</math>
|<math>P(x) + P^{(1)}(x)x'\varepsilon</math>
|}

其中 <math>P^{(1)}</math> 表示 <math>P</math> 對第一個參數的導數。
而 <math>x'</math> 則稱作“種子”，可以任意選擇。

新的算術是由[[有序對]]、寫成<math>\langle x, x' \rangle</math>
及對第一項的運算和對第二項的第一階微分運算所組成。
將上述結果應用於多項式的[[解析函數]]上，
我們可以得到一系列關於基本算術和一些標準函數的新算術：
:<math>\langle u,u'\rangle +\langle v,v'\rangle = \langle u+v, u'+v' \rangle </math>
:<math>\langle u,u'\rangle -\langle v,v'\rangle = \langle u-v, u'-v' \rangle </math>
:<math>\langle u,u'\rangle *\langle v,v'\rangle = \langle u v, u'v+uv' \rangle </math>
:<math>\langle u,u'\rangle /\langle v,v'\rangle = \left\langle \frac{u}{v}, \frac{u'v-uv'}{v^2} \right\rangle \quad ( v\ne 0) </math>
:<math>\sin\langle u,u'\rangle = \langle \sin(u) , u' \cos(u) \rangle </math>
:<math>\cos\langle u,u'\rangle = \langle \cos(u) , -u' \sin(u) \rangle </math>
:<math>\exp\langle u,u'\rangle = \langle \exp u , u' \exp u \rangle </math>
:<math>\log\langle u,u'\rangle = \langle \log(u) , u'/u \rangle \quad (u>0) </math>
:<math>\langle u,u'\rangle^k = \langle u^k , k u^{k-1} u' \rangle \quad (u \ne 0) </math>
:<math>\left| \langle u,u'\rangle \right| = \langle \left| u \right| , u' \mbox{sign} u \rangle \quad (u \ne 0)</math>
並且，一般而言，對於一個函數 <math>g</math>，我們會有
:<math>g(\langle u,u' \rangle , \langle v,v' \rangle ) = \langle g(u,v) , g^{(1)}(u,v) u' + g^{(2)}(u,v) v' \rangle</math>
其中<math>g^{(1)}</math>和<math>g^{(2)}</math>分別是<math>g</math>對其第一項和第二項的導數。

對一個二元算術運算作用於混合的參數時（數對<math>\langle u, u' \rangle</math>和實數<math>c</math>），
實數會先被轉成<math>\langle c, 0 \rangle</math>。
函數<math>f : \mathbb{R}\rightarrow\mathbb{R}</math>在<math>x_0</math>上的導數
則為以上述算術計算<math>f(\langle x_0, 1 \rangle)</math>，其結果為<math>\langle f ( x_0 ) , f' ( x_0 ) \rangle </math>。

===向量參數和函數===

藉由採取[[方向導數]]的運算，
多變數函數也可以同單變數函數的效率和機制來處理。
亦即，函數<math>f:\mathbb{R}^n\rightarrow\mathbb{R}^m</math>在<math>x \in \mathbb{R}^n</math>這點，
和<math>x' \in \mathbb{R}^n</math>這個方向上的方向導數<math>y' \in \mathbb{R}^m</math>，
可以使用上述相同的算術來計算
<math>(\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)</math>
而求得。

===更高階微分===

以上的算術可以被一般化，以用於二階及三階導數。
然而，此算術的規則將會迅速變得複雜。
其複雜度將與最高階導數階數成平化。
取而代之的是使用限縮[[泰勒級數]]。
這是可行的，因為函數的泰勒級數中的通項為己知係數和函數導數的乘積。
使用自動微分來計算[[黑塞矩陣]]在某些最佳化已被證明是可行的。

== 實作 ==

前向式積累是由對程式的非標準化轉譯程序來實作。
即將實數替換成二元數，常數則換成有第二項為零係數的二元數。
而數值上基本運算則被換成二元數的運算。
非標準化轉譯程序一般使用兩者策略之一：''程式碼轉換''和''運算符重載''。

=== 程式碼轉換 ===
[[File:SourceTransformationAutomaticDifferentiation.png|thumb|right|300px|Figure 4: Example of how source code transformation could work]]

一個函數的程式碼會被自動產生的程式碼所替換，
新生成用來計算導數的程式碼則會插入原程式碼中。

程式碼轉換可實作在所有的程式語言上，且它對編譯器而言，是容易最佳化的。
然而，實作自動微分的工具則是比較困難的。

例子：
* ADIC<ref>[http://www-fp.mcs.anl.gov/adic/ ADIC] {{Wayback|url=http://www-fp.mcs.anl.gov/adic/ |date=20080917143429 }}</ref> (C/C++, 前向積累)
* ADIFOR<ref>[http://www-unix.mcs.anl.gov/autodiff/ADIFOR/ ADIFOR] {{Wayback|url=http://www-unix.mcs.anl.gov/autodiff/ADIFOR/ |date=20080702064329 }}</ref> (Fortran77)
* OpenAD<ref>[http://www-unix.mcs.anl.gov/~utke/OpenAD/ OpenAD] {{Wayback|url=http://www-unix.mcs.anl.gov/~utke/OpenAD/ |date=20150814154918 }}</ref> (Fortran77, Fortran95, C/C++)
* TAPENADE<ref>[http://tapenade.inria.fr:8080/tapenade/index.jsp TAPENADE] {{Wayback|url=http://tapenade.inria.fr:8080/tapenade/index.jsp |date=20210418013916 }}</ref> (Fortran77, Fortran95)

=== 運算符重載 ===

[[File:OperatorOverloadingAutomaticDifferentiation.png|thumb|right|300px|Figure 5: Example of how operator overloading could work]]

如果所使用的程式語言支持，[[運算符重載]]是個可行的方法。
實數的物件跟基本數學運算必須重載以滿足上述 augmented 算術。
這不須要改變要被微分的函數的程式碼。

運算符重載對前向積累是容易實作的，並且可能對反向積累亦如此。
然而，與前向積累相比，現有的編譯器在最佳化程式碼方面則是較為落後。

例子：
* ADC Version 4.0<ref>[http://www.vivlabs.com/subpage_adc_v4.php ADC Version 4.0] {{Wayback|url=http://www.vivlabs.com/subpage_adc_v4.php |date=20080509091543 }}</ref> (C/C++)
* ADF Version 4.0<ref>[http://www.vivlabs.com/subpage_adf_v4.php ADF Version 4.0] {{Wayback|url=http://www.vivlabs.com/subpage_adf_v4.php |date=20080509064752 }}</ref> (Fortran 77, Fortran 95)
* ADOL-C<ref>[https://web.archive.org/web/20090312035629/http://www.math.tu-dresden.de/~adol-c/ ADOL-C]</ref> (C/C++)
* FADBAD++<ref>[http://www.fadbad.com/ FADBAD++] {{Wayback|url=http://www.fadbad.com/ |date=20210228104144 }}</ref> (C/C++)
* CppAD<ref>[http://www.coin-or.org/CppAD CppAD] {{Wayback|url=http://www.coin-or.org/CppAD |date=20210303115817 }}</ref> (C/C++)
* MAD<ref>[http://matlabad.com/ MAD] {{Wayback|url=http://matlabad.com/ |date=20210224142418 }}</ref> (Matlab)
* Sacado (Trilinos<ref>[https://web.archive.org/web/20080514042153/http://trilinos.sandia.gov/ Trilinos]</ref>的一部分) (C++, forward/reverse)

== 參考文獻 ==
{{reflist|2}}
* {{cite book
  | last = Rall
  | first = Louis B.
  | title = Automatic Differentiation: Techniques and Applications
  | publisher = [[Springer Science+Business Media|Springer]]
  | series = Lecture Notes in Computer Science
  | volume = 120
  | year = 1981
  | isbn = 978-3-540-10861-0
}}
* {{cite book
  | last = Griewank
  | first = Andreas
  | title = Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation
  | publisher = [[Society for Industrial and Applied Mathematics|SIAM]]
  | series = Frontiers in Applied Mathematics
  | volume = 19
  | year = 2000
  | isbn = 0-89871-451-6
}}<div class="references-small"><references /></div>

==外部連結==

* [http://www.autodiff.org/ www.autodiff.org] {{Wayback|url=http://www.autodiff.org/ |date=20210414194835 }}, An "entry site to everything you want to know about automatic differentiation"
* [https://web.archive.org/web/20070928073555/http://karminghenry.sinaman.com/adindex.html Automatic Differentiation of Parallel OpenMP Programs]
* [https://web.archive.org/web/20050315101043/http://homepage.mac.com/sigfpe/paper.pdf Automatic Differentiation, C++ Templates and Photogrammetry]
* [http://www.vivlabs.com/subpage_ad.php Automatic Differentiation, Operator Overloading Approach] {{Wayback|url=http://www.vivlabs.com/subpage_ad.php |date=20070927120356 }}
* [https://web.archive.org/web/20090930225144/http://apmonitor.ath.cx/ Compute analytic derivatives through a web-based interface] Automatic differentiation of nonlinear models
* [http://tapenade.inria.fr:8080/tapenade/index.jsp Compute analytic derivatives of any Fortran77 or Fortran95 through a web-based interface] {{Wayback|url=http://tapenade.inria.fr:8080/tapenade/index.jsp |date=20210418013916 }} Automatic Differentiation of Fortran programs
{{Differentiable computing}}
[[Category:微分学]]
[[Category:计算机代数]]