雷鋒網(wǎng)按：如果對(duì)人工智能稍有了解的小伙伴們，或多或少都聽過(guò)反向傳播算法這個(gè)名詞，但實(shí)際上BP到底是什么？它有著怎樣的魅力與優(yōu)勢(shì)？本文發(fā)布于 offconvex.org，作者 Sanjeev Arora與 Tengyu Ma，雷鋒網(wǎng)對(duì)此進(jìn)行了編譯，未經(jīng)許可不得轉(zhuǎn)載。

目前網(wǎng)絡(luò)上關(guān)于反向傳播算法的教程已經(jīng)很多，那我們還有必要再寫一份教程嗎？答案是‘需要’。

為什么這么說(shuō)呢？我們教員Sanjeev最近要給本科生上一門人工智能的課，盡管網(wǎng)上有很多反向傳播算法的教程，但他卻找不到一份令他滿意的教程，因此我們決定自己寫一份關(guān)于反向傳播算法的教程，介紹一下反向傳播算法的歷史背景、原理、以及一些最新研究成果。

PS：本文默認(rèn)讀者具備一定的基礎(chǔ)知識(shí)（如了解梯度下降、神經(jīng)網(wǎng)絡(luò)等概念）。

一、什么是反向傳播算法？

反向傳播算法是訓(xùn)練神經(jīng)網(wǎng)絡(luò)的經(jīng)典算法。在20世紀(jì)70年代到80年代被多次重新定義。它的一些算法思想來(lái)自于60年代的控制理論。

在輸入數(shù)據(jù)固定的情況下、反向傳播算法利用神經(jīng)網(wǎng)絡(luò)的輸出敏感度來(lái)快速計(jì)算出神經(jīng)網(wǎng)絡(luò)中的各種超參數(shù)。尤其重要的是，它計(jì)算輸出f對(duì)所有的參數(shù)w的偏微分，即如下所示：?f/?wi，f代表神經(jīng)元的輸出，wi是函數(shù)f的第i個(gè)參數(shù)。參數(shù)wi代表網(wǎng)絡(luò)的中邊的權(quán)重或者神經(jīng)元的閾值，神經(jīng)元的激活函數(shù)具體細(xì)節(jié)并不重要，它可以是非線性函數(shù)Sigmoid或RELU。這樣就可以得到f相對(duì)于網(wǎng)絡(luò)參數(shù)的梯度?f ，有了這個(gè)梯度，我們就可以使用梯度下降法對(duì)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，即每次沿著梯度的負(fù)方向（??f）移動(dòng)一小步，不斷重復(fù)，直到網(wǎng)絡(luò)輸出誤差最小。

在神經(jīng)網(wǎng)絡(luò)訓(xùn)練過(guò)程中，我們需要注意的是，反向傳播算法不僅需要準(zhǔn)確計(jì)算梯度。還需要使用一些小技巧對(duì)我們的網(wǎng)絡(luò)進(jìn)行訓(xùn)練。理解反向傳播算法可以幫助我們理解那些在神經(jīng)網(wǎng)絡(luò)訓(xùn)練過(guò)程中使用的小技巧。

反向傳播算法之所以重要，是因?yàn)樗男矢摺?/strong>假設(shè)對(duì)一個(gè)節(jié)點(diǎn)求偏導(dǎo)需要的時(shí)間為單位時(shí)間，運(yùn)算時(shí)間呈線性關(guān)系，那么網(wǎng)絡(luò)的時(shí)間復(fù)雜度如下式所示：O(Network Size)=O(V+E)，V為節(jié)點(diǎn)數(shù)、E為連接邊數(shù)。這里我們唯一需要用的計(jì)算方法就是鏈?zhǔn)椒▌t，但應(yīng)用鏈?zhǔn)椒▌t會(huì)增加我們二次計(jì)算的時(shí)間，由于有成千上萬(wàn)的參數(shù)需要二次計(jì)算，所以效率就不會(huì)很高。為了提高反向傳播算法的效率，我們通過(guò)高度并行的向量，利用GPU進(jìn)行計(jì)算。

注：業(yè)內(nèi)人士可能已經(jīng)注意到在標(biāo)準(zhǔn)的神經(jīng)網(wǎng)絡(luò)訓(xùn)練中，我們實(shí)際上關(guān)心的是訓(xùn)練損失函數(shù)的梯度，這是一個(gè)與網(wǎng)絡(luò)輸出有關(guān)的簡(jiǎn)單函數(shù)，但是上文所講的更具有普遍意義，因?yàn)樯窠?jīng)網(wǎng)絡(luò)是可以增加新的輸出節(jié)點(diǎn)的，此時(shí)我們要求的就是新的網(wǎng)絡(luò)輸出與網(wǎng)絡(luò)超參數(shù)的偏微分。

二、問(wèn)題設(shè)置

反向傳播算法適用于有向非循環(huán)網(wǎng)絡(luò)，為了不失一般性，非循環(huán)神經(jīng)網(wǎng)絡(luò)可以看做是一個(gè)多層神經(jīng)網(wǎng)絡(luò)，第t+1層神經(jīng)元的輸入來(lái)自于第t層及其下層。我們使用f表示網(wǎng)絡(luò)輸出，在本文中我們認(rèn)為神經(jīng)網(wǎng)絡(luò)是一個(gè)上下結(jié)構(gòu)，底部為輸入，頂部為輸出。

規(guī)則1：為了先計(jì)算出參數(shù)梯度，先求出 ?f/?u ，即表示輸出f對(duì)節(jié)點(diǎn)u的偏微分。

我們使用規(guī)則1來(lái)簡(jiǎn)化節(jié)點(diǎn)偏微分計(jì)算。下面我將具體說(shuō)一下?f/?u的含義。我們做如下假設(shè)，先刪除節(jié)點(diǎn)u的所有輸入節(jié)點(diǎn)。然后保持網(wǎng)絡(luò)中的參數(shù)不變。現(xiàn)在我們改變u的值，此時(shí)與u相連的高層神經(jīng)元也會(huì)受到影響，在這些高層節(jié)點(diǎn)中，輸出f也會(huì)受到影響。那么此時(shí)?f/?u就表示當(dāng)節(jié)點(diǎn)u變化時(shí)，節(jié)點(diǎn)f的變化率。

規(guī)則1就是鏈?zhǔn)椒▌t的直接應(yīng)用，如下圖所示，u是節(jié)點(diǎn) z1,…,zm的加權(quán)求和，即u=w1*z1+?+wn*zn，然后通過(guò)鏈?zhǔn)椒▌t對(duì)w1求偏導(dǎo)數(shù)，具體如下：

由上式所示，只有先計(jì)算?f/?u，然后才能計(jì)算?f/?w1。

多元鏈?zhǔn)椒▌t

為了計(jì)算節(jié)點(diǎn)的偏微分，我們先回憶一下多元鏈?zhǔn)椒▌t，多元鏈?zhǔn)椒▌t常用來(lái)描述偏微分之間的關(guān)系。 即假設(shè)f是關(guān)于變量u1,…,un的函數(shù)，而u1,…,un又都是關(guān)于變量z的函數(shù)，那么f關(guān)于z的偏導(dǎo)數(shù)如下：

這是鏈?zhǔn)椒▌t2的一般式，是鏈?zhǔn)椒▌t的1的子式。這個(gè)鏈?zhǔn)椒▌t很適合我們的反向傳播算法。下圖就是一個(gè)符合多元鏈?zhǔn)椒▌t的神經(jīng)網(wǎng)絡(luò)示意圖。

如上圖所示，先計(jì)算f相對(duì)于u1,…,un的偏導(dǎo)數(shù)，然后將這些偏導(dǎo)數(shù)按權(quán)重線性相加，得到f對(duì)z的偏導(dǎo)數(shù)。這個(gè)權(quán)重就是u1,…,un對(duì)z的偏導(dǎo)，即?uj/?z。此時(shí)問(wèn)題來(lái)了，我么怎么衡量計(jì)算時(shí)間呢？為了與教課書中保持一致，我們做如下假設(shè)：u節(jié)點(diǎn)位于t+1層的，z節(jié)點(diǎn)位于t層或t層以下的子節(jié)點(diǎn)，此時(shí)我們記?u/?z的運(yùn)算時(shí)間為單位時(shí)間。

樸素前饋算法（低效算法）

我們首先要指出鏈?zhǔn)椒▌t是包含二次計(jì)算的時(shí)間。許多作者都不屑于講這種算法，直接跳過(guò)的。這就好比我們?cè)谏纤惴ㄅ判蛘n時(shí)，老師都是直接講快速排序的，像那些低效排序算法都是直接跳過(guò)不講的。

樸素算法就是計(jì)算節(jié)點(diǎn)對(duì)ui與uj之間偏導(dǎo)數(shù)，在這里節(jié)點(diǎn)ui的層級(jí)要比uj高。在V*V個(gè)節(jié)點(diǎn)對(duì)的偏導(dǎo)值中包含?f/?ui的值，因?yàn)閒本身就是一個(gè)節(jié)點(diǎn)，只不過(guò)這個(gè)節(jié)點(diǎn)比較特殊，它是一個(gè)輸出節(jié)點(diǎn)。

我們以前饋的形式進(jìn)行計(jì)算。我們計(jì)算了位于t層及t層以下的所有節(jié)點(diǎn)對(duì)之間的偏導(dǎo)數(shù)，那么位于t+1層的ul對(duì)uj的偏導(dǎo)數(shù)就等于將所有ui與uj的偏導(dǎo)數(shù)進(jìn)行線性加權(quán)相加。固定節(jié)點(diǎn)j，其時(shí)間復(fù)雜度與邊的數(shù)量成正比，而j是有V個(gè)值，此時(shí)時(shí)間復(fù)雜度為O(VE)。

三、反向傳播算法（線性時(shí)間）

反向傳播算法如其名所示，就是反向計(jì)算偏微分，信息逆向傳播，即從神經(jīng)網(wǎng)絡(luò)的高層向底層反向傳播。

信息協(xié)議：節(jié)點(diǎn)u通過(guò)高層節(jié)點(diǎn)獲取信息，節(jié)點(diǎn)u獲取的信息之和記做S。u的低級(jí)節(jié)點(diǎn)z獲取的信息為S??u/?z

很明顯，每個(gè)節(jié)點(diǎn)的計(jì)算量與其連接的神經(jīng)元個(gè)數(shù)成正比，整個(gè)網(wǎng)絡(luò)的計(jì)算量等于所有節(jié)點(diǎn)運(yùn)算時(shí)間之和，所有節(jié)點(diǎn)被計(jì)算兩次，故其時(shí)間復(fù)雜度為O(Network Size)。

我們做如下證明：S等于?f/?z。

證明如下：當(dāng)z為輸出層時(shí)，此時(shí)?f/?z=?f/?f=1

假如對(duì)于t+1層及其高層假設(shè)成立，節(jié)點(diǎn)u位于t層，它的輸出邊與t+1層的u1,u2,…,um節(jié)點(diǎn)相連，此時(shí)節(jié)點(diǎn)從某個(gè)節(jié)點(diǎn)j收到的信息為(?f/?uj)×(?uj/?z)，根據(jù)鏈?zhǔn)椒▌t，節(jié)點(diǎn)z收到的總信息為S=

四、自動(dòng)微分

在上文中，關(guān)于神經(jīng)網(wǎng)絡(luò)、節(jié)點(diǎn)計(jì)算，我們并沒(méi)有細(xì)講。下面我們將具體講一下，我們將節(jié)點(diǎn)與節(jié)點(diǎn)之間的計(jì)算看做是一個(gè)無(wú)環(huán)圖模型，許多自動(dòng)計(jì)算微分的工具包（如：autograd，tensorflow）均采用這一模型。這些工具就是通過(guò)這個(gè)無(wú)向圖模型來(lái)計(jì)算輸出與網(wǎng)絡(luò)參數(shù)的偏導(dǎo)數(shù)的。

我們首先注意到法則1就是對(duì)這個(gè)的一般性描述，這個(gè)之所以不失一般性是因?yàn)槲覀兛梢詫⑦叺臋?quán)值也看做節(jié)點(diǎn)(即葉節(jié)點(diǎn))。這個(gè)很容易轉(zhuǎn)換，如下圖所示，左側(cè)是原始網(wǎng)絡(luò)，即一個(gè)單節(jié)點(diǎn)和其輸入節(jié)點(diǎn)、輸入節(jié)點(diǎn)的權(quán)重。右側(cè)是將邊的權(quán)重轉(zhuǎn)換為葉節(jié)點(diǎn)。網(wǎng)絡(luò)中的其它節(jié)點(diǎn)也做類似轉(zhuǎn)換。

只要局部偏導(dǎo)數(shù)計(jì)算的效率足夠高，那么我們就可以利用上文所說(shuō)的信息協(xié)議來(lái)計(jì)算各個(gè)節(jié)點(diǎn)的偏微分。即對(duì)節(jié)點(diǎn)u來(lái)講，我們應(yīng)該先找出它的的輸入節(jié)點(diǎn)有哪些，即z1,…,zn。然后計(jì)算在u的偏微分的基礎(chǔ)上計(jì)算zj的偏微分，由于輸出f對(duì)u的偏微分記做S，所以計(jì)算輸出f對(duì)zj的偏微分就是S??u?zj

這個(gè)算法可以按照如下規(guī)則分塊計(jì)算，首先明確節(jié)點(diǎn)u與輸入節(jié)點(diǎn)z1,…,zn 的關(guān)系，然后就是怎么計(jì)算偏導(dǎo)數(shù)的倍數(shù)（權(quán)重）S。即S??u/?zj。

擴(kuò)展到向量空間：為了提高偏微分權(quán)重的計(jì)算效率，我們可以將節(jié)點(diǎn)的輸出也變?yōu)橐粋€(gè)向量（矩陣或張量）。此時(shí)我們將?u/?zj?S改寫為?u/?zj[S], 這個(gè)與我們的反向傳播算法思想是一致的，在反向傳播算法中，y是一個(gè)p維向量，x是一個(gè)q維向量，y是關(guān)于x的函數(shù)，我們用?y/?x來(lái)表示由 ?yj/?xi所組成的q*p矩陣。聰明的讀者很快就會(huì)發(fā)現(xiàn)，這就是我們數(shù)學(xué)中的雅克比矩陣。此外我們還可以證明S與u的維度相同、?u?zj[S] 與zj的維度也相同。

如下圖所示，W是一個(gè)d2*d3的矩陣，Z是一個(gè)d1*d2的矩陣，U=WZ故U是一個(gè)d1*d3維的矩陣，此時(shí)我們計(jì)算?U/?Z，最終得到一個(gè)d2d3×d1d3維的矩陣。但我們?cè)诜聪騻鞑ニ惴ㄖ?，這個(gè)會(huì)算的很快，因?yàn)?U/?Z[S]=W?S，在計(jì)算機(jī)中我們可以使用GPU來(lái)進(jìn)行類似向量計(jì)算。

五、重要知識(shí)擴(kuò)展

1、權(quán)重共享

在許多神經(jīng)網(wǎng)絡(luò)框架中，設(shè)計(jì)者想要是一些神經(jīng)元的參數(shù)能夠共享，這些參數(shù)包括邊的權(quán)重或者節(jié)點(diǎn)的閾值參數(shù)。例如，在卷積神經(jīng)網(wǎng)絡(luò)中，同一個(gè)卷集核使用的參數(shù)都是一樣的。簡(jiǎn)而言之，就是a、b是兩個(gè)不同的參數(shù)，但我們強(qiáng)制要求a與b的值相同，即參數(shù)共享。這就好比我們給神經(jīng)網(wǎng)絡(luò)新增一個(gè)節(jié)點(diǎn)u，并且節(jié)點(diǎn)u與a和b相連，并且a=u，b=u.，此時(shí)根據(jù)鏈?zhǔn)椒▌t，?f/?u=(?f/?a)?(?a/?u)+(?f/?b)?(?b/?u)=?f/?a+?f/?b. 因此，對(duì)一個(gè)共享參數(shù)而言，其梯度就是輸出與參數(shù)節(jié)點(diǎn)之間的中間節(jié)點(diǎn)的偏導(dǎo)數(shù)之和。

2、反向傳播算法在循環(huán)神經(jīng)網(wǎng)絡(luò)的應(yīng)用

上面我們講的是非循環(huán)神經(jīng)網(wǎng)絡(luò)，許多前沿應(yīng)用（機(jī)器翻譯、語(yǔ)言理解）往往使用有向循環(huán)神經(jīng)網(wǎng)絡(luò)。在這種結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)中會(huì)存在記憶單元或注意力機(jī)制，在這些單元或機(jī)制中往往存在復(fù)雜的求導(dǎo)計(jì)算。一開始我們使用梯度下降法訓(xùn)練網(wǎng)絡(luò)，即在時(shí)間序列上對(duì)神經(jīng)網(wǎng)絡(luò)使用反向傳播算法，即對(duì)這個(gè)有向環(huán)狀結(jié)構(gòu)進(jìn)行無(wú)限循環(huán)，每一次循環(huán)的網(wǎng)絡(luò)結(jié)構(gòu)、網(wǎng)絡(luò)參數(shù)都是一樣的，但是網(wǎng)絡(luò)的輸入與輸出是不一樣的。在實(shí)際應(yīng)用中我們會(huì)遇到梯度爆炸或梯度消失等問(wèn)題，這些都會(huì)對(duì)結(jié)果收斂產(chǎn)生影響。為了解決這些問(wèn)題，我們使用梯度剪切或者長(zhǎng)短記憶模型（LSTM）等技術(shù)解決上述問(wèn)題。

環(huán)狀神經(jīng)網(wǎng)絡(luò)可以高效計(jì)算梯度的事實(shí)促進(jìn)了有記憶網(wǎng)絡(luò)甚至數(shù)據(jù)結(jié)構(gòu)的發(fā)展。使用梯度下降法，我們可可以對(duì)環(huán)狀結(jié)構(gòu)神經(jīng)網(wǎng)絡(luò)進(jìn)行優(yōu)化，尋找最佳參數(shù)，使得這個(gè)網(wǎng)絡(luò)可以解決特定計(jì)算問(wèn)題。梯度下降法的極限目前仍在探索中。

3、海森向量乘積計(jì)算耗時(shí)

在近似線性時(shí)間中，我們不僅可以使用梯度下降法，或許我們也可以使用2階導(dǎo)數(shù)對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化。在優(yōu)化過(guò)程中，最關(guān)鍵的一步是計(jì)算海森矩陣與一個(gè)向量的積，下面我將向大家介紹如何在規(guī)模是O(Network size)的神經(jīng)網(wǎng)絡(luò)應(yīng)用上述思想，這個(gè)例子與前面所講稍有不同，我們的初始神經(jīng)網(wǎng)絡(luò)應(yīng)該是一個(gè)用反向傳播算法進(jìn)行簡(jiǎn)單優(yōu)化過(guò)的神經(jīng)網(wǎng)絡(luò)。

法則：假設(shè)在無(wú)環(huán)神經(jīng)網(wǎng)絡(luò)中，有V個(gè)節(jié)點(diǎn)，E條邊，網(wǎng)絡(luò)輸出為f，葉節(jié)點(diǎn)為z1,…,zm，那么必存在一個(gè)大小為O(V+E)的網(wǎng)絡(luò)，這個(gè)網(wǎng)絡(luò)的的輸入節(jié)點(diǎn)為z1,…,zm，輸出節(jié)點(diǎn)為?f/?z1,…,?f/?zm。

上面的定理可以通過(guò)在無(wú)環(huán)神經(jīng)網(wǎng)絡(luò)中實(shí)現(xiàn)消息直接傳遞來(lái)證明，緊接著我們將解釋一下如何計(jì)算?2f(z)?v。設(shè)g(z)=??f(z),v? ，有定理可知， g(z)可以由大小是O(V+E)神經(jīng)網(wǎng)絡(luò)計(jì)算得到，同理我們?cè)俅螒?yīng)用法則，在這個(gè)大小是O(V+E)的網(wǎng)絡(luò)計(jì)算g(z)的梯度，此時(shí)?g(z)=?2f(z)?v，此時(shí)我們就算出了海森矩陣與向量積的積，此時(shí)耗費(fèi)的時(shí)間復(fù)雜度就是網(wǎng)絡(luò)規(guī)模的大小。

以上便是BP學(xué)習(xí)過(guò)程中需要了解的一些內(nèi)容，雷鋒網(wǎng)希望能讓你在學(xué)習(xí)過(guò)程中得到一個(gè)比較清晰的思路。當(dāng)然，也歡迎你關(guān)注雷鋒網(wǎng)旗下公眾號(hào)“AI科技評(píng)論”與我們交流哦。

via Back-propagation, an introduction

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。