零基礎入門深度學習(7) - 遞歸神經網絡
機器學習深度學習入門
無論即將到來的是大數據時代還是人工智能時代，亦或是傳統行業使用人工智能在云上處理大數據的時代，作為一個有理想有追求的程序員，不懂深度學習（Deep ）這個超熱的技術，會不會感覺馬上就out了？現在救命稻草來了，《零基礎入門深度學習》系列文章旨在講幫助愛編程的你從零基礎達到入門級水平。零基礎意味著你不需要太多的數學知識，只要會寫程序就行了，沒錯，這是專門為程序員寫的文章。雖然文中會有很多公式你也許看不懂，但同時也會有更多的代碼，程序員的你一定能看懂的（我周圍是一群狂熱的Clean Code程序員，所以我寫的代碼也不會很差）。
文章列表
零基礎入門深度學習(1) - 感知器
零基礎入門深度學習(2) - 線性單元和梯度下降
零基礎入門深度學習(3) - 神經網絡和反向傳播算法
零基礎入門深度學習(4) - 卷積神經網絡
零基礎入門深度學習(5) - 循環神經網絡
零基礎入門深度學習(6) - 長短時記憶網絡(LSTM)
零基礎入門深度學習(7) - 遞歸神經網絡
往期回顧
在前面的文章中，我們介紹了循環神經網絡，它可以用來處理包含序列結構的信息。然而，除此之外，信息往往還存在著諸如樹結構、圖結構等更復雜的結構。對于這種復雜的結構，循環神經網絡就無能為力了。本文介紹一種更為強大、復雜的神經網絡：遞歸神經網絡 ( Neural Network, RNN)，以及它的訓練算法BPTS (Back Through )。顧名思義，遞歸神經網絡（巧合的是，它的縮寫和循環神經網絡一樣，也是RNN）可以處理諸如樹、圖這樣的遞歸結構。在文章的最后，我們將實現一個遞歸神經網絡，并介紹它的幾個應用場景。
遞歸神經網絡是啥
因為神經網絡的輸入層單元個數是固定的，因此必須用循環或者遞歸的方式來處理長度可變的輸入。循環神經網絡實現了前者，通過將長度不定的輸入分割為等長度的小塊，然后再依次的輸入到網絡中，從而實現了神經網絡對變長輸入的處理。一個典型的例子是，當我們處理一句話的時候，我們可以把一句話看作是詞組成的序列，然后，每次向循環神經網絡輸入一個詞，如此循環直至整句話輸入完畢，循環神經網絡將產生對應的輸出。如此，我們就能處理任意長度的句子了。入下圖所示：
然而，有時候把句子看做是詞的序列是不夠的，比如下面這句話『兩個外語學院的學生』：
上圖顯示了這句話的兩個不同的語法解析樹。可以看出來這句話有歧義，不同的語法解析樹則對應了不同的意思。一個是『兩個外語學院的/學生』，也就是學生可能有許多，但他們來自于兩所外語學校；另一個是『兩個/外語學院的學生』，也就是只有兩個學生，他們是外語學院的。為了能夠讓模型區分出兩個不同的意思，我們的模型必須能夠按照樹結構去處理信息，而不是序列，這就是遞歸神經網絡的作用。當面對按照樹/圖結構處理信息更有效的任務時，遞歸神經網絡通常都會獲得不錯的結果。
遞歸神經網絡可以把一個樹/圖結構信息編碼為一個向量，也就是把信息映射到一個語義向量空間中。這個語義向量空間滿足某類性質，比如語義相似的向量距離更近。也就是說，如果兩句話（盡管內容不同）它的意思是相似的，那么把它們分別編碼后的兩個向量的距離也相近；反之，如果兩句話的意思截然不同，那么編碼后向量的距離則很遠。如下圖所示：
從上圖我們可以看到，遞歸神經網絡將所有的詞、句都映射到一個2維向量空間中。句子『the country of my birth』和句子『the place where I was born』的意思是非常接近的，所以表示它們的兩個向量在向量空間中的距離很近。另外兩個詞『Germany』和『France』因為表示的都是地點，它們的向量與上面兩句話的向量的距離，就比另外兩個表示時間的詞『Monday』和『Tuesday』的向量的距離近得多。這樣，通過向量的距離，就得到了一種語義的表示。
上圖還顯示了自然語言可組合的性質：詞可以組成句、句可以組成段落、段落可以組成篇章，而更高層的語義取決于底層的語義以及它們的組合方式。遞歸神經網絡是一種表示學習，它可以將詞、句、段、篇按照他們的語義映射到同一個向量空間中，也就是把可組合（樹/圖結構）的信息表示為一個個有意義的向量。比如上面這個例子，遞歸神經網絡把句子"the country of my birth"表示為二維向量[1,5]。有了這個『編碼器』之后，我們就可以以這些有意義的向量為基礎去完成更高級的任務（比如情感分析等）。如下圖所示，遞歸神經網絡在做情感分析時，可以比較好的處理否定句，這是勝過其他一些模型的：
在上圖中，藍色表示正面評價，紅色表示負面評價。每個節點是一個向量，這個向量表達了以它為根的子樹的情感評價。比如" humor"是正面評價，而"care about wit or any other kind of humor"是中性評價。我們可以看到，模型能夠正確的處理doesn't的含義，將正面評價轉變為負面評價。
盡管遞歸神經網絡具有更為強大的表示能力，但是在實際應用中并不太流行。其中一個主要原因是，遞歸神經網絡的輸入是樹/圖結構，而這種結構需要花費很多人工去標注。想象一下，如果我們用循環神經網絡處理句子，那么我們可以直接把句子作為輸入。然而，如果我們用遞歸神經網絡處理句子，我們就必須把每個句子標注為語法解析樹的形式，這無疑要花費非常大的精力。很多時候，相對于遞歸神經網絡能夠帶來的性能提升，這個投入是不太劃算的。
我們已經基本了解了遞歸神經網絡是做什么用的，接下來，我們將探討它的算法細節。
遞歸神經網絡的前向計算
接下來，我們詳細介紹一下遞歸神經網絡是如何處理樹/圖結構的信息的。在這里，我們以處理樹型信息為例進行介紹。
遞歸神經網絡的輸入是兩個子節點（也可以是多個），輸出就是將這兩個子節點編碼后產生的父節點，父節點的維度和每個子節點是相同的。如下圖所示：
和分別是表示兩個子節點的向量，是表示父節點的向量。子節點和父節點組成一個全連接神經網絡，也就是子節點的每個神經元都和父節點的每個神經元兩兩相連。我們用矩陣表示這些連接上的權重，它的維度將是，其中，表示每個節點的維度。父節點的計算公式可以寫成：
式
在上式中，tanh是激活函數（當然也可以用其它的激活函數），是偏置項，它也是一個維度為的向量。如果讀過前面的文章，相信大家已經非常熟悉這些計算了，在此不做過多的解釋了。
然后，我們把產生的父節點的向量和其他子節點的向量再次作為網絡的輸入，再次產生它們的父節點。如此遞歸下去，直至整棵樹處理完畢。最終，我們將得到根節點的向量，我們可以認為它是對整棵樹的表示，這樣我們就實現了把樹映射為一個向量。在下圖中，我們使用遞歸神經網絡處理一棵樹，最終得到的向量，就是對整棵樹的表示：
舉個例子，我們使用遞歸神將網絡將『兩個外語學校的學生』映射為一個向量，如下圖所示：
最后得到的向量就是對整個句子『兩個外語學校的學生』的表示。由于整個結構是遞歸的，不僅僅是根節點，事實上每個節點都是以其為根的子樹的表示。比如，在左邊的這棵樹中，向量是短語『外語學院的學生』的表示，而向量是短語『外語學院的』的表示。
式1就是遞歸神經網絡的前向計算算法。它和全連接神經網絡的計算沒有什么區別，只是在輸入的過程中需要根據輸入的樹結構依次輸入每個子節點。
需要特別注意的是，遞歸神經網絡的權重和偏置項在所有的節點都是共享的。
遞歸神經網絡的訓練
遞歸神經網絡的訓練算法和循環神經網絡類似，兩者不同之處在于，前者需要將殘差從根節點反向傳播到各個子節點，而后者是將殘差從當前時刻反向傳播到初始時刻。
下面，我們介紹適用于遞歸神經網絡的訓練算法，也就是BPTS算法。
誤差項的傳遞
首先，我們先推導將誤差從父節點傳遞到子節點的公式，如下圖：
定義為誤差函數E相對于父節點的加權輸入的導數，即：
設是父節點的加權輸入，則
在上述式子里，、、都是向量，而是矩陣。為了看清楚它們的關系，我們將其展開：
在上面的公式中，表示父節點p的第i個分量；表示子節點的第i個分量；表示子節點的第i個分量；表示子節點的第k個分量到父節點p的第i個分量的的權重。根據上面展開后的矩陣乘法形式，我們不難看出，對于子節點來說，它會影響父節點所有的分量。因此，我們求誤差函數E對的導數時，必須用到全導數公式，也就是：
有了上式，我們就可以把它表示為矩陣形式，從而得到一個向量化表達：
其中，矩陣是從矩陣W中提取部分元素組成的矩陣。其單元為：
上式看上去可能會讓人暈菜，從下圖，我們可以直觀的看到到底是啥。首先我們把W矩陣拆分為兩個矩陣和，如下圖所示：
顯然，子矩陣和分別對應子節點和的到父節點權重。則矩陣為：
也就是說，將誤差項反向傳遞到相應子節點的矩陣就是其對應權重矩陣的轉置。
現在，我們設是子節點的加權輸入，是子節點c的激活函數，則：
這樣，我們得到：
如果我們將不同子節點對應的誤差項連接成一個向量。那么，上式可以寫成：
式
式2就是將誤差項從父節點傳遞到其子節點的公式。注意，上式中的也是將兩個子節點的加權輸入和連在一起的向量。
有了傳遞一層的公式，我們就不難寫出逐層傳遞的公式。
上圖是在樹型結構中反向傳遞誤差項的全景圖，反復應用式2，在已知的情況下，我們不難算出為：
在上面的公式中，，表示取向量屬于節點p的部分。
權重梯度的計算
根據加權輸入的計算公式：
其中，表示第l層的父節點的加權輸入，表示第l層的子節點。是權重矩陣，是偏置項。將其展開可得：
那么，我們可以求得誤差函數在第l層對權重的梯度為：
上式是針對一個權重項的公式，現在需要把它擴展為對所有的權重項的公式。我們可以把上式寫成矩陣的形式（在下面的公式中，m=2n）：
式
式3就是第l層權重項的梯度計算公式。我們知道，由于權重是在所有層共享的，所以和循環神經網絡一樣，遞歸神經網絡的最終的權重梯度是各個層權重梯度之和。即：
式
因為循環神經網絡的證明過程已經在零基礎入門深度學習(4) - 卷積神經網絡一文中給出，因此，遞歸神經網絡『為什么最終梯度是各層梯度之和』的證明就留給讀者自行完成啦。
接下來，我們求偏置項的梯度計算公式。先計算誤差函數對第l層偏置項的梯度：
把上式擴展為矩陣的形式：
式
式5是第l層偏置項的梯度，那么最終的偏置項梯度是各個層偏置項梯度之和，即：
式
權重更新
如果使用梯度下降優化算法，那么權重更新公式為：
其中，是學習速率常數。把式4帶入到上式，即可完成權重的更新。同理，偏置項的更新公式為：
把式6帶入到上式，即可完成偏置項的更新。
這就是遞歸神經網絡的訓練算法BPTS。由于我們有了前面幾篇文章的基礎，相信讀者們理解BPTS算法也會比較容易。
遞歸神經網絡的實現
完整代碼請參考GitHub:(python2.7)
現在，我們實現一個處理樹型結構的遞歸神經網絡。
在文件的開頭，加入如下代碼：
?#!/usr/bin/env python# -*- coding: UTF-8 -*-import numpy as npfrom cnn tor
上述四行代碼非常簡單，沒有什么需要解釋的。激活函數是在我們介紹卷積神經網絡時寫的，現在引用一下它。
我們首先定義一個樹節點結構，這樣，我們就可以用它保存卷積神經網絡生成的整棵樹：
?(object):def (self, data, =[], =[]):self.parent =. = . = .data = datafor child in :child.parent = self
接下來，我們把遞歸神經網絡的實現代碼都放在類中，下面是這個類的構造函數：
?# 遞歸神經網絡實現(object):def (self, , ,, ):'''遞歸神經網絡構造函數: 表示每個節點的向量的維度: 每個父節點有幾個子節點: 激活函數對象: 梯度下降算法學習率'''self. = . = . = . = # 權重數組Wself.W = np.random.uniform(-1e-4,1e-4,(, * ))# 偏置項bself.b = np.zeros((,1))# 遞歸神經網絡生成的樹的根節點self.root =None
下面是前向計算的實現：
?def forward(self,*):'''前向計算''' = self.() = self..forward(np.dot(self.W, )+ self.b)self.root =(, , )
forward函數接收一系列的樹節點對象作為輸入，然后，遞歸神經網絡將這些樹節點作為子節點，并計算它們的父節點。最后，將計算的父節點保存在self.root變量中。
上面用到的函數，是將各個子節點中的數據拼接成一個長向量，其代碼如下：
?def (self, ):'''將各個樹節點中的數據拼接成一個長向量'''concat = np.zeros((0,1))for node in :concat = np.((concat, node.data))return concat
下面是反向傳播算法BPTS的實現：
?def (self, ):'''BPTS反向傳播算法'''self。(, self。root)self。W_grad, self。b_grad = self。(self。root)def (self, , parent):'''計算每個節點的delta'''parent。delta = parent。:# 根據式2計算每個子節點的 = np。dot(self。W。T, )*(self。。(parent。))# slices = [(子節點編號，子節點delta起始位置，子節點delta結束位置)]slices =[(i, i * self。,(i +1)* self。
)for i in range(self。)]# 針對每個子節點，遞歸調用函數for s in slices:self。([s[1]:s[2]],parent。[s[0]])def (self, parent):'''計算每個節點權重的梯度，并將它們求和，得到最終的梯度'''W_grad = np。zeros((self。,self。 * self。))b_grad = np。zeros((self。,1))ifnot parent。:return W_grad, 。W_grad = np。dot(parent。delta, parent。。T)parent。b_grad = parent。 += parent。 += parent。 child in parent。:W, b = self。(child)W_grad += Wb_grad += breturn W_grad, b_grad
在上述算法中，函數和函數分別計算各個節點的誤差項以及最終的梯度。它們都采用遞歸算法，先序遍歷整個樹，并逐一完成每個節點的計算。
下面是梯度下降算法的實現（沒有weight decay），這個非常簡單：
?def update(self):'''使用SGD算法更新權重'''self.W -=self. *self..b -=self. *self.b_grad