統(tǒng)計(jì)機(jī)器學(xué)習(xí)-條件隨機(jī)場(chǎng)

條件隨機(jī)場(chǎng)是給定一組輸入隨機(jī)變量條件下另一組隨機(jī)變量的條件概率分布模型 $P(Y|X)$ ，其特點(diǎn)是假設(shè)輸出隨機(jī)變量構(gòu)成馬爾可夫隨機(jī)場(chǎng)。類似隱馬爾可夫模型，條件隨機(jī)場(chǎng)也有概率計(jì)算問(wèn)題，學(xué)習(xí)問(wèn)題和預(yù)測(cè)問(wèn)題西雀，后面會(huì)給出解決這些問(wèn)題的算法。首先定義馬爾可夫隨機(jī)場(chǎng)歉摧。

概率無(wú)向圖模型（馬爾可夫隨機(jī)場(chǎng)）

概率無(wú)向圖模型又叫做馬爾可夫隨機(jī)場(chǎng)艇肴。如下圖所示

概率無(wú)向圖

$Y_1,Y_2,\cdots,Y_5$ 是五個(gè)隨機(jī)變量，是概率無(wú)向圖的結(jié)點(diǎn)叁温，結(jié)點(diǎn)的集合記做 $V$ 再悼。連線代表隨機(jī)變量之間的依賴關(guān)系，是概率無(wú)向圖的邊膝但，邊的集合記做 $E$ 冲九，如果兩個(gè)變量之間沒(méi)有連線，說(shuō)明這兩個(gè)隨機(jī)變量獨(dú)立跟束。整個(gè)概率無(wú)向圖可以記做 $G=(V,E)$ 莺奸。

概率無(wú)向圖可以通過(guò)以下方式定義丑孩，首先描述成對(duì)馬爾可夫性、局部馬爾可夫性灭贷、全局馬爾可夫性：

成對(duì)馬爾可夫性：設(shè) $u$ 和 $v$ 是無(wú)向圖 $G$ 中任意兩個(gè)沒(méi)有邊連接的結(jié)點(diǎn)嚎杨，結(jié)點(diǎn) $u$ 和 $v$ 分別對(duì)應(yīng)隨機(jī)變量 $Y_u$ 和 $Y_v$ ，其他所有結(jié)點(diǎn)為 $O$ 氧腰，對(duì)應(yīng)的隨機(jī)變量為 $Y_O$ ，這些隨機(jī)變量滿足：
$P(Y_u,Y_v|Y_O)=P(Y_u|Y_O)P(Y_u|Y_O)$
即隨機(jī)變量 $Y_u$ 和 $Y_v$ 條件獨(dú)立刨肃。

局部馬爾可夫性：設(shè) $v\in V$ 是無(wú)向圖 $G$ 中任意一個(gè)結(jié)點(diǎn)古拴， $W$ 是與 $v$ 有邊連接的所有結(jié)點(diǎn)。同樣真友，隨機(jī)變量 $Y_v$ 和 $Y_O$ 條件獨(dú)立：
$P(Y_v,Y_O|Y_W)=P(Y_v|Y_W)P(Y_O|Y_W)$
全局馬爾可夫性：設(shè)結(jié)點(diǎn)集合 $A$ 黄痪， $B$ 是被結(jié)點(diǎn)集合 $C$ 分開的任意結(jié)點(diǎn)集合，對(duì)應(yīng)的隨機(jī)變量滿足：
$P(Y_A,Y_B|Y_C)=P(Y_A|Y_C)P(Y_B|Y_C)$

可以看出盔然，上述成對(duì)的桅打、局部的、全局的馬爾可夫性定義是等價(jià)的愈案。

概率無(wú)向圖模型的定義

設(shè)有聯(lián)合概率分布 $P(Y)$ 挺尾，由無(wú)向圖 $G=(V,E)$ 表示，在圖 $G$ 中站绪，結(jié)點(diǎn)表示隨機(jī)變量遭铺，邊表示隨機(jī)變量之間的依賴關(guān)系。如果聯(lián)合概率分布 $P(Y)$ 滿足成對(duì)恢准、局部或全局馬爾可夫性魂挂，就稱此聯(lián)合概率分布為概率無(wú)向圖模型，或馬爾可夫隨機(jī)場(chǎng)馁筐。

有了如上定義涂召，重要的是如何求聯(lián)合 $P(Y)$ 。事實(shí)上敏沉，聯(lián)合概率可以寫成若干子聯(lián)合概率的乘積形式果正，也就是將聯(lián)合概率進(jìn)行因子分解。

概率無(wú)向圖模型的因子分解

首先定義圖與最大團(tuán)赦抖。

團(tuán)與最大團(tuán)的定義

無(wú)向圖 $G$ 中任何兩個(gè)結(jié)點(diǎn)均有邊連接的結(jié)點(diǎn)子集稱為團(tuán)舱卡。若 $C$ 是無(wú)向圖 $G$ 的一個(gè)團(tuán)，并且不能再加進(jìn)任何一個(gè) $G$ 的結(jié)點(diǎn)使其成為一個(gè)更大的團(tuán)队萤，則稱 $C$ 為最大團(tuán)轮锥。

如下圖

團(tuán)與最大團(tuán)

上圖有7個(gè)團(tuán)， $\{Y_1,Y_2\}, \{Y_2,Y_3\}, \{Y_3,Y_4\}, \{Y_4,Y_2\}, \{Y_1,Y_3\}, \{Y_1,Y_2,Y_3\}, \{Y_2,Y_3,Y_4\}$ 要尔，其中 $\{Y_1,Y_2,Y_3\}, \{Y_2,Y_3,Y_4\}$ 是最大團(tuán)舍杜。

Hammersley-Clifford定理

概率無(wú)向圖模型的聯(lián)合概率分布 $P(Y)$ 可以表示為如下形式：
$P(Y)=\frac1Z\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ù)（通常定義為指數(shù)函數(shù) $\Psi_C(Y_C)=\exp\{-E(Y_C)\}$ ）概龄，乘積是在無(wú)向圖所有的最大團(tuán)上進(jìn)行的。規(guī)范化因子 $Z$ 是對(duì) $Y$ 所有可能的取值情況求和饲握，使其符合概率分布私杜。

條件隨機(jī)場(chǎng)的定義與形式

條件隨機(jī)場(chǎng)是在給定隨機(jī)變量 $X$ 的條件下，隨機(jī)變量 $Y$ 的馬爾可夫隨機(jī)場(chǎng) $P(Y|X)$ 。其中 $X$ 是輸入變量，表示需要標(biāo)注的觀測(cè)序列粱锐。 $Y$ 是輸出變量拟逮，表示標(biāo)記序列，也稱為狀態(tài)序列（類似隱馬爾可夫模型，是沒(méi)有標(biāo)注的隱變量）。可以用下圖表示：

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

某個(gè)隨機(jī)變量 $Y_v$ 依賴于 $X$ 和有邊相連接的隨機(jī)變量 $Y_W$ 瓢捉。于是有如下定義

條件隨機(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\neq v)=P(Y_v|X,Y_w,w\sim v)$
對(duì)任意結(jié)點(diǎn) $v$ 成立，則稱條件隨機(jī)概率分布 $P(Y|X)$ 為條件隨機(jī)場(chǎng)迂卢。式中 $w\sim v$ 表示在圖 $G=(V,E)$ 中與結(jié)點(diǎn) $v$ 有邊連接的所有結(jié)點(diǎn) $w$ 兽赁， $w\neq v$ 表示結(jié)點(diǎn) $v$ 以外的所有結(jié)點(diǎn)， $Y_v$ 冷守， $Y_w$ 為結(jié)點(diǎn) $v,w$ 對(duì)應(yīng)的隨機(jī)變量刀崖。

為了簡(jiǎn)化問(wèn)題，通常假設(shè)隨機(jī)變量 $Y$ 的概率無(wú)向圖是一條線性鏈拍摇，叫做線性鏈條件隨機(jī)場(chǎng)亮钦，這種假設(shè)雖然簡(jiǎn)化了問(wèn)題，但是依然可以取得比較好的效果充活，并大大降低了計(jì)算的復(fù)雜度蜂莉。如下圖

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

此時(shí)，相鄰的兩個(gè)隨機(jī)變量構(gòu)成一個(gè)最大團(tuán)混卵。但是這種情況依然很復(fù)雜映穗，在此假設(shè)上，再假設(shè)隨機(jī)變量 $X$ 有著和 $Y$ 相同的圖結(jié)構(gòu)幕随，如下圖

XY相同圖結(jié)構(gòu)的線性鏈條件隨機(jī)場(chǎng)

此時(shí)每個(gè)隨機(jī)變量 $Y_i$ 只依賴于有邊相連接的隨機(jī)變量 $Y_{i-1}$ 蚁滋， $Y_{i+1}$ 和 $X_i$ 。線性鏈條件隨機(jī)場(chǎng)有如下定義

線性鏈條件隨機(jī)場(chǎng)的定義

設(shè) $X=(X_1,X_2,\cdots,X_n)$ ， $Y=(Y_1,Y_2,\cdots,Y_n)$ 均為線性鏈表示的隨機(jī)變量序列辕录，若在給定隨機(jī)變量序列 $X$ 的條件下睦霎，隨機(jī)變量序列 $Y$ 的條件概率分布 $P(Y|X)$ 構(gòu)成條件隨機(jī)場(chǎng)，即滿足馬爾可夫性
$P(Y_i|X,Y_i,\cdots,Y_{i-1},Y_{i+1},\cdots,Y_n)=P(Y_i|X,Y_{i-1},Y_{i+1})\\ i=1,2,\cdots,n\ \ (在i=1和n時(shí)只考慮單邊)\tag1$
則稱 $P(Y|X)$ 為線性鏈條件隨機(jī)場(chǎng)走诞。在標(biāo)注問(wèn)題中副女， $X$ 表示輸入觀測(cè)序列， $Y$ 表示對(duì)應(yīng)的輸出標(biāo)記序列或狀態(tài)序列蚣旱。

條件隨機(jī)場(chǎng)的參數(shù)化形式

根據(jù)Hammersley-Clifford定理碑幅，可以給出線性鏈條件隨機(jī)場(chǎng)的參數(shù)化形式。

線性鏈條件隨機(jī)場(chǎng)的參數(shù)化形式

設(shè) $P(Y|X)$ 為線性鏈條件隨機(jī)場(chǎng)塞绿，則在隨機(jī)變量 $X$ 取值為 $x$ 的條件下枕赵，隨機(jī)變量 $Y$ 取值為 $y$ 的條件概率具有如下形式：
$P(y|x)=\frac1{Z(x)}\exp\bigg(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_ls_l(y_i,x,i)\bigg)\tag2$
其中
$Z(x)=\sum_y\exp\bigg(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_ls_l(y_i,x,i)\bigg)\tag3$
式中， $t_k$ 和 $s_l$ 是特征函數(shù)位隶， $\lambda_k$ 和 $\mu_l$ 是特征對(duì)應(yīng)的權(quán)值。 $Z(x)$ 是規(guī)范化因子开皿，求和是在所有可能的輸出序列上進(jìn)行的涧黄。

值得注意的是，特征函數(shù) $t_k$ 依賴于輸入 $x$ 赋荆，當(dāng)前位置 $y_i$ 和上個(gè)位置 $y_{i-1}$ 笋妥，稱為轉(zhuǎn)移特征。特征函數(shù) $s_l$ 依賴于輸入 $x$ 和當(dāng)前位置 $y_i$ 窄潭，稱為狀態(tài)特征春宣。特征函數(shù) $t_k$ 和 $s_l$ 取值通常為0或1，當(dāng)滿足特征時(shí)嫉你，取1月帝。

條件隨機(jī)場(chǎng)的簡(jiǎn)化形式

將轉(zhuǎn)移特征 $t_k$ 和狀態(tài)特征 $s_l$ 用統(tǒng)一的方式表示，對(duì)上述參數(shù)化形式進(jìn)行簡(jiǎn)化幽污。假設(shè)有 $K_1$ 個(gè)轉(zhuǎn)移特征嚷辅， $K_2$ 個(gè)狀態(tài)特征，則共有 $K=K_1+K_2$ 個(gè)特征函數(shù)距误，記
$f_k(y_{i-1},y_i,x,i)= \begin{cases} t_k(y_{i-1},y_i,x,i),\ \ k=1,2,\cdots,K_1\\ s_l(y_i,x,i),\ \ k=K_1+l;l=1,2,\cdots,K_2 \end{cases}$
使用特征函數(shù)對(duì)各個(gè)位置 $i$ 求和簸搞，記為
$f_k(y,x)=\sum_{i=1}^nf_k(y_{i-1},y_i,x,i),\ \ k=1,2,\cdots,K$
各個(gè)特征的權(quán)值記為
$w_k= \begin{cases} \lambda_k,\ \ k=1,2,\cdots,K_1\\ \mu_l,\ \ k=K_1+l;l=1,2,\cdots,K_2 \end{cases}$
則線性鏈條件隨機(jī)場(chǎng)的參數(shù)形式可以簡(jiǎn)化為
$P(y|x)=\frac1{Z(x)}\exp{\sum_{k=1}^Kw_kf_k(y,x)}\tag4$

$Z(x)=\sum_y\exp\sum_{k=1}^Kw_kf_k(y,x)\tag5$

回顧最大熵模型：
$P_w(y|x)=\frac1{Z_w(x)}\exp\bigg(w_if_i(x,y)\bigg)$

$Z_w(x)=\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)$

可以看出兩者有著非常類似的形式，并且線性鏈條件隨機(jī)場(chǎng)也是對(duì)數(shù)線性模型准潭。

若以 $w$ 表示權(quán)值向量趁俊，即
$w=(w_1,w_2,\cdots,w_K)^T$
以 $F(y,x)$ 表示全局特征向量，即
$F(y,x)=(f_1(y,x),f_2(y,x),\cdots,f_K(y,x))^T$
則線性鏈條件隨機(jī)場(chǎng)還有以下內(nèi)積形式：
$P_w(y|x)=\frac{\exp(w\cdot F(y,x))}{Z_w(x)}$

$Z_w(x)=\sum_y\exp(w\cdot F(y,x))$

條件隨機(jī)場(chǎng)的矩陣形式

在標(biāo)記（狀態(tài)）序列 $y$ 引入特殊的起點(diǎn)和終點(diǎn)狀態(tài)標(biāo)記 $y_0=\mathrm{start}$ 刑然， $y_{n+1}=\mathrm{stop}$ 寺擂，這時(shí) $P_w(y|x)$ 可以通過(guò)矩陣形式表示。

對(duì)觀測(cè)序列 $x$ 的每一個(gè)位置 $i=1,2,\cdots,n+1$ ，定義一個(gè) $m$ 階矩陣（ $m$ 是標(biāo)記 $y_i$ 取值的個(gè)數(shù)沽讹，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=y_0" alt="y_0" mathimg="1">和 $y_{n+1}$ 只有是不是start或是不是stop兩個(gè)取值般卑，所以在起點(diǎn)和終點(diǎn) $m=2$ ，其余位置正常）
$M_i(x)=[M_i(y_{i-1},y_i|x)]_{m_{y_{i-1}}\times m_{y_i}}$

$M_i(y_{i-1},y_i|x)=\exp(W_i(y_{i-1},y_i|x))$

$W_i(y_{i-1},y_i|x)=\sum_{k=1}^Kw_kf_k(y_{i-1},y_i,x,i)$

$M_i(y_{i-1},y_i|x)=\exp[\sum_{k=1}^Kw_kf_k(y_{i-1},y_i,x,i)]$ 可以看做各個(gè)位置 $i$ 上特征函數(shù)的加權(quán)和再求 $\exp$ 爽雄，得到輸入 $x$ 條件下蝠检，未規(guī)范化的狀態(tài) $y_{i-1}$ 到狀態(tài) $y_i$ 之間的狀態(tài)轉(zhuǎn)移概率。

這樣挚瘟，給定觀測(cè)序列 $x$ 叹谁，相應(yīng)標(biāo)記序列 $y$ 的非規(guī)范概率可以通過(guò)該序列 $n+1$ 個(gè)矩陣適當(dāng)元素的乘積 $\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)$ 表示。于是乘盖，條件概率 $P_w(y|x)$ 是
$P_w(y|x)=\frac1{Z_w(x)}\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)\tag6$
其中 $Z_w(x)$ 為規(guī)范化因子焰檩，是 $n+1$ 個(gè)矩陣的乘積的下標(biāo)為 $(\mathrm{start},\mathrm{stop})$ 的元素
$Z_w(x)=(M_1(x)M_2(x)\cdots M_{n+1}(x))_{\mathrm{start},\mathrm{stop}}\tag7$
$y_0=\mathrm{start}$ ， $y_{n+1}=\mathrm{stop}$ 订框，表示開始狀態(tài)與終止?fàn)顟B(tài)析苫，規(guī)范化因子 $Z_w(x)$ 是以 $\mathrm{start}$ 為起點(diǎn) $\mathrm{stop}$ 為終點(diǎn)通過(guò)狀態(tài)的所有路徑 $y_1,y_2,\cdots,y_n$ 的非規(guī)范化概率 $\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)$ 之和〈┌猓可以通過(guò)矩陣計(jì)算公式得到衩侥，過(guò)程略。

條件隨機(jī)場(chǎng)的概率計(jì)算問(wèn)題

條件隨機(jī)場(chǎng)的概率計(jì)算問(wèn)題是給定條件隨機(jī)場(chǎng) $P(Y|X)$ 矛物，輸入序列 $x$ 和輸出序列 $y$ 茫死，計(jì)算條件概率 $P(Y_i=y_i|x)$ ， $P(Y_{i-1}=y_{i-1},Y_i=y_i|x)$ 以及相應(yīng)的數(shù)學(xué)期望的問(wèn)題履羞。類似隱馬爾可夫模型峦萎，使用前向-后向算法。

前向-后向算法

對(duì)每個(gè)指標(biāo) $i=0,1,\cdots,n+1$ 忆首，定義前向向量 $\alpha_i(x)$ ：
$\alpha_0(y|x)= \begin{cases} 1,\ \ y=\mathrm{start}\\ 0,\ \ 否則 \end{cases}$
遞推公式為
$\alpha_i^T(y_i|x)=\alpha_{i-1}^T(y_{i-1}|x)[M_i(y_{i-1},y_i|x)],\ \ i=1,2,\cdots,n+1\tag8$
又可表示為
$\alpha_i^T(x)=\alpha_{i-1}^T(x)M_i(x)$
$\alpha_i(y_i|x)$ 表示在位置 $i$ 的標(biāo)記是 $y_i$ 并且到位置 $i$ 的前部分標(biāo)記序列的非規(guī)范化概率爱榔， $y$ 的取值有 $m$ 個(gè)，所以 $\alpha_i(x)$ 是 $m$ 維列向量糙及。

同樣搓蚪，對(duì)每個(gè)指標(biāo) $i=0,1,\cdots,n+1$ ，定義后向向量 $\beta_i(x)$ ：
$\beta_{n+1}(y_{n+1}|x)= \begin{cases} 1,\ \ y_{n+1}=\mathrm{stop}\\ 0,\ \ 否則 \end{cases}$
遞推公式
$\beta_i(y_i|x)=[M_i(y_i,y_{i+1}|x)]\beta_{i+1}(y_{i+1}|x)\tag9$
又可表示為
$\beta_i(x)=M_{i+1}(x)\beta_{i+1}(x)$
$\beta_i(y_i|x)$ 表示在位置 $i$ 的標(biāo)記為 $y_i$ 并且從 $i+1$ 到 $n$ 的后部分標(biāo)記序列的非規(guī)范化概率丁鹉， $y$ 的取值有 $m$ 個(gè)妒潭，所以 $\beta_i(y_i|x)$ 是 $m$ 維列向量。

由前向-后向向量的定義不難得到：
$Z(x)=\alpha_n^T(x)\cdot\textbf1=\textbf1^T\beta_1(x)\tag{10}$
這里揣钦， $\textbf1$ 是元素均為1的 $m$ 維列向量雳灾。

概率計(jì)算

$P(Y_i=y_i|x)=\frac{\alpha_i^T(y_i|x)\beta_i(y_i|x)}{Z(x)}\tag{11}$

$P(Y_{i-1}=y_{i-1},Y_i=y_i|x)=\frac{\alpha_i^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)}\tag{12}$

其中，
$Z(x)=\alpha_n^T(x)\cdot\textbf1\tag{13}$

期望值計(jì)算

$\begin{align} E_{P(Y|X)}[f_k]&=\sum_yP(y|x)f_k(y,x)\\ &=\sum_{i=1}^{n+1}\sum_{y_{i-1},y_i}f_k(y_{i-1},y_i,x,i)P(Y_{i-1}=y_{i-1},Y_i=y_i|x)\\ &=\sum_{i=1}^{n+1}\sum_{y_{i-1},y_i}f_k(y_{i-1},y_i,x,i)\frac{\alpha_i^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)} \end{align}\\ k=1,2,\cdots,K\tag{14}$

其中冯凹，
$Z(x)=\alpha_n^T(x)\cdot\textbf1$

$\begin{align} E_{P(X,Y)}[f_k]&=\sum_{x,y}P(x,y)\sum_{i=1}^{n+1}f_k(y_{i-1},y_i,x,i)\\ &=\sum_x\tilde P(x)\sum_yP(y|x)\sum_{i=1}^{n+1}f_k(y_{i-1},y_i,x,i)\\ &=\sum_x\tilde P(x)\sum_y\sum_{i=1}^{n+1}f_k(y_{i-1},y_i,x,i)\frac{\alpha_i^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)} \end{align}\\ k=1,2,\cdots,K\tag{15}$

其中 $\tilde P(x)$ 是 $x$ 的經(jīng)驗(yàn)分布谎亩。

$f_k(y_{i-1},y_i,x,i)$ 在 $1\leq k\leq K_1$ 時(shí)炒嘲，是轉(zhuǎn)移特征函數(shù)，對(duì)應(yīng)概率 $P(y|x)=P(Y_{i-1}=y_{i-1},Y_i=y_i|x)$ 匈庭，在 $K_1\lt k\leq K_1+K_2$ 時(shí)夫凸，是狀態(tài)特征函數(shù)，對(duì)應(yīng)概率 $P(y|x)=P(Y_i=y_i|x)$ 阱持∝舶瑁可以通過(guò)一次前向掃描得到 $\alpha_i$ 和 $Z(x)$ ，通過(guò)一次后向掃描計(jì)算 $\beta_i$ 衷咽，從而計(jì)算所有的概率和特征的期望鸽扁。

條件隨機(jī)場(chǎng)的學(xué)習(xí)算法

條件隨機(jī)場(chǎng)模型實(shí)際上是定義在時(shí)序數(shù)據(jù)上的對(duì)數(shù)線性模型，類似最大熵模型镶骗，所以也可以用IIS法桶现，梯度下降法以及擬牛頓法。

改進(jìn)的迭代尺度法（IIS）法

IIS法的思路是找到特征函數(shù)權(quán)值參數(shù) $w$ 的更新量 $\delta$ 鼎姊，使得極大似然函數(shù)改變量 $L(w+\delta)-L(\delta)$ 的下界在每次迭代時(shí)提高骡和，達(dá)到極大似然估計(jì)的效果，具體推導(dǎo)參考最大熵模型相寇。

條件隨機(jī)場(chǎng)模型學(xué)習(xí)的改進(jìn)的迭代尺度法

輸入：特征函數(shù) $t_1,t_2,\cdots,t_{K_1}$ 慰于， $s_1,s_2,\cdots,s_{K_2}$ ；經(jīng)驗(yàn)分布 $\tilde P(x,y)$ 裆赵；

輸出：參數(shù)估計(jì)值 $\hat w$ ；模型 $P_{\hat w}$ 跺嗽。

（1）對(duì)所有 $k\in \{1,2,\cdots,K\}$ 战授，取初值 $w_k=0$

（2）對(duì)每一 $k\in \{1,2,\cdots,K\}$ ：

（a）當(dāng) $k=1,2,\cdots,K_1$ 時(shí)，令 $\delta_k$ 是方程
$\sum_{x,y}\tilde P(x)P(y|x)\sum_{i=1}^{n+1}t_k(y_{i-1},y_i,x,i)\exp(\delta_kT(x,y))=E_{\tilde P}[t_k]$
的解桨嫁；

當(dāng) $k=K_1+l$ 植兰， $l=1,2,\cdots,K_2$ 時(shí)，令 $\delta_{K_1+l}$ 是方程
$\sum_{x,y}\tilde P(x)P(y|x)\sum_{i=1}^ns_l(y_i,x,i)\exp(\delta_{K_1+l}T(x,y))=E_{\tilde P}[s_l]$
的解璃吧，其中
$T(x,y)=\sum_kf_k(y,x)=\sum_{k=1}^K\sum_{i=1}^{n+1}f_k(y_{i-1},y_i,x,i)$
是在數(shù)據(jù) $(x,y)$ 中出現(xiàn)所有特征的總和楣导。

（b）更新 $w_k$ 值： $w_k\leftarrow w_k+\delta_k$

（3）如果不是所有 $w_k$ 都收斂，重復(fù)步驟（2）

當(dāng) $T(x,y)$ 是常數(shù)時(shí)畜挨，方程比較容易求解筒繁，當(dāng) $T(x,y)$ 不是常數(shù)時(shí)，方程比較難求解巴元，在《統(tǒng)計(jì)機(jī)器學(xué)習(xí)》條件隨機(jī)場(chǎng)部分有其他相關(guān)解決方法的描述毡咏。

擬牛頓法

對(duì)于條件隨機(jī)場(chǎng)模型
$P_w(y|x)=\frac{\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)}{\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(y,x)\bigg)}$
學(xué)習(xí)的優(yōu)化目標(biāo)函數(shù)是對(duì)數(shù)似然函數(shù)的相反數(shù)：
$\min_{w\in\textbf R^n}f(w)=\sum_x\tilde P(x)\log\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)-\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x,y)$
其梯度函數(shù)是
$g(w)=\sum_{x,y}\tilde P(x)P_w(y|x)f(x,y)-E_{\tilde P}(f)$

條件隨機(jī)場(chǎng)模型學(xué)習(xí)的BFGS算法

輸入：特征函數(shù) $t_1,t_2,\cdots,t_{K_1}$ ， $s_1,s_2,\cdots,s_{K_2}$ 逮刨；經(jīng)驗(yàn)分布 $\tilde P(x,y)$ 呕缭；

輸出：參數(shù)估計(jì)值 $\hat w$ ；模型 $P_{\hat w}$ 。

（1）選定初始點(diǎn) $w^{(0)}$ 恢总，取 $B_0$ 為正定對(duì)稱矩陣迎罗，置 $k=0$

（2）計(jì)算 $g_k=g(w^{(k)})$ 。若 $g_k=0$ 片仿，則停止計(jì)算纹安，否則轉(zhuǎn)（3）

（3）由 $B_kp_k=-g_k$ 求出 $p_k$

（4）一維搜索：求 $\lambda_k$ 使得
$f(w^{(k)}+\lambda_kp_k)=\min_{\lambda\geq0}f(w^{(k)}+\lambda p_k)$
（5）置 $w^{(k+1)}=w^{(k)}+\lambda_kp_k$

（6）計(jì)算 $g_{k+1}=g(w^{(k+1)})$ ，若 $g_{k+1}=0$ 滋戳，則停止計(jì)算钻蔑；否則，按下式求出 $B_{k+1}$ ：
$B_{k+1}=B_k+\frac{y_ky_k^T}{y_k^T\delta_k}-\frac{B_k\delta_k\delta_k^TB_k}{\delta_k^TB_k\delta_k}$
其中
$y_k=g_{k+1}-g_k,\ \ \delta_k=w^{(k+1)}-w^{(k)}$
（7）置 $k=k+1$ 奸鸯，轉(zhuǎn)（3）

條件隨機(jī)場(chǎng)的預(yù)測(cè)算法

條件機(jī)場(chǎng)的預(yù)測(cè)問(wèn)題是給定條件隨機(jī)場(chǎng) $P(Y|X)$ 和輸入序列（觀測(cè)序列） $x$ 咪笑，求條件概率最大的輸出序列（標(biāo)記序列） $y^*$ 。常用的算法是維比特算法娄涩，使用了動(dòng)態(tài)規(guī)劃的思路窗怒，推導(dǎo)詳見隱馬爾可夫模型。

條件隨機(jī)場(chǎng)的維特比算法

輸入：模型特征向量 $F(y,x)$ 和權(quán)值向量 $w$ 蓄拣，觀測(cè)序列 $x=(x_1,x_2,\cdots,x_n)$ 扬虚；

輸出：最優(yōu)路徑 $y^*=(y_1^*,y_2^*,\cdots,y_N^*)$ 。

（1）初始化
$\delta_1(j)=w\cdot F_1(y_0=start,y_1=j,x),\ \ j=1,2,\cdots,m$
其中
$w=(w_1,w_2,\cdots,w_K)^T$

$F_i(y_{i-1},y_i,x)=(f_1(y_{i-1},y_i,x,i),f_2(y_{i-1},y_i,x,i),\cdots,f_K(y_{i-1},y_i,x,i))^T$

（2）遞推球恤。對(duì) $i=2,3,\cdots,n$
$\delta_i(l)=\max_{1\leq j\leq m}\{\delta_{i-1}(j)+w\cdot F_i(y_{i-1}=j,y_i=l,x)\},\ \ l=1,2,\cdots,m$

$\Psi_i(l)=\arg\max_{1\leq j\leq m}\{\delta_{i-1}(j)+w\cdot F_i(y_{i-1}=j,y_i=l,x)\},\ \ l=1,2,\cdots,m$

（3）終止
$\max_y(w\cdot F(y,x))=\max_{1\leq j\leq m}\delta_n(j)$

$y_n^*=\arg\max_{1\leq j\leq m}\delta_n(j)$

（4）返回路徑
$y_i^*=\Psi_{i+1}(y_{i+1}^*),\ \ i=n-1,n-2,\cdots,1$
求得最優(yōu)路徑 $y^*=(y_1^*,y_2^*,\cdots,y_N^*)$ 辜昵。

最后編輯于：2020.08.07 17:27:22

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

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市咽斧，隨后出現(xiàn)的幾起案子堪置，更是在濱河造成了極大的恐慌，老刑警劉巖张惹，帶你破解...
沈念sama閱讀 218,607評(píng)論 6贊 507
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件舀锨，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡宛逗，警方通過(guò)查閱死者的電腦和手機(jī)坎匿，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,239評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)雷激，“玉大人替蔬，你說(shuō)我怎么就攤上這事∈合荆” “怎么了进栽？”我有些...
開封第一講書人閱讀 164,960評(píng)論 0贊 355
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)恭垦。經(jīng)常有香客問(wèn)我快毛，道長(zhǎng)格嗅，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,750評(píng)論 1贊 294
?港島之戀（遺憾婚禮）
正文為了忘掉前任唠帝，我火速辦了婚禮屯掖，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘襟衰。我一直安慰自己贴铜，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,764評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開白布瀑晒。她就那樣靜靜地躺著绍坝，像睡著了一般。火紅的嫁衣襯著肌膚如雪苔悦。梳的紋絲不亂的頭發(fā)上轩褐，一...
開封第一講書人閱讀 51,604評(píng)論 1贊 305
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音玖详，去河邊找鬼把介。笑死，一個(gè)胖子當(dāng)著我的面吹牛蟋座，可吹牛的內(nèi)容都是我干的拗踢。我是一名探鬼主播，決...
沈念sama閱讀 40,347評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼向臀，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼巢墅！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起券膀，我...
開封第一講書人閱讀 39,253評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤君纫，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后三娩，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體庵芭，經(jīng)...
沈念sama閱讀 45,702評(píng)論 1贊 315
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡妹懒，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,893評(píng)論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年雀监，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片眨唬。...
茶點(diǎn)故事閱讀 40,015評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡会前，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出匾竿，到底是詐尸還是另有隱情瓦宜，我是刑警寧澤，帶...
沈念sama閱讀 35,734評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布岭妖，位于F島的核電站临庇，受9級(jí)特大地震影響反璃，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜假夺，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,352評(píng)論 3贊 330
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一淮蜈、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧已卷，春花似錦梧田、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,934評(píng)論 0贊 22
一樁弒父案裁眯，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至讳癌，卻和暖如春穿稳，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背析桥。一陣腳步聲響...
開封第一講書人閱讀 33,052評(píng)論 1贊 270
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工司草，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人泡仗。一個(gè)月前我還...
沈念sama閱讀 48,216評(píng)論 3贊 371
代替公主和親
正文我出身青樓埋虹，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親娩怎。傳聞我的和親對(duì)象是個(gè)殘疾皇子搔课，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,969評(píng)論 2贊 355