自動微分原理
自動微分原理
自動微分（Automatic Differentiation，AD）是一種對電腦程式進行高效準確求導的技術，一直被廣泛應用於計算流體力學、大氣科學、工業設計模擬優化等領域。而近年來，機器學習技術的興起也驅動著對自動微分技術的研究進入一個新的階段。隨著自動微分和其他微分技術研究的深入，其與程式語言、計算框架、編譯器等領域的聯繫愈發緊密，從而衍生擴展出更通用的可微編程概念。
本章將從常見的微分方法開始介紹，然後深入自動微分基本概念。
常見電腦求導方法
對電腦程式求導的方法可以歸納為以下四種：
- 手動求解法(Manual Differentiation) ：完全手動完成，手工求導並編寫對應的結果程式，依據鏈式法則解出梯度公式，帶入數值，得到梯度。
- 數值微分法(Numerical Differentiation)：利用導數的原始定義，通過有限差分近似方法完成求導，直接求解微分值。
- 符號微分法(Symbolic Differentiation)：基於數學規則和程式表達式變換完成求導。利用求導規則對表達式進行自動計算，其計算結果是導函數的表達式而非具體的數值。即，先求解析解，然後轉換為程式，再通過程式計算出函數的梯度。
- 自動微分法(Automatic Differentiation)：介於數值微分和符號微分之間的方法，採用類似有向圖的計算來求解微分值，介於數值微分和符號微分之間的一種求導方法，也是本文介紹的重點。
手動微分
手動微分就是對每一個目標函數都需要利用求導公式手動寫出求導公式，然後依照公式編寫程式碼，帶入數值，求出最終梯度。
這種方法準確有效，但是不適合工程實現，因為通用性和靈活性很差，每一次我們修改演算法模型，都要修改對應的梯度求解演算法。如果模型複雜或者項目頻繁反覆迭代，那麼工作量將會是巨大的。
數值微分
數值微分方式應該是最直接而且簡單的一種自動求導方式，使用差分近似方法完成，其本質是根據導數的定義推導而來。
當 $h$ 取很小的數值，比如 0.000001 時，導數是可以利用差分來近似計算出來的。只需要給出函數值以及自變數的差值，數值微分演算法就可計算出導數值。單側差分公式根據導數的定義直接近似計算某一點處的導數值。
觀察導數的定義容易想到，當 $h$ 充分小時，可以用差商 $\frac{f(x+h)-f(x)}{h}$ 近似導數結果。而近似的一部分誤差（截斷誤差，Truncation Error）可以由泰勒公式中的二階及二階後的所有餘項給出：
因此數值微分中常用的三種計算方式及其對應的截斷誤差可以歸納為三種。
- 向前差商（Forward Difference）：
其中Forward Difference的階段誤差為$O(h)$。
- 向後差商（Reverse Difference）：
其中Reverse Difference的階段誤差為$O(h)$。
- 中心差商（Center Difference）
其中Center Difference的階段誤差為 $O(h^2)$。
可以看出來，數值微分中的截斷誤差與步長 $h$ 有關，$h$ 越小則截斷誤差越小，近似程式越高。
但實際情況數值微分的精確度並不會隨著 $h$ 的減小而無限減小，因為電腦系統中對於浮點數的運算由於其表達方式存在另外一種誤差（舍入誤差，Round-off Error），而舍入誤差則會隨著 $h$ 變小而逐漸增大。因此在截斷誤差和舍入誤差的共同作用下，數值微分的精度將會形成一個變化的函數並在某一個 $h$值處達到最小值。
為了緩解截斷錯誤，提出了中心微分近似（Center Difference Approximation），這方法仍然無法解決舍入誤差，只是減少誤差，但是它比單側差分公式有更小的誤差和更好的穩定性：
數值微分的優點是：
- 具有計算適用性，對大部分表達式適用
- 對用於顯示地隱藏了求導過程
- 簡單容易實現
數值微分的缺點是：
- 計算量大，求解速度最慢，因為每計算一個參數的導數，都需要重新計算。
- 引入誤差，因為是數值逼近，所有會不可靠，不穩定的情況，無法獲得一個相對準確的導數值。如果 h 選取不當，可能會得到與符號相反的結果，導致誤差增大。尤其是兩個嚴重問題：
- 截斷錯誤（Truncation error）：在數值計算中 h 無法真正取零導致的近似誤差。
- 舍入誤差（Round-off Error）：在計算過程中出現的對小數位數的不斷舍入會導致求導過程中的誤差不斷累積。
符號微分
符號微分（Symbolic Differentiation）屬符號計算的範疇，利用求導規則對表達式進行自動計算，其計算結果是導函數的表達式。符號計算用於求解數學中的公式解，得到的是解的表達式而非具體的數值。
符號微分適合符號表達式的自動求導，符號微分的原理是用下面的簡單求導規則，對電腦程式中的表達式進行遞歸變換來完成求導替代手動微分：
另外有：
由於變換過程中並不涉及計算且是嚴格等價，因此其可以大大減小微分結果的誤差（僅存在變換完成後計算過程中的舍入誤差）。除此之外，符號微分的計算方式使其還能用於類似極值 $\frac{\delta}{\delta x}f(x)=0$ 的數學問題求解。
從某種角度看，這種遞歸思想和嚴格的程式變換讓符號微分看上去是一種「完美」的計算過程。
符號微分利用代數軟體，實現微分的一些公式，然後根據基本函數的求導公式以及四則運算、複合函數的求導法則，將公式的計算過程轉化成微分過程，這樣就可以對用戶提供的具有closed form的數學表達式進行”自動微分”求解。就是先求解析解，然後轉換為程式，再通過程式計算出函數的梯度。
符號微分計算出的表達式需要用字元串或其他數據結構存儲，如表達式樹。因為符號微分的這些優點，其也在包括 Mathematica、Maple、matlab、Maxima 等現代代數系統工具軟體中使用。
但符號微分的最大弊病在於其對表達式的嚴格展開和變換也導致了所謂的表達式膨脹（expression swell）問題。以遞歸表達式為例：
可以看到在不同的迭代中其符號微分的結果相比人工簡化後的結果複雜很多，且隨著迭代次數而增大。
數值微分的優點是：
- 精度高，可適用於更複雜的數學問題求解等場景
- 簡單容易實現
數值微分的缺點是：
- 表達式必須是閉包（closed form），也就是必須能寫成完整數學表達式的，不能有程式語言中的循環結構，條件結構等，這樣才能將整個問題轉換為一個純數學符號問題
- 表達式複雜時候，求導結果存在表達式膨脹問題
自動微分
其實，對於機器學習中的應用，不需要得到導數的表達式，而只需計算函數在某一點處的導數值。
基本原理
自動微分是介於數值微分和符號微分之間的方法，採用類似有向圖的計算來求解微分值。
- 數值微分：一開始就直接代入數值近似求解
- 符號微分：直接對代數表達式求解析解，最後才代入數值進行計算
- 自動微分：首先對基本運算元（函數）應用符號微分方法，其次帶入數值進行計算，保留中間結果，最後通過鏈式求導法將中間結果應用於整個函數，這樣可以做到完全向用戶隱藏微分求解過程，也可以靈活於程式語言的循環結構、條件結構等結合起來
關於解析解我們還要做一些說明。幾乎所有機器學習演算法在訓練或預測時都可以歸結為求解最優化問題，如果目標函數可導，則問題就變為求訓練函數的駐點。但是通常情況下我們無法得到駐點的解析解，因此只能採用數值優化演算法，如梯度下降法，牛頓法，擬牛頓法等等。這些數值優化演算法都依賴於函數的一階導數值或二階導數值（包括梯度與Hessian矩陣）。因此需要解決如何求一個複雜函數的導數問題，自動微分技術是解決此問題的一種通用方法。
由於自動微分法只對基本函數或常數運用符號微分法則，所以它可以靈活結合程式語言的循環結構，條件結構等。使用自動微分和不使用自動微分對程式碼總體改動非常小，由於它實際是一種圖計算，可以對其做很多優化，所以該方法在現代深度學習系統中得到廣泛應用。
數學基礎
在計算鏈式法則之前，我們先回顧一下複合函數。複合函數在本質上就是有關函數的函數（function of functions）。它將一個函數的返回值作為參數傳遞給另一個函數，並且將另一個函數的返回值作為參數再傳遞給下一個函數，也就是 函數套函數，把幾個簡單的函數複合為一個較為複雜的函數。
鏈式法則是微積分中的求導法則，用於求一個複合函數的導數，是在微積分的求導運算中一種常用的方法。複合函數的導數將是構成複合這有限個函數在相應點的 導數的乘積，就像鎖鏈一樣一環套一環，故稱鏈式法則。
自動微分的思想則是將電腦程式中的運算操作分解為一個有限的基本操作集合，且集合中基本操作的求導規則均為已知在完成每一個基本操作的求導後，使用鏈式法則將結果組合得到整體程式的求導結果。
比如求導：
鏈式求導，令：
有：
自動微分
自動微分的精髓在於它發現了微分計算的本質：微分計算就是一系列有限的可微運算元的組合。
自動微分法被認為是對電腦程式進行非標準的解釋。自動微分基於一個事實，即每一個電腦程式，不論它有多麼複雜，都是在執行加減乘除這一系列基本算數運算，以及指數、對數、三角函數這類初等函數運算。於是自動微分先將符號微分法應用於最基本的運算元，比如常數，冪函數，指數函數，對數函數，三角函數等，然後代入數值，保留中間結果，最後再通過鏈式求導法則應用於整個函數。
通過將鏈式求導法則應用到這些運算上，我們能以任意精度自動地計算導數，而且最多只比原始程式多一個常數級的運算。
我們以如下為例，這是原始公式：
自動微分以鏈式法則為基礎，把公式中一些部分整理出來成為一些新變數，然後用這些新變數整體替換這個公式，於是得到：
然後把這些新變數作為節點，依據運算邏輯把公式整理出一張有向無環圖（DAG）。即，原始函數建立計算圖，數據正向傳播，計算出中間節點 xi，並記錄計算圖中的節點依賴關係。
因此，自動微分可以被認為是將一個複雜的數學運算過程分解為一系列簡單的基本運算， 其中每一項基本運算都可以通過查表得出來。
因此自動微分的優缺點可以簡單總結如下：
- 優點：精度高，無表達式膨脹問題
- 缺點：需要存儲一些中間求導結果，記憶體佔用會增加
參考
[1] Automatic Differentiation in Machine Learning: a Survey: //arxiv.org/abs/1502.05767
[2] Rirchard L. Burden and J. Douglas Faires. Numerical Analysis. Brooks/Cole, 2001.
[3] Max E. Jerrell. Automatic differentiation and interval arithmetic for estimation of disequilibrium models. Computational Economics, 10(3):295–316, 1997.
[4] Johannes Grabmeier and Erich Kaltofen. Computer Algebra Handbook: Foundations, Applications, Systems. Springer, 2003.
[5] G. W. Leibniz. Machina arithmetica in qua non additio tantum et subtractio sed et multiplicatio nullo, diviso vero paene nullo animi labore peragantur. Hannover, 1685.
[6] George F. Corliss. Application of differentiation arithmetic, volume 19 of Perspectives in Computing, pages 127–48. Academic Press, Boston, 1988.
[7] Arun Verma. An introduction to automatic differentiation. Current Science, 78(7):804–7, 2000.
[8] Andreas Griewank and Andrea Walther. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. Society for Industrial and Applied Mathematics, Philadelphia, 2008. doi: 10.1137/1.9780898717761.
[9] John F. Nolan. Analytical differentiation on a digital computer. Master』s thesis, Massachusetts Institute of Technology, 1953.
[10] L. M. Beda, L. N. Korolev, N. V. Sukkikh, and T. S. Frolova. Programs for automatic differentiation for the machine BESM (in Russian). Technical report, Institute for Precise Mechanics and Computation Techniques, Academy of Science, Moscow, USSR, 1959.
[11] Robert E. Wengert. A simple automatic derivative evaluation program. Communications of the ACM, 7:463–4, 1964.
[12] Andreas Griewank. On automatic differentiation. pages 83–108, 1989.
[13] Hascoet, Laurent, and Valérie Pascual. “The Tapenade automatic differentiation tool: principles, model, and specification.” ACM Transactions on Mathematical Software (TOMS) 39.3 (2013): 1-43.
[14] 知乎專欄：自動微分（Automatic Differentiation）: //zhuanlan.zhihu.com/p/61103504
[15] 知乎專欄：數值計算方法 第六章 數值積分和數值微分: //zhuanlan.zhihu.com/p/14
[16] 知乎專欄：技術分享 | 從自動微分到可微程式語言設計 //zhuanlan.zhihu.com/p/393160344
[17] 部落格園：深度學習利器之自動微分 //www.cnblogs.com/rossiXYZ/p/
