©PaperWeekly 原創 · 作者｜蘇劍林
單位｜追一科技
研究方向｜NLP、神經網絡
HMM、MEMM、CRF 被稱為是三大經典概率圖模型，在深度學習之前的機器學習時代，它們被廣泛用於各種序列標註相關的任務中。一個有趣的現象是，到了深度學習時代，HMM 和 MEMM 似乎都「沒落」了，舞臺上就只留下 CRF。相信做 NLP 的讀者朋友們就算沒親自做過也會聽說過 BiLSTM+CRF 做中文分詞、命名實體識別等任務，卻幾乎沒有聽說過 BiLSTM+HMM、BiLSTM+MEMM 的，這是為什麼呢？今天就讓我們來學習一番 MEMM，並且通過與 CRF 的對比，來讓我們更深刻地理解概率圖模型的思想與設計。從 MEMM 全稱 Maximum Entropy Markov Model，中文名可譯為「最大熵馬爾可夫模型」。不得不說，這個名字可能會嚇退 80% 的初學者：最大熵還沒搞懂，馬爾可夫也不認識，這兩個合起來怕不是天書？而事實上，不管是 MEMM 還是 CRF，它們的模型都遠比它們的名字來得簡單，它們的概念和設計都非常樸素自然，並不難理解。
回顧 CRF
作為對比，我們還是來回顧一下 CRF。說是「回顧」，是因為筆者之前已經撰文介紹過 CRF 了，如果對 CRF 還不是很了解的讀者，可以先去閱讀舊作簡明條件隨機場CRF介紹 | 附帶純Keras實現。簡單起見，本文介紹的 CRF 和 MEMM 都是最簡單的「線性鏈」版本。
本文都是以序列標註為例，即輸入序列 x=(x1,x2,…,xn)，希望輸出同樣長度的標籤序列 y=(y1,y2,…,yn)，那麼建模的就是概率分布：
CRF 把 y 看成一個整體，算一個總得分，計算公式如下：
這個打分函數的特點就是顯式地考慮了相鄰標籤的關聯，其實 g(yk−1,yk) 被稱為轉移矩陣。現在得分算出來了，概率就是得分的 softmax，所以最終概率分布的形式設為：
如果僅局限於概念的話，那麼 CRF 的介紹到此就結束了。總的來說，就是將目標序列當成一個整體，先給目標設計一個打分函數，然後對打分函數進行整體的 softmax，這個建模理念跟普通的分類問題是一致的。CRF 的困難之處在於代碼實現，因為上式的分母項包含了所有路徑的求和，這並不是一件容易的事情，但在概念理解上，筆者相信並沒有什麼特別困難之處。
更樸素的 MEMM
現在我們來介紹 MEMM，它可以看成一個極度簡化的 seq2seq 模型。對於目標 (1) ，它考慮分解：
然後假設標籤的依賴只發生在相鄰位置，所以：
接著仿照線性鏈 CRF 的設計，我們可以設：
至此，這就得到了 MEMM 了。由於 MEMM 已經將整體的概率分布分解為逐步的分布之積了，所以算 loss 只需要把每一步的交叉熵求和。
兩者的關係
將式 (6) 代回式 (5) ，我們可以得到：
對比式 (7) 和式 (3)，我們可以發現，MEMM 跟 CRF 的區別僅在於分母（也就是歸一化因子）的計算方式不同，CRF 的式 (3) 我們稱之為是全局歸一化的，而 MEMM 的式 (7) 我們稱之為是局部歸一化的。
這一節我們來分析 MEMM 的優劣、改進與效果。
MEMM 的優劣
MEMM 的一個明顯的特點是實現簡單、速度快，因為它只需要每一步單獨執行 softmax，所以 MEMM 是完全可以並行的，速度跟直接逐步 Softmax 基本一樣。
而對於 CRF，式 (3) 的分母並不是那麼容易算的，它最終轉化為一個遞歸計算，可以在 O(n) 的時間內算出來（具體細節還請參考簡明條件隨機場CRF介紹 | 附帶純Keras實現），遞歸就意味著是串行的，因此當我們模型的主體部分是高度可並行的架構（比如純 CNN 或純 Attention 架構）時，CRF 會嚴重拖慢模型的訓練速度。後面我們有比較 MEMM 和 CRF 的訓練速度（當然，僅僅是訓練慢了，預測階段 MEMM 和 CRF 的速度都一樣）。
至於劣勢，自然也是有的。前面我們提到過，MEMM 可以看成是一個極度簡化的 seq2seq 模型。既然是這樣，那麼普通 seq2seq 模型有的弊端它都有。seq2seq 中有一個明顯的問題是 exposure bias，對應到 MEMM 中，它被稱之為 label bias，大概意思是：在訓練 MEMM 的時候，對於當前步的預測，都是假設前一步的真實標籤已知。
這樣一來，如果某個標籤 A 後面只能接標籤 B ，那麼模型只需要通過優化轉移矩陣就可以實現這一點，而不需要優化輸入 x 對 B 的影響（即沒有優化好 f(B;x)）；然而，在預測階段，真實標籤是不知道的，我們可能無法以較高的置信度預測前一步的標籤 A ，而由於在訓練階段，當前步的 f(B;x) 也沒有得到強化，所以當前步 B 也無法準確預測，這就有可能導致錯誤的預測結果。
雙向 MEMM
label bias可能不好理解，但我們可以從另外一個視角看 MEMM 的不足：事實上，相比 CRF，MEMM 明顯的一個不夠漂亮的地方就是它的不對稱性——它是從左往右進行概率分解的。
筆者的實驗表明，如果能解決這個不對稱性，能夠稍微提高 MEMM 的效果。筆者的思路是：將 MEMM 也從右往左做一遍，這時候對應的概率分布是：
然後也算一個交叉熵，跟從左往右的式 (7) 的交叉熵平均，作為最終的 loss。這樣一來，模型同時考慮了從左往右和從右往左兩個方向，並且也不用增加參數，彌補了不對稱性的缺陷。作為區分，筆者類比 Bi-LSTM 的命名，將其稱為 Bi-MEMM。
註：Bi-MEMM 這個名詞並不是在此處首次出現，據筆者所查，首次提出 Bi-MEMM 這個概念的，是論文 Bidirectional Inference with the Easiest-First Strategy for Tagging Sequence Data [1]，裡邊的 Bi-MEMM 是指一種 MEMM 的雙向解碼策略，跟本文的 Bi-MEMM 含義並不相同。
為了驗證和比較 MEMM 的效果，筆者將 CRF 和 MEMM 同時寫進了 bert4keras [2] 中，並且寫了中文分詞 [3] 和中文命名實體識別 [4] 兩個腳本。在這兩個腳本中，從 CRF 切換到 MEMM 非常簡單，只需將 ConditionalRandomField 替換為 MaximumEntropyMarkovModel 。 詳細的實驗數據就不貼出來了，反正就是一些數字罷了，下面直接給出一些相對比較的結果： 1. 相同的實驗參數下，Bi-MEMM 總是優於 MEMM，MEMM 總是優於 Softmax； 2. 相同的實驗參數下，CRF 基本上不差於 Bi-MEMM； 3. 當編碼模型能力比較強時，CRF 與 Bi-MEMM 效果持平；當編碼模型較弱時，CRF 優於 Bi-MEMM，幅度約為 0.5% 左右； 4. 用 12 層 bert base 模型作為編碼模型時，Bi-MEMM 比 CRF 快 25%；用 2 層 bert base 模型作為編碼模型時，Bi-MEMM 比 CRF 快 1.5 倍。註：由於筆者發現 Bi-MEMM 效果總比 MEMM 略好，並且兩者的訓練時間基本無異，所以 bert4keras 裡邊的 MaximumEntropyMarkovModel 默認就是 Bi-MEMM。根據上面的結論，在深度學習時代，MEMM 的「沒落」似乎就可以理解了——MEMM 除了訓練速度快點之外，相比 CRF 似乎也就沒什麼好處了，兩者的預測速度是一樣的，而很多時候我們主要關心預測速度和效果，訓練速度稍微慢點也無妨。
這兩個模型的比較結果是有代表性的，可以說這正是所有全局歸一化和局部歸一化模型的差異：全局歸一化模型效果通常好些，但實現通常相對困難一些；局部歸一化模型效果通常不超過全局歸一化模型，但勝在易於實現，並與易於拓展。
如何易於拓展？這裡舉兩個方向的例子。
第一個例子，假如標籤數很大的時候，比如用序列標註的方式做文本糾錯或者文本生成時（相關例子可以參考論文 Fast Structured Decoding for Sequence Models [5]），標籤的數目就是詞表裡邊的詞彙數 |V| ，就算用了 subword 方法，詞彙數少說也有一兩萬，這時候轉移矩陣的參數量就達到數億（），難以訓練。
讀者可能會想到低秩分解，不錯，低秩分解可以將轉移矩陣的參數量控制為 2d|V| ，其中 d 是分解的中間層維度。不幸的是，對於 CRF 來說，低秩分解不能改變歸一化因子計算量大的事實，因為 CRF 的歸一化因子依然需要恢復為 |V| × |V| 的轉移矩陣才能計算下去，所以對於標籤數目巨大的場景，CRF 無法直接使用。
但幸運的是，對於 MEMM 來說，低秩分解可以有效低降低訓練時的計算量，從而依然能夠有效的使用。bert4keras 裡邊所帶的 MaximumEntropyMarkovModel 已經把低秩序分解集成進去了，有興趣的讀者可以查看源碼了解細節。
第二個例子，上述介紹的 CRF 和 MEMM 都只考慮相鄰標籤之間的關聯，如果我要考慮更複雜的鄰接關聯呢？比如同時考慮 跟 的關聯？
這時候 CRF 的全局歸一化思路就很難操作了，歸根結底還是歸一化因子難算；但如果是 MEMM 的局部歸一化思路就容易進行。事實上，筆者之前設計的信息抽取分層標註思路，也可以說是一種跟 MEMM 類似的局部歸一化的概率圖模型，它考慮的關聯就更複雜化了。
本文介紹並簡單推廣了跟 CRF 一樣同為概率圖經典案例的 MEMM，它與 CRF 的區別主要是歸一化方式上的不一樣，接著筆者從實驗上對兩者做了簡單的比較，得出 MEMM 訓練更快但效果不優於 CRF 的結論。儘管如此，筆者認為 MEMM 仍有可取之處，所以最後構思了 MEMM 的一些拓展。
[1] https://www.aclweb.org/anthology/H05-1059/
[2] https://github.com/bojone/bert4keras
[3] https://github.com/bojone/bert4keras/blob/master/examples/task_sequence_labeling_cws_crf.py
[4] https://github.com/bojone/bert4keras/blob/master/examples/task_sequence_labeling_ner_crf.py
[5] https://arxiv.org/abs/1910.11555
點擊以下標題查看更多往期內容：
#投 稿 通 道#
讓你的論文被更多人看到
如何才能讓更多的優質內容以更短路逕到達讀者群體，縮短讀者尋找優質內容的成本呢？答案就是：你不認識的人。
總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發出更多的可能性。
PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優質內容，可以是最新論文解讀，也可以是學習心得或技術乾貨。我們的目的只有一個，讓知識真正流動起來。
📝 來稿標準：
• 稿件確係個人原創作品，來稿需註明作者個人信息（姓名+學校/工作單位+學歷/職位+研究方向）
• 如果文章並非首發，請在投稿時提醒並附上所有已發布連結
• PaperWeekly 默認每篇文章都是首發，均會添加「原創」標誌
📬 投稿郵箱：
• 投稿郵箱：hr@paperweekly.site
• 所有文章配圖，請單獨在附件中發送
• 請留下即時聯繫方式（微信或手機），以便我們在編輯發布時和作者溝通
🔍
現在，在「知乎」也能找到我們了
進入知乎首頁搜索「PaperWeekly」
點擊「關注」訂閱我們的專欄吧
關於PaperWeekly
PaperWeekly 是一個推薦、解讀、討論、報導人工智慧前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公眾號後臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群裡。
▽ 點擊 | 閱讀原文 | 查看作者博客