?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

點擊以下標題查看更多往期內容：?

• 簡明條件隨機場CRF介紹 | 附帶純Keras實現
  

• 你的CRF層的學習率可能不夠大
  

• 基于DGCNN和概率圖的輕量級信息抽取模型
  

• 深度學習預訓練模型可解釋性概覽
  

• 如何快速理解馬爾科夫鏈蒙特卡洛法？
  

• 神經網絡中的常用激活函數總結

#投 稿 通 道#

?讓你的論文被更多人看到?

如何才能讓更多的優質內容以更短路徑到達讀者群體，縮短讀者尋找優質內容的成本呢？答案就是：你不認識的人。

總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發出更多的可能性。?

PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優質內容，可以是最新論文解讀，也可以是學習心得或技術干貨。我們的目的只有一個，讓知識真正流動起來。

?????來稿標準：

? 稿件確系個人原創作品，來稿需注明作者個人信息（姓名+學校/工作單位+學歷/職位+研究方向）?

? 如果文章并非首發，請在投稿時提醒并附上所有已發布鏈接?

? PaperWeekly 默認每篇文章都是首發，均會添加“原創”標志

???? 投稿郵箱：

? 投稿郵箱：hr@paperweekly.site?

? 所有文章配圖，請單獨在附件中發送?

? 請留下即時聯系方式（微信或手機），以便我們在編輯發布時和作者溝通

????

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

關于PaperWeekly

PaperWeekly 是一個推薦、解讀、討論、報道人工智能前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公眾號后臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群里。

▽ 點擊 |?閱讀原文?| 查看作者博客

總結

以上是生活随笔為你收集整理的CRF用过了，不妨再了解下更快的MEMM？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。