Sequence to Sequence

本篇概要

好啦，各位讀者，我們要來繼續往下一個NLP的里程碑來邁進了，今天要來介紹的就是我們當今所有NLP Pretrained Model的基石 - Sequence to Sequence。該model是起於2014年ilyasu等人所發表的技術，真的Google工程師跟學者不是蓋的，總是能想到獨特的方式甚至實作出來，希望在一生中有機會進去磨練(離題了..

所以我們今天要探討的Paper是如下這篇:
Sequence to Sequence Learning with Neural Networks

今天我們會來好好講解這篇的重點與技術內容，而下一篇就會提到從這裡延伸出來的Attention Mechanism(注意力機制)，請各位讀者要好好按照我的步調走喔，我是期許能在這裡寫到像是Longformer、ELECTRA等2020年出來的NLP paper文章，期待那一天趕快到來。

RNN & LSTM

再來講解Seq2Seq之前，要先來介紹這個model的基石，RNN跟LSTM，同時也是學者在paper中特別提到的，所以我會透過我理解完後的方式來說明給大家(好像Seq2Seq的概念喔XD)。

RNN

RNN相信有做過Deep learning來說，想必都不陌生，任何市面上關於DL的書一定會提到兩個基本model，分別是CNN跟RNN。那為什麼會有RNN這個model的出現呢？其實不難想像，在很多現實的場景當中有些結果除了會與特定原因相關之外，也有可能存在者順序性或序列上的關係，比如說時間，當下時間點的結果有可能會因為前一個時間點的結果造成一定程度的影響，這其實有一個專有名詞，就叫做相依性(Depenency)。

而這樣的RNN模型其實對於文字、NLP來說一定是相對最佳的選擇，因為人的溝通語句，就是透過文字的順序性所表達出來的，而這樣特性整合到傳統的神經網路做學習的話，其實就RNN的核心精神了。講了這麼多，不如來看一點數學公式：

ht : 我們可以視為第t個時間點(或第t個元素)的輸出
xt : 在第t個時間點的輸入
ht-1: 第 t−1 個時間點的輸出
Wh,Uh,bh : 是 RNN 的參數
σ : activation function

其中Wh 跟 Uh的重點是:
Wh: 決定xt 如何去影響同時間點的輸出ht
Uh: 決定前t-1的輸出ht-1要如何影響目前要輸出的ht(簡單來說，就是透過1.....t-1之元素來決定t的影響程度)

利用這個公式就會產生以下的網路架構圖：

然而在這樣的架構當中存在著幾個問題:

1. 輸入序列元素為n時，輸出的序列元素也是為n，也就是受到輸入的長度限制。我們這樣想好了，假設是一個中翻英翻譯的應用場景，有一句話是『我討厭你』共4個字，照理來說應該會翻譯成『I hate you』，但結果是3個字，這就會造成整體輸出的落差。
2. 第二個問題是不適用長度過長的資料訓練，容易造成梯度消逝(Gradient Vanish),梯度爆炸(Gradient Explode)，因為RNN在反向訓練誤差時，會乘上參數，參數乘上誤差的結果，大則出現梯度爆炸;小則梯度消失，進而導致模型成效不好，甚至無法學習到更早以前的因子與特徵。

LSTM

為了解決RNN所存在的問題，所以後來就有了LSTM(Long-Short Term Model, 長短記憶網路)的模型出來了，透過Memory Cell來控制每次計算的數值是否要記起來以用到下次cell的運算。要如何解決呢？在LSTM當中有了三個機制，分別是forget-Gate, input-Gate和output-Gate來加以解決訓練誤差等問題，我們先來架構圖，如下

• forget-Gate
  簡單來說就是來決定哪些資訊要被遺忘，哪些要被記錄下來。
  
  對應的圖如下:
  

• input-Gate
  用來決定當前的輸入，以及所產生的memory-cell是否要加入到long-term memory內，其中會透過Sigmoid function 來決定是否加入，並且透過tanh 得到一個vector-Ct，決定有多少資訊 Ct 要用來更新主要單元。
  
  

接著結合前兩個步驟來做到memory cell state的更新。

• output-Gate
  決定當前的資訊是否加到output，透過Sigmoid function 以及 tanh 的配置，來決定哪些資訊要被output。
  
  

所以透過這些cell跟處理步驟，LSTM就可以取得距離很遠的資訊來做為考量，必且output的長度也不會因為input的長度而有所侷限，藉此獲得了改善。

Paper重點

有了前期提要，我們就可以來切入到Sequence to Sequence的重點了，其實這篇paper一開始也是要解決傳統DNN在訓練時，必須要dimension固定下來的問題，因為對於翻譯或是語句的訓練，我們是無法事先知道最大的output length多大，如果是就分類問題，我們可以知道分類的個數，但如果是翻譯、文字生成、問答系統等，這些是『無法事先知道output的dimension』，所以學者透過LSTM的特性以及Sequence to Sequence的搭配來做到Dynamic Length的狀態。

這邊在進入探討的時候，我先整理了幾個重點給讀者們，大家先幫我記在心裡一下，接續會帶大家一一來理解。

Paper重點
1. 解決過往傳統DNN必須要先fix output dimension的問題
2. Encoder-Decoder的概念基礎
3. 更深層的LSTM比淺層來得更有效果
4. Reverse input sequence會來得更有效果
5. Beam Search

Encoder-Decoder

上面是學者在Paper畫出來的架構，簡單來說Encoder跟Decoder是個別不同的LSTM架構，其實這樣的概念稱Conditional Generation:

Encoder: 負責將輸入的句子理解成一個固定的Context Vector
Decoder: 負責將Context Vector加以生成
推測步驟中，則是計算給定輸入序列 x， 生成序列，y 的條件機率（conditional probability）。

根據學者的例子，將原先的 [A，B，C] 先加入[EOS]成 [A，B，C，EOS]，主要目的是要讓model知道input句子結束的地方，然而透過Encoder壓縮成一個Context Vector，接著Decoder再加以生成，一樣到[EOS]出現即結束，這個方式就可以解決無法事先知道output 的length之狀況。

除此之外，學者們在實驗過程中也發現到在這樣的架構中，可以訓練過往模型所無法訓練的長句子。然而，學者在整體訓練過程中有發現到效能的問題，所以也提出了幾個Tricking的方式
1. Deeper LSTM
在學者的實驗當中，其採用了4層的LSTM效果比過往2,3層的LSTM效果來得更好，

原文敘述
we found that deep LSTMs significantly outperformed shallow LSTMs, so we chose an LSTM with four layers

2. Reverse Input Sequence
將input的sequence做反轉，原先的句子[A, B, C, EOS]，反轉成[C, B, A, EOS] 再丟入model中，得到 [W, X, Y, Z, EOS]的效果更好。為什麼可以這樣做呢？原因在與反轉前與反轉後的sequence都與output sequence的平均距離都是一樣的，再加上尚未反轉的A有可能在encode被遺漏進而造成與輸出的W距離拉遠，還記得我們是使用RNN類型的model嗎？所以如果第一步造成很大的loss，那麼接下來可能會造成整體output更遠，所以學者才改用這個方式去做嘗試，卻發現意外得到了更好的結果。

原文敘述
So for example, instead of mapping the sentence a,b,c to the sentence α,β,γ, the LSTM is asked to map c,b,a to α,β,γ, where α, β, γ is the translation of a, b, c. This way, a is in close proximity to α, b is fairly close to β, and so on, a fact that makes it easy for SGD to “establish communication” between the input and the output. We found this simple data transformation to greatly improve the performance of the LSTM.

3. Beam Search
在這篇paper當中是採用的machine translation作為實驗例子，簡單來說就是根據 encoder 的input sequence所算出的聯合機率（joint probability），找出擁有最大 p(y|x) 條件機率之最佳的output sequence。

在過往的Language model都是採用Greedy Search來找出當前state最佳的聯合機率來生成sequence，為什麼這樣說呢？其實Greedy Search著重於當前最優的方式來挑選機率最好的state來輸出，再加上每一步都是independent，但其實當前最有並無法保證整體最優，所以是有一定的機會loss掉最優的sequence，這個方式在HMM稱為Viterbi;但利用梯度來說就是容易進入到local minimum(局部最佳解)。

所以Beam Search的Beam其實可以想像成是一個參數，在Decoder每一個state時，如果Beam=3，其會找出會好的3個選擇(想像成有一個candidate list)，再接續往後生成，最後在找出整體最優的組合來輸出，如此一來就可以避免掉最佳輸出的可能性，也比較容易得到global minimum(全局最佳解)。

那其實Beam search雖然看似簡單，但其實有兩個重點要特別注意且要解決，分別如下:

(a) Length Normalization
Maximum likelihood probability的估算是每一位置的狀態和輸出機率乘積，而此機率連乘可能會隨著產生序列的長度而衰減，所以對於Decoder生成的長度會有機會造成誤差，尤其是length拉長的時候。

所以在length拉長的時候，可以log 函式轉換成總和使之能夠處理更多的乘積。接著再予以求出平均值，也是除以產生序列長度的部分，進而達成length normalization

(b) How to choise the better Beam
如何找出最佳的Beam，這個參數的設定可是會影響到計算的效能，設定太大在整體計算就會變慢，但就是更有機會找到更好的組合，這可是有一好沒兩好啊...反之，Beam設定太小，則計算效速度較快，但很容易遺漏真正最好的sequecne組合。然而像這樣hyper parameter的參數調教，大部分都還是用Grid search、Hyperopt、Bayes Optimization等方法來找到最合適的值。

Training Details

學者也在paper當中提到了其訓練的相關細節來提升machine translation performance，如下:

1. LSTM參數按照uniform distribution來設定，其中range為[-0.08, 0.08]
2. 採用SGD做Gradient Descent，並且前5個epoch learning rate固定，之後每半個epoch 做 decay，總共訓練7.5 epoch
3. 為了避免造成Gradient Explode，所以對於輸出有設定一個約束條件
4. 每個句子長短不一，所以為了增加訓練效能，確保每一個minibatch的句子長度是一致的，就是針對訓練資料中的語句長度做sorting.

Experiment Result

學者在後面透過BLEU的指標來比較model的performance，其實可以Sequence to Sequence的方式確實帶來的好的結果，然而對於一些主被動的語法也會有辦法處理。

Conclusion

其實這篇不算太難，也沒有牽扯到過多的數學公式，但確實在那時候對於NLP的帶來很大的突破，而後續的attention、Transformers、Bert等都是奠基於此所發展出來的。再加上其實網路上有很多如何實作的code, github，包含tensorflow, pytorch的example，所以也相信在實作過程中難度不高，但最重要的還是這當中的核心精神與概念，因為後續的發展都與此脫離不了關係。

最後我在這裡留下一個伏筆，其實Sequence to Sequence有一個問題，對於一個sequence中每一個token或是元件都一視同仁，但其實這對於在NLP的應用上會產生一些狀況，我們可以想像在人的對話當中，一句話內一定有些字是重要的、有些則是不重要，所以對於資訊的存取來說，一句話內的每一個字並不完全相同，所以在2015年有學者提出了Attention Mechanism(注意力機制)，找出sequence內對應重要的資訊加以訓練，如此一來後續應用上也更貼切人對於文字的行為了。

所以下一篇就會介紹Attention Mechanism(注意力機制)，以及在Sequence to Sequence是如何做到的。

Reference

• Sequence to Sequence Learning with Neural Networks
• Neural Machine Translation using Bahdanau Attention Mechanism
• [NLP] Seq2Seq #2014
• Beam Search
• seq2seq 中的 beam search 算法过程是怎样的？
• 淺談遞歸神經網路 (RNN) 與長短期記憶模型 (LSTM)
• 維特比演算法