數(shù)學推導+純Python實現(xiàn)機器學習算法23:CRF條件隨機場

Python機器學習算法實現(xiàn)

Author：louwill

Machine Learning Lab

? ? ?

? ? ?本文我們來看一下條件隨機場（Conditional Random Field，CRF）模型。作為概率圖模型的經(jīng)典代表之一，CRF理解起來并不容易。究其緣由，還是在于CRF模型過于抽象，大量的概率公式放在一起時常讓人犯暈。還有就是即使理解了公式，很多朋友也迷惑CRF具體用在什么地方。

? ? ?所以在本文的開頭，我們先具體化一個應用場景，明確一下CRF的用途。就拿筆者來舉例：假設現(xiàn)在有筆者從早到晚的一系列照片，現(xiàn)在我們想根據(jù)這些照片對筆者日?；顒舆M行分類，比如說吃飯、上班、學習等等。要達到這個目的我們可以訓練一個圖像分類模型來對圖片所對應的活動進行分類。在訓練數(shù)據(jù)足夠的情況下，我們是可以達到這個分類目的的。但這種方法一個最大的缺陷在于忽略了筆者這些照片之間是存在時序關系的，如果能確定某一張照片的前一張或者后一張的活動狀態(tài)，那對于我們做分類工作大有幫助。而CRF模型就是一種能夠考慮相鄰時序信息的模型。比如說詞性標注就是CRF最常用的一個場景之一。另外在早期深度學習語義分割模型中，CRF也被作為的一種后處理技術來優(yōu)化神經(jīng)網(wǎng)絡的分割結果。

概率無向圖

? ? 概率圖模型是一種用圖來表示概率分布的模型。而概率無向圖模型（Probabilistic Undirected Graphical Model）也叫馬爾可夫隨機場（Markov Random Field），是一種用無向圖來表示聯(lián)合概率分布。

? ? 假設有聯(lián)合概率分布，由無向圖表示，其中圖的結點表示隨機變量，邊表示為隨機變量之間的依賴關系。如果聯(lián)合概率分布滿足成對、局部或者全局馬爾可夫性，則該聯(lián)合概率分布為概率無向圖模型。所謂馬爾可夫性，即在給定一組隨機變量的條件下，另外兩個隨機變量之間的條件獨立性。

? ? 無向圖中任何兩個結點均有邊連接的結點子集稱為團，若為的一個團，且不能再加進任何一個結點使其成為更大的團，則稱為的最大團?；谧畲髨F，概率無向圖模型的聯(lián)合概率分布可寫作圖中所有最大團上的函數(shù)的乘積形式：

其中為規(guī)范化因子：

花一點篇幅說一下概率無向圖，主要在于CRF是一種概率無向圖模型。所以它滿足概率無向圖的一些特征，包括上述最大團函數(shù)乘積條件。

CRF詳解

CRF定義

? ? CRF就是在給定隨機變量的條件下，隨機變量的馬爾可夫隨機場。假設和為隨機變量，是給定的條件下的條件概率分布。并且當該條件概率分布能夠構成一個由無向圖表示的馬爾可夫隨機場，即：

? ? 其中表示在圖中與結點有邊連接的所有結點，表示結點以外的所有結點。從CRF的定義我們大致能夠明白它就是一個滿足馬爾可夫隨機場的條件概率分布，我們以線性鏈CRF為例來看其參數(shù)化表達方法。

CRF參數(shù)化表達

? ? 假設為線性CRF，在隨機變量取值為的條件下，隨機變量取值為的條件概率具備如下形式：

其中:

上式中和為特征函數(shù)，和為對應的權值，為規(guī)范化因子，求和是在所有可能的輸出序列上進行的。為了加深對上述式子的理解，我們以一個例子來說明：假設我們要進行一個詞性標注任務，那么上式中就是輸入的整個句子，為當前位置，和為當前位置和前一位置的標簽，以上四項作為特征函數(shù)的輸入。其中為轉(zhuǎn)移特征函數(shù)，為狀態(tài)特征函數(shù)。當滿足特征條件時特征函數(shù)取值為1，不滿足時取值為0。

線性CRF的三個問題

? ? 線性CRF需要解決三個核心問題，包括基于前向-后向的概率估計算法、基于極大似然和牛頓優(yōu)化的學習算法以及基于維特比算法的預測算法。

前向-后向算法

? ? 所謂CRF的概率估計算法，即給定條件概率分布和輸入輸出序列和時，計算條件概率和以及對應的期望。

? ? 要計算條件概率和，我們可以使用前向-后向算法。先看前向計算過程。定義表示當序列位置的標記為時，在位置之前的部分標記序列的非規(guī)范化概率，下式定義了給定下從轉(zhuǎn)移到的非規(guī)范化概率：

? ? 相應的可以得到序列位置的標記為時，在位置之前的部分標記序列的非規(guī)范化概率的遞推公式：

在序列起點處定義：

假設可能標記的總數(shù)為，則的取值有個，用表示這個值組成的前向向量如下：

用矩陣表示由構成的階矩陣：

最后的遞推公式可以由矩陣表達為：

同理可定義后向計算過程，即定義為序列位置的標記時，在位置之后的部分標記序列的非規(guī)范化概率的遞推公式：

在序列終點處定義：

其向量化表達為：，而規(guī)范化因子為：

最后的向量表達為：
。

按照前向-后向算法，我們可計算標記序列在位置是標記的條件概率和在位置與是標記和的條件概率：

CRF模型學習算法

? ? 線性CRF是如何訓練的呢？在給定訓練數(shù)據(jù)集和對應標記序列以及個特征函數(shù)，需要學習的包括模型參數(shù)和條件概率，且條件概率和模型參數(shù)滿足如下關系：

? ? 這個式子是不是有點眼熟？其實就是softmax表達式。當訓練得到模型參數(shù)之后，我們就可以根據(jù)上式計算出條件概率。

? ? ?線性CRF的學習模型實際上是定義在時序數(shù)據(jù)上的對數(shù)線形模型，其學習方法包括極大似然估計和正則化的極大似然估計方法。模型優(yōu)化算法包括梯度下降法、牛頓法、擬牛頓法以及迭代尺度法等。具體的優(yōu)化算法求解這里略過。

CRF模型預測算法

? ? CRF的預測問題是給定條件隨機場和輸入序列，求條件概率最大的輸出序列，即要對觀測序列進行標注。CRF使用維特比（Viterbi）算法進行標注預測。

我們先看一下維特比算法的輸入輸出和基本流程。維特比算法的輸入是模型的特征向量和權值向量以及觀測序列，輸出為最優(yōu)路徑。其算法流程如下：

• 初始化

• 遞推。對于，有：

• 終止：，

• 返回路徑：

按照上述維特比算法可球的最優(yōu)路徑。

? ? ?可以看到維特比算法本質(zhì)上是一種求最優(yōu)路徑的動態(tài)規(guī)劃算法，但上述流程理解起來過于抽象，是否有更加具體的方式來理解呢。

? ? ?假設我們要在下述有向圖中找出一條從到的最短路徑。最簡單粗暴的方法莫過于遍歷所有路徑然后比較一條最短的，但這么做時間復雜度太高。而維特比算法就是一種可以高效尋找最優(yōu)路徑的算法。

? ? 我們將該圖從左至右來看。先看起點到第一列的可能路徑有三種：、、。僅從第一列我們尚不能確定某一段就是最終最優(yōu)路徑中的某一段，所以我們接著看列。經(jīng)過的所有路徑有三條：、、，比較這三個路徑，選擇一個最短的，因為其他兩條不再可能是最優(yōu)路徑，我們可以將其他兩條路徑刪掉。假設這里我們保留的是最短路徑。同理我們再對和進行路徑比較，假設經(jīng)過和保留下來的最短路徑分別為和。最后我們到達終點點，將上述三條路徑鏈接點后分別比較、和，假設路徑最短，那么它就是最優(yōu)路徑。從這個過程我們可以體會到維特比算法是一個典型的動態(tài)規(guī)劃算法。

CRF實現(xiàn)

實現(xiàn)一個完整的CRF模型包括權重初始化、參數(shù)化表達、概率得分計算以及維特比解碼算法等模塊。完整的CRF實現(xiàn)參考：

https://github.com/lancifollia/crf/blob/master/crf.py

下面給出維特比算法的一個參考實現(xiàn)代碼。

import numpy as np
def viterbi(y, A, B, Pi=None):    """    Return the MAP estimate of state trajectory of Hidden Markov Model.    Parameters    ----------    y : array (T,)        Observation state sequence. int dtype.    A : array (K, K)        State transition matrix. See HiddenMarkovModel.state_transition  for        details.    B : array (K, M)        Emission matrix. See HiddenMarkovModel.emission for details.    Pi: optional, (K,)        Initial state probabilities: Pi[i] is the probability x[0] == i. If        None, uniform initial distribution is assumed (Pi[:] == 1/K).
    Returns    -------    x : array (T,)        Maximum a posteriori probability estimate of hidden state trajectory,        conditioned on observation sequence y under the model parameters A, B,        Pi.    T1: array (K, T)        the probability of the most likely path so far    T2: array (K, T)        the x_j-1 of the most likely path so far    """    # Cardinality of the state space    K = A.shape[0]    # Initialize the priors with default (uniform dist) if not given by caller    Pi = Pi if Pi is not None else np.full(K, 1 / K)    T = len(y)    T1 = np.empty((K, T), 'd')    T2 = np.empty((K, T), 'B')
    # Initilaize the tracking tables from first observation    T1[:, 0] = Pi * B[:, y[0]]    T2[:, 0] = 0
    # Iterate throught the observations updating the tracking tables    for i in range(1, T):        T1[:, i] = np.max(T1[:, i - 1] * A.T * B[np.newaxis, :, y[i]].T, 1)        T2[:, i] = np.argmax(T1[:, i - 1] * A.T, 1)
    # Build the output, optimal model trajectory    x = np.empty(T, 'B')    x[-1] = np.argmax(T1[:, T - 1])    for i in reversed(range(1, T)):        x[i - 1] = T2[x[i], i]
    return x, T1, T2

參考資料：

李航 統(tǒng)計學習方法 第二版

https://www.zhihu.com/question/20136144/answer/763021768

https://stackoverflow.com/questions/9729968/python-implementation-of-viterbi-algorithm/9730083

https://github.com/lancifollia/crf/blob/master/crf.py

往期精彩：

數(shù)學推導+純Python實現(xiàn)機器學習算法20：隨機森林

數(shù)學推導+純Python實現(xiàn)機器學習算法22：EM算法

一個算法工程師的成長之路

長按二維碼.關注機器學習實驗室

喜歡您就點個在看！