前言

機率序列模型：它的工作是為序列中的每個單元配置設定一個标簽或類，進而将一個觀察序列映射到一個标簽序列。給定一個機關序列(單詞、字母、語素、句子，等等)，它計算可能的标簽序列的機率分布，并選擇最佳的标簽序列。

本文都是以序列标注（如分詞、詞性标注、命名實體識别，從字元級别中文分詞到詞語級别命名實體識别）為例，即輸入序列

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考

，希望輸出同樣長度的标簽序列

，那麼模組化的就是機率分布

生成式模型：利用p(x,y)和貝葉斯規則計算p(y|x)

判别式模型：直接計算p(y|x)

## 序列标注與中文分詞

## 序列标注與詞性标注

## 序列标注與命名實體識别

# 原理：Markov Chains馬爾科夫鍊

馬爾可夫假設: 每個事件的發生機率隻取決于前一個事件。将滿足該假設的連續多個事件串聯在一起，就構成了馬爾可夫鍊。

圖中節點表示狀态，弧線表示狀态的轉移，其上數字表示轉移的機率（注：離開給定狀态的弧的值之和必須為1

一個馬爾可夫鍊由以下部分組成：

# 原理：HMM 隐式馬爾可夫模型

💥 TMI：“1988 年隐馬爾可夫模型被用于詞性标注。在所有序列标注模型中，隐馬爾可夫模型是最基礎的一種。”

在許多情況下，我們感興趣的事件是隐藏的，例如我們通常不會在文本中觀察詞性标記。相反，我們看到單詞，必須從單詞序列推斷标簽。在我們的機率模型中，我們将觀測事件和隐藏事件認為是因果因素。

輸入：觀測序列

輸出：狀态序列

一個隐式馬爾可夫模型由以下部分組成：

初始狀态機率向量π、狀态轉移機率矩陣A與發射機率矩陣B被稱為隐馬爾可夫模型的三元組 λ=(π, A, B) 隻要三元組确定了，隐馬爾可夫模型就确定了。

👀 序列标注最大的結構特點就是标簽互相之間的依賴性。在隐馬爾可夫模型中，這種依賴性利用初始狀态機率向量π和狀态轉移機率矩陣A來展現。

一階隐馬爾可夫模型執行個體化了兩個假設：

① 一個特定狀态的機率隻取決于前一個的狀态

② 輸出觀測oi的機率僅取決于産生該觀測的狀态

則一階隐馬爾可夫模型可以表示為：

這張圖也許有一絲違和感，按通常了解，應當是x決定y而不是反過來。這是由于在聯合機率分布p(x, y) 中，兩個随機變量并沒有固定的先後與因果關系，p(x, y) = p(y, x)。從貝葉斯定理的角度來講，聯合分布完全可以做兩種等價變換:

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考
隐馬爾可夫模型隻不過在假設②中采用了後一種變換而己，即假定先有狀态，後有觀測，取決于兩個序列的可見與否。

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考

① HMM Tagger

對于詞性标注，HMM解碼的目标是選擇标簽序列

，它是最可能的給定的觀察單詞序列

的詞性（在這裡o是w，q是t）：

我們在HMM中使用的方法是使用貝葉斯規則來代替計算

進行簡化：

一階HMM taggers做了兩個進一步簡化的假設：

① 一個标簽的機率隻依賴于前一個标簽，而不是整個标簽序列

② 單詞出現的機率僅取決于它自己的标簽，與相鄰的單詞和标簽無關

進一步簡化後，一個二進制标記器的最有可能的标記序清單示公式：

這裡的 emission(發射機率矩陣) 和 transition(狀态轉移機率矩陣) 分别對應上文提及的 B 和 A矩陣，在HMM tagger中，這些機率是通過計算已标記的訓練語料庫來估計的。

舉例：在WSJ語料庫中，MD出現了13124次，後面跟着VB的次數為10471

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考
舉例：在WSJ語料庫的13124例MD中，它與will關聯了4046次

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考

💥 【二階隐馬爾科夫模型：初始狀态機率向量 π 和發射機率矩陣B的估計與一階隐馬爾可夫模型完全一緻。唯一不同之處在于二階轉移機率張量A的估計，因為二階隐馬爾可夫模型的依賴假設發生了改變。】

如何求該值的max值呢？HMM的解碼算法是Viterbi算法

維特比算法首先建立一個機率矩陣：

每個單元vt(j)的值通過遞歸地使用最可能将我們引向該單元的路徑來計算：

Viterb遞歸地填充每個單元格：

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考
：前一個時間步長的維特比路徑機率

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考
：從之前狀态

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考
到目前狀态

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考
的轉變機率

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考
：給定目前狀态j，觀測符号

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考
的狀态觀測可能性

舉例

示例：“Janet will back the bill”

資料：A、B矩陣（來自《華爾街日報》語料庫中的統計資料

再回顧一下公式：

即：

舉例：對于第一個單詞Janet，我們分别查表得到 ① P(7種詞性|start) 和 ② P(Janet|7種詞性)，兩者相乘得到

；

到第二個單詞，先計算

的最大值，對于

來說，即先計算

的最大值

則

可以了解為：

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考
到達B3的路徑有四條：S-A1-B3、S-A2-B3、S-A3-B3、S-A4-B3，經過計算得到S-A2-B3的值最大，則意味着當我們計算完成該矩陣，進行動态規劃選取路徑時，若選擇到B3，則一定是選擇了S-A2-B3這條路徑，其它路徑并不納入考慮。

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考

最終用維特比算法得到一個機率矩陣，尋求最大路徑（從最後一列傳回來檢索所需的标簽集機率最大

注：以 t=2 了解，此時假設

中最大值在

，而

獲得最大的值的情況是NNP->MD這條路徑（想說明當t=1時不一定就是選擇

最大的節點，而要考慮之後的乘積，當然若其他均為零，就隻能選擇該節點

最終正确的标簽為：Janet/NNP will/MD back/VB the/DT bill/NN

⭐如何通俗地講解 viterbi 算法？

語言含有更多特征，而隐馬爾可夫模型沒有捕捉到。隐馬爾可夫模型能捕捉的特征僅限于兩種：其一，前一個标簽是什麼；其二，目前字元是什麼。因而效果并不理想。--《自然語言處理入門》

當狀态數N增長非常大時，Viterb算法的速度較慢。bigram tagger算法的複雜度為

👉（枚舉每個時刻的N種備選狀态，相鄰兩個時刻之間的狀态就有

種組合。由于一共有T個時刻，是以複雜度是

。）若是采用 trigram tagger等，算法複雜度還要再上一個量級。

一種常見的解決複雜性問題的方法是使用Beam Search解碼，在束搜尋中，我們不保留每個時間點t的整個狀态列，我們隻保留那個點上最好的幾個假設（算出該t時刻各狀态N的viterbi分數後進行排序），其餘的被修剪掉，并且不能繼續到時間t +1。

束寬β（beam width）是一個固定大小的狀态數，即表示每個時間點t保留多少個最優狀态。束搜尋的算法複雜度為

下圖所示的束寬為2。在每個時間 t，所有的（非零）狀态都被計算出來，然後對它們進行排序，隻有最好的兩個狀态被向前傳播，其餘的被剪掉（📍 t=1時其它狀态viterbi值均為0，是以隻選擇了一個狀态。

在每一步深度擴充的時候，剪掉一些品質比較差的結點，保留下一些品質較高的結點。這樣減少了空間消耗，并提高了時間效率，但缺點就是有可能存在潛在的最佳方案被丢棄，是以Beam Search算法是不完全的，一般用于解空間較大的系統中。

# 原理：最大熵原理

“熵”不起：從熵、最大熵原理到最大熵模型（一）

“熵”不起：從熵、最大熵原理到最大熵模型（二）

“熵”不起：從熵、最大熵原理到最大熵模型（三）

② Maximum Entropy Markov Models最大熵馬爾可夫模型

為了實作是對整個序列進行的分類，在每個時刻t時，它的特征不僅來自目前觀測值

，而且還來自前一狀态值

。是以MEMM中，給定觀測序列

，某個狀态序

的機率是：

通過最大熵分類器模組化(參考最大熵模型的推導)為 :

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考

其中

分别表示特征函數數量，特征函數權重和第a個特征函數

#幾個特征函數的例子 [來源]

- 句子s（就是我們要标注詞性的句子）

- i，用來表示句子s中第i個單詞

- l_i，表示要評分的标注序列給第i個單詞标注的詞性

- l_i-1，表示要評分的标注序列給第i-1個單詞标注的詞性

① 當l_i是“副詞”并且第i個單詞以“ly”結尾時，我們就讓f1 = 1，其他情況f1為0。不難想到，f1特征函數的權重λ1應當是正的。而且λ1越大，表示我們越傾向于采用那些把以“ly”結尾的單詞标注為“副詞”的标注序列

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考
② 如果i=1，l_i=動詞，并且句子s是以“？”結尾時，f2=1，其他情況f2=0。同樣，λ2應當是正的，并且λ2越大，表示我們越傾向于采用那些把問句的第一個單詞标注為“動詞”的标注序列。

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考

表示歸一化因子，為:

其中y表示所有的可能狀态取值

使用維特比算法進行解碼時，MEMM對應的公式為：

MEMM可以看成是一個極度簡化的seq2seq模型。既然是這樣，那麼普通seq2seq模型有的弊端它都有。seq2seq中有一個明顯的問題是exposure bias，對應到MEMM中，它被稱之為label bias（标簽偏置問題）

根據上述遞推式，則機率最大路徑如下1->1->1->1，但從全局的角度分析：State 1 總是更傾向于轉移到State 2；State 2 總是更傾向于轉移到State 2.（因為狀态2可以轉換的狀态比狀态1要多，進而使轉移機率降低,即MEMM傾向于選擇擁有更少轉移的狀态。

MEMM所做的是本地歸一化，導緻有更少轉移的狀态擁有的轉移機率普遍偏高，機率最大路徑更容易出現轉移少的狀态。因MEMM存在着标注偏置問題，故全局歸一化的CRF被提了出來

Bi-MEMM 雙向MEMM

相比CRF，MEMM明顯的一個不夠漂亮的地方就是它的不對稱性——它是從左往右進行機率分解的。筆者的實驗表明，如果能解決這個不對稱性，能夠稍微提高MEMM的效果。筆者的思路是：将MEMM也從右往左做一遍 [來源]

HMM V.S. MEMM

兩種方法計算方式不同：HMMs計算似然性(觀察詞以标簽為條件)，MEMMs計算後驗性(以觀察詞為條件的标簽）

③ CRF條件随機場

網址：introduction-to-conditional-random-fields

在CRF中，函數F将整個輸入序列X和整個輸出序列Y映射到一個特征向量。讓我們假設我們有K個特性，每個特性的權重工作是Fk

這個限制僅依賴于目前和之前的輸出令牌yi和yi−1，這就是線性鍊CRF的特征

MEMM隻考慮

對

的影響，而沒有把

作為整體來考慮，導緻的是本地歸一化，而CRF做的則是全局的歸一化，避免了label bias的問題。

MEMM V.S. CRF

# HMM、MEMM、CRF差別

對于一個标注任務，“我愛北京天安門“，标注為” s s b e b c e”

對于HMM的話，其判斷這個标注成立的機率為 P= P(s轉移到s)*P(‘我’表現為s)* P(s轉移到b)*P(‘愛’表現為s)* …*P().訓練時，要統計狀态轉移機率矩陣和表現矩陣。

對于MEMM的話，其判斷這個标注成立的機率為 P= P(s轉移到s|’我’表現為s)*P(‘我’表現為s)* P(s轉移到b|’愛’表現為s)*P(‘愛’表現為s)*..訓練時，要統計條件狀态轉移機率矩陣和表現矩陣。

對于CRF的話，其判斷這個标注成立的機率為 P= F(s轉移到s,’我’表現為s)….F為一個函數，是在全局範圍統計歸一化的機率而不是像MEMM在局部統計歸一化的機率。

CRF沒有HMM那樣嚴格的獨立性假設條件，因而可以容納任意的上下文資訊。特征設計靈活（與ME最大熵一樣） ————與HMM比較

同時，由于CRF計算全局最優輸出節點的條件機率，它還克服了最大熵馬爾可夫模型标記偏置（Label-bias）的缺點。 ————與MEMM比較

CRF是在給定需要标記的觀察序列的條件下，計算整個标記序列的聯合機率分布，而不是在給定目前狀态條件下，定義下一個狀态的狀态分布。

凡事都有兩面，正由于這些優點，CRF需要訓練的參數更多，與MEMM和HMM相比，它存在訓練代價大、複雜度高的缺點。

表1-2 收錄了《華爾街日報》語料庫上的詞性标注任務的前沿準确率。截止 2015 年，除了 Bi-LSTM-CRF以外，其他系統都是傳統模型，最高準确率為 97.36%，而Bi-LSTM-CRF 深度學習模型為 97.55%，僅僅提高了0.19%。2016 年，傳統系統 NLP4J 通過使用額外資料與動态特征提取算法，準确率可以達到 97.64%。 ---摘自《自然語言處理入門》何晗[著]

參考

https://www.zhihu.com/question/35866596

【中文分詞】最大熵馬爾可夫模型MEMM

蘇劍林. (Feb. 24, 2020). 《CRF用過了，不妨再了解下更快的MEMM？》

蘇劍林. (May. 18, 2018). 《簡明條件随機場CRF介紹（附帶純Keras實作）》

從HMM到MEMM再到CRF

HMM、MEMM、CRF差別

⭐用命名實體識别(NER)解釋CRF (BiLSTM+CRF)

⭐條件随機場(CRF)

NLP：HMM、MEMM、CRF序列标注前言# 原理：Markov Chains馬爾科夫鍊# 原理：HMM 隐式馬爾可夫模型① HMM Tagger# 原理：最大熵原理② Maximum Entropy Markov Models最大熵馬爾可夫模型③ CRF條件随機場# HMM、MEMM、CRF差別參考

前言

# 原理：Markov Chains馬爾科夫鍊

# 原理：HMM 隐式馬爾可夫模型

① HMM Tagger

舉例

# 原理：最大熵原理

② Maximum Entropy Markov Models最大熵馬爾可夫模型

Bi-MEMM 雙向MEMM

HMM V.S. MEMM

③ CRF條件随機場

MEMM V.S. CRF

# HMM、MEMM、CRF差別

參考

繼續閱讀

seq2seq模型 + Attention機制

傳統的seq2seq模型與seq2seq with attention的模型原理細節解析

torch.nn.Embedding的使用torch.nn.Embedding

nn.Embedding()參數的了解nn.Embedding()

pytorch中nn.RNN()總結

聯考志願填報：人工智能專業怎麼樣？人工智能行業發展前景如何？

【Python學習筆記】- Day6

Windows版本的Google word2vec和Stanford GloVe工具

seq2sqe與attenton實作聊天機器人

奮戰聊天機器人（四）自然語言進行中的文本分類nltk中的貝葉斯分類器

從詞向量衡量标準到全局向量的詞嵌入模型GloVe再到一詞多義的解決方式衡量标準Evaluation引子全局向量的詞嵌入應用對一詞多義的思考Reference

GloVe與word2vec的差別，及GloVe的缺陷

統計學習大作業-BERT模型1 文本處理-BERT模型2 參考資料：

anaconda中科大鏡像

NLP從入門到放棄_IBM Model1IBM Model1

解碼器用于語義分割：資料依賴的解碼可以實作靈活的特征聚合