第2章
Chapter Two
反向傳播算法

2.1 導數(shù)和導數(shù)的應(yīng)用

作為深度學習的基礎(chǔ)算法，反向傳播算法（Back Propagation，BP）是最著名的人工智能算法之一。也許你對它并不陌生，但是BP算法的實質(zhì)是什么呢？為什么這個算法就能幫助人工神經(jīng)元網(wǎng)絡(luò)優(yōu)化參數(shù)？要回答這兩個問題，我們不得不從高等數(shù)學中的導數(shù)說起。請不要急于把這本書或者這一章丟到一邊。我知道，即使是高等數(shù)學考得還不錯的學生，也有很大概率對它不感興趣。下面我們將通過實際例子講導數(shù)，例如怎么用導數(shù)求解平方根，然后自然過渡到深度學習。你會發(fā)現(xiàn)，這是一段奇妙的數(shù)學之旅。

2.1.1 導數(shù)

導數(shù)就是函數(shù)在某一點處的切線的斜率，如圖2－1所示。更進一步，導數(shù)是函數(shù)因變量y的變化與自變量x的變化的比值的極限。即：

這個公式告訴我們：根據(jù)導數(shù)，我們有可能根據(jù)y的變化推斷x的變化。

設(shè)有函數(shù)y＝f（x），現(xiàn)在我們的目標是求出當y＝y^?時x的值，即求x^?滿足f（x^?）＝y^?。這其實是一件非常有意義的事。例如，根據(jù)函數(shù)y＝x²我們可以很容易算出任意一個數(shù)的平方。但是反過來，當y＝2時x應(yīng)該等于幾就不好計算了。這個問題實際上就是求2的平方根。

那么怎么辦呢？方法就是先給x一個初值，例如1，然后計算出對應(yīng)的y值，顯然也是1。再計算y的當前值與目標值2之間的誤差Δy＝y^?－y，根據(jù)Δy和導數(shù)再不斷地調(diào)整x的值以盡量減少Δy的絕對值。當Δy＝0時，對應(yīng)的x就是2的平方根。

根據(jù)問題分解方法，我們現(xiàn)在要考慮的子問題是如何根據(jù)Δy和導數(shù)調(diào)整x的值。這其實并沒有想象中那么困難。假設(shè)Δy＞0，此時如果導數(shù)y′也大于0，則意味著我們應(yīng)該把x往右移動，即令Δx＞0，這樣才有可能得到更大的y，如圖2－2所示。

再把其他3種情況也考慮在內(nèi)，我們可以得出一個非常有意思的結(jié)論。

梯度下降法（Gradient Descent，GD）第一個公式如下：

其中a是一個大于0的調(diào)整因子，又叫作步長。Δy決定了Δx的變化方向，a決定了變化步長。我們可以使用如下迭代算法計算出x^?。

算法2－1 根據(jù)導數(shù)迭代求解最優(yōu)解（迭代求解算法）

1）給x賦予一個隨機初值。

2）按照一定循環(huán)條件，反復執(zhí)行：

a）計算Δy＝y^?－y。

b）根據(jù)式（2－1）或者式（2－2）（后面介紹）求Δx。

c）令x＝x+Δx。

其中的循環(huán)條件可以是|Δy|＜ε（ε是事先指定的一個小正數(shù)），可以是固定的循環(huán)次數(shù)，也可以是這兩個條件的或。下面以這個算法為基礎(chǔ)，令a＝0.01，按照固定循環(huán)次數(shù)試著求1～10的平方根。代碼如下：

輸出結(jié)果如下：

sqrt（1）＝1.00000000

sqrt（2）＝1.41421352

sqrt（3）＝1.73205081

sqrt（4）＝2.00000000

sqrt（5）＝2.23606798

sqrt（6）＝2.44948974

sqrt（7）＝2.64575131

sqrt（8）＝2.82842712

sqrt（9）＝3.00000000

sqrt（10）＝3.16227766

我們看到，這個結(jié)果是相當準確的。有趣的是，式（2－1）是一個通用公式。只要選取合適的步長，并且函數(shù)y＝f（x）在定義域區(qū)間內(nèi)處處可導^[1]，就能用類似的方法求解f的反函數(shù)^[2]（又叫逆函數(shù)，以下我們無差別地使用這兩個概念）。

2.1.2 梯度下降法求函數(shù)的最小值

如果y^?是事先不確定的，那么我們就不能直接使用式（2－1）。例如，求y的最小值和最大值。求y的最大值可以轉(zhuǎn)化為求－y的最小值，所以我們只需考慮如何求y的最小值即可。

假設(shè)我們用迭代法求解函數(shù)y＝f（x）的最小值，并且當前x＝x₁。如果導數(shù)值f′（x₁）＞0，如圖2－3所示，則意味著當x＞x₁時因變量y的變化趨勢是增大的。所以，為了獲得更小的y值，應(yīng)該讓x變小，即Δx＜0。如果f′（x₁）＜0，如圖2－4所示，則意味著當x＞x₁時因變量y的變化趨勢是減小。所以，為了獲得更小的y值，應(yīng)該讓x變大，即Δx＞0。綜上所述，我們可以得到梯度下降法第二個公式，即

式（2－1）和式（2－2）就是梯度下降法（GD）的兩個公式。前者用來計算y在特定值y^?下的解；后者用來求y最小值的解。值得一提的是，式（2－1）的使用可以轉(zhuǎn)為使用式（2－2）。例如，求滿足f（x）＝y^?的x可以轉(zhuǎn)為求下面函數(shù)的最小值：

g（x）＝［f（x）－y^?］²

世界上絕大多數(shù)深度學習框架，例如后面要學習的Tensorflow，幾乎都是基于GD法的。因此我們后面的學習幾乎都是圍繞著GD法以及GD法與其他方法的比較進行的。請注意，雖然我們以求最小值為目的推導了式（2－2），但一般情況下，該公式只能求到函數(shù)在當前點附近的極小值，其他位置的極小值求不到。因為在極小值點存在＝0，這使得Δx＝0，從而導致無法更新x。

式（2－2）是針對一元函數(shù)的，多元函數(shù)也有類似的公式。對于多元函數(shù)y＝f（x₁，x₂，…，x_n）來說，為了求它的最小值，每個x_i都應(yīng)該按照下面的公式進行迭代，即多元函數(shù)梯度下降法公式：

下面，我們編寫程序來求函數(shù)y＝（x₁+2）²+（x₂－3）²在什么情況下可取得最小值。

輸出結(jié)果：

（－1.9999999999999947，2.9999999999999893）

GD法的實質(zhì)是在函數(shù)曲線上，沿著導數(shù)所指示的方向，按照步長所規(guī)定的距離移動一個點，看看新位置處的y值是不是比原位置的更小或者離y^?更近。這意味著GD法是通過試探來獲得比當前解更優(yōu)的解的。你也可以采用其他方法進行試探，例如牛頓法、二分法和黃金分割法等。下面以牛頓法為例進行說明。

2.1.3 牛頓法求平方根

所謂牛頓法，其理論根據(jù)是：，從而有牛頓法公式：

對比式（2－1）、式（2－2）、式（2－3）和式（2－4），你會發(fā)現(xiàn)這些公式的目的都一樣，都是為了計算Δx，從而幫助我們計算逆函數(shù)。逆函數(shù)之所以重要，是因為它的實質(zhì)是透過現(xiàn)象看本質(zhì)，透過結(jié)果看原因。這是深度學習乃至人工智能的根本目的。下面我們用牛頓法計算平方根。

令y＝x²，則有y′＝2x。代入牛頓法公式有Δx＝，其中p是要求平方根的數(shù)。根據(jù)算法2－1中的迭代方法，則有：

這就是牛頓法求解平方根的公式。下面我們編寫程序來驗證這個公式：

輸出結(jié)果如下：

sqrt（1）＝1.00000000

sqrt（2）＝1.41421356

sqrt（3）＝1.73205081

sqrt（4）＝2.00000000

sqrt（5）＝2.23606798

sqrt（6）＝2.44948974

sqrt（7）＝2.64575131

sqrt（8）＝2.82842713

sqrt（9）＝3.00000000

sqrt（10）＝3.16227767

此代碼僅僅循環(huán)5次就達到了這樣精確的結(jié)果，而代碼2－1循環(huán)5次是遠遠達不到這個效果的。既然如此，為什么我們不放棄GD法而統(tǒng)一使用牛頓法呢？原因就在于牛頓法計算得到的Δx沒有經(jīng)過步長a的調(diào)整，步子往往跨得太大，從而導致最優(yōu)解x^?被錯過。

如圖2－5所示，設(shè)有曲線y＝f（x），曲線在A點（x_a，y_a）的切線斜率是y′，切線AB交直線y＝y^?于B點（x_b，y^?）。y^?是目標值。我們的目的是求最優(yōu)解x^?，使得f（x^?）＝y^?。假設(shè)當前x＝x_a，請根據(jù)牛頓法求x的下一個值x₂。

解答：切線的斜率滿足

而根據(jù)牛頓法有：

把y′代入，得：

Δx＝x_b－x_a

所以：

x ₂＝x_a+Δx＝x_b

這意味著切線AB與y＝y^?的交點B就是x的下一個位置。我們發(fā)現(xiàn)x _b不但錯過了最優(yōu)解x^?，而且離x^?的距離比x_a還要遠。這就是牛頓法的問題，即很容易導致解的發(fā)散。換句話說，就是步子跨得太大了。極端情況下，x會越來越發(fā)散，永遠也到達不了最優(yōu)解。而GD法利用步長因子a解決了這個問題。

當然，也可以給牛頓法加一個步長因子。問題是牛頓法Δx＝中導數(shù)位于分母位置，這就限制了y′，因為其不能等于0。

2.1.4 復合函數(shù)和鏈式法則

根據(jù)前面的論述，解決問題是試圖透過現(xiàn)象看本質(zhì)，透過結(jié)果看原因，通過函數(shù)求解逆函數(shù)。而為了求逆函數(shù)，我們采用了GD法。后者的實質(zhì)是求函數(shù)對自變量的導數(shù)，對多元函數(shù)來說就是求偏導。

對于復合函數(shù)，可以利用鏈式法則求偏導。例如，設(shè)有函數(shù)y＝f（x），z＝g（y），即z＝g（f（x））。如果用GD法求z^?的解或者求z的最小值，根據(jù)鏈式法則，則有：

若設(shè)y＝sin（x），z＝3y²，則有：

上述變量x、y、z之間的依賴關(guān)系可以用圖2－6表示。圖中的結(jié)點表示變量，從一個結(jié)點指向另一個結(jié)點的指針表示后者的計算依賴于前者。前者稱為后者的前驅(qū)，后者稱為前者的后繼。我們把這種圖稱為依賴關(guān)系圖。依賴關(guān)系圖一定是一個有向無環(huán)圖（Directed Acyclic Graph，DAG）。

最簡單的依賴關(guān)系圖猶如一條直線，除最后一個結(jié)點外每個結(jié)點都有且僅有一個后繼，除第一個結(jié)點外每個結(jié)點都有且僅有一個前驅(qū)。我們在所有的有向弧上標記后者對前者的偏導，如圖2－6所示。在這樣的依賴關(guān)系圖中計算兩個變量之間的偏導，只需把它們之間路徑上的所有偏導相乘即可。這就是圖示化的鏈式法則。

2.1.5 多元函數(shù)和全微分方程

復合函數(shù)有助于我們用一堆簡單的函數(shù)組合成一個復雜函數(shù)。構(gòu)成復雜函數(shù)的另一個方法是利用多元函數(shù)。設(shè)有多元函數(shù)y＝f（x₁，x₂，…，x_n），則有全微分方程：

如果假設(shè)式（2－5）中的每一個x_i都是x的函數(shù)，即x_i＝f_i（x），i＝1，2，…，n，則有dx_i＝dx，代入式（2－5）得：

可以用圖2－7所示的依賴關(guān)系圖表示。其表明，y對x的偏導等于從x到y的所有可能路徑上導數(shù)乘積的和。

值得一提的是，這個結(jié)論不僅對圖2－7和圖2－6有效，其對任意形式的關(guān)系依賴圖都有效，只要它是一個DAG。

例如，在圖2－8所示的依賴關(guān)系圖中，從x到y的所有可能路徑有：xacy、xady、xbdy。這些路徑上的導數(shù)乘積分別是1、－1.5和－1，把這些值相加得到＝－1.5。有了偏導，在GD法的幫助下，我們就可以計算逆函數(shù)。

由于深度學習的目的是透過現(xiàn)象看本質(zhì)，根據(jù)原函數(shù)計算逆函數(shù)，所以依賴關(guān)系圖和上述計算偏導的過程就構(gòu)成了整個深度學習大廈的基石。所有深度學習的算法、理論和模型幾乎都是建立在這個基礎(chǔ)上的。

接下來我們要考慮的問題是：如何優(yōu)化計算過程，避免重復計算？有沒有什么辦法幫助我們自動求偏導，自動求解逆函數(shù)？

2.1.6 反向傳播算法

如圖2－8所示，我們在計算y對x的偏導時，有很多路徑是共享的，例如弧xa和dy。沒有必要對這些路徑上的導數(shù)乘積進行重復計算。所以我們可以從y出發(fā)，沿著有向弧的反方向，每經(jīng)過一個結(jié)點，就看看該結(jié)點是否可以計算y對它的偏導。如果能，就進行計算，并訪問它的所有前驅(qū)結(jié)點。這個過程不斷地往前推進，直到遇到x結(jié)點為止。

而一個結(jié)點A是否可計算y對它的偏導，取決于它的所有后繼結(jié)點是否都已計算了y對其的偏導。如果都算過了，就把這些偏導分別乘以相應(yīng)結(jié)點到A的偏導，再對所有這些乘積求和即可。

如圖2－9所示，從y出發(fā)，沿著有向弧的反方向，我們首先會遇到d、c兩個結(jié)點。顯然，和都是可以計算的，我們在c、d結(jié)點邊上分別寫上0.5和－0.5。接著，遇到了結(jié)點a和b。＝2×0.5+3 ×（－0.5）＝－0.5，＝－2 ×（－0.5）＝1.0，在a、b結(jié)點邊上分別寫上－0.5和1.0。最后計算＝1 ×（－0.5）－1 ×1.0＝－1.5。計算過程中不需要重復計算共享路徑上的偏導乘積。這就是反向傳播算法（Back Propagation，BP）。

算法2－2 反向傳播算法（BP）

deriv（y，graph）

說明：在有向圖graph上計算，x是任何y所依賴的結(jié)點。

1）構(gòu)建一個字典＝｛y：1｝，用來保存y對每個結(jié)點的偏導。其中y對自己的偏導是1。▽

2）構(gòu)建集合open＝｛y｝，用來保存可以計算偏導的結(jié)點。

3）當open集合不為空時，反復執(zhí)行：

a）任取open中的一個元素t。

b）從open集合中刪除t。

c）sum＝0。

d）對t的每個后繼結(jié)點p，執(zhí)行：

sum＝sum+▽［p］

e）令▽［t］ ＝sum。

f）對t的每個前驅(qū)q，如果q的所有后繼都在字典▽中出現(xiàn)，就把q加入集合open。

算法2－1指明了如何利用導數(shù)迭代求解最優(yōu)解，而算法2－2給出了求解復雜函數(shù)偏導數(shù)的方法。

既然y對x的偏導等于從x到y的所有可能路徑上導數(shù)乘積的和，那么正向傳播（FP）也能計算這個值。甚至FP算法有一個優(yōu)點：每計算完一個結(jié)點就可以釋放這個結(jié)點所占內(nèi)存，無須再保留這個結(jié)點。而BP算法在計算偏導時可能要為某些結(jié)點保存函數(shù)值，例如函數(shù)f（x）＝的導函數(shù)f′（x）＝f（x）［1－f（x）］。那我們?yōu)槭裁赐扑]使用BP算法而不是FP算法來計算偏導呢？

首先，BP算法保證了只有必要結(jié)點的導數(shù)值和/或函數(shù)值會被計算，無關(guān)結(jié)點不會被涉及。其次，更重要的是，BP算法每計算一個結(jié)點就能得到y對該結(jié)點的偏導。也就是說，一次BP計算可以把y對所有相關(guān)變量的偏導都計算出來，而FP算法只能計算y對x的偏導。

2.1.7 梯度

前面章節(jié)中提到了梯度下降法GD，但是沒有嚴格說明什么是梯度。算法2－2中為了計算y對任何一個所依賴的結(jié)點的偏導數(shù)，使用了字典▽，用來保存結(jié)點的偏導數(shù)。這個偏導數(shù)就是該結(jié)點的梯度。偏導數(shù)和梯度概念的區(qū)別在于：梯度特別強調(diào)是網(wǎng)絡(luò)的最后一個結(jié)點對當前結(jié)點的偏導數(shù)；而偏導數(shù)不強調(diào)是最后一個結(jié)點，任何兩個結(jié)點之間都可以有偏導數(shù)。梯度用符號▽表示。結(jié)點x的梯度記為▽_x。梯度有以下性質(zhì)：

1）▽_y＝1，y是網(wǎng)絡(luò)的最后一個結(jié)點。

2）▽_x＝，y_i是x的第i個后繼。

注意，梯度不是微分，▽_x不等價于dx。

2.1.8 分段求導

由于GD法要用到導數(shù)，所以人們很容易認為，GD法和BP算法只適合于求解在定義域內(nèi)處處可導的函數(shù)的逆函數(shù)。真的是這樣嗎？我們考慮函數(shù)y＝|x|。顯然，它在x＝0處沒有切線，因而也就不可導，如圖2－10所示。

那是不是就意味著GD法和BP算法不能使用在y＝|x|這類如此簡單的函數(shù)上？答案是能，只要函數(shù)在定義域內(nèi)任意一點存在左導數(shù)或者右導數(shù)即可。

極限稱為函數(shù)點a的右導數(shù)，極限稱為函數(shù)點a的左導數(shù)。以左導數(shù)為例，如果左導數(shù)存在，意味著x從左邊接近a時，計算導數(shù)的極限是存在的。

用數(shù)學語言來說，連續(xù)函數(shù)f（x）在某一點a不可導的充分必要條件是：

例如在圖2－10中，x＝0處的左右切線斜率分別是－1和1。所以不可導并不意味著左右導數(shù)不存在，只是這兩個值不等罷了。而GD法是一個迭代算法，是根據(jù)x的當前值計算它的下一個值（見算法2－1），即使是多元復合函數(shù)也是如此。所以在遇到不可導點a前，我們必然要么處在它的左邊，要么處在它的右邊。計算不會因為a點的導數(shù)不存在而崩潰。即使到達a點，也可以根據(jù)之前自變量位于a的哪一邊，用a的左導數(shù)或者右導數(shù)代替，計算仍然不會崩潰。

基于此，GD法僅要求函數(shù)連續(xù)即可。其實質(zhì)就是以不可導點為分界，把函數(shù)定義域分成若干段，然后對每段分別求導。這大大降低了GD法的應(yīng)用門檻。以我們后面要學的Tensorflow為例，它允許用戶使用幾乎所有可能的函數(shù)。某些不可導函數(shù)，例如relu（），甚至在其中扮演了極其重要的角色。