基于時間的反向傳播算法BPTT（Backpropagation through time）

本文是讀“Recurrent Neural Networks Tutorial, Part 3 – Backpropagation Through Time and Vanishing Gradients”的讀書筆記，加入了自己的一些了解，有興趣可以直接閱讀原文。

1. 算法介紹

這裡引用原文中的網絡結構圖

其中 x x x為輸入， s s s為隐藏層狀态，o為輸出，按時間展開

為了與文獻中的表示一緻，我們用 y ^ \hat y y^​來代替o，則

s t = t a n h ( U x t + W s t − 1 ) y ^ = s o f t m a t ( V s t ) s_t=tanh(Ux_t+Ws_{t-1}) \\ \hat y=softmat(Vs_t) st​=tanh(Uxt​+Wst−1​)y^​=softmat(Vst​)

使用交叉熵（cross entropy）作為損失函數

E t ( y , y ^ ) = − y t l o g y ^ E ( y , y ^ ) = ∑ t E t ( y t , y ^ t ) = − ∑ t y t l o g y ^ E_t(y,\hat y)=-y_tlog\hat y \\ E(y, \hat y) = \sum_t E_t(y_t, \hat y_t)=-\sum_t y_tlog\hat y Et​(y,y^​)=−yt​logy^​E(y,y^​)=t∑​Et​(yt​,y^​t​)=−t∑​yt​logy^​

我們使用鍊式法則來計算後向傳播時的梯度，以網絡的輸出 E 3 E_3 E3​為例，

y ^ 3 = e z 3 ∑ i e z i E 3 = − y 3 l o g y ^ 3 = − y 3 ( z 3 − l o g ∑ i e z i ) z 3 = V s 3 s 3 = t a n h ( U x 3 + W s 2 ) \hat y_3=\frac{e^{z_3}}{\sum_ie^{z_i}} \\ E_3=-y_3log\hat y_3=-y_3(z_3-log\sum_ie^{z_i}) \\ z_3=Vs_3 \\ s_3=tanh(Ux_3+Ws_2) y^​3​=∑i​ezi​ez3​​E3​=−y3​logy^​3​=−y3​(z3​−logi∑​ezi​)z3​=Vs3​s3​=tanh(Ux3​+Ws2​)

是以可以求V的梯度

∂ E 3 ∂ V = ∂ E 3 ∂ z ^ 3 ∂ z 3 ∂ V = y 3 ( y ^ 3 − 1 ) ∗ s 3 \frac{\partial E_3}{\partial V}=\frac{\partial E_3}{\partial \hat z_3}\frac{\partial z_3}{\partial V}=y_3(\hat y_3-1)*s3 ∂V∂E3​​=∂z^3​∂E3​​∂V∂z3​​=y3​(y^​3​−1)∗s3

這裡求導時将 y ^ 3 \hat y_3 y^​3​帶入消去了，求導更直覺，這裡給出的是标量形式，改成向量形式應該是 y ^ − 1 3 \hat y-1_3 y^​−13​，也就是輸出機率矩陣中，對應結果的那個機率-1，其他不變，而輸入y恰好可以認為是對應結果的機率是1，其他是0，是以原文中寫作

∂ E 3 ∂ V = ( y ^ 3 − y 3 ) ⊗ s 3 \frac{\partial E_3}{\partial V}=(\hat y_3-y_3)\otimes s_3 ∂V∂E3​​=(y^​3​−y3​)⊗s3​

相對V的梯度，因為 s t s_t st​是W，U的函數，而且含有的 s t − 1 s_{t-1} st−1​在 求導時，不能簡單的認為是一個常數，是以在求導時，如果不加限制，需要對從t到0的所有狀态進行回溯，在實際中一般按照場景和精度要求進行截斷。

∂ E 3 ∂ W = ∂ E 3 ∂ z ^ 3 ∂ z 3 ∂ s 3 ∂ s 3 ∂ s k ∂ s k ∂ W \frac{\partial E_3}{\partial W}=\frac{\partial E_3}{\partial \hat z_3}\frac{\partial z_3}{\partial s_3}\frac{\partial s_3}{\partial s_k}\frac{\partial s_k}{\partial W} ∂W∂E3​​=∂z^3​∂E3​​∂s3​∂z3​​∂sk​∂s3​​∂W∂sk​​

其中 s 3 s_3 s3​對W的求導是一個分部求導

∂ s t ∂ W = ( 1 − s t 2 ) ( s t − 1 + W ∗ ∂ s t − 1 ∂ s W ) \frac{\partial s_t}{\partial W}=(1-s_t^2)(s_{t-1}+W*\frac{\partial s_{t-1}}{\partial s_{W}}) ∂W∂st​​=(1−st2​)(st−1​+W∗∂sW​∂st−1​​)

U的梯度類似

∂ s t ∂ U = ( 1 − s t 2 ) ( x t + W ∗ ∂ s t − 1 ∂ s U ) \frac{\partial s_t}{\partial U}=(1-s_t^2)(x_t+W*\frac{\partial s_{t-1}}{\partial s_{U}}) ∂U∂st​​=(1−st2​)(xt​+W∗∂sU​∂st−1​​)

2. 代碼分析

首先我們給出作者自己實作的完整的BPTT，再各部分分析

def bptt(self, x, y):
    T = len(y)
    # Perform forward propagation
    o, s = self.forward_propagation(x)
    # We accumulate the gradients in these variables
    dLdU = np.zeros(self.U.shape)
    dLdV = np.zeros(self.V.shape)
    dLdW = np.zeros(self.W.shape)
    delta_o = o
    delta_o[np.arange(len(y)), y] -= 1.
    # For each output backwards...
    for t in np.arange(T)[::-1]:
        dLdV += np.outer(delta_o[t], s[t].T)
        # Initial delta calculation: dL/dz
        delta_t = self.V.T.dot(delta_o[t]) * (1 - (s[t] ** 2))
        # Backpropagation through time (for at most self.bptt_truncate steps)
        for bptt_step in np.arange(max(0, t-self.bptt_truncate), t+1)[::-1]:
            # print "Backpropagation step t=%d bptt step=%d " % (t, bptt_step)
            # Add to gradients at each previous step
            dLdW += np.outer(delta_t, s[bptt_step-1])              
            dLdU[:,x[bptt_step]] += delta_t
            # Update delta for next step dL/dz at t-1
            delta_t = self.W.T.dot(delta_t) * (1 - s[bptt_step-1] ** 2)
    return [dLdU, dLdV, dLdW]
           

2.1. 初始化

結合完整的代碼，我們可知梯度的次元

#100*8000
dLdU = np.zeros(self.U.shape)
#8000*100
dLdV = np.zeros(self.V.shape)
#100*100
dLdW = np.zeros(self.W.shape)
           

2.2. 公共部分

對照上面的理論可知，無論是V，還是U，W，都有 ∂ E 3 ∂ z ^ 3 \frac{\partial E_3}{\partial \hat z_3} ∂z^3​∂E3​​，這部分可以預先計算出來，也就是代碼中的delta_o

#o是forward的輸出，T（句子的實際長度）*8000維,每一行是8000維的，就是詞表中所有詞作為輸入x中每一個詞的後一個詞的機率
delta_o = o
#[]中是索引操作，對y中的詞對應的索引的機率-1
delta_o[np.arange(len(y)), y] -= 1.
           

2.3. V的梯度

s [ t ] . T s[t].T s[t].T是取 s [ t ] s[t] s[t]的轉置，numpy.outer是将第一個參數和第二個參數中的所有元素分别按行展開，然後拿第一個參數中的數是以乘以第二個參數的每一行，例如 a = [ a 0 , a 1 , . . . , a M ] a=[a_0, a_1, ..., a_M] a=[a0​,a1​,...,aM​], b = [ b 0 , b 1 , . . . , b N ] b=[b_0, b_1, ..., b_N] b=[b0​,b1​,...,bN​]，則相乘後變成

[ [ a 0 ∗ b 0 a 0 ∗ b 1 . . . a 0 ∗ b N ] [ a 1 ∗ b 0 a 1 ∗ b 1 . . . a 1 ∗ b N ] . . . [ a M ∗ b 0 a M ∗ b 1 . . . a M ∗ b N ] ] [[a_0*b_0\quad a_0*b_1 \quad ... \quad a_0*b_N] \\ [a_1*b_0\quad a_1*b_1 \quad ... \quad a_1*b_N] \\ ... \\ [a_M*b_0\quad a_M*b_1 \quad ... \quad a_M*b_N]] [[a0​∗b0​a0​∗b1​...a0​∗bN​][a1​∗b0​a1​∗b1​...a1​∗bN​]...[aM​∗b0​aM​∗b1​...aM​∗bN​]]

結果是M*N維的

#delta_o是1*8000維向量，s[t]是1*100的向量，轉不轉置對outer并沒有什麼差別，其實和delta_o[t].T * s[t]等價，*是矩陣相乘，結果是8000*100維的矩陣
dLdV += np.outer(delta_o[t], s[t].T)
           

2.4. W和U的梯度

對比W和U的梯度公式，我們可以看到，兩者+号的第二部分前面的系數是一樣的，也就是 ( 1 − s t 2 ) ∗ W (1-s_t^2)*W (1−st2​)∗W，這部分可以存起來減少計算量，也就是代碼中的delta_t

delta_t = self.V.T.dot(delta_o[t]) * (1 - (s[t] ** 2)) 
# Backpropagation through time (for at most self.bptt_truncate steps)
#截斷
for bptt_step in np.arange(max(0, t-self.bptt_truncate), t+1)[::-1]:
    # print "Backpropagation step t=%d bptt step=%d " % (t, bptt_step)
    # Add to gradients at each previous step
    #計算+号的第一部分，第二部分本次還沒得到，下次累加進來
    dLdW += np.outer(delta_t, s[bptt_step-1])
    #x為單詞的位置向量，與delta_t相乘相當于dLdU按x取索引（對應的詞向量）直接與delta_t相加                                  
    dLdU[:,x[bptt_step]] += delta_t
    # Update delta for next step dL/dz at t-1 
    #更新第二部分系數
    delta_t = self.W.T.dot(delta_t) * (1 - s[bptt_step-1] ** 2)