HMM MEMM CRF

01-24

概率模型提供了一種描述框架，將學習任務歸結於計算變數的概率分布。在概率模型中，利用已知變數推測未知變數的分布稱為「推斷」，其核心是如何基於可觀測變數推測未知變數的條件分布。

概率圖模型是一類用圖來表達變數相關關係的概率模型。概率圖模型可大致分為兩類：

使用有向無環圖表示變數間的依賴關係，稱為有向圖模型或貝葉斯網
使用無向圖表示變數間的相關關係，稱為無向圖模型或馬爾可夫網

隱馬爾可夫模型（HMM）

HMM是一種結構比較簡單的動態貝葉斯網路結構。在隱馬爾可夫模型中，有兩組變數：

不可觀測的狀態變數（隱變數） ${y_1,y_2,cdots,y_n}$ ，其中 $y_i$ 表示第i時刻的系統狀態
觀測變數 ${x_1,x_2,cdots,x_n}$ ，其中 $x_i$ 表示第i時刻的觀測值

其中隱變數 $y_iin Y$ （狀態空間）通常是有N個取值的離散空間。而觀測變數 $x_iin X$ （觀測空間）可以為離散型也可以為連續型，這裡僅討論離散型（M個取值）。

HMM模型的圖結構如上所示，圖中的箭頭顯示了變數間的依賴關係，可以看出HMM模型就是一個馬爾可夫鏈：

觀測變數的取值僅依賴於當前的狀態變數
當前的狀態變數僅由上一個狀態變數決定，不依賴於其他的任何變數

這種性質決定了HMM中所有變數的聯合概率分布為

$P(x_1,y_1,cdots,x_n,y_n)=P(y_1)prod^n_{i=2}P(y_i|y_{i-1})P(x_i|y_i)$

顯而易見，HMM還需要下面三類參數：

狀態轉移概率：記為矩陣 $A=[a_{ij}]_{N imes N}$ ，其中 $a_{ij}=P(y_{t+1}=s_j|y_t=s_i),~~~~1leq i,jleq N$ ，s代表狀態的取值
輸出觀測概率：記為矩陣 $B=[b_{ij}]_{N imes M}$ ，其中 $b_{ij}=P(x_{t}=o_j|y_t=s_i),~~~~1leq ileq N, 1leq jleq M$ ，o代表觀測值
初始狀態概率：模型在初始時刻各狀態的概率，記作 $pi=(pi_1,pi_2,cdots,pi_N)$ ，其中 $pi_i=P(y_1=s_i)~~~~1leq ileq N$

通過指定狀態空間 $Y$ 、觀測空間 $X$ 、以及參數 $lambda=[A,B,pi]$ ，就能確定一個隱馬爾可夫模型。而根據馬爾可夫性，HMM產生觀測序列的過程也很簡單了。

在實際應用中，通常關注HMM的三個基本問題：

概率計算問題：給定模型 $lambda=[A,B,pi]$ ，有效計算其產生觀測序列 $x={x_1,x_2,cdots,x_n}$ 的概率 $P(x|lambda)$ （前向演算法）

預測問題（解碼問題）：給定模型 $lambda=[A,B,pi]$ 和觀測序列 $x={x_1,x_2,cdots,x_n}$ ，找到與此觀測序列最匹配的狀態序列 $y={y_1,y_2,cdots,y_n}$ （維特比演算法）

學習問題：給定觀測序列 $x={x_1,x_2,cdots,x_n}$ ，找到適合的模型參數 $lambda=[A,B,pi]$ 使得該序列出現的概率 $P(x|lambda)$ 最大（前向-後向演算法）

最大熵馬爾可夫模型（MEMM）

MEMM是一種判別式有向圖模型。對比於HMM的聯合概率分布

$P(x_1,y_1,cdots,x_n,y_n)=P(y_1)prod^n_{i=2}P(y_i|y_{i-1})P(x_i|y_i)$

MEMM直接對條件概率建模，用 $P(y_i|y_{i-1}, x_i)$ 來代替HMM中的兩個條件概率，它表示在先前狀態 $y_{i-1}$ ，觀測值 $x_i$ 下得到當前狀態 $y_i$ 的概率，即根據前一狀態和當前觀測預測當前狀態。從圖結構可以明白地展示出來

也就是

$P(y|x)=P(y_1)prod^n_{i=2}P(y_i|y_{i-1},x_i)$

$P_{y_{i-1}}(y_i|x_{i})=frac{1}{Z(x_{i},y_{i-1})}sum_a^m(lambda_af_a(x_{i},y_i))$

每個這樣的分布函數 $P_{y_{i-1}}(y_i|x_i)$ 都是一個服從最大熵的指數模型。

由於MEMM在 $(y_{i-1},x_i,y_i)$ 做了局部歸一化，因而可能會產生標註偏置的問題。

MEMM vs HMM：

HMM是生成式模型，MEMM是判別式模型
HMM由隱藏狀態產生輸入（觀測），MEMM基於輸入（觀測）產生隱藏狀態（condition on observations）
相比於MEMM，HMM更不直觀，因為目標是預測出隱藏狀態，而不是基於隱藏狀態來預測觀測
HMM的馬爾可夫性導致觀測值嚴格獨立，MEMM摒棄了這個假設，可以在長距離上得到features（每一個分布函數也可以定義為 $P_{y_{i-1}}(y_i|x_{1:n})=frac{1}{Z(x_{1:n},y_{i-1})}sum_a^m(lambda_af_a(x_{1:n},y_i))$ ）

條件隨機場（CRF）

條件隨機場是一種判別式無向圖模型（滿足於馬爾可夫性）。具體來說若 $x={x_1,x_2,cdots,x_n}$ 為觀測序列， $y={y_1,y_2,cdots,y_n}$ 為對應的標記序列，則條件隨機場的目標是對 $P(y|x)$ 建模。通常情況下我們討論的都是鏈式條件隨機場（下面稱為CRF）

CRF的條件概率被定義為

$P(y|x)=frac{1}{Z}exp(sum_jsum_{i=1}^{n-1}lambda_jt_j(y_{i+1},y_i,x,i)+sum_ksum_{i=1}^nu_ks_k(y_i,x,i))$

其中 $t_j(y_{i+1},y_i,x,i)$ 是定義在觀測序列的兩個相鄰標記位置上的轉移特徵函數，用於刻畫相鄰標記變數之間的相關關係以及觀測序列對它們的影響， $s_k(y_i,x,i)$ 是定義在觀測序列的標記位置i上的狀態特徵函數，用於刻畫觀測序列對標記變數的影響， $lambda_i,u_k$ 為參數，Z為規範化因子。因而使用條件隨機場的關鍵在於定義合適的特徵函數。

MEMM vs CRF：

MEMM有向圖模型，CRF無向圖模型
從概率公式上也可以看出，CRF的歸一化在模型上更加合理，是全局性的，相比於MEMM的局部歸一化更優，因而解決了MEMM存在的標註偏置問題
CRF的特徵函數定義非常靈活，還可以使用外部特徵，保證了獲取信息的豐富性

參考

《機器學習》周志華
MEMM&CRF
如何用簡單易懂的例子解釋條件隨機場（CRF）模型？它和HMM有什麼區別？
如何理解CRF？
HMM MEMM CRF 區別聯繫
hmm-memm-crf