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

哈哈哈沒(méi)錯(cuò)就是我,我我我又跑過(guò)來(lái)開(kāi)新坑了,今天來(lái)和大家嘮嘮CRF的那點(diǎn)事兒.

條件隨機(jī)場(chǎng)(conditional random field, CRF)

我們用CRF來(lái)做什么?

可以用于構(gòu)造在給定一組輸入隨機(jī)變量的條件下,另一組輸出隨機(jī)變量的條件概率分布模型.

在開(kāi)始之前

概率無(wú)向圖

即馬爾可夫隨機(jī)場(chǎng),是一個(gè)用無(wú)向圖表示的聯(lián)合概率分布.
- 定義: 圖(graph) 是由 節(jié)點(diǎn)(node) 與 邊(edge) 組成的集合,我們記節(jié)點(diǎn)為 $v$ ,記邊為 $e$ ,將節(jié)點(diǎn)和邊所處的集合分別置為
  $V$ 與 $E$ ,相應(yīng)的,我們把該圖記作 $G=(V,E)$ ,設(shè)由 $G$ 表示聯(lián)合概率分布 $P(Y)$ ,在圖 $G$ 中,每一個(gè)節(jié)點(diǎn) $v∈V$ 都表示一個(gè)隨機(jī)變量 $Y_v$ , $Y=(Y_v)_{v∈V}$ ,而與之對(duì)應(yīng)的, $e∈E$ 則表示了隨機(jī)變量之間的概率依賴關(guān)系.
- 三個(gè)性質(zhì):
  - 成對(duì)馬爾可夫性:
    $P(Y_u,Y_v|Y_O)=P(Y_u|Y_O)P(Y_v|Y_O)$
  - 局部馬爾可夫性:
    $P(Y_u,Y_W|Y_O)=P(Y_u|Y_O)P(Y_W|Y_O)$
  - 全局馬爾可夫性:
    $P(Y_M,Y_W|Y_O)=P(Y_M|Y_O)P(Y_W|Y_O)$
  顯然成對(duì),局部,全局馬爾可夫性質(zhì)都是等價(jià)的ww
- 我們可以說(shuō):
  - 如果聯(lián)合概率分布圖 $P(Y)$ 滿足成對(duì)令杈、局部或全局馬爾可夫性,則我們可以稱此聯(lián)合概率分布為概率無(wú)向圖模型或者馬爾可夫隨機(jī)場(chǎng).
- 概率無(wú)向圖因子分解:
  
  無(wú)向圖模型實(shí)例.jpg
  - 最大團(tuán): 如上圖 ${Y_1,Y_2,Y_3}$ 構(gòu)成一個(gè)最大團(tuán),該最大團(tuán)的特點(diǎn)是,從圖上的各個(gè)其他節(jié)點(diǎn)當(dāng)中,任選一個(gè)節(jié)點(diǎn),都不可能同時(shí)存在與 $Y_1,Y_2,Y_3$ 的關(guān)系,這樣的團(tuán)(clique)我們稱之為最大團(tuán)(maximal clique).
  - 無(wú)向圖會(huì)滿足如下性質(zhì):
    $P(Y)=\frac {1} {Z}\prod_C \Psi_C(Y_C)$
    
    其中,C代表一個(gè)最大團(tuán), $Y_C$ 表示C對(duì)應(yīng)的隨機(jī)變量.
    
    $Z=\sum_Y \prod_C\Psi_C(Y_C)$
    
    我們通常稱 $\Psi_C(Y_C)$ 為勢(shì)函數(shù),我們這里要求勢(shì)函數(shù) $\Psi_C(Y_C)$ 是嚴(yán)格正項(xiàng).
    
    $\Psi_C(Y_C)=exp\{-E(Y_C)\}$
    
    這里我們用指數(shù)的形式來(lái)表達(dá)是因?yàn)橹笖?shù)函數(shù)良好的性質(zhì).
  - Hammersley-Clifford 定理
    - 概率無(wú)向圖模型的聯(lián)合概率分布 $P(Y)$ 可以表示為如下形式:
      $P(Y)=\frac{1}{Z} \prod_C \Psi_C(Y_C)$
      $Z=\sum_Y \prod_C \Psi_C (Y_C)$
    其中,C是無(wú)向圖的最大團(tuán), $Y_C$ 是 $C$ 的節(jié)點(diǎn)對(duì)應(yīng)的隨機(jī)變量, $\Psi_C(Y_C)$ 是 $C$ 上定義的嚴(yán)格整函數(shù),乘積在無(wú)向圖所有的最大團(tuán)上進(jìn)行.

條件隨機(jī)場(chǎng)的基礎(chǔ)表達(dá)

條件隨機(jī)場(chǎng)(conditional random field)是給定隨機(jī)變量 $X$ 條件下,隨機(jī)變量 $Y$ 的馬爾可夫隨機(jī)場(chǎng).這里我們主要介紹定義在線性鏈上的特殊條件隨機(jī)場(chǎng),我們稱之為線性鏈馬爾可夫隨機(jī)場(chǎng)(linear chain conditional random field).在該條件概率模型 $P(Y|X)$ 中, $Y$ 是輸出變量,表示標(biāo)記序列,即狀態(tài)序列, $X$ 是輸入變量,也就是我們得到的需要標(biāo)注的觀測(cè)序列.研究學(xué)習(xí)問(wèn)題時(shí),我們利用訓(xùn)練數(shù)據(jù)集通過(guò)極大似然估計(jì)或正則化的極大似然估計(jì)得到條件概率模型 $\hat P(Y|X)$ ,在研究預(yù)測(cè)問(wèn)題時(shí),我們根據(jù)給定的輸入序列 $x$ ,求出條件概率 $\hat P(y|x)$ 最大的輸出序列 $\hat y$ .
條件隨機(jī)場(chǎng)的成立條件: 設(shè) $X$ 與 $Y$ 是隨機(jī)變量, $P(Y|X)$ 是在給定 $X$ 的條件下 $Y$ 的條件概率分布.若隨機(jī)變量 $Y$ 構(gòu)成一個(gè)由無(wú)向圖 $G=(V,E)$ 表示的馬爾可夫隨機(jī)場(chǎng),即
$P(Y_v|X,Y_w,w \ne v)=P(Y_v|X,Y_w,w~v)$
對(duì)任意結(jié)點(diǎn) $v$ 成立,則稱條件概率分布 $P(Y|X)$ 為條件隨機(jī)場(chǎng),式中 $w~v$ 表示在圖 $G=(V,E)$ 中與結(jié)點(diǎn) $v$ 有邊鏈接的所有結(jié)點(diǎn) $w$ , $w \ne v$ 表示結(jié)點(diǎn) $v$ 以外的所有節(jié)點(diǎn), $Y_v,Y_u,Y_w$ 為結(jié)點(diǎn) $v,u,w$ 分別對(duì)應(yīng)的隨機(jī)變量.
線性鏈條件隨機(jī)場(chǎng): 設(shè) $X=(X_1,X_2,...,X_n)$ , $Y=(Y_1,Y_2,...,Y_n)$ 均為線性鏈表示的隨機(jī)變量序列,若在給定的隨機(jī)變量序列 $X$ 的條件下,隨機(jī)變量序列 $Y$ 的條件概率分布 $P(Y|X)$ 構(gòu)成條件隨機(jī)場(chǎng),即滿足馬爾可夫性
$P(Y_i|X,Y_1,...,Y_{i-1},Y_{i+1},...,Y_n)=P(Y_i|X,Y_{i-1},Y_{i+1})$
$i=1,2,...,n$ (在 $i=1$ 和 $n$ 時(shí)只考慮單邊)
則稱 $P(Y|X)$ 為線性鏈條件隨機(jī)場(chǎng),在標(biāo)注問(wèn)題中, $X$ 表示輸入觀測(cè)序列, $Y$ 表示對(duì)應(yīng)的輸出標(biāo)記序列,或者我們可以稱之為狀態(tài)序列.

線性鏈條件隨機(jī)場(chǎng).png

X和Y具有相同圖結(jié)構(gòu)的線性鏈條件隨機(jī)場(chǎng).png

條件隨機(jī)場(chǎng)的參數(shù)化形式:
$P(y|x)=\frac {1} {Z(x)} exp(\sum _{i,k} \lambda _k t_k(y_{i-1},y_i,x,i)+\sum _{i,l}\mu _ls_l(y_i,x,i))$

其中, $t_k,s_l$ 是特征函數(shù), $\lambda_k,\mu_l$ 是對(duì)應(yīng)的權(quán)值,而 $Z(x)$ 是規(guī)范化因子.

$Z(x)=\sum _y exp(\sum _{i,k} \lambda _k t_k(y_{i-1},y_i,x,i)+\sum _{i,l}\mu _ls_l(y_i,x,i)$
- 其中 $t_k$ 是定義在邊上的特征函數(shù),我們稱之為轉(zhuǎn)移特征,它同時(shí)依賴于當(dāng)前位置和上一個(gè)位置.
- 而 $s_t$ 是定義在節(jié)點(diǎn)上的特征函數(shù),我們稱之為狀態(tài)特征,它僅僅依賴于當(dāng)前位置.
- 以上兩個(gè)變量都依賴于位置屬于局部特征,在滿足條件時(shí)它們的取值為1,不滿足條件時(shí),它們的取值為0.
條件隨機(jī)場(chǎng)的簡(jiǎn)化形式:為了方便記錄起見(jiàn),我們將轉(zhuǎn)移特征和狀態(tài)特征及其權(quán)值用統(tǒng)一的符號(hào)來(lái)表示.設(shè)有 $K_1$ 個(gè)轉(zhuǎn)移特征, $K_2$ 個(gè)狀態(tài)特征, $K=K_1+K_2$ ,記:

相應(yīng)的我們把和寫為如下格式:

權(quán)值對(duì)應(yīng)的統(tǒng)一符號(hào):

條件隨機(jī)場(chǎng)對(duì)應(yīng)的概率表達(dá):

w表示權(quán)值向量:

$F(y,x)$ 表示全局特征向量:

我們可以對(duì)應(yīng)地把條件隨機(jī)場(chǎng)寫成向量 $w$ 與 $F(y,x)$ 的內(nèi)積的形式:

與之對(duì)應(yīng)的歸一化參數(shù) $Z_w(x)$
條件隨機(jī)場(chǎng)的矩陣形式:
對(duì)于觀測(cè)序列 $x$ 的每一個(gè)位置我們都定義一個(gè) $m$ 階矩陣( $m$ 是標(biāo)記 $y_i$ 的取值的個(gè)數(shù)):

矩陣化表示

這樣一來(lái),對(duì)于給定的觀測(cè)序列 $x$ ,標(biāo)記序列 $y$ 的非規(guī)范化概率可以通過(guò) $n+1$ 個(gè)矩陣的乘積 $\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)$ 來(lái)表示,于是,條件概率 $P_w(y|x)$ 就是:

其中 $Z_w(x)$ 為規(guī)范化因子,是 $n+1$ 個(gè)矩陣的乘積的 $( start,stop )$ 元素:

$y_0=start$ 與 $y_{n+1}=stop$ 表示開(kāi)始狀態(tài)與結(jié)束狀態(tài),規(guī)范化因子是這期間所有的概率矩陣的乘積.

CRF的概率計(jì)算問(wèn)題

前向-后向算法:對(duì)于每個(gè)指標(biāo) $i=0,1,...,n+1$ ,定義前向向量 $\alpha_i(x)$ :

遞推公式為:

終結(jié)項(xiàng)為:

同理可知我們的后向向量 $\beta_i(x)$ :

遞推公式:

終結(jié)項(xiàng):

由此我們可得出如下關(guān)系:

在已知前向后向序列時(shí)的條件概率運(yùn)算:

其中:
期望值計(jì)算:

其中:

特征函數(shù) $f_k$ 關(guān)于聯(lián)合分布 $P(X,Y)$ 的數(shù)學(xué)期望是:

其中:

最后編輯于：2018.08.25 00:15:13

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末滚秩，一起剝皮案震驚了整個(gè)濱河市旷祸，隨后出現(xiàn)的幾起案子色冀，更是在濱河造成了極大的恐慌缤弦，老刑警劉巖柳骄，帶你破解...
沈念sama閱讀 216,591評(píng)論 6贊 501
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件饲帅，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡耍休，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,448評(píng)論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門货矮，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)羊精，“玉大人，你說(shuō)我怎么就攤上這事囚玫⌒酰” “怎么了？”我有些...
開(kāi)封第一講書(shū)人閱讀 162,823評(píng)論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵抓督，是天一觀的道長(zhǎng)燃少。經(jīng)常有香客問(wèn)我，道長(zhǎng)铃在，這世上最難降的妖魔是什么阵具？我笑而不...
開(kāi)封第一講書(shū)人閱讀 58,204評(píng)論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮定铜，結(jié)果婚禮上阳液，老公的妹妹穿的比我還像新娘。我一直安慰自己揣炕，他們只是感情好帐我，可當(dāng)我...
茶點(diǎn)故事閱讀 67,228評(píng)論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布认臊。她就那樣靜靜地躺著膝捞，像睡著了一般架忌。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上丁恭，一...
開(kāi)封第一講書(shū)人閱讀 51,190評(píng)論 1贊 299
城市分裂傳說(shuō)
那天曹动，我揣著相機(jī)與錄音，去河邊找鬼涩惑。笑死仁期，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的竭恬。我是一名探鬼主播跛蛋，決...
沈念sama閱讀 40,078評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼痊硕！你這毒婦竟也來(lái)了赊级？” 一聲冷哼從身側(cè)響起，我...
開(kāi)封第一講書(shū)人閱讀 38,923評(píng)論 0贊 274
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤岔绸，失蹤者是張志新（化名）和其女友劉穎理逊，沒(méi)想到半個(gè)月后橡伞，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,334評(píng)論 1贊 310
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡晋被，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,550評(píng)論 2贊 333
?白月光啟示錄
正文我和宋清朗相戀三年兑徘，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片羡洛。...
茶點(diǎn)故事閱讀 39,727評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡挂脑，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出欲侮，到底是詐尸還是另有隱情崭闲，我是刑警寧澤，帶...
沈念sama閱讀 35,428評(píng)論 5贊 343
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布威蕉，位于F島的核電站刁俭，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏韧涨。R本人自食惡果不足惜牍戚，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,022評(píng)論 3贊 326
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望氓奈。院中可真熱鬧翘魄，春花似錦鼎天、人聲如沸舀奶。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 31,672評(píng)論 0贊 22
一樁弒父案斋射，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)育勺。三九已至，卻和暖如春罗岖，著一層夾襖步出監(jiān)牢的瞬間涧至，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 32,826評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工桑包，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留南蓬，地道東北人。一個(gè)月前我還...
沈念sama閱讀 47,734評(píng)論 2贊 368
代替公主和親
正文我出身青樓哑了，卻偏偏與公主長(zhǎng)得像赘方，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子弱左，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,619評(píng)論 2贊 354

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

條件隨機(jī)場(chǎng)(conditional random field, CRF)

在開(kāi)始之前

概率無(wú)向圖

條件隨機(jī)場(chǎng)的基礎(chǔ)表達(dá)

CRF的概率計(jì)算問(wèn)題

推薦閱讀更多精彩內(nèi)容