深度學習利器之自動微分(1)

0x00 摘要

本文和下文以 Automatic Differentiation in Machine Learning: a Survey 這篇論文為基礎，逐步分析自動微分這個機器學習的基礎利器。

0.1 緣起

筆者計劃分析 PyTorch 的分散式實現，但是在分析分散式autograd 時發現，如果不把自動微分以及普通 autograd 引擎梳理清楚，分散式autograd的分析就是寸步難行，因此返回頭來學習，遂有此文。

0.2 自動微分

我們知道，深度學習框架訓練模型的基本流程是：

依據模型搭建計算圖。
依據輸入計算損失函數。
計算損失函數對模型參數的導數。
根據得出的導數，利用梯度下降法等方法來反向更新模型參數，讓損失函數最小化。

搭建計算圖（依賴關係）和計算損失函數的過程，稱為”正向傳播」，這個是依據用戶模型完成，本質上是用戶自己處理。而依據損失函數求導的過程，稱為”反向傳播」，這個對於用戶來說太繁重，所以各種深度學習框架都提供了自動求導功能。深度學習框架幫助我們解決的核心問題就是兩個:

反向傳播時的自動梯度計算和更新。
使用 GPU 進行計算。

於是這就牽扯出來自動梯度計算這個概念。

在數學與計算代數學中，自動微分或者自動求導（Automatic Differentiation，簡稱AD）也被稱為微分演算法或數值微分。它是一種數值計算的方式，其功能是計算複雜函數（多層複合函數）在某一點處的導數，梯度，Hessian矩陣值等等。

0x01 基本概念

為了行文完整，我們首先要介紹一些基本概念或者思想，可能部分概念大家已經熟知，請直接跳到第二章。

1.1 機器學習

赫伯特·西蒙（Herbert Simon，1975年圖靈獎獲得者、1978年諾貝爾經濟學獎獲得者）對”學習」下過一個定義：”如果一個系統，能夠通過執行某個過程，就此改進了它的性能，那麼這個過程就是學習」。

所以說，機器學習就是從經驗數據中學習，提取數據中的重要的模式和趨勢，從而改進預估函數（有關特定輸入和預期輸出的功能函數）的性能。

比如：一個函數可以用來區分貓和狗，我們需要使用大量的訓練數據來挖掘培養這個函數，改進其性能。

1.2 深度學習

傳統機器學習使用知識和經驗從原始數據中提取各種特徵進行訓練。提取特徵就是機器學習的重要組成部分：特徵工程。因為原始數據涉及到的特徵數目太龐大，而且特徵種類千差萬別，所以特徵工程是個極具挑戰的部分。深度學習則是讓神經網路自己學習/提取數據的各種特徵，或者通過組合各種底層特徵來形成一些高層特徵。

1.3 損失函數

對於機器學習的功能函數，我們給定一個輸入，會得到一個輸出，比如輸入貓，輸出”是否為貓」。但是這個實際輸出值可能與我們的預期值不一樣。因此，我們需要構建一個評估體系，來辨別函數的好壞，這就引出了損失函數。

損失函數（loss function）或者是代價函數（cost function）就是用來度量預期輸出（真實值）和實際輸出（預測值）的”落差」程度或者說是精確度。

損失函數可以把模型擬合程度量化成一個函數值，如果我們選取不同的模型參數，則損失函數值會做相應的改變。損失函數值越小，說明實際輸出和預期輸出的差值就越小，也就表明構建的模型精確度就越高。比如常見的均方誤差（Mean Squared Error）損失函數，從幾何意義上來說，它可以看成預測值和實際值的平均距離的平方。

1.4 權重和偏置

損失函數里一般有兩種參數：

我們把神經元與神經元之間的影響程度叫作為權重（weight）。權重的大小就是連接的強弱。它通知下一層相鄰神經元更應該關注哪些輸入訊號量。
除了連接權值，神經元內部還有一個施加於自身的特殊權值，叫偏置（bias）。偏置用來調整函數與真實值距離的偏差。偏置能使輔助神經元是否更容易被激活。也就是說，它決定神經元的連接加權和得有多大，才能讓激發變得有意義。

神經網路結構的設計目的在於，讓神經網路以”更佳」的性能來學習。而這裡的所謂”學習」，就是不斷調整權重和偏置，從而找到神經元之間最合適的權重和偏置，讓損失函數的值達到最小。

1.5 導數和梯度

神經網路的特徵之一，就是從數據樣本中學習。也就是說，可以由訓練數據來自動確定網路權值參數的值。

既然我們有了損失函數這個評估體系，那麼就可以利用其來反向調整網路中權重，使得損失最小，即如果某些權重使得損失函數達到最小值，這些權重就是我們尋找的最理想參數。

假設損失函數為 y = f(x)，我們尋找其最小值，就是求這個函數的極值點，那麼就是求其一階導數 f'(x) = 0 這個微分方程的解。但是電腦不擅長求微分方程，所以只能通過插值等方法進行海量嘗試，把函數的極值點求出來。

什麼是導數呢？

所謂導數，就是用來分析函數”變化率」的一種度量。針對函數中的某個特定點 x0，該點的導數就是x0點的”瞬間斜率」，也即切線斜率。

什麼是梯度呢?

梯度的本意是一個向量（矢量），表示某一函數在該點處的方嚮導數沿著該方向取得最大值，即函數在該點處沿著該方向（此梯度的方向）變化最快，變化率最大（為該梯度的模）。

在單變數的實值函數中，對於函數的某個特定點，它的梯度方向就表示從該點出發，函數值增長最為迅猛的方向或者說是函數導數變化率最大的方向。

對於機器學習/深度學習來說，梯度方向就是損失函數變化最快的方向，因為我們希望損失最小，所以我們就通常利用數值微分來計算神經網路權值參數的梯度，按照梯度下降來確定調參的方向，按照這個方向來優化。

1.6 梯度下降

梯度下降的大致思路是：首先給參數 w, b 隨機設定一些初值，然後採用迭代的演算法，計算當前網路的輸出，然後根據網路輸出與預期輸出之間的差值，反方向地去改變前面各層的參數，直至網路收斂穩定。

具體來說，就是：

給參數 w, b 隨機設定一些初值。
for i = 0 to 訓練數據的個數：
- 根據參數 w, b 這些初值來計算當前網路對於第 i 個訓練數據的輸出
- 根據網路輸出與預期輸出之間的差值，得到一個權重 w 和偏差 b 相對於損失函數的梯度。
最終，針對每一個訓練數據，都得到一個權重和偏差的梯度值。
把各個樣本數據的權重梯度加起來，計算所有樣本的權重梯度的平均值 \(\nabla w\)。
把各個樣本數據的偏差梯度加起來，計算所有樣本的偏差梯度的平均值 \(\nabla b\)。
更新權重值和偏差值：
- w = w – \(\nabla w\)
- b = b – \(\nabla b\)
返回 2，繼續迭代，直至網路收斂。

當然，梯度下降有很多優化方法，具體邏輯各有不同。

1.7 反向傳播

說到back propagation演算法，我們通常強調的是反向傳播。其實在本質上，它是一個雙向演算法。也就是說，它其實是分兩大步走：

前向傳播：把批量數據送入網路，計算&正向傳播輸入資訊（就是把一系列矩陣通過激活函數的加工，一層一層的向前”蔓延」，直到抵達輸出層），最終輸出的預測值與真實label比較之後，用損失函數計算出此次迭代的損失，其關注點是輸入怎麼影響到每一層。

反向傳播：反向傳播誤差從網路最後端開始進入到網路模型中之前的每一層，根據鏈式求導，調整網路權重和偏置，最終逐步調整權重，使得最終輸出與期望輸出的差距達到最小，其關注點是每一層怎麼影響到最終結果。

具體如下圖：

我們可以看到，這個圖中涉及到了大量的梯度計算，於是又涉及到一個問題：這些梯度如何計算？深度學習框架，幫助我們解決的核心問題就是兩個:

反向傳播時的自動梯度計算和更新，也被稱作自動微分。
使用 GPU 進行計算。

1.8 可微分編程

1.8.1 可微分編程永生

Yann Lecun在其博文 “深度學習已死，可微分編程永生」之中提到：

“深度學習本質上是一種新的編程方式——可微分編程——而且這個領域正試圖用這種方式來制定可重用的結構。目前我們已經有：卷積，池化，LSTM，GAN，VAE，memory單元，routing單元，等等。」

但重要的一點是，人們現在正在將各種參數化函數模組的網路組裝起來，構建一種新的軟體，並且使用某種基於梯度的優化來訓練這些軟體。

越來越多的人正在以一種依賴於數據的方式（循環和條件）來程式化地定義網路，讓它們隨著輸入數據的動態變化而變化。這與是普通的程式非常類似，除了前者是參數化的、可以自動可微分，並且可以訓練和優化。動態網路變得越來越流行（尤其是對於NLP而言），這要歸功於PyTorch和Chainer等深度學習框架（注意：早在1994年，以前的深度學習框架Lush，就能處理一種稱為Graph Transformer Networks的特殊動態網路，用於文本識別）。

1.8.2 深度學習成功的關鍵

MIT媒體實驗室的David Dalrymple 也介紹過可微分編程。Dalrymple認為，深度學習的成功有兩大關鍵，一是反向傳播，二是權重相關（weight-tying），這兩大特性與函數編程（functional programing）中調用可重用函數十分相同。可微分編程有成為”timeless」的潛力。

反向傳播以非常優雅的方式應用了鏈式規則（一個簡單的微積分技巧），從而把連續數學和離散數學進行了深度整合，使複雜的潛在解決方案族可以通過向量微積分自主改進。

反向傳播的關鍵是將潛在解決方案的模式（template）組織為一個有向圖。通過反向遍歷這個圖，演算法能夠自動計算”梯度向量」，而這個”梯度向量” 能引導演算法尋找越來越好的解決方案。

權重相關（weight-tying）是第二個關鍵之處，它使得同一個權重相關的網路組件可以同時在多個地方被使用，組件的每個副本都保持一致。Weight-tying 會使網路學習到更加泛化的能力，因為單詞或者物體可能出現在文本塊或影像的多個位置。權重相關（weight-tied）的組件，實際上與編程中可重用函數的概念相同（就類似於你編寫一個函數，然後在程式中多個地方都進行調用），而且對組件的重用方式也與函數編程中通用的”高階函數」生成的方式完全一致。

1.8.3 可微分編程

可微分編程是一個比較新的概念，是反向傳播和weight-tying的延伸。用戶僅指定了函數的結構以及其調用順序，函數程式實際上被編譯成類似於反向傳播所需的計算圖。圖的各個組成部分也必須是可微的，可微分編程把實現/部署的細節留給優化器——語言會使用反向傳播根據整個程式的目標自動學習細節，基於梯度進行優化，就像優化深度學習中的權重一樣。

特斯拉人工智慧部門主管Andrej Karpathy也提出過一個”軟體2.0」概念。

軟體1.0（Software 1.0）是用Python、C++等語言編寫，由對電腦的明確指令組成。通過編寫每行程式碼，程式設計師可以確定程式空間中的某個特定點。

Software 2.0 是用神經網路權重編寫的。沒有人參與這段程式碼的編寫。在軟體2.0的情況下，人類對一個理想程式的行為指定一些約束（例如，輸入輸出數據集），並依據可用的計算資源來搜索程式空間中滿足約束條件的程式。在這個空間中，搜索過程可以利用反向傳播和隨機梯度下降滿足要求。

Karpathy認為，在現實世界中，大部分問題都是收集數據比明確地編寫程式更容易。未來，大部分程式設計師不再需要維護複雜的軟體庫，編寫複雜的程式，或者分析程式運行時間。他們需要做的是收集、整理、操作、標記、分析和可視化提供給神經網路的數據。

綜上，既然知道了自動計算梯度的重要性，我們下面就來藉助一篇論文 Automatic Differentiation in Machine Learning: a Survey 來具體學習一下。

0x02 微分方法

2.1 常見方法

我們首先看看微分的幾種比較常用的方法：

手動求解法(Manual Differentiation) : 完全手動完成，依據鏈式法則解出梯度公式，帶入數值，得到梯度。
數值微分法(Numerical Differentiation) ：利用導數的原始定義，直接求解微分值。
符號微分法(Symbolic Differentiation) : 利用求導規則對表達式進行自動計算，其計算結果是導函數的表達式而非具體的數值。即，先求解析解，然後轉換為程式，再通過程式計算出函數的梯度。
自動微分法(Automatic Differentiation) ：介於數值微分和符號微分之間的方法，採用類似有向圖的計算來求解微分值。

具體如下圖：

2.2 手動微分

手動微分就是對每一個目標函數都需要利用求導公式手動寫出求導公式，然後依照公式編寫程式碼，帶入數值，求出最終梯度。

這種方法準確有效，但是不適合工程實現，因為通用性和靈活性很差，每一次我們修改演算法模型，都要修改對應的梯度求解演算法。如果模型複雜或者項目頻繁反覆迭代，那麼演算法工程師別說 996 了，就是 365 x 24 也頂不住。

2.3 數值微分

數值微分方式應該是最直接而且簡單的一種自動求導方式。從導數的原始定義中，我們可以直觀看到前向差分公式為：

當h取很小的數值，比如0.000001 時，導數是可以利用差分來近似計算出來的。只需要給出函數值以及自變數的差值，數值微分演算法就可計算出導數值。單側差分公式根據導數的定義直接近似計算某一點處的導數值。

數值微分的優點是：

上面的計算式幾乎適用所有情況，除非該點不可導，
實現簡單。
對用戶隱藏求解過程。

但是，數值微分有幾個問題：

計算量太大，求解速度是這幾種方法中最慢的，尤其是當參數多的時候，因為因為每計算一個參數的導數，你都需要重新計算f(x+h)。
因為是數值逼近，所有會不可靠，不穩定的情況，無法獲得一個相對準確的導數值。如果 h 選取不當，可能會得到與符號相反的結果，導致誤差增大。尤其是兩個嚴重問題：
- 截斷錯誤(Truncation error)：在數值計算中 h 無法真正取零導致的近似誤差。
- 舍入誤差(Roundoff Error)：在計算過程中出現的對小數位數的不斷舍入會導致求導過程中的誤差不斷累積。

為了緩解截斷錯誤，人們提出了中心微分近似（center difference approximation），這方法仍然無法解決舍入誤差，只是減少誤差，但是它比單側差分公式有更小的誤差和更好的穩定性。具體公式如下：

雖然數值微分有一些缺點，但是好處是簡單實現，所以可以用來校驗其他演算法所得到梯度的正確性，比如”gradient check”就是利用數值微分法。

2.4 符號微分

符號微分（Symbolic Differentiation）屬符號計算的範疇，利用求導規則對表達式進行自動計算，其計算結果是導函數的表達式。符號計算用於求解數學中的公式解（也稱解析解），得到的是解的表達式而非具體的數值。

符號微分適合符號表達式的自動求導，符號微分的原理是用下面的簡單求導規則替代手動微分：

符號微分利用代數軟體，實現微分的一些公式，然後根據基本函數的求導公式以及四則運算、複合函數的求導法則，將公式的計算過程轉化成微分過程，這樣就可以對用戶提供的具有closed form的數學表達式進行”自動微分”求解。就是先求解析解，然後轉換為程式，再通過程式計算出函數的梯度。

符號微分計算出的表達式需要用字元串或其他數據結構存儲，如表達式樹。數學軟體如Mathematica，Maple，matlab中實現了這種技術。python語言的符號計算庫也提供了這類演算法。

符號微分的問題是：

表達式必須是closed form的數學表達式，也就是必須能寫成完整數學表達式的，不能有程式語言中的循環結構，條件結構等。這樣才能將整個問題轉換為一個純數學符號問題，從而利用一些代數軟體進行符號微分求解。
表達式複雜時候（深層複合函數，如神經網路的映射函數），因為電腦也許並不能進行智慧的簡化，所以容易出現”表達式膨脹」(expression swell)的問題。

表達式膨脹如下圖所示，稍不注意，符號微分求解就會如下中間列所示，表達式急劇膨脹，導致問題求解也隨著變慢，計算上的冗餘且成本高昂:

其實，對於機器學習中的應用，不需要得到導數的表達式，而只需計算函數在某一點處的導數值。

2.5 自動微分

2.5.1 中間方法

自動微分是介於數值微分和符號微分之間的方法，採用類似有向圖的計算來求解微分值。

數值微分：一開始就直接代入數值近似求解。
符號微分：直接對代數表達式求解析解，最後才代入數值進行計算。
自動微分：首先對基本運算元（函數）應用符號微分方法，其次帶入數值進行計算，保留中間結果，最後通過鏈式求導法將中間結果應用於整個函數，這樣可以做到完全向用戶隱藏微分求解過程，也可以靈活於程式語言的循環結構、條件結構等結合起來。

關於解析解我們還要做一些說明。幾乎所有機器學習演算法在訓練或預測時都可以歸結為求解最優化問題，如果目標函數可導，則問題就變為求訓練函數的駐點。但是通常情況下我們無法得到駐點的解析解，因此只能採用數值優化演算法，如梯度下降法，牛頓法，擬牛頓法等等。這些數值優化演算法都依賴於函數的一階導數值或二階導數值（包括梯度與Hessian矩陣）。因此需要解決如何求一個複雜函數的導數問題，自動微分技術是解決此問題的一種通用方法。

由於自動微分法只對基本函數或常數運用符號微分法則，所以它可以靈活結合程式語言的循環結構，條件結構等。使用自動微分和不使用自動微分對程式碼總體改動非常小，由於它實際是一種圖計算，可以對其做很多優化，所以該方法在現代深度學習系統中得到廣泛應用。