自动微分(Automatic Differentiation)
目錄
什么是自動微分
手動求解法
數(shù)值微分法
符號微分法
自動微分法
自動微分Forward Mode
自動微分Reverse Mode
參考引用
現(xiàn)代深度學習系統(tǒng)中（比如MXNet， TensorFlow等）都用到了一種技術(shù)——自動微分。在此之前，機器學習社區(qū)中很少發(fā)揮這個利器，一般都是用Backpropagation進行梯度求解，然后進行SGD等進行優(yōu)化更新。手動實現(xiàn)過backprop算法的同學應該可以體會到其中的復雜性和易錯性，一個好的框架應該可以很好地將這部分難點隱藏于用戶視角，而自動微分技術(shù)恰好可以優(yōu)雅解決這個問題。接下來我們將一起學習這個優(yōu)雅的技術(shù):-)。本文主要來源于陳天奇在華盛頓任教的課程CSE599G1: Deep Learning System和《Automatic differentiation in machine learning: a survey》。
什么是自動微分
微分求解大致可以分為4種方式：
- 手動求解法(Manual Differentiation)
- 數(shù)值微分法(Numerical Differentiation)
- 符號微分法(Symbolic Differentiation)
- 自動微分法(Automatic Differentiation)
為了講明白什么是自動微分，我們有必要了解其他方法，做到有區(qū)分有對比，從而更加深入理解自動微分技術(shù)
手動求解法
手動求解其實就對應我們傳統(tǒng)的backprop算法，我們求解出梯度公式，然后編寫代碼，代入實際數(shù)值，得出真實的梯度。在這樣的方式下，每一次我們修改算法模型，都要修改對應的梯度求解算法，因此沒有很好的辦法解脫用戶手動編寫梯度求解的代碼，這也是為什么我們需要自動微分技術(shù)的原因。
數(shù)值微分法
數(shù)值微分法是根據(jù)導數(shù)的原始定義：
那么只要h hh取很小的數(shù)值，比如0.0001，那么我們可以很方便求解導數(shù)，并且可以對用戶隱藏求解過程，用戶只要給出目標函數(shù)和要求解的梯度的變量，程序可以自動給出相應的梯度，這也是某種意義上的“自動微分”?。不幸的是，數(shù)值微分法計算量太大，求解速度是這四種方法中最慢的，更加雪上加霜的是，它引起的roundoff error和truncation error使其更加不具備實際應用場景，為了彌補缺點，便有如下center difference approximation：
可惜并不能完全消除truncation error，只是將誤差減小。雖然數(shù)值微分法有如上缺點，但是由于它實在是太簡單實現(xiàn)了，于是很多時候，我們利用它來檢驗其他算法的正確性，比如在實現(xiàn)backprop的時候，我們用的"gradient check"就是利用數(shù)值微分法。
符號微分法
符號微分是代替我們第一種手動求解法的過程，利用代數(shù)軟件，實現(xiàn)微分的一些公式比如：
然后對用戶提供的具有closed form的數(shù)學表達式進行“自動微分"求解，什么是具有closed form的呢？也就是必須能寫成完整數(shù)學表達式的，不能有編程語言中的循環(huán)結(jié)構(gòu)，條件結(jié)構(gòu)等。因此如果能將問題轉(zhuǎn)化為一個純數(shù)學符號問題，我們能利用現(xiàn)有的代數(shù)軟件進行符號微分求解，這種程度意義上的“自動微分"其實已經(jīng)很完美了。然而缺點我們剛剛也提及過了，就是必須要有closed form的數(shù)學表達式，另一個有名的缺點是“表達式膨脹"（expression swell）問題，如果不加小心就會使得問題符號微分求解的表達式急速“膨脹"，導致最終求解速度變慢，對于這個問題請看如下圖：
稍不注意，符號微分求解就會如上中間列所示，表達式急劇膨脹，導致問題求解也隨著變慢。
自動微分法
終于輪到我們的主角登場，自動微分的存在依賴于它識破如下事實：
所有數(shù)值計算歸根結(jié)底是一系列有限的可微算子的組合
自動微分法是一種介于符號微分和數(shù)值微分的方法：數(shù)值微分強調(diào)一開始直接代入數(shù)值近似求解；符號微分強調(diào)直接對代數(shù)進行求解，最后才代入問題數(shù)值；自動微分將符號微分法應用于最基本的算子，比如常數(shù)，冪函數(shù)，指數(shù)函數(shù)，對數(shù)函數(shù)，三角函數(shù)等，然后代入數(shù)值，保留中間結(jié)果，最后再應用于整個函數(shù)。因此它應用相當靈活，可以做到完全向用戶隱藏微分求解過程，由于它只對基本函數(shù)或常數(shù)運用符號微分法則，所以它可以靈活結(jié)合編程語言的循環(huán)結(jié)構(gòu)，條件結(jié)構(gòu)等，使用自動微分和不使用自動微分對代碼總體改動非常小，并且由于它的計算實際是一種圖計算，可以對其做很多優(yōu)化，這也是為什么該方法在現(xiàn)代深度學習系統(tǒng)中得以廣泛應用。
自動微分Forward Mode
考察如下函數(shù)：
我們可以將其轉(zhuǎn)化為如下計算圖：
轉(zhuǎn)化成如上DAG（有向無環(huán)圖）結(jié)構(gòu)之后，我們可以很容易分步計算函數(shù)的值，并求取它每一步的導數(shù)值：
上表中左半部分是從左往右每個圖節(jié)點的求值結(jié)果，右半部分是每個節(jié)點對于的求導結(jié)果，比如,注意到每一步的求導都利用到上一步的求導結(jié)果，這樣不至于重復計算，因此也不會產(chǎn)生像符號微分法的"expression swell"問題。
自動微分的forward mode非常符合我們高數(shù)里面學習的求導過程，只要您對求導法則還有印象，理解forward mode自不在話下。如果函數(shù)輸入輸出為：
那么利用forward mode只需計算一次如上表右邊過程即可，非常高效。對于輸入輸出映射為如下的：
這樣一個有n個輸入的函數(shù)，求解函數(shù)梯度需要n遍如上計算過程。然而實際算法模型中，比如神經(jīng)網(wǎng)絡，通常輸入輸出是極其不成比例的，也就是：
那么利用forward mode進行自動微分就太低效了，因此便有下面要介紹的reverse mode。
自動微分Reverse Mode
如果您理解神經(jīng)網(wǎng)絡的backprop算法，那么恭喜你，自動微分的backward mode其實就是一種通用的backprop算法，也就是backprop是reverse mode自動微分的一種特殊形式。從名字可以看出，reverse mode和forward mode是一對相反過程，reverse mode從最終結(jié)果開始求導，利用最終輸出對每一個節(jié)點進行求導，其過程如下紅色箭頭所示：
其具體計算過程如下表所示：
上表左邊和之前的forward mode一致，用于求解函數(shù)值，右邊則是reverse mode的計算過程，注意必須從下網(wǎng)上看，也就是一開始先計算輸出對于節(jié)點的導數(shù)，用表示,這樣的記號可以強調(diào)我們對當前計算結(jié)果進行緩存，以便用于后續(xù)計算，而不必重復計算。由鏈式法則我們可以計算輸出對于每個節(jié)點的導數(shù)。
比如對于節(jié)點v3 :
用另一種記法便得到：
比如對于節(jié)點v0：
如果用另一種記法，便可得出：
和backprop算法一樣，我們必須記住前向時當前節(jié)點發(fā)出的邊，然后在后向傳播的時候，可以搜集所有受到當前節(jié)點影響節(jié)點。
如上的計算過程，對于像神經(jīng)網(wǎng)絡這種模型，通常輸入是上萬到上百萬維，而輸出損失函數(shù)是1維的模型，只需要一遍reverse mode的計算過程，便可以求出輸出對于各個輸入的導數(shù)，從而輕松求取梯度用于后續(xù)優(yōu)化更新。
#自動微分的實現(xiàn)
這里主要講解reverse mode的實現(xiàn)方式，forward mode的實現(xiàn)基本和reverse mode一致，但是由于機器學習算法中大部分用reverse mode才可以高效求解，所以它是我們理解的重心。代碼設(shè)計輪廓來源于CSE599G1的作業(yè)，通過分析完成作業(yè)，可以展示自動微分的簡潔性和靈活可用性。
首先自動微分會將問題轉(zhuǎn)化成一種有向無環(huán)圖，因此我們必須構(gòu)造基本的圖部件，包括節(jié)點和邊?？梢韵瓤纯垂?jié)點是如何實現(xiàn)的：
首先節(jié)點可以分為三種：
- 常數(shù)節(jié)點
- 變量節(jié)點
- 帶操作算子節(jié)點
因此Node類中定義了op成員用于存儲節(jié)點的操作算子，const_attr代表節(jié)點的常數(shù)值，name是節(jié)點的標識，主要用于調(diào)試。
對于邊的實現(xiàn)則簡單的多，每個節(jié)點只要知道本身的輸入節(jié)點即可，因此用inputs來描述節(jié)點的關(guān)系。
有了如上的定義，利用操作符重載，我們可以很簡單構(gòu)造一個計算圖，舉一個簡單的例子：
對于如上函數(shù)，只要重載加法和乘法操作符，我們可以輕松得到如下計算圖：
操作算子是自動微分最重要的組成部分，接下來我們重點介紹，先上代碼：
從定義可以看出，所有實際計算都落在各個操作算子中，上面代碼應該抽象一些，我們來舉一個乘法算子的例子加以說明：
我們重點講解一下gradient方法，它接收兩個參數(shù)，一個是node，也就是當前要計算的節(jié)點，而output_grad則是后面節(jié)點傳來的，我們來看看它到底是啥玩意，對于如下例子：
return [node.inputs[1] * output_grad, node.inputs[0] * output_grad]再來介紹一個特殊的op——PlaceHolderOp，它的作用就如同名字，起到占位符的作用，也就是自動微分中的變量，它不會參與實際計算，只等待用戶給他提供實際值，因此他的實現(xiàn)如下：
了解了節(jié)點和操作算子的定義，接下來我們考慮如何協(xié)調(diào)執(zhí)行運算。首先是如何計算函數(shù)值，對于一幅計算圖，由于節(jié)點與節(jié)點之間的計算有一定的依賴關(guān)系，比如必須先計算node1之后才可以計算node2，那么如何能正確處理好計算關(guān)系呢？一個簡單的方式是對圖節(jié)點進行拓撲排序，這樣可以保證需要先計算的節(jié)點先得到計算。這部分代碼由Executor掌控：
Executor是實際計算圖的引擎，用戶提供需要計算的圖和實際輸入，Executor計算相應的值和梯度。
如何從計算圖中計算函數(shù)的值，上面我們已經(jīng)介紹了，接下來是如何自動計算梯度。reverse mode的自動微分，要求從輸出到輸入節(jié)點，按照先后依賴關(guān)系，對各個節(jié)點求取輸出對于當前節(jié)點的梯度，那么和我們上面介紹的剛好相反，為了得到正確計算節(jié)點順序，我們可以將圖節(jié)點的拓撲排序倒序即可。代碼也很簡單，如下所示：
這里先介紹一個新的算子——oneslike_op。他是一個和numpy自帶的oneslike函數(shù)一樣的算子，作用是構(gòu)造reverse梯度圖的起點，因為最終輸出關(guān)于本身的梯度就是一個和輸出shape一樣的全1數(shù)組，引入oneslike_op可以使得真實計算得以延后，因此gradients方法最終返回的不是真實的梯度，而是梯度計算圖，然后可以復用Executor，計算實際的梯度值。
緊接著是根據(jù)輸出節(jié)點，獲得倒序的拓撲排序序列，然后遍歷序列，構(gòu)造實際的梯度計算圖。我們重點來介紹node_to_output_grad和node_to_output_grads_list這兩個字典的意義。
先關(guān)注node_to_output_grads_list，他key是節(jié)點，value是一個梯度列表，代表什么含義呢？先看如下部分計算圖：
而對于Executor而言，它并不知道此時的圖是否被反轉(zhuǎn)，它只關(guān)注用戶實際輸入，還有計算相應的值而已。
#自動梯度的應用
有了上面的大篇幅介紹，我們其實已經(jīng)實現(xiàn)了一個簡單的自動微分引擎了，接下來看如何使用：
使用相當簡單，我們像編寫普通程序一樣，對變量進行各種操作，只要提供要求導數(shù)的變量，還有提供實際輸入，引擎可以正確給出相應的梯度值。
下面給出一個根據(jù)自動微分訓練Logistic Regression的例子：
看到吧，用戶可以完全感受不到微分求解過程，真正做到自動微分！?完整實現(xiàn)代碼可戳此處。
參考引用
- CSE599G1: Deep Learning System
- Automatic differentiation in machine learning: a survey
————————————————
版權(quán)聲明：本文為CSDN博主「Carl-Xie」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/aws3217150/article/details/70214422
總結(jié)
以上是生活随笔為你收集整理的自动微分(Automatic Differentiation)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： pythonChallenge：第1关
- 下一篇： sobol敏感性分析 matlab代码