seq2seq models in sub-quadratic time

最基本的 seq2seq 模型（用一個 RNN 做 encoder，另一個 RNN 做 decoder）推斷所需的時間是 O(T1+T2)，其中 T1 和 T2 分別是源語言和目標語言長度。但它的缺點是，需要把變長的句子壓縮成一個定長的向量，從而處理長句時力不從心，例如在機器翻譯中長句的翻譯效果迅速下降。

Attention mechanism 解決了這個問題，方法是在生成目標序列的每個元素的時候，允許 decoder 回過頭看源序列的每個詞，從而拓展了模型的記憶力，使模型有能力處理更長的序列。但它的缺點是，推斷需要 O(T1*T2) 的平方時間（因為每一步都需要用一個向量跟 encoder 得到的所有 T1 個隱層狀態計算相似度）。

那麼，有沒有可能在低於平方時間裡做推斷，同時性能又不顯著下降呢？我了解的比較有意思的文章主要有以下幾篇，這裡簡單聊一聊：

1、TOWARDS NEURAL PHRASE-BASED MACHINE TRANSLATION

2、Learning to Translate in Real-time with Neural Machine Translation

3、Online and Linear-Time Attention by Enforcing Monotonic Alignments

【第一篇】

顯式地建模了自然語言中的短語。其初衷是：在一對互為翻譯的句子中，詞數可能不相同，並且不同語言語序不同，導致無法用 sequence labeling 的方法來學習（比如說用 RNN 做 POS Tagging，每一步做一個 softmax，預測當前詞的詞性就行）。但是短語級別是可以一一對應的，頂多是語言 A 兩個詞，到語言 B 中變成了三個詞。於是，這篇文章在短語級別做了一個 sequence labeling，從而把推斷時間縮短到了線性（如果有足夠的計算核心，不做 beam search 等複雜的操作進行 rerank，各個短語甚至可以同時解碼，從而做到次線性時間）。

這種想法其實我也之前也想過，但是不知道怎麼實現，因為不知道怎麼建模短語……而本文的巧(ji)妙(zei)之處在於，他認為長為 T1 的源句子一定有 T1 個短語，每個詞都對應了一個短語，只不過有些詞對應的短語為空，從而簡化了計算和建模過程。作者把本文提出的模型叫 NPMT (Neural Phrase Machine Translation)。文章的後續工作也說，希望以後能顯式地建模源語言中的短語。

模型結構是先把輸入序列經過一個 reorder 層對詞序做微調，然後再經過 RNN，最後經過一個 SWAN 層得到輸出。示意圖如下：

其中 reorder 層是一個類似卷積的操作，通過把下層前 w 後 w 窗口範圍內的 embedding 按不同的權重（權重用一個 sigmoid 學出來，其實我覺得這裡可以做得稍微複雜一點，比如說做成 additive attention 裡面的那種兩層 MLP，效果可能會更好）進行加權組合，再輸入給後面，就相當於對輸入的詞向量進行了調序：

而SWAN 層參考的是另一篇文章（Sequence Modeling via Segmentations），全稱是 Sleep-WAke Network。其大意是說，輸入的每個節點都對應了一個輸出短語，如果輸出短語為空，就說這個節點 sleep 了；否則這個節點要解碼出一個短語（稱為 awake），具體做法是用一個 RNN 逐步解碼出各個詞，就像普通的 RNN decoder 一樣。整體結構如下所示：

在訓練的時候，因為不知道短語間的對齊關係，所以就把所有對齊關係枚舉一遍求和計算邊緣概率。但是這樣的話太慢了，於是有一個動態規劃演算法來枚舉所有對齊關係，具體實現有點像 CTC loss 那種感覺。從上面的介紹可以看出來，這個模型像是 HMM + CTC 的組合（把 HMM 改成 CRF 說不定是一個潛在的優化點）。不過即使用了動態規劃，訓練起來還是比較慢（所以可能需要等這個演算法流行開來，然後哪位大神在 CUDA 上好好實現一遍，就像百度搞的那個 warp-ctc 一樣，然後才能實用）。文章中的實驗都是在小規模數據集（大概 10w 句量級）上做的，四塊 M40 卡要訓兩三天。

不過最後效果不錯，達到了 SOTA，而且可解釋性也很棒。一個貪心解碼做推斷的例子如下：

可以看到模型非常機智地從 danke 解碼出了 thank you（一對多的短語翻譯）；後面在翻譯 das beste（意為 the best）的時候先跳過 das（德語中的定冠詞 the），然後從 beste 中解碼出了 the best thing。這個現象可以這麼解釋：das 那一步模型得不到什麼信息，就暫時不翻譯了；等到 beste 那一步，RNN 的感受野也包含了 das（因為 soft reordering 有一個前 3 後 3 的小窗口），模型就把 das beste 翻譯成了 the best thing，簡直機智！

至於怎麼把這個拓展到顯式建模源語言中的短語，也許一種可能的解決方案是把各種對齊方式全部求和的那一項鬆弛成一個變分下界 ELBO，然後優化 ELBO？

另外，從直覺上講，這篇文章的方法有可能在大範圍的語序調整上有一些困難，例如英語中在說 replace A with B 或者 denote A by B 的時候，如果 A 很長而 B 很短，習慣於把語序調整成 replace with B A 或者 denote by B A；假如要把這樣的句子翻譯成中文，不知道模型能不能把 with B/by B 移動到合適的位置。

最後再插播一段關於 SWAN 的評論：

其實作者在介紹 SWAN 的動機的時候，就說了這個模型是被 CTC 和 Sequence Transducer（Sequence Transduction with Recurrent Neural Networks）啟發的。CTC 的缺點是沒有建模各個輸出標籤之間的依賴（output-output dependency），只定義在離散標籤上，而且只能處理輸出長度不超過輸入長度的情形（於是 CTC 在語音識別里用的很廣，而在其對偶任務 TTS 中卻沒怎麼應用）。Sequence Transducer 則一口氣解決了這幾個問題，其中解決 output-output dependency 的辦法就是給 output 層再加一個 prediction model，把輸出做一下鏈式分解，根據前一步的輸出計算當前步的，頗有語言模型的味道。（這倆工作都是 Alex Graves 大佬的工作，紮實而又延續性好，服氣 Orz 看到田淵棟講研究員面試的文章 關於面試，裡面提到「有人長於堅持但方向有誤，有人反應敏捷但淺嘗輒止，有人思路新奇但不得要領，有人高談闊論但於細節一無所知，有人發文如流水但從不啃硬骨頭，有人堆砌概念卻不對題」，深以為然。文章不在多而在精啊~）

而 SWAN 原論文也是仿照了 Sequence Transducer 的做法，再加一個單獨的 RNN 建模 output-output dependency，如下圖所示（用上面那條橫線代表）：

在 NPMT 的論文里，SWAN 層卻沒有用這個建模 output-output dependency 的單獨的 RNN，原因作者在腳註里提到了，他說加這個 RNN 以後模型效果反而變差了，並分析原因可能是語言模型好學而短語分塊難學，導致模型卡在好學的語言模型上了。一個佐證是，加入這個 RNN 之前模型學到的 average segment length 是 1.4-1.5，加入之後模型學到的短語的平均長度顯著變短。

作者也考慮了向 NPMT 引入語言模型的方案，只不過不是在訓練的時候用，而是在推斷的時候用：在做 beam search 的時候，把目標語言的語言模型（可以在大規模外部語料上訓練）的打分也算進來，對候選翻譯進行排序篩選。實驗結果表明，引入語言模型重排序之後，效果確實提升了一些，不過不太明顯：

【第二篇】

則是一種類似同聲傳譯的思路，可以 on-the-fly 地一邊讀源句子一邊翻譯，而不需要把源句子讀完再翻譯。其動機是，距離太遠的詞對於當前部分的翻譯往往是不相關的，只要一個意群完整了，其實就可以翻譯這個意群了。示意圖如下（左邊是本文，右邊是普通的 seq2seq + attention）：

向下的藍色箭頭代表讀入一個詞，向右的紅色箭頭表示譯出一個詞。可以看到，本文的方法只需要在讀過的詞里做 attention 計算權重，不需要看未來的詞，就減少了一部分計算量。

其實如果假定所有詞可以一對一翻譯出來，attention 矩陣應該是恰好填一半，所以複雜度還是 O(T1*T2)，只是常數小一半……不過也許可以想辦法讓網路不再看之前已經看過的詞，這樣就真的做到次平方級別的複雜度了。

具體實現的時候，需要判斷一下當前是要繼續讀入新詞，還是要開始生成翻譯。訓練是採用強化學習的手段做的。我個人對強化學習不太熟，就不班門弄斧了……有興趣的同學可以自己詳細讀（逃

文章里還有一堆觀察翻譯質量 (quality) 和翻譯延遲 (delay) 關係的表格，也蠻有趣的。

【第三篇】

的想法是說，雖然機器翻譯里不同語言語序不同，但是很多語言其實是很相近的，語序近似相同，只需要局部的、很少的調序即可，所以搞一個 attention reader 來回看是殺雞用牛刀。於是可以給 attention 加一個單調性約束，只需要從前一步關注的位置繼續向後看就好了，如下圖所示：

具體做法是，每次選一個 encoder 狀態 hj，以及 decoder 的狀態 si，這倆向量計算一下打分得到一個概率，然後按這個概率扔硬幣，決定就 attention 到源語言的第 j 個詞，還是說 attention reader 接著往後走看後面的詞。最終做到的效果就是說，attention reader 從前往後只走了一遍，所以複雜度是線性的。

但是上面描述的過程只是推斷時候的用法，不能用於訓練（除非你想用極其低效的強化學習手段……）；所以訓練的時候其實是在期望的意義下訓練的，定義一個變數 p_{i, j} 表示 decoder 在第 i 步 attention 到 encoder 第 j 步的概率，然後弄一個遞推式求個和。這就好像普通的 attention 理論上說只看最相關的那個狀態，實際上卻用各個狀態的加權和來避免不可微的問題一樣。所以，這個方法在訓練的時候還是平方的複雜度，只是測試的時候可以用採樣的手段做成線性複雜度。

看論文的效果還行，勉強可以算 competitive with SOTA，不過還是不盡如人意，在各個實驗上最現在最好的方法都略差一點（畢竟嚴格單調的假設還是有點強）。也許一個擴充方向是，每一步 attention 的時候，不要只單調向後走，而是允許回退一個固定的步數 w（即從前一步減 w 的位置起往後走）再挑合適的位置，從而緩解單調性約束過於嚴苛的問題。