十倍加速！ adaptive softmax
來自 Facebook ICML 2017 論文 Efficient softmax approximation for GPUs 。主要用於訓練辭彙表巨大的語言模型。這篇文章還涉及了 GPU 優化方面的知識，很值得一看。
Idea
文中採用的模型可以簡單理解為 LSTM + softmax
想法很簡單，文章的大多數詞都是有辭彙表裡的少數詞構成的，即長尾理論或28原則。而語言模型在預測詞的時候往往需要預測每個詞的概率（通常是softmax），辭彙表可能非常大，低頻詞非常多。
那麼在訓練時完全可以把詞語分成高頻詞和低頻次兩類，先預測詞屬於哪一類，然後再預測具體是哪個詞，這樣簡單的分類就使得softmax的計算量大大減少。
原來是每個詞都要計算一次， 現在是： V(高頻) + P(低頻) * V(低頻)， V(高頻) 大大變小， 而 V(低頻 雖然大 但 P(低頻) 很小。
一個具體的例子，把辭彙分成多類，然後將除了第一個類之外的類表示成一個「詞」圖中的Vh大小就是 n + 3 （n為高頻詞數量），放進第一個類的詞一起訓練（注意第一個類並不單獨表示為一個類，見上圖每一個藍色方塊表示一個詞，白色表示一個類），第一個類的詞概率不變，假如預測到了V1類表示的「詞」，再在V1中預測一次具體是哪個詞，依次類推。
事實上，我們可以用另一種方式，把高頻詞也表示成一類，低頻詞一類或多個類，都作為葉子結點，表示成一棵樹，但這樣會帶來性能下降（5%~10%），可能的原因是高頻詞的概率表示不夠「直接」，被整個高頻詞類的概率所影響。
即原來是 P (w| h) (h 為隱含層向量，w為詞)
變成 P(C| h) * P (w| C, h) 其中C 為類別
矩陣大小及計算優化
計算大量小矩陣是不划算的，很容易理解，數據傳輸、函數調用開銷等計算本身就有額外 overhead，具體關係可表示如下：
可以直觀看出，分的類別不是越多越好，大致關係如下，訓練時間先下降後略微提升：
低頻詞優化
低頻詞上下文信息有限，並不需要太多的維度，因此可以用一個矩陣變換降低softmax的輸入維度，即隱藏層的輸出維度再進行計算。
Idea 來源
基於 hierarchical softmax 及變種等
優勢
- 計算速度快，2x / 10x 對比普通的 softmax
2. 適合 GPU 計算
3. 對比原始的 softmax 幾乎不降低準確度
代碼
有點老，還是基於 lua 版本的 torch
facebookresearch/adaptive-softmax
推薦閱讀：
