第2章
Chapter Two
反向傳播算法

2.1 導數和導數的應用

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

2.1.1 導數

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

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

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

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

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

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

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

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

算法2－1 根據導數迭代求解最優解（迭代求解算法）

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

2）按照一定循環條件，反復執行：

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

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

c）令x＝x+Δx。

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

輸出結果如下：

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

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

2.1.2 梯度下降法求函數的最小值

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

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

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

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

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

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

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

輸出結果：

（－1.9999999999999947，2.9999999999999893）

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

2.1.3 牛頓法求平方根

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

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

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

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

輸出結果如下：

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

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

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

解答：切線的斜率滿足

而根據牛頓法有：

把y′代入，得：

Δx＝x_b－x_a

所以：

x ₂＝x_a+Δx＝x_b

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

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

2.1.4 復合函數和鏈式法則

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

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

若設y＝sin（x），z＝3y²，則有：

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

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

2.1.5 多元函數和全微分方程

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

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

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

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

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

由于深度學習的目的是透過現象看本質，根據原函數計算逆函數，所以依賴關系圖和上述計算偏導的過程就構成了整個深度學習大廈的基石。所有深度學習的算法、理論和模型幾乎都是建立在這個基礎上的。

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

2.1.6 反向傳播算法

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

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

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

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

deriv（y，graph）

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

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

2）構建集合open＝｛y｝，用來保存可以計算偏導的結點。

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

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

b）從open集合中刪除t。

c）sum＝0。

d）對t的每個后繼結點p，執行：

sum＝sum+▽［p］

e）令▽［t］ ＝sum。

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

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

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

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

2.1.7 梯度

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

1）▽_y＝1，y是網絡的最后一個結點。

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

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

2.1.8 分段求導

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

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

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

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

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

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