定義及區(qū)別

1. 隨機(jī)場(chǎng)：
   隨機(jī)場(chǎng)是有若干個(gè)位置組成的整體，對(duì)于每個(gè)位置安裝某種分布隨機(jī)賦予一個(gè)值琐旁，其全體就叫做隨機(jī)場(chǎng)碉京。

2.馬爾可夫隨機(jī)場(chǎng)
馬爾可夫隨機(jī)場(chǎng)是隨機(jī)場(chǎng)的一個(gè)特例，它假設(shè)隨機(jī)場(chǎng)中某一個(gè)位置的賦值僅僅只和他相鄰的位置的賦值有關(guān)课舍，與其他位置的賦值無(wú)關(guān)塌西。

3. 條件隨機(jī)場(chǎng)
   條件隨機(jī)場(chǎng)(CRF)是馬爾可夫隨機(jī)場(chǎng)的特例，他假設(shè)馬爾可夫隨機(jī)場(chǎng)中只有X和Y兩種變量筝尾，X一般是給定的雨让，Y是根據(jù)給定X的條件下的輸出。

給出數(shù)學(xué)定義就是忿等，設(shè)X與Y是隨機(jī)變量栖忠，P(Y|X)是給定X時(shí)Y的條件概率分布，若隨機(jī)變量Y構(gòu)成的是一個(gè)馬爾科夫隨機(jī)場(chǎng)贸街，則稱條件概率分布P(Y|X)是條件隨機(jī)場(chǎng)庵寞。

4. 線性鏈條件隨機(jī)場(chǎng)
   假設(shè)X 和Y有相同的結(jié)構(gòu)的CRF就構(gòu)成了線性鏈條件隨機(jī)場(chǎng)(Linear chain Conditional Random Fields,簡(jiǎn)稱 linear-CRF)。

給出數(shù)學(xué)定義 設(shè)X=(X1,X2,...Xn),Y=(Y1,Y2,...Yn)均為線性鏈表示的隨機(jī)變量序列薛匪，在給定隨機(jī)變量序列X的情況下捐川，隨機(jī)變量Y的條件概率分布P(Y|X)構(gòu)成條件隨機(jī)場(chǎng)，即滿足馬爾科夫性：
P(Yi|X,Y1,Y2,...Yn)=P(Yi|X,Yi?1,Yi+1)
則稱P(Y|X)為線性鏈條件隨機(jī)場(chǎng)逸尖。

馬爾可夫過(guò)程

定義：
假設(shè)一個(gè)隨機(jī)過(guò)程中古沥，tn時(shí)刻的狀態(tài)xn的條件發(fā)布，知與前一個(gè)狀態(tài)xn-1相關(guān)娇跟，即：

這個(gè)過(guò)程就是為馬爾可夫過(guò)程岩齿。

image.png

隱馬爾科夫算法

定義：
隱式馬爾可夫算法是對(duì)有未知參數(shù)(隱狀態(tài))的馬爾可夫鏈進(jìn)行建模的生成模型,如下圖所示：

在隱馬爾可夫中，包含隱狀態(tài)和觀察狀態(tài)苞俘，隱狀態(tài)xi對(duì)于觀察者而言是不可見(jiàn)的盹沈，
觀察狀態(tài)yi對(duì)于觀察者是可見(jiàn)的。
隱狀態(tài)之間存在轉(zhuǎn)移概率吃谣，隱狀態(tài)xi到對(duì)應(yīng)的觀察狀態(tài)yi之間存在輸出概率乞封。

假設(shè)：

1. 假設(shè)隱藏狀態(tài)xi的狀態(tài)滿足馬爾可夫過(guò)程做裙，i時(shí)刻的狀態(tài)xi的條件分布，僅與前一個(gè)狀態(tài)xi-1相關(guān)肃晚，即：
   

2. 假設(shè)觀察序列中的各個(gè)狀態(tài)僅取決于他所對(duì)應(yīng)的隱狀態(tài)锚贱，即：
   

存在問(wèn)題
在序列問(wèn)題中，隱狀態(tài)(標(biāo)注)不僅和單個(gè)觀測(cè)狀態(tài)相關(guān)关串，還和觀察序列的長(zhǎng)度惋鸥、上下文等信息相關(guān)。例如詞性標(biāo)注問(wèn)題中悍缠，一個(gè)詞被標(biāo)注為動(dòng)詞還是名詞，不僅和本身以及前一個(gè)詞的標(biāo)注有關(guān)耐量，還和上下文中的其他詞相關(guān)飞蚓。

條件隨機(jī)場(chǎng) （以線性鏈條件隨機(jī)場(chǎng)為例）

定義：
給定 ， 均為線性鏈表示的隨機(jī)變量
序列廊蜒，若在給隨機(jī)變量序列X的條件下趴拧，隨機(jī)變量序列Y的條件概率分布P(Y|X)構(gòu)成條件隨機(jī)場(chǎng)，即滿足馬爾可夫性：

則稱為 P(Y|X) 為線性鏈條件隨機(jī)場(chǎng)山叮。

通過(guò)去除了隱馬爾科夫算法中的觀測(cè)狀態(tài)相互獨(dú)立假設(shè)著榴，使算法在計(jì)算當(dāng)前隱狀態(tài) xi 時(shí)，會(huì)考慮整個(gè)觀測(cè)序列屁倔，從而獲得更高的表達(dá)能力脑又，并進(jìn)行全局歸一化解決標(biāo)注偏置問(wèn)題。

參數(shù)化形式

其中：

Z(x)為歸一化因子锐借，在全局范圍進(jìn)行歸一化问麸，就是整個(gè)隱狀態(tài)序列x1....n的全部可能，從而解決了局部歸一化帶來(lái)的偏置問(wèn)題钞翔。

tk 為定義在邊上的特征函數(shù)严卖，轉(zhuǎn)移特征，依賴于前一個(gè)和當(dāng)前位置

s1 為定義在節(jié)點(diǎn)上的特征函數(shù)布轿，狀態(tài)特征哮笆，依賴于當(dāng)前位置。

簡(jiǎn)化形式

因?yàn)闂l件隨機(jī)場(chǎng)中同一特征在各個(gè)位置都有定義汰扭，所以可以對(duì)同一個(gè)特征在各個(gè)位置求和稠肘，將局部特征函數(shù)轉(zhuǎn)化為一個(gè)全局特征函數(shù)，這樣就可以將條件隨機(jī)場(chǎng)寫成權(quán)值向量和特征向量的內(nèi)積形式萝毛，即條件隨機(jī)場(chǎng)的簡(jiǎn)化形式启具。

step1：
將轉(zhuǎn)移特征和狀態(tài)特征及其權(quán)值用統(tǒng)一的符合表示，設(shè)有k1個(gè)轉(zhuǎn)移特征珊泳，k2個(gè)狀態(tài)特征鲁冯，K=k1+k2 記

step2：
對(duì)轉(zhuǎn)移與狀態(tài)特征在各個(gè)位置i求和拷沸，記作

step3：
將 λx 和 μl 用統(tǒng)一的權(quán)重表示，記作

step4：
轉(zhuǎn)化后的條件隨機(jī)場(chǎng)可表示為：

step5：
若 w 表示權(quán)重向量：

以 F(y,x) 表示特征向量薯演，即

則撞芍，條件隨機(jī)場(chǎng)寫成內(nèi)積形式為：

矩陣形式：

將linear-CRF的參數(shù)化形式寫成矩陣形式。為此我們定義一個(gè)m×m的矩陣M跨扮，m為y所有可能的狀態(tài)的取值個(gè)數(shù)序无。M定義如下：

我們引入起點(diǎn)和終點(diǎn)標(biāo)記y0=start,yn+1=stop, 這樣，標(biāo)記序列y的規(guī)范化概率可以通過(guò)n+1個(gè)矩陣元素的乘積得到衡创，即：

其中Zw(x)為規(guī)范化因子帝嗡。

條件隨機(jī)場(chǎng)包含概率計(jì)算問(wèn)題、學(xué)習(xí)問(wèn)題和預(yù)測(cè)問(wèn)題三個(gè)問(wèn)題璃氢。

1. 概率計(jì)算問(wèn)題：已知模型的所有參數(shù)哟玷，計(jì)算觀測(cè)序列 Y 出現(xiàn)的概率，常用方法：前向和后向算法一也；
2. 學(xué)習(xí)問(wèn)題：已知觀測(cè)序列 Y 巢寡，求解使得該觀測(cè)序列概率最大的模型參數(shù)，包括隱狀態(tài)序列椰苟、隱狀態(tài)間的轉(zhuǎn)移概率分布和從隱狀態(tài)到觀測(cè)狀態(tài)的概率分布抑月，常用方法：Baum-Wehch 算法；
3. 預(yù)測(cè)問(wèn)題：已知模型所有參數(shù)和觀測(cè)序列 Y 舆蝴，計(jì)算最可能的隱狀態(tài)序列 X ,常用算法：維特比算法谦絮。

1.概率計(jì)算問(wèn)題

給定條件隨機(jī)場(chǎng) P(Y|X) ，輸入序列 x 和 輸出序列 y ;
計(jì)算條件概率

計(jì)算相應(yīng)的數(shù)學(xué)期望問(wèn)題洁仗；

向前-向后算法：

• 向前算法
  向前計(jì)算:
  對(duì)觀測(cè)序列 x 的每個(gè)位置 i=1,2,...,n+1 挨稿，定義一個(gè) m 階矩陣（ m 為標(biāo)記 Yi 取值的個(gè)數(shù)）
  

對(duì)每個(gè)指標(biāo) i=0,1,...,n+1 ，定義前向向量 αi(x) 京痢，則遞推公式:

其中奶甘，

向后計(jì)算:
對(duì)每個(gè)指標(biāo) i=0,1,...,n+1 ，定義前向向量 βi(x) 祭椰，則遞推公式:

概率計(jì)算：
所以臭家，標(biāo)注序列在位置 i 是標(biāo)注 yi 的條件概率為：

其中：

期望計(jì)算：
通過(guò)利用前向-后向向量，計(jì)算特征函數(shù)關(guān)于聯(lián)合概率分布 P(X,Y) 和 條件概率分布 P(Y|X) 的數(shù)學(xué)期望方淤，即特征函數(shù) fk 關(guān)于條件概率分布 P(Y|X) 的數(shù)學(xué)期望：

其中钉赁，

2. 學(xué)習(xí)問(wèn)題

這里主要介紹一下 BFGS 算法的思路。

輸入：特征函數(shù) ：經(jīng)驗(yàn)分布 携茂；

輸出：最優(yōu)參數(shù)值 你踩，最優(yōu)模型。

1. 選定初始點(diǎn) w^{(0)}， 取 為正定對(duì)稱矩陣带膜，k = 0;

2. 計(jì)算 吩谦，若 ，則停止計(jì)算膝藕，否則轉(zhuǎn) (3) 式廷；

3. 利用 計(jì)算 ；

4. 一維搜索：求 使得
   

5. 設(shè)

6. 計(jì)算 = g(w^{(k+1)}),

   若 芭挽， 則停止計(jì)算滑废；否則，利用下面公式計(jì)算 :
   

7. 令 袜爪，轉(zhuǎn)步驟（3）蠕趁；

3. 預(yù)測(cè)問(wèn)題

對(duì)于預(yù)測(cè)問(wèn)題，常用的方法是維特比算法辛馆，其思路如下：

輸入：模型特征向量 和權(quán)重向量 俺陋，輸入序列（觀測(cè)序列） ；

輸出：條件概率最大的輸出序列（標(biāo)記序列）怀各，也就是最優(yōu)路徑；

1. 初始化

   
   

2. 遞推术浪，對(duì)
   

3. 終止

   
   

4. 返回路徑

   
   

求得最優(yōu)路徑

總結(jié)

linear-CRF模型是判別模型瓢对，即linear-CRF模型要優(yōu)化求解的是條件概率P(y|x),

linear-CRF是利用最大熵模型的思路去建立條件概率模型，對(duì)于觀測(cè)序列并沒(méi)有做馬爾科夫假設(shè)胰苏。

參考材料

條件隨機(jī)場(chǎng)