如何評價微軟亞洲研究院提出的LightRNN？

01-21

這個工作剛出來的時候我就讀了這篇論文，沒想到知乎竟然看到了這個問題，就貼一下吧。
個人很喜歡這篇工作，可以說是16年讀過的論文裡面我非常喜歡的一篇了。裡面的想法很簡單同時很有效，並且有一些很有趣的結論。

總結一下LightRNN，模型方面：核心的想法就是通過修改常見的word embedding為2-Component (2C) shared embedding。即對某一詞向量 $X_i$ 變為 $(X^{r}_i, X^{c}_j)$ 。其中，2C體現在分解詞向量為兩部，shared embedding體現在這樣的分解向量是放在一個二維表中，其中每一行由一個向量表示（上角標 r），每一列由另一個向量表示（上角標 c）。根據一個詞在二維表中的位置，該詞可由行向量和列向量聯合表示（這裡注意一下，下角標因此分別用不同的符號表示）。「因為該表中同一行里的所有詞共享相同的行向量，同一列的所有詞共享相同的列向量，所以LightRNN僅僅需要2√|V|個向量來表示有|V|個詞的辭彙表，遠遠少於標準的RNN所需要的向量數|V|。這種詞嵌入的做法被稱做兩部共享嵌入」。
預測階段，這樣在一個大詞表的RNN語言模型中為了預測下一個詞，LightRNN需要首先基於前面所有的詞預測其行向量，然後基於前面所有的詞和已經預測出來的行向量預測其列向量。雖然這樣會將一個句子的預測長度翻了倍，但是實際中，因為詞表的規模極大地減小，根據論文，在One Billion數據集上，「標準的RNN的模型參數個數為16-41億，而LightRNN的模型參數個數僅為4千萬，達到了40-100倍的壓縮比」，模型訓練時間快了一倍。一次預測的平均時間論文中沒有給出（個人比較關心，因為關係到部署，實際能不能上線還是跟這個時間關係很大的），個人經驗的結論是：雖然預測時長度變為2倍，但是因為最後Softmax顯著減小了，總時間應該是少了的，但是有沒有到一個顯著的程度需要實驗驗證。
另外值得一提的是，這個二維詞表在訓練過程中是如何分配行列向量呢？這是一個很關鍵的問題。LightRNN的做法是：初始階段，隨機初始化；訓練RNN直到模型收斂，收斂後，固定好學到的embedding參數，但是詞需要被重新地分配到詞表中合適的位置。語言模型的訓練目標是最大化對數似然。類似地，詞表重分配也應該滿足這樣的一個過程。（省略公式推導細節）通過一些簡單的推導，這個重分配問題最終變為最小割最大流問題（見下圖），求解這個問題完成一次詞表的分配。完成一次重新分配，按照新的位置和參數繼續訓練RNN到收斂。論文中表示大概經歷3-4次詞表重分配就可以完成整個的訓練了；而且雖然求一次重分配要花時間，但是相對於整個訓練時間來講這個開銷還是很低的。

相關結論中：與標準的RNN進行單模型比對，LightRNN還達到了更好的PPL。這個可能是通過shared embedding的參數減少帶來的。除了前面提到的模型大小、訓練時間等問題，一個很有趣的現象是：LightRNN發現了詞表中的一些語義。比如某一行或者某一列的詞有著近似的表達；「其次，通過讓有語義關聯的詞共享行或列向量，可以使低頻的詞的向量表達得到更充分的訓練」（這一點是我第一次讀這個論文沒有注意到的點）。
最後簡單評價一下：
LightRNN的優點中，模型大小的顯著減小在嵌入式設備中的意義更大（考慮到ngram模型動輒幾個幾十個G的大小，對於Server類任務這個大小無所謂）；而對於多GPU的訓練也是能減小通訊開銷（但是這一點個人認為意義不是特別大，因為當下及未來對於RNN的訓練的問題會越來越小，訓練時間往往大家不是特別在意，堆機器堆數據對大公司是家常便飯）。當然，「它使得單GPU訓練超大詞表的語料庫成為現實」（對於窮人意義還是很大的！）。
進一步的研究可能是存在的：詞的二部共享嵌入得到了一些有趣的語義上的結果（包括近似單詞在一行/一列，以及低頻詞的向量表達），是不是有進一步研究的可能？（個人不會完全樂觀於論文中挑出來的那些語義相近的例子）；另外就是如果做k（&>2）部分解呢？
這樣的論文還是非常有趣的！

*答案中帶引號的句子引用了MSRA自己的評價，參見：Sina Visitor System；論文鏈接：Memory and Computation-Efficient Recurrent Neural Networks

奇文共賞，轉自：LightRNN：深度學習之以小見大。秦濤微軟亞洲研究院
歷經沉浮，AI終去頹勢，一掃六合，雄踞當今IT江湖之巔，江湖幫派無論大小皆以AI為榮。然幫派雖眾，論及武功秘籍，江湖中只有一個傳說，「深度學習，AI至尊，號令天下，莫敢不從，RL不出，誰與爭鋒」。江湖公認，深度學習，無他，唯大爾。深度學習之大，境界有三重，大數據、大模型、大計算，傳言唯有修至三重境者，方能領會深度學習之真諦。然成也蕭何、敗也蕭何，深度學習，因大而崛起聞名於江湖，亦因大而阻礙其一統江湖的步伐：唯有大型幫派，方有財力人力體會三重境之美妙，而限於財力人力小門小派往往不能承受深度學習之大。所幸江湖兒女多豪傑，我輩AI中人多志士，諸多英雄好漢前赴後繼，不斷鑽研，力圖以小見大，使得深度學習之大能夠返璞歸真。本文所要講述的正是發生在M幫AI部門亞洲分舵的一小段故事。
話說M幫是個超大型幫派，幫眾甚多，直接服務IT江湖的產品部門和分舵也眾多。聽聞循環神經網路（RNN）乃武功秘籍深度學習中的一大絕招，橫掃很多應用，包括語言建模、機器翻譯、聊天機器人、看圖說話（Image captioning）等等，很多分舵嘗試把該絕招應用到產品中。然而儘管前途光明，但道路總是曲折的。大家很快發現RNN應用於自然語言處理任務中面臨著一個巨大挑戰：當語料庫詞表很大時，模型的體量將變得非常大。例如，當使用 RNN 進行語言建模（language modeling）時，每個詞首先需要通過一個輸入嵌入矩陣（input-embedding matrix）從 one-hot 向量（其維度與辭彙表大小相同）映射到一個詞向量。然後為了預測下一詞的概率，通過輸出嵌入矩陣（output-embedding matrix）將隱藏層映射到辭彙表中每個詞的概率。當詞表包含上千萬個不同的詞時（這在 Web 語料庫中很常見），如果每個詞用一個1024維的嵌入向量表示，這兩個矩陣就會包含數百億（10Million×1024×2=20Billion）個不同的元素，這會使 RNN 模型變得過大（超過80GB），而當今江湖深度學習的獨門武器GPU的內存最大也只有24GB——很顯然，RNN模型之大已超出了深度武器的能力，從而阻礙了RNN在實際中的應用。

解決這一問題的一種思路是陣法。陣法可以使多個GPU組成陣列，從而應對大數據大模型的挑戰。這種思路的本質是以力服人、一力降十會，你有大數據大模型，我有大計算。一般來說，陣法非常有效，然而其帶來的一個問題就是進一步加劇了對計算資源的需求，這與以小見大的目標背道相馳。為此，M幫AI部門亞洲分舵一小撮幫眾聚集在一起，對RNN這一深度學習的絕招做出精巧的改進，其本質是四兩撥千斤，將標準的RNN提升到新的一種境界，即LightRNN：標準的RNN模型之所以大，是因為每個詞都有一個單獨的嵌入向量表達。LightRNN的解決方案是引入一個二維詞表，其每一行關聯了一個行向量（上圖中的二維詞表的第一行對應的行向量是x?），每一列關聯了一個列向量（上圖中的二維詞表的第一列對應的列向量是y?）。然後把語料庫里的每一個詞放到二維詞表的一個表格，根據一個詞在二維表中的位置，該詞可由行向量和列向量聯合表示(上圖中，January的表達為（x?，y?）, two的向量表達為（x?，y?））。因為該表中同一行里的所有詞共享相同的行向量，同一列的所有詞共享相同的列向量，所以LightRNN僅僅需要2√|V|個向量來表示有|V|個詞的辭彙表，遠遠少於標準的RNN所需要的向量數|V|。這種詞嵌入的做法被稱做兩部共享嵌入。
因為在LightRNN中每個詞由兩部分表達，所以在語言模型中為了預測下一個詞，LightRNN需要首先基於前面所有的詞預測其行向量，然後基於前面所有的詞和已經預測出來的行向量預測其列向量。LightRNN的網路結構具體如下圖左邊所示，它區別於標準RNN結構（見右邊）的地方在於，在標準的RNN中一次預測即可以找出下一個詞。在某種程度上來說，LightRNN相當於把句子的長度增加了一倍，把對每個詞的預測變成了兩次預測。有人可能會問，LightRNN會不會效率變低，訓練和測試時間變長。實際情況恰好相反，LightRNN會減少訓練和測試時間，原因在於每次預測的複雜度降低：如果語料庫詞表有一百萬個詞，標準的RNN為了預測下一個詞，需要對這一百萬個詞每個都打分計算概率，然後選擇概率最大的詞，因此複雜度是一百萬；而LightRNN的二維詞表只有一千行一千列，對行做預測時只需要對一千行打分計算概率選擇概率最大的行，然後再對一千列打分計算概率選擇概率最大的列，因此LightRNN預測一個詞的複雜度是兩千，遠小於標準的RNN。
在公共數據集上測試的結果表明，LightRNN能夠大大降低模型的大小，同時還達到了無損甚至更好的精度。如下表所示，在BillionW這個數據集（詞表大小接近一百萬）上，傳統演算法及標準的RNN的模型參數個數為16-41億，而LightRNN的模型參數個數僅為4千萬，達到了40-100倍的壓縮比。並且隨著詞表的變大，LightRNN的壓縮比會進一步的提高。下表中的PPL反映了語言模型的精度，PPL越小，精度越高。

有讀者可能會好奇，為什麼在減小模型的同時，LightRNN還能達到更好的精度。原因在於共享嵌入。標準RNN假設每個詞都有一個獨立的向量表達；LightRNN中很多詞會共享行或者列向量，二維詞表的行列向量都是從數據里學習得到的，並且哪些詞在同一行或同一列也是學習得到的，因此LightRNN能夠發現詞表中的一些語義。如下表所示，通過訓練，LightRNN把很多有語義關聯的詞放在同一行，如832行都是地名，852行都是數字，861行都是數字+單位，872行都是被動分詞，877行都是動詞第三人稱單數形式，等等。也就是說，LightRNN的二維詞表的共享行列向量比標準RNN的獨立向量更能發現詞之間的語義關聯。其次，通過讓有語義關聯的詞共享行或列向量，可以使低頻的詞的向量表達得到更充分的訓練。例如44kg這個詞在語料庫里出現的次數較少，在標準RNN里它的嵌入向量學習不充分，而在LightRNN里，這個詞的行向量由同一行的所有詞共同訓練，它的列向量也由同一列的所有詞共同訓練，相當於增加了這個詞的訓練數據，因此能夠提高語言模型的精度。
總結而言，LightRNN有以下優勢。
第一，它使單GPU訓練大詞表的語料庫成為現實。有人可能會問，實際中有沒有必要用非常大的詞表，比如說1百萬個詞的詞表，因為實際常用漢字或者英文單詞也就3、5千。答案是非常肯定的，現在很多輸入法里都把人名地名以及每天不斷湧現的新的網路辭彙放到詞表裡以提高輸入法的準確度，這會極大地增大詞表的大小。另外，在語音識別里，如果某個人名或地名不在詞表裡，任何語音識別演算法基本上都不可能正確識別該人名或地名。這些應用里在計算資源能夠容納的條件下，詞表是越大越好。
其次，因為LightRNN極大地壓縮了模型的大小，它對並行機器學習也非常有用。考慮用多GPU分散式訓練一個語言模型，標準RNN的模型大小為數GB，這樣不同機器之間的模型同步就非常耗時，使通訊時間超過計算時間而成為瓶頸；相比之下LightRNN的模型大小僅為幾十MB，非常容易在機器之間傳輸，通訊代價非常小，從而大大提高並行訓練的效率。
第三，考慮到功耗和可定製性，現在很多公司都嘗試在FPGA上開發深度學習演算法和平台。由於FPGA的內存較小（相對於GPU而言），很多深度學習演算法很難在FPGA上實現。 LightRNN因為其模型的極度緊緻，為FPGA上的RNN的實現提供一種可能。
第四，現在移動設備在人們的日常生活中扮演著不可或缺的角色。儘管深度學習日益普及，但是在移動設備上的應用始終非常受限，例如當前不可能在手機輸入法里使用一個2-4GB大小的語言模型，儘管它的準確度可能很高。LightRNN的模型大小僅為幾十MB，非常適合在移動設備上使用，因此LightRNN為深度學習在移動場景中的普及提供了一個可行的方案。
如前文所述，RNN乃是序列建模的絕招，適合非常多的應用，包括語言建模、機器翻譯、聊天機器人、看圖說話（Image captioning）、圖像生成、語音識別等等。相應的，LightRNN通過以小見大、返璞歸真，推動深度學習在在這些問題、場景里的實用化。我們相信，LightRNN會進一步提升深度學習在AI的江湖地位，並促進AI普及化進程（Democratizing AI，參見「薩提亞·納德拉：面向每個人和每個組織普及人工智慧」），而不是讓AI或深度學習發展成為大型幫派的特權。
更多詳細信息參見NIPS 2016 論文。
Xiang Li, Tao Qin, Jian Yang, and Tie-Yan Liu, LightRNN: Memory and Computation-Efficient Recurrent Neural Networks, NIPS 2016. http://papers.nips.cc/paper/6512-lightrnn-memory-and-computation-efficient-recurrent-neural-networks

我也來參合一下，把自己最近用TensorFlow 實現LightRNN過程中遇到的問題放出來，還請各位大神幫忙答疑了吧。
圖1中左邊為LightRNN的示意圖，我的理解是：先輸入 $w_{t-1}$ 的行詞向量 $X_r$ （對應於LightRNN示意圖的第一列），再輸入 $w_{t-1}$ 的列詞向量 $X_c$ （對應於LightRNN示意圖的第二列），這時候輸出的是 $w_t$ 的行分布 $P_r(w_t)$ 。再接著是從前一步的行分布 $P_r(w_t)$ 中選出最大概率的下標並將在該下標所在的共享行向量作為輸入，此時第三列的輸出的是 $w_t$ 的列分布 $P_c(w_t)$ 。最終我選擇 $P_r(w_t)$ $P_c(w_t)$ 各自最大下標並且到二維詞表中找到該詞作為我們想要 $w_t$ .
這個只是我的個人理解，如有錯誤，還請指正。
圖1. LightRNN與RNN的對比圖。
疑惑一：論文中提到構建LightRNN使用兩個vanilla RNN model，可是我覺得一個RNN model就可以了呀，為啥一定要用兩個。
疑惑二：論文中在算 $w_t$ 列分布的概率 $P_c(w_t)$ ，為啥是將行概率分布 $P_r(w_t)$ 中最大概率的下標所在的行向量作為輸入，而不是多個比較大概率所對應的下標所對應的行向量。換句話說就是：下一個詞 $w_t$ 不一定行最大概率所在下標與列最大概率所在下標（將行概率最大下標所對應的行向量作為輸入）。

推薦閱讀：