《Online Segment to Segment Neural Transduction》閱讀筆記

01-31

轉載請註明出處：西土城的搬磚日常

原文鏈接：Online Segment to Segment Neural Transduction

文章來源：EMNLP, 2016

學術機構：牛津大學，DeepMind

研究問題：Seq2Seq問題online模式，解決句子級文本摘要，詞形變化等問題；

摘要：

這篇文章的工作與之前經常提到的Seq2Seq的研究工作有比較大的不同，常見的Seq2Seq的框架中，都是輸入序列處理（encoding）完畢之後才會開始生成（decoding）輸出序列，而本文提出的模型是在輸入序列輸入的同時交替進行encoding與decoding；文章工作是受到了 Statistical Translation中的基於HMM（隱馬爾科夫模型）的Alignment model（對齊模型）的啟發，主要的學習演算法也類似於HMM的前向後向學習演算法，整體來說，本文的模型是一個貪心演算法，與Attention機制相比來說，生成當前的輸出序列不需要全部的輸入序列的信息，只跟截止目前的輸入序列，這也就是「Online」的意思。

論文思路來源：

本文的工作是受到Stephan Vogel的《HMM-based word alignment in statistical translation》的啟發，Vogel論文的主要工作是將語音識別中的HMM模型遷移應用到Statistical Translation的對齊模型中，獲得了不錯的效果；本文除了將HMM模型遷移到摘要任務以外，還在原來的基礎上引入RNN等網路結構，記憶並利用前序信息來生成摘要。

句子級文本摘要：

我覺得這個概念可以大概理解為句子壓縮，介紹下本文文本摘要任務的語料應該就比較清楚了，本文從Gigaword（六大新聞社的新聞語料）中只選擇first sentence和headline組成pair對，並且加上以下兩個條件：

1，text的單詞數不能超過50，headline的單詞數不能超過25；

2，二者長度的乘積不能超過500；

本文在HMM的alignment model上的改進主要有以下兩點：

1，限制alignment是遞增的；

2，結合遞歸網路來引入locally非遞增alignment的序列的信息；

alignment的可視化：

直觀來講，alignment只能向右和向下擴展，並且只與在此之前的輸入有關，而引入遞歸網路的意義在於alignment不向右擴展的時候，網路能夠「記住」locally（局部）信息；

HMM及其前後向演算法：

本小節主要參考李航老師《統計學習方法》中第10章的相關內容整理：

另外關於隱馬爾科夫模型也可參考知乎回答，比較通俗易懂的介紹；

定義：隱馬爾可夫模型是關於時序的概率模型，描述由一個隱藏的馬爾科夫鏈隨機生成不可觀測的狀態隨機序列，再由各個狀態生成一個觀測而產生觀測隨機序列的過程。

三要素：隱馬爾科夫模型由初始概率向量 $pi$ 、狀態轉移概率矩陣 $A$ 和觀測概率矩陣 $B$ 決定。 $pi$ 和 $A$ 決定狀態序列， $B$ 決定觀測序列。因此，模型 $lambda =(A,B,pi )$ 。

三個基本問題：

1. 概率計算問題：

給定模型參數 $lambda =(A,B,pi )$ 和特定觀測序列 $O=(o_1,o_2,...o_T)$ ，計算在模型 $lambda$ 下觀測序列 $O$ 出現的概率 $P(O|lambda)$ 。演算法為： Forward-backward algorithm.

2. 預測問題

給定模型參數 $lambda =(A,B,pi )$ 特定的觀測序列 $O=(o_1,o_2,...o_T)$ ，計算產生此觀測序列的最可能（maximum liklihood）的隱狀態序列（稱為"Viterbi路徑"）。演算法：Viterbi演算法.

3. 學習問題

給定一個或一組觀測序列，計算最可能的隱狀態轉移概率矩陣A、輸出概率矩陣B。目前沒有可行的計算全局最優概率的演算法，局部最優解(local maximum likelihood)演算法有Baum-Welch演算法和 Baldi-Chauvin演算法。

前向-後向演算法：

前向概率及前向演算法：

給定隱馬爾科夫模型 $lambda$ ，定義到時刻 $t$ 部分觀測序列為 $o_1,o_2,...o_t$ 且狀態為 $q_in$ 的概率為前向概率，記做

$alpha _t(i)=P(o_1,o_2,...o_t,i_t=q_i|lambda)$

前向演算法是替代枚舉演算法的利用前向概率遞推地求得觀測概率 $P(O|lambda )$ 的演算法：

（糾錯：圖中箭頭上的 $j$ 應該是 $i$ ，例如 $a_{1j}$ 應該為 $a_{1i}$ ）

後向概率及後向演算法：

給定隱馬爾科夫模型 $lambda$ ，定義在時刻 $t$ 狀態為 $q_in$ 的條件下，從 $t+1$ 到 $T$ 的部分觀測序列為 $o_{t+1},o_{t+2}...o_{T}$ 的概率為後向概率，記作：

$beta _t(i)=P(o_{t+1},o_{t+2}...o_{T}|i_t=q_i,lambda )$

後向演算法是替代枚舉演算法的利用後向概率遞推地求得觀測概率 $P(O|lambda )$ 的演算法：

本文的模型：

模型的目標與其他摘要任務是一致的，即根據輸入 $x$ 和之前的輸出來生成當前的符號：

其中， $x_1^I$ 表示長度為I $I$ 的輸入序列， $y_1^J$ 表示長度為 $J$ 的輸出序列；

本文提出一個隱含對齊序列變數（hidden alignment sequence） $a_1^J$ ,舉例來說， $a_j=i$ 表示在生成 $y_j$ 的時候，我們應該focus輸入序列的哪個position， $p(y|x)$ 可以表示為：

為了介紹word predict和transition prediction，首先介紹下輸入序列的表示：

跟常見的seq2seq模型一樣，模型採用LSTM來編碼輸入序列，雙向和單向均可，但是為了實現「online」的想法，只能使用單向的（可以想一想為什麼），

Word prediction：

其實本質就是一個語言模型，與常見的seq2seq模型基本沒有差別：

根據前一步的狀態和前一步的輸出計算當前狀態，然後根據alignment的focus信息，選擇focus的輸入隱層狀態，經過 $softmax$ 得到輸出符號（word）；

Translation prediction：

由於之前限制alignment是遞增的，因此，我們可以把由當前時間步過渡到下一時間步的操作分為兩個部分，shift和emit，emit表示當前時間步生成一個word，而shift表示跳轉到輸入序列的下一個word，由模型決定當前時間步執行哪個操作；

文章提出了兩個建模alignment 轉移概率的方法：

1，幾何分布（geometric distribution）：

其中， $e$ 是指emit的概率，根據極大似然可以估計:

2，神經網路擬合：

其中， $p(e_{i,j})$ 表示alignment $a_j=in$ 時採取emit操作的概率，由前饋網路來得到;

$p(a_j = i|a_{j-1} = k)$ 是 $p(a_j = i|a_{j-1} = k, s_j, h^i_k)$ 的簡化表示；

由於alignment的組合是指數級別的，因此按照上述公式計算 $p(y|x)$ 是不現實的，作者採用了類似HMM的前向後向演算法的動態規劃演算法來解決這個問題；

Training：

前向變數： $alpha (i, j) = p(a_j = i, y^j_1|x)$ ，表示對所有可以到達這個狀態的路徑的概率的加和，定義如下：

後向變數： $beta(i, j) =p(y^J_ {j+1}|a_j = i, y^j_1, x)$ 計算如下：

在訓練過程中，我們通過降低訓練集上的對數似然損失函數來優化參數；

用 $theta _jn$ 表示網路在位置j輸出的參數，

上式第一部分（利用 $p(y|x;theta)$ = $alpha (i,j)cdot beta(i,j)$ ）：

上式第二部分對前向變數求導為：

計算出梯度之後，對參數 $theta$ 進行更新。

Decoding：

搜索演算法主要思想是存儲一個路徑概率矩陣 $Q$ ,然後不斷地用到達這個狀態的最大概率路徑來更新 $Q[i,j]$ ， $bp$ 表示back pointers， $W$ 存儲預測出的word；

實驗結果：

簡評：

傳統方法結合神經網路的比較好的工作，在傳統的HMM演算法的基礎上，融入遞歸網路的特性，實現任務效果的提升；

這個框架目測確實比較適合做句子壓縮，對於稍微長一些的文本做摘要的話，肯定還是attention機制效果會好一些；