2019年2月份的時候?qū)戇^“理解隱馬爾可夫模型”一文，清晰而通俗地講解了隱馬爾可夫模型的原理，收到了眾多的贊譽。本篇承上啟下，用相同的風(fēng)格講解條件隨機場的原理。二者同屬應(yīng)用最廣泛的概率圖模型。本文的內(nèi)容經(jīng)過嚴格化之后加入了《機器學(xué)習(xí)與應(yīng)用》第2版（更名為《機器學(xué)習(xí)-算法，原理與應(yīng)用》），是對本書第1版的補充。第1版自2019年1月在清華大學(xué)出版社出版以來，已經(jīng)重印4次，收到了大量讀者的好評，也得到了大量反饋意見，為此做了優(yōu)化。

本文的電子版可以在張量無限在線學(xué)習(xí)平臺（www.tensorinfinity.com）免費獲取，只能用于個人學(xué)習(xí)，未經(jīng)授權(quán)不能用于任何商業(yè)目的。

序列預(yù)測問題對相互存在依賴的隨機變量序列建模。給定輸入序列x，算法預(yù)測出序列y，即實現(xiàn)如下形式的映射

x→y

與單純利用每個時刻的輸入值進行預(yù)測相比，序列預(yù)測能夠利用上下文信息。除循環(huán)神經(jīng)網(wǎng)絡(luò)、隱馬爾可夫模型之外，本文將要介紹的條件隨機場（Conditional Random Fields，簡稱CRF）也能完成此任務(wù)。條件隨機場是一種概率無向圖模型，用于在已知觀測序列x的條件下對標簽序列y的條件概率進行建模，即預(yù)測條件概率值

p(x丨y)

x和y一般都是離散型隨機變量序列。實際應(yīng)用時的目標一般為尋找條件概率最大的狀態(tài)序列，與隱馬爾可夫模型的解碼問題相同。條件隨機場在自然語言處理中的分詞，詞性標注，命名實體識別問題，計算機視覺中的圖像分割問題上得到了成功的應(yīng)用。一般的條件隨機場計算復(fù)雜度高，本文將重點介紹它的一種特殊情況-線性鏈條件隨機場。

條件隨機場是一種概率無向圖模型，也是馬爾可夫隨機場的特例。本節(jié)首先介紹概率無向圖的概念，然后在其基礎(chǔ)上介紹馬爾可夫隨機場。

概率圖模型是機器學(xué)習(xí)中的一類算法，它用圖進行建模。學(xué)過離散數(shù)學(xué)或數(shù)據(jù)結(jié)構(gòu)的同學(xué)對圖的概念不會陌生。圖的頂點為隨機變量，邊為變量之間的概率關(guān)系。如果是有向圖，則稱為概率有向圖模型；如果圖無向，則稱為概率無向圖模型。下圖是一個簡單的概率有向圖，也稱為貝葉斯網(wǎng)絡(luò)

概率有向圖模型

在上圖中有4個頂點，對應(yīng)于4個隨機變量。邊表示隨機變量之間的條件概率，如果xi到xj有一條邊，則表示它們之間的條件概率為p(xj丨xi)。以上圖為例，所有隨機變量的聯(lián)合概率為

如果頂點xi沒有邊射入，則在聯(lián)合概率的乘積項中會出現(xiàn)p(xi)。如果從頂點xi到xj有邊，則在乘積項中有p(xj丨xi)。之前介紹的隱馬爾可夫模型就是一種有向圖模型。

接下來定義團（clique）與最大團（maximal clique）的概念。如果一個無向圖的所有頂點之間均有邊連接，則稱為團。以下圖為例，子圖{x1,x2,x3}和{x2,x4}是整個圖的兩個團，而不是團，因為x3與x4之間沒有邊連接。如果一個子圖是團，再加入一個頂點之后不是團，則稱為最大團。根據(jù)定義，{x1,x2,x3}和{x2,x4}是最大團。而{x1,x2}不是最大團，因為加入頂點x3之后還是一個團。

在概率無向圖中邊是無向的，聯(lián)合概率的計算方式與有向圖不同。以下圖為例

概率無向圖模型

這里的邊不是變量之間的條件概率。計算聯(lián)合概率的方式是因子分解，計算公式為

C為無向圖的最大團，x為所有隨機變量構(gòu)成的向量，xc為團C中所有頂點對應(yīng)的隨機變量構(gòu)成的向量，為勢函數(shù)（也稱為因子）。Z為歸一化因子，用于保證上式計算出的是合法的概率值

即對x所有可能的取值求和。勢函數(shù)必須嚴格為正，一般使用指數(shù)函數(shù)

E(X)為任意函數(shù)，有時稱為能量函數(shù)。上面這種形式的無向圖模型也稱為隨機場。以上圖21.2為例，所有變量的聯(lián)合概率為

上式的兩個乘積項對應(yīng)于圖的兩個最大團。勢函數(shù)的具體設(shè)計將后面介紹。

假設(shè)u和v是無向圖中任意兩個沒有邊連接的頂點，對應(yīng)的隨機變量為xu和xv，除去這兩個頂點之外其他頂點構(gòu)成的集合為O，對應(yīng)的隨機向量為xo。如果在給定隨機向量的條件下xu和xv條件獨立，即

則稱圖滿足成對馬爾可夫性。

假設(shè)u是圖的任意頂點，W是與u有邊連接的頂點構(gòu)成的集合，O是除u和W之外的頂點構(gòu)成的集合，它們對應(yīng)的隨機變量為xu，xW和xO。如果在給定xW的條件下xu和xO條件獨立，即

則稱圖滿足局部馬爾可夫性。

假設(shè)頂點子集A和B被C分隔，即子圖A和C、B和C之間有邊連接，但A和B之間沒有邊連接。它們對應(yīng)的隨機向量為xA，xB和xC。如果在給定xC的條件下xA和xB條件獨立，即

則稱圖滿足全局馬爾可夫性。一個重要結(jié)論是上面3種馬爾可夫性是等價的。一個概率無向圖模型如果滿足上面定義的3種馬爾可夫性，則稱為馬爾可夫隨機場（Markov random field）。

下面以馬爾可夫隨機場為基礎(chǔ)，介紹條件隨機場，線性鏈條件隨機場的概念。條件隨機場是馬爾可夫隨機場的特例，而線性鏈條件隨機場又是條件隨機場的特例。

條件隨機場是馬爾可夫隨機場的特例，這種模型中有x和y兩組隨機向量。前者是觀測序列，其值可見；后者是隱變量，也稱為標簽序列，其值不可見。如果給定x的條件下y是馬爾可夫隨機場，則稱為條件隨機場。

下面給出條件隨機場的形式化定義。假設(shè)有無向圖模型，其頂點對應(yīng)的隨機向量為y，對于圖中任意頂點u，與該頂點有邊連接的頂點集合為W，除u之外的頂點的集合為O。如果滿足

則稱條件概率p(y丨x)為條件隨機場。條件隨機場中任意一個隱變量的條件概率與和該頂點沒有邊連接的頂點無關(guān)。條件隨機場的條件概率可以按照下式計算

其中m為最大團的數(shù)量，Ci為第i個最大團，xci和yci為該團的所有頂點對應(yīng)的隨機變量構(gòu)成的向量，為勢函數(shù)。Z(x)為歸一化因子

條件隨機場只對p(y丨x)建模，而沒有對p(x丨y)或p(x,y)建模，因此是一種判別模型。讀者對此千萬不要理解錯。

一般的條件隨機場需要枚舉所有的最大團，不易計算，下面介紹它的一種特殊情況，稱為線性鏈條件隨機場（linear chain conditional random field），由Lafferty等人在2001年提出[2]。線性鏈條件隨機場中的狀態(tài)變量形成一個線性鏈，類似于數(shù)據(jù)結(jié)構(gòu)中的鏈表結(jié)構(gòu)，每個節(jié)點只與前一個節(jié)點（如果存在），后一個節(jié)點（如果存在）有關(guān)。即在時間序列中每個變量只和前一時刻、后一個時刻的變量有關(guān)

下圖是一個簡單的線性鏈條件隨機場

一個簡單的線性鏈條件隨機場

上圖中觀測變量序列為x，狀態(tài)變量序列為{y1,...,y5}，每一個隱變量和所有觀測變量有概率依賴關(guān)系。除y1與y5之外，每個狀態(tài)變量只和它前一個時刻的狀態(tài)量、后一時刻的狀態(tài)變量有關(guān)，而與其他時刻的狀態(tài)變量無關(guān)。

根據(jù)條件隨機場的概率計算公式，已知觀測序列x的條件下，狀態(tài)變量的所有最大團為相鄰兩個狀態(tài)變量，如果勢函數(shù)為

狀態(tài)序列y的條件概率為

為了統(tǒng)一表述，與隱馬爾可夫模型類似，增加了一個特殊的狀態(tài)y0作為初始狀態(tài)。Z(x)為歸一化因子，是對標簽序列所有可能取值求和

t和s為特征函數(shù)，前者是轉(zhuǎn)移特征，類似于隱馬爾可夫模型中的狀態(tài)轉(zhuǎn)移概率；后者是狀態(tài)特征，類似于隱馬爾可夫模型中的觀測概率。它們根據(jù)具體的問題由人工設(shè)定。T是觀測序列的長度，n和m為特征函數(shù)的數(shù)量，由人工設(shè)定λ和μ為特征函數(shù)的權(quán)重，為模型的參數(shù)，其值越大說明此特征越有用。需要注意的是λ和μ與序列的位置無關(guān)。

特征函數(shù)s的以觀測序列x，第i個標簽值yi為輸入，根據(jù)不同的輸入值組合其輸出值為1和0，此特征函數(shù)用于對輸入變量和標簽變量的概率依賴關(guān)系建模。特征函數(shù)t以觀測序列x，第i個標簽值yi，第i-1個標簽值yi-1為輸入，其輸出值同樣為1和0，該函數(shù)用于對輸入變量與標簽變量的概率關(guān)系、相鄰標簽變量之間的概率關(guān)系建模。

下面以中文分詞問題為例，介紹條件隨機場如何用于實際問題，這是典型的序列標注問題。中文分詞即斷句，是自然語言處理中的核心、基礎(chǔ)問題。因為中文和英文不同，各個詞之間沒有空格隔開。對于下面的句子

在這里觀測序列是輸入的語句，每個字為每個時刻的觀測值。狀態(tài)序列為分詞的結(jié)果，每個時刻的狀態(tài)值有如下幾種情況

{B,M,E,S}

其中B表示當前字為一個詞的開始，M表示當前字是一個詞的中間位置，E表示當前字是一個詞的結(jié)尾，S表示單字詞。則上面這個句子的分詞標注結(jié)果為

我/S     是/S      中/B      國/M     人/E

顯然，得到了這個標注結(jié)果，我們就可以得到分詞結(jié)果，做法很簡單：

遇到S，則為一個單字詞；遇到B，則為一個詞的開始，直到遇到下一個E，則為一個詞的結(jié)尾。

分詞問題為給定觀測序列x，計算出條件概率p{y丨x}最大的標記序列y，對應(yīng)的就是分詞的結(jié)果。

下面是中文分詞問題狀態(tài)轉(zhuǎn)移特征函數(shù)的例子

其含義是如果句子中的第i個漢字是“是”，第i-1個漢字的標記結(jié)果為E，第i個漢字的標記結(jié)果為B時函數(shù)返回1，否則返回0。

如果在訓(xùn)練文件中有句子“我是中國人”，則會生成下列狀態(tài)特征函數(shù)（限于篇幅，只列出了一部分）

if (x_i = ‘我’ and y_i = B) return 1 else return 0

if (x_i = ‘我’ and y_i = M) return 1 else return 0

if (x_i = ‘我’ and y_i = E) return 1 else return 0

if (x_i = ‘我’ and y_i = S) return 1 else return 0

if (x_i = ‘是’ and y_i = B) return 1 else return 0

if (x_i = ‘是’ and y_i = M) return 1 else return 0

if (x_i = ‘是’ and y_i = E) return 1 else return 0

if (x_i = ‘是’ and y_i = S) return 1 else return 0

其中x_i為公式中的xi，y_i為公式中的yi。如果字典中的字符數(shù)為D，標簽的取值數(shù)為L，則上面這種狀態(tài)特征函數(shù)的總數(shù)為D×L。另外還會生成下列狀態(tài)轉(zhuǎn)移特征函數(shù)（同樣只列出了一部分）

if (x_i= ‘我’ and y_i_1 = B and y_i = B) return 1 else return 0

if (x_i= ‘我’ and y_i_1 = B and y_i = M) return 1 else return 0

if (x_i= ‘我’ and y_i_1 = B and y_i = E) return 1 else return 0

if (x_i= ‘我’ and y_i_1 = B and y_i = S) return 1 else return 0

其中y_i_1為公式中的yi-1。對于這種情況，狀態(tài)轉(zhuǎn)移函數(shù)的總數(shù)為D×L×L。除了上面兩種最簡單的特征函數(shù)之外，在實現(xiàn)時還可以設(shè)計更復(fù)雜的特征函數(shù)，以對更長的上下文依賴進行建模。特征函數(shù)可以看作輸入序列與標簽位置關(guān)系的規(guī)則。

每一個特征函數(shù)都可以用來為一個標注序列評分，把集合中所有特征函數(shù)對同一個標簽序列的評分綜合起來，得到標簽序列最終的評分值。

如果將兩種特征函數(shù)合并，條件概率可以寫成

其中T為序列長度，n為特征函數(shù)的數(shù)量。歸一化因子變?yōu)?/p>

線性鏈條件隨機場的因子分解為所有相鄰兩個狀態(tài)變量，如下圖所示

線性鏈條件隨機場的因子分解

對上面的條件概率取對數(shù)，Z(x)是一個常數(shù)，因此條件隨機場是一個對數(shù)線性模型

以中文分詞為例，要建立條件隨機場需要定義特征函數(shù)集。每個特征函數(shù)以整個句子x，當前位置i，位置i和i-1處的標簽作為輸入。模型訓(xùn)練完成之后，每一個特征函數(shù)有一個權(quán)重，對每一個標注序列l(wèi)，對所有的特征函數(shù)加權(quán)求和，通過指數(shù)變換和歸一化得到條件概率值。

推斷問題指給定模型的參數(shù)和觀測序列x，計算條件隨機場的各種概率值，分為兩個問題。第一個推理問題是給定條件隨機場的參數(shù)，以及觀測序列x，找到條件概率最大的狀態(tài)序列y，即求解如下極值問題

這類似于隱馬爾可夫模型的解碼問題。第二個問題是計算標簽序列子集的邊緣分布，如節(jié)點的邊緣概率p(yt丨x)以及邊的邊緣概率p(yt,yt-1丨x)，這些值將被訓(xùn)練算法使用。

首先考慮第二個問題。與隱馬爾可夫模型面臨的問題相同，如果直接計算p(yt,yt-1丨x)，需要考慮狀態(tài)序列除t和t-1時刻之外其他所有時刻所有可能的取值情況，計算量是指數(shù)級的。實現(xiàn)時采用遞推計算的思路，定義函數(shù)

定義前向變量

它表示t時刻取值為i，1到t-1時刻取值任意的狀態(tài)序列出現(xiàn)的概率。這里的求和符號表示對狀態(tài)序列中1到t-1時刻所有可能的取值情況求和。求和項表示從1到t-1時刻按照某種取值，t時刻取值為i的狀態(tài)序列的概率。前向變量的初始值為

根據(jù)定義，前向變量滿足下面的遞推公式

其中S為標記變量的取值集合。根據(jù)前向變量可以計算出歸一化因子的值

類似的定義后向變量

它表示t時刻值為i，t+1到T時刻取值為任意的狀態(tài)序列出現(xiàn)的概率。根據(jù)定義可以得到下面的遞推公式

初始值為根據(jù)前向變量和后向變量可以方便的計算出下面的邊緣概率值，根據(jù)前向變量、后向變量的定義有

現(xiàn)時先計算各個時刻的前向變量和后向變量值，然后按照上面的公式計算出條件概率值。這一過程如下圖所示

前向變量和后向變量的遞推計算

類似的有

對于解碼問題，定義變量下面的遞推變量

根據(jù)定義可以建立遞推公式

根據(jù)這一遞推公式可以找到條件概率最大的標記序列。解碼問題的最優(yōu)解可以按照下面的公式計算

具體流程類似于求解隱馬爾可夫模型解碼問題的維特比算法，不再重復(fù)講述。

條件隨機場在訓(xùn)練時確定參數(shù)λ的值。給定訓(xùn)練樣本集D={xi,yi}，i=1,...N,每個樣本是由觀測序列xi與狀態(tài)序列yi構(gòu)成的。訓(xùn)練時的目標是最大化此訓(xùn)練集的條件概率值，這通過最大似然估計實現(xiàn)。

訓(xùn)練算法采用最大似然估計，使得一組樣本的條件概率的乘積最大化，求解下面的對數(shù)似然函數(shù)的極大值

將條件概率的計算公式代入目標函數(shù)可以得到

這個問題是凸優(yōu)化問題（求凹函數(shù)的極大值，對于凸優(yōu)化，SIGAI之前的公眾號文章《理解凸優(yōu)化》有詳細的講解），因此可以保證得到全局最優(yōu)解。為防止過擬合，可以為目標函數(shù)加上正則化項。如果使用L2正則化項，目標函數(shù)為

加上正則項后還是凸優(yōu)化問題。σ為人工設(shè)定的常數(shù)。如果采用L1正則化項，目標函數(shù)為

α是人工設(shè)定的常數(shù)。如果使用L2正則化，目標函數(shù)對參數(shù)的偏導(dǎo)數(shù)為

目標函數(shù)前半部分的導(dǎo)數(shù)容易計算，是λ的線性函數(shù)。下面計算lnZ(xi)的導(dǎo)數(shù)，根據(jù)鏈式法則有

導(dǎo)數(shù)計算公式中的第一項是訓(xùn)練樣本集對單個特征fk的數(shù)學(xué)期望

其值容易計算。第二項是訓(xùn)練樣本集對條件隨機場所定義的概率分布的數(shù)學(xué)期望

此值的計算要對標簽序列y的所有取值情況進行求和，直接計算的成本太高，可以借助21.3節(jié)的算法高效的實現(xiàn)。利用之前定義的前向變量和后向變量，其計算公式為

實際應(yīng)用中特征函數(shù)、觀測值的取值數(shù)量可能非常大，梯度下降法、牛頓法求解速度太慢，一般采用L-BFGS算法，其原理在《機器學(xué)學(xué)習(xí)與應(yīng)用》一書中有詳細的講解。

條件隨機場在很多序列標注問題上得到了應(yīng)用。在自然語言處理中，被用于解決中文分詞[3]，詞性標注[4]等問題。除了單獨使用，還可以與深度神經(jīng)網(wǎng)絡(luò)如卷積神經(jīng)網(wǎng)絡(luò)、循環(huán)神經(jīng)網(wǎng)絡(luò)整合，完成圖像分割、詞性標注等任務(wù)。