AI 從頭學（一０）：Automatic Differentiation

AI 從頭學（一０）：Automatic Differentiation

2017/02/15

前言：

本篇不是要教你 Automatic Differentiation（AD），只是解答我在自學 Deep Learning（DL）過程中所產生的疑問。

-----

Fig. Differentiation（圖片來源：Pixabay）。

-----

Summary:

自動微分，又叫做演算式微分，英文分別是 automatic 或 algorithmic differentiation，縮寫都是 AD [1], [2]。AD 有兩種，forward mode 跟 reverse mode [1]-[4], [12]。

AD 可直接用程式語言完成 [5]-[8]，也可藉由軟體套件實現 [9]-[11]。更進階則是配合 GPU 等硬體 [12]-[20]，將 reverse mode AD [13], [14] 運用於 DL [1]-[3]。

-----

Q1：What is AD？
Q2：What are forward and reverse modes？
Q3：What are AD S/W tools？
Q4：What are GPU, CUDA, and OpenCL？

-----

Q1：What is AD？

AD 是自動微分，所謂自動，不是你寫一個函數，他自動幫你產生程式碼，而是你寫好微分的程式碼，電腦幫你一行一行自動執行。

自動微分不是符號微分，也不是數值微分。說太多無用，請看圖一的範例自明。

Fig. 1a. Automatic, symbolic, and numerical differentiation [1]。

Fig. 1b. Automatic, symbolic, and numerical differentiation [2]。

-----

Q2：What are forward and reverse modes？

Forward mode 是在求特定數值的函數值時，順便就幫你把導數求出來。Reverse mode 則是先有導數值再逆推求偏導數值 [1]-[4], [12]。一樣，請參考圖二會更清楚。

在實作 AD 之前，要把函數先拆解成 Kanotorivich graph，參考圖三。

我找了 MATLAB、Scala、C＋＋、與 Fortran 的 AD 程式碼，有興趣可以看看 [5]-[8]。

Fig. 2a. Forward mode [2]。

Fig. 2b. Reverse mode [2]。

Fig. 3a. Kanotorivich graph [1]。

Fig. 3b. Kanotorivich graph [12]。

-----

Q3：What are AD S/W tools？

使用 AD 符合下列四項需求：Reliability, Computational Cost, Scalability, Human Effort。另外設計 AD tools 有兩種方法：Operator Overloading 跟 Source Transformation，各有其優缺點 [9]，參考圖四。

所謂 AD 軟體套件，自然是別人先幫你寫好 AD 囉，常見用 Python 開發的tools的有 PyADOL-C、PyCppAD、CasADi、Theano、CGT、AD [11]。

Fig. 4a. Operator Overloading [10]。

Fig. 4b. Source Transformation [10]。

-----

Q4：What are GPU, CUDA, and OpenCL？

Graphics Processing Unit (GPU) [18]。可搭配 CUDA [19] 或 OpenCL [20] 使用。

CUDA 是首次可以利用 GPU 作為 C-編譯器的開發環境，專用於 NVIDIA 的 GPU [19]。OpenCL 是一個為 CPU、GPU、DSP、FPGA 等處理器與硬體加速器的框架 [20]。無論是CUDA C-語言或是 OpenCL，指令最終都會被驅動程式轉換成 PTX 代碼，交由顯示核心計算 [19]。研究顯示，OpenCL 並未因其通用性而減低性能 [17]。

有關 GPU、CUDA、OpenCL 可參考圖五到七幫助瞭解。圖五是 Gradient Forward Mode 的演算法，有 sequential 跟 parallel version [12]。圖六是一個向量加法的程式碼，使用 CUDA，pp. 41-42 [15]。圖七則是 serial 跟 parallel multipication 硬體架構, pp. 31-32 [16]。

Fig. 5a. Gradient Forward Mode – the sequential version [12]。

Fig. 5b. Gradient Forward Mode – the parallel version [12]。

Fig. 6a. Parallel Programming in CUDA C。

Fig. 6b. Parallel Programming in CUDA C。

Fig. 7a. H/W of serial multiplication。

Fig. 7b. H/W of parallel multipication。

-----

結論：

設計 AD 套件很困難，然而 AD 的觀念其實很簡單。瞭解 AD 的觀念後，再去使用套件就不致於太心虛。重新看一次 BP，您對於全手工用 Python 實作 LeNet，是否多了幾分信心？：）

Fig. 8. Back propagation。

-----

出版說明：

2019/09/09

自動微分其實並不適合初學者。之前強迫自己完成的解說文章，比較像是資料整理而已。本次新增一篇參考文章 [21]，並摘錄其要點，相信對於理解這個主題，會有不少幫助。

計算導數有四種方法：手動微分法、數值微分法、符號微分法、自動微分法。數值微分法代入數值近似求解，符號微分法通過表達式求解。自動微分法介於數值微分法與符號微分法之間。

手動微分法要自行編寫損失函數與激活函數的求導代碼，麻煩且容易出錯。數值微分法通過使用函數值來估計函數的導數，計算速度慢且精度差。符號微分法廣泛用在各種數學套裝軟體中如 Matlab 等，通過使用符號表達式進行求導。

自動微分的反向模式也就是我們在深度學習中所說的 BP 算法（反向傳播法），只需要一個前向傳播、一個反向傳播就可以求得所有參數的導數，性能很高，非常適用於深度學習中的自動求導。

它通過正向遍歷計算圖求出每個節點的值，然後再通過反向遍歷整個圖，計算出每個節點的偏導，其原理為微積分鏈式法則。

-----

References

[1] 2015_Automatic differentiation in machine learning, a survey

[2] 2014_Automatic differentiation of algorithms for machine learning

[3] 2006_Automatic Differentiation, Applications, Theory, and Implementations

[4] 1992_Automatic Differentiation, Overview and Application to Systems of  Parameterized Nonlinear Equations

[5] 2010_Introduction to Automatic Differentiation and MATLAB Object-Oriented Programming

[6] 2010_Automatic Differentiation with Scala

[7] 2004_Automatic Differentiation, C++ Templates and Photogrammetry

[8] 1964_A simple automatic derivative evaluation program

[9] 2000_Computing derivatives of computer programs

[10] Automatic differentiation – Wikipedia
https://en.wikipedia.org/wiki/Automatic_differentiation

[11] 2016_Benchmarking Python Tools for Automatic Differentiation

[12] 2012_Interval arithmetic and automatic differentiation on GPU using OpenCL

[13] 2016_GPU-accelerated adjoint algorithmic differentiation

[14] 2013+_Adjoint Algorithmic Differentiation of a GPU Accelerated Application

[15] 2010_CUDA by Example, An Introduction to General-Purpose GPU Programming, p. 41.

[16] 2011_Algorithms and Parallel Computing

[17] 2011_A comprehensive performance comparison of CUDA and OpenCL

[18] 圖形處理器 - 維基百科，自由的百科全書
https://zh.wikipedia.org/wiki/%E5%9C%96%E5%BD%A2%E8%99%95%E7%90%86%E5%99%A8

[19] CUDA - 維基百科，自由的百科全書
https://zh.wikipedia.org/wiki/CUDA 

[20] OpenCL - 維基百科，自由的百科全書
https://zh.wikipedia.org/wiki/OpenCL 

[21] 微积分——自动微分 _ Solinx
http://www.solinx.co/archives/1177