數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法23:CRF條件隨機(jī)場(chǎng)

Python機(jī)器學(xué)習(xí)算法實(shí)現(xiàn)

Author：louwill

Machine Learning Lab

? ? ?

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

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

概率無(wú)向圖

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

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

? ? 無(wú)向圖中任何兩個(gè)結(jié)點(diǎn)均有邊連接的結(jié)點(diǎn)子集稱為團(tuán)，若為的一個(gè)團(tuán)，且不能再加進(jìn)任何一個(gè)結(jié)點(diǎn)使其成為更大的團(tuán)，則稱為的最大團(tuán)。基于最大團(tuán)，概率無(wú)向圖模型的聯(lián)合概率分布可寫作圖中所有最大團(tuán)上的函數(shù)的乘積形式：

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

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

CRF詳解

CRF定義

? ? CRF就是在給定隨機(jī)變量的條件下，隨機(jī)變量的馬爾可夫隨機(jī)場(chǎng)。假設(shè)和為隨機(jī)變量，是給定的條件下的條件概率分布。并且當(dāng)該條件概率分布能夠構(gòu)成一個(gè)由無(wú)向圖表示的馬爾可夫隨機(jī)場(chǎng)，即：

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

CRF參數(shù)化表達(dá)

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

其中:

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

線性CRF的三個(gè)問(wèn)題

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

前向-后向算法

? ? 所謂CRF的概率估計(jì)算法，即給定條件概率分布和輸入輸出序列和時(shí)，計(jì)算條件概率和以及對(duì)應(yīng)的期望。

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

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

在序列起點(diǎn)處定義：

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

用矩陣表示由構(gòu)成的階矩陣：

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

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

在序列終點(diǎn)處定義：

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

最后的向量表達(dá)為：
。

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

CRF模型學(xué)習(xí)算法

? ? 線性CRF是如何訓(xùn)練的呢？在給定訓(xùn)練數(shù)據(jù)集和對(duì)應(yīng)標(biāo)記序列以及個(gè)特征函數(shù)，需要學(xué)習(xí)的包括模型參數(shù)和條件概率，且條件概率和模型參數(shù)滿足如下關(guān)系：

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

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

CRF模型預(yù)測(cè)算法

? ? CRF的預(yù)測(cè)問(wèn)題是給定條件隨機(jī)場(chǎng)和輸入序列，求條件概率最大的輸出序列，即要對(duì)觀測(cè)序列進(jìn)行標(biāo)注。CRF使用維特比（Viterbi）算法進(jìn)行標(biāo)注預(yù)測(cè)。

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

• 初始化

• 遞推。對(duì)于，有：

• 終止：，

• 返回路徑：

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

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

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

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

CRF實(shí)現(xiàn)

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

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

下面給出維特比算法的一個(gè)參考實(shí)現(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)計(jì)學(xué)習(xí)方法 第二版

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ù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法20：隨機(jī)森林

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法22：EM算法

一個(gè)算法工程師的成長(zhǎng)之路

長(zhǎng)按二維碼.關(guān)注機(jī)器學(xué)習(xí)實(shí)驗(yàn)室

喜歡您就點(diǎn)個(gè)在看！