11_條件隨機場
今天是2020年6月14號星期日。從這篇開始，發布時間就正常了。前邊的文章是在寒假寫好的，後來因為趕進度和改小論文，沒有及時整理。3月到6月，兩個半月的時間做了些什麼？真的好怕浪費了時間~《統計學習方法》這本書（第二版），大概在四月底就看個差不多了，半生不熟的好歹是通篇過了一遍，當然不止一遍，除了潛在狄利克雷分配。期間夾雜着手撕代碼的過程，因為腦容量有限的原因，寫代碼的時候，又要把書面內容重新過一遍。就連發布，也要重新過一遍，把重要的地方加上不同顏色…於是這個假期，《統計學習方法》這本書的每個章節，不知道反反覆復的過了多少遍，肯定不超過十遍…也就是看的多，不代表學的多…但是看了總歸是看了，也比不看強…
CRF條件隨機場~本節說難，挺難；說簡單，也簡單。為什麼我覺得CRF和LR很像呢？可能有很多人在應用場景上反駁我，LR做數據分類問題，CRF是針對序列標註問題。我覺得像，提供一下幾個觀點（遞進着看）：
1.LR和CRF都是判別模型。這句話要從計算方式上來理解：LR是通過線性函數，對特徵向量擬合不同的權值，最後加和的線性函數值作為sigmoid函數的輸入，轉換為概率值（對數幾率）。CRF在公式(11.10)中，不，在更明顯的公式(11.15)中，wkfk(y,x)對1->K加和。個人膚淺的理解：公式(11.15)就是對各個特徵擬合不同的權值wk，加和的線性函數值作為某個“求概率公式”的輸入。
2.從觀點1出發，思考一下“特徵”。在LR中，“特徵”很明顯，就是特徵向量的各個分量，相當於一個分量一個特徵。LR擬合的w，其實就是看看每個特徵分量對分類結果占什麼樣的貢獻。在CRF中，“特徵”是定義在最大團上的，拋去“最大團”“勢函數”“特徵函數”這些抽象概念，CRF的“特徵”其實不就是定義在相互聯繫的兩個節點上嘛？相當於“成對”構成一個特徵。轉移特徵也好，狀態特徵也罷，線性鏈條件隨機場不就限定了“特徵”要產生在“成對”的關聯關係上。然後，公式(11.15)告訴我，[權值×特徵==》加和]，CRF和LR計算線性函數值的方式沒區別啊（區別在特徵的定義上）。
3.從觀點1出發，思考一下“概率的計算”。不知道大家有沒有仔細思考LR中，第六章公式(6.6)分母位置的1是怎麼計算的，或者為什麼要在分母添加這一項。是不是可以理解為exp(0*wx)=1，這樣能夠把分母作為歸一化項Z(x)看待。分母的1+exp(wx)看作Z(x)=exp(0*wx)+exp(1*wx)，P(Y=1|x)=exp(1*wx)/Z(x),另一個類別Y=0的概率P(Y=0|x)=exp(0*wx)/Z(x)，怎麼樣，香不香？這裏不就是兩個項的線性函數值進行了指數歸一化。在這個角度上，看CRF的概率計算方式，公式(11.15)和公式(11.16)不就是多了幾項嘛…多個項(K項)進行了歸一化，把數值轉換成了概率值，這這這，和softmax()指數歸一化不就是一回事嘛…然後再考慮考慮為什麼CRF中勢函數是嚴格正的…
暫時先這三點，實際上都是圍繞[判別模型]提出的。
GitHub：https://github.com/wangzycloud/statistical-learning-method
條件隨機場
引入
書中對條件隨機場CRF的描述是：給定一組輸入隨機變量條件下另一組輸出隨機變量的條件概率分佈模型，其特點是假設輸出隨機變量構成馬爾可夫隨機場。先拋去“輸出隨機變量構成馬爾可夫隨機場”這個限定條件不看，該模型是條件概率模型，並且是一組隨機變量，在另外一組隨機變量條件下的條件概率模型。
組這個概念，限定了模型中發生作用的因素要產生在多個隨機變量上。類似這樣，形象不（僅代表個人理解哈~不能保證正確）：
像示意圖中表示的，如果一組隨機變量之間，關係是散亂無序的，我們該怎樣求解呢？各個組上隨機變量的關係都發現不了，何談尋找A組在B組條件下的條件概率分佈？因此，考慮對輸出組的隨機變量施加限定條件。人類最常做的就是發現規律，總結經驗。比如說，讓輸出組的隨機變量兩兩之間產生聯繫，會不會簡化問題？
於是，模型變成了這樣。又或者，讓輸入組隨機變量和輸出組隨機變量，都變成序列關係。這時，問題變成了由輸入序列對輸出序列預測的判別模型。具體的，讓輸出組隨機變量構成馬爾可夫隨機場。需要的知識包括圖與無向圖、馬爾可夫性、無向圖模型的因子分解、團與最大團…
概率無向圖
概率無向圖模型，又稱為馬爾可夫隨機場，是一個可以由無向圖表示的聯合概率分佈。“馬爾可夫隨機場”正式出場了，簡單講它是一個聯合概率分佈，是由無向圖表示的。想象無向圖的樣子，由結點和邊構成，且邊沒有方向（無箭頭）。深入一點，一個結點表示一個隨機變量，如果兩個結點之間有邊關聯，就認為這兩個結點具有關聯關係，並且是“相互關聯”（無向邊），相互產生影響。
可以看到，“有向變無向”這個操作，讓限定條件變的更寬泛了，也就是讓CRF的應用場景增多。當然，無向圖不只是上圖的線性序列關係。根據馬爾可夫性的不同，概率無向圖模型也有很多種類。接下來由圖開始，具體介紹一下模型的定義。
看一下馬爾可夫性，我的理解是這樣：在無向圖G上給定Cs（與集合C有關的一堆結點），As和Bs條件獨立。As和Bs之間沒有邊關聯，就算利用Cs作為結點把As和Bs連接了起來，兩者仍然保持獨立關係。
有三種類型，分別是成對馬爾可夫性、局部馬爾可夫性、全局馬爾可夫性，具體定義較晦澀。如下：
由以上馬爾可夫性，概率無向圖模型定義為：
有了概率無向圖的定義，實際上我們更關心的是如何求解各個隨機變量的聯合概率分佈。那麼，對給定的概率無向圖模型，我們能不能找到將整體的聯合概率寫成若干個子聯合概率的乘積的方法？也就是將聯合概率進行因子分解（類似：6=2×3，整數6可以分解成因子2乘以因子3），就能方便模型的學習與計算了。事實上，概率無向圖模型最大的特點就是易於因子分解。這裏留幾個疑問，“整體的”變成若干個“子聯合概率的”這句話，子聯合概率我不是可以理解成“子集”的，這個子集要如何劃分？我們知道，圖結構動不動就會像漁網一樣，橫七豎八的全是連接邊。
另外，聯合概率的因子分解，不僅要能解決無向圖上劃分小子集的問題，還要保證各個小子集乘積的聯合概率要等於整體的聯合概率。
這裏劃分小子集的問題，由無向圖上的“最大團”解決的，定義如下：
例子中描述的，應該是挺清楚的，最大團中的任何兩個結點均有邊連接。於是，概率無向圖模型的聯合概率分佈可以表示為其最大團上的隨機變量的函數的乘積，這種操作稱為概率無向圖模型的因子分解。接下來，考慮聯合概率如何計算。
不管整體的聯合概率也好，子集的聯合概率也好，無非是表示一大撮和一小撮隨機變量的區別。問題在於，這個東西它是概率啊。怎麼在圖結構上體現概率啊…公式(11.15)和公式(11.16)給出了答案，對每個Yi（N個狀態序列中的一個序列Yi）求分值，將各個“得分”歸一化后的結果作為該無向圖Yi的聯合概率。實際上也就是每一個無向圖Yi是所有狀態序列中的一種情況，這個Yi的得分佔所有情況的比例，就認為是Yi的聯合概率。
這裏Yi的得分，是如何反映的呢？可以從公式(11.15)看出，圖中所有最大團上各個最大團勢函數的乘積，作為Yi的得分。
串到CRF特徵抓取的過程中，我認為這裏的勢函數，就是抓取最大團集合中的結點特徵，並且是各個結點之間的關聯特徵。由於訓練過程中擬合參數wk,所以這裏只需要將每個特徵作為正的“量”就可以了。勢函數僅作標示“特徵”的度量（metric），擬合的wk決定該特徵對“得分”影響的正負、大小程度(對應開頭的觀點3)。
現在利用的這種方式，不是空穴來風，是有定理來保證的：
條件隨機場的定義與形式
條件隨機場是給定隨機變量X條件下，隨機變量Y的馬爾可夫隨機場。我們要用到的CRF指的是定義在線性鏈上的特殊的條件隨機場，稱為線性鏈條件隨機場。一般情況下，在條件概率模型P(Y|X)中，Y是輸出變量，表示標記序列；X是輸入變量，表示觀測序列。這裏，我們也把標記序列稱為狀態序列。在學習時，利用訓練數據通過極大似然估計或正則化的極大似然估計得到條件概率模型；預測時，對於給定的輸入序列x，求出條件概率模型最大的輸出序列y。
我認為在給定輸入序列X的條件下，計算輸出序列Y的條件概率（且序列Y構成線性鏈條件隨機場）的場景是與圖11.4相符合的。文中描述的，現實中一般假設X和Y有相同的圖結構，形如圖11.5這樣，這就好像對模型進行了簡化，讓模型更容易實現。換一個角度看，圖11.4中的X表達的是輸入序列整體對輸出序列Y的影響，具體到如何產生影響，如圖11.5表達的這樣，輸入序列X的每個分量Xi，與相同時刻的Yi相互影響。
這裏留兩個疑問，(Xi,Yi)的相互影響關係，會不會傳遞到t時刻？與時刻t有沒有關係？
看一下線性鏈條件隨機場的具體定義：
圖示如下，公式(11.9)實際上表達了：馬爾可夫性規定Yi(Y3)只與相鄰的結點有關聯關係（藍框代表等式左側，紅框代表等式右側）。
根據定理11.1，可以給出線性鏈條件隨機場P(Y|X)的因子分解式，各因子是定義在相鄰兩個結點（最大團）上的勢函數。兩個疑問的解答，相信後面部分的描述中可以找到答案。接下來看一下條件隨機場的三種形式。
1)條件隨機場的參數化形式
該基本形式，表示給定輸入序列x，對輸出序列y預測的條件概率。實際上現在的具體定義，就是把最大團、勢函數、概率求解等概念落實下來，變成可以量化的東西。公式(11.11)為歸一化項，相當於把Y的每種情況（各種Y序列）考慮到，作為求概率時的分母（每種情況下，各個得分加和）。在某個情況Y下，計算該Y的概率，需要先得到所有勢函數構成的特徵和，也就是“得分分值”。
這裏的特徵來自兩部分，yi-1與yi橫向上的轉移特徵tk(·)和yi與x豎向上的狀態特徵sl(·)。
看一下具體定義：
這裏tk和sl的取值，類似於最大熵模型中特徵函數的定義。我的理解，取1或者0，是標記這個特徵有還是沒有。至於此時該特徵的貢獻是大是小，是正是負，這取決於模型訓練時擬合的參數情況（λ、μ）。
舉個例子，看下計算時的具體過程：
該標記序列y=(y1,y2,y3)的非規範化概率，實際上就是通過存在的特徵×對應權重，然後加和。符合[權值×特徵==》加和]這個方式。
2)條件隨機場的簡化形式
注意到條件隨機場公式(11.10)中同一個特徵在各個位置都有定義，可以對同一個特徵在各個位置求和，從而將局部特徵轉化為一個全局特徵函數。這樣就可以將條件隨機場寫成權值向量和特徵向量的內積形式，也就是現在要描述的簡化形式。實際上，這更進一步貼近了[權值×特徵==》加和]這種方式。
如上圖所示，假設每個位置i都有這個局部特徵（沒有該特徵的話，特徵值為0），每個i都要針對這一個局部特徵求一個參數，這個工作量似乎有點大，並且重複。那麼，是不是可以把該局部變量上升到全局特徵，每個局部位置特徵值加和，讓這一個特徵在全局上學習一個權重參數。一來減少沒必要的參數估計，二來可以把重點放在“特徵”的增加和估計上。
這裏公式(11.13)表明了全局特徵是通過各個位置i的局部特徵加和得到的。
接下來，用向量形式進行表示：
這樣就得到了條件隨機場的簡化形式。經過知識點細化，再抽象，看CRF公式(11.19)和公式(11.20)和LR中的公式(6.5)和公式(6.6)多像。各個特徵的線性函數值（得分），通過指數歸一化轉化成概率，學習的過程擬合各個參數。
3)條件隨機場的矩陣形式
先看定義：
這裏先記一個要點，對每個標記序列引進特殊的起點和終點狀態標記，這時標註序列的概率Pw(y|x)可以通過矩陣形式表示並有效計算。划重點：引進特殊起點和重點標記之後，才可以通過矩陣形式計算。
不知道怎麼分析這個地方，現在從以下幾個問題開始：
①公式(11.21)中Mi的下標i和yi的下標i是否表示同一個意思？
我認為這兩個下標i指的不是同一個意思，yi的i表示該矩陣中狀態的取值；Mi中的i表示第i個矩陣，實際上每個位置都有對應的矩陣。同時矩陣的維度是M×M維的，因為yi可以取到M個狀態（yi有M個狀態，yi-1的某個狀態可以轉移到M个中任意一個，yi-1有M個狀態，所以轉移有M×M種）。例M2(1,3)表示在狀態序列的第2個位置上(t=2)，由t=1時刻的“狀態1”轉移到t=2的“狀態3”的非規範化概率。
②Mi中的元素是怎麼計算的，是什麼？
計算方式見公式(11.22)和公式(11.23)。我先想到的是，Mi矩陣為yi-1到yi的轉移矩陣，每個時刻yi都是M種狀態，轉移也都是yi-1到yi這些轉移方式，計算方式都由公式(11.23)計算。那麼，不同的Mi之間的區別是什麼呢。我的理解是針對不同的時刻t、不同的x，特徵函數是否存在和相應的權值大小，決定了Mi不同。
③公式(11.24)的分子部分n+1個矩陣的適當元素的乘積，是什麼？
仔細看一下CRF的簡化形式中公式(11.15)的分子部分，利用公式(11.13)對i進行展開，有：
是不是就變成了公式(11.24)的分子部分n+1個矩陣的適當元素乘積的形式。也就是說，CRF的矩陣形式來源於簡化形式，至於為什麼會有這種方式，我覺得是便於計算吧，下邊前後向算法會用到這種形式。
④公式(11.25)規範化因子，是什麼？
看上去是對所有序列的非規範化概率的總和。其實追根究底④這個問題是想知道矩陣運算在這裏計算的是什麼。
綜上，條件隨機場矩陣形式的要點有：
以2×2的Mi矩陣為例(例11.2)，具體表示如下：
看一下例11.2：
以狀態序列(1,2,1)為例：
解析如下：
接下來看一下求規範化因子的過程：
上面提到的問題④，n+1個矩陣連乘后，得到的結果仍然是M×M維的。但第1行第1列的元素，正好是所有路徑上的非規範化概率之和。
了解完概率無向圖、條件隨機場的定義和各種表示方法之後，與隱馬爾可夫模型類似的，接下來介紹條件隨機場的3個基本問題：概率計算問題、學習問題、預測問題。
條件隨機場的概率計算問題
與隱馬爾可夫模型類似，引進前向-後向向量，遞歸的計算概率（遞歸的計算過程是非常不同的）。
先看前向計算過程。注意CRF作為無向圖模型，拋去了HMM的方向性，我們要從矩陣乘法的角度進行分析。仔細看一下公式(11.28)，轉換成矩陣語言如下（以m=5為例，這裏將時刻的下標標記為t，用來區分yi的狀態和時刻t：αi->αt,Mi->Mt）：
具體到轉換過程中（考慮矩陣乘法的過程）：
可以看到，α1t的得出，是結合了t-1時刻各個αi的結果。再來理解一下“αt(yi|x)表示在位置t的標記是yi並且從1到t的前部分標記序列的非規範化概率”這句話，見下圖：
實際上，t時刻α向量中的某一個分量，αi可以視作終點狀態取yi時的非規範化概率，並且這個概率是1->t時刻的整個過程中，所有可能序列的非規範化概率之和（從start到stop所有路徑上的非規範化概率之和）。如圖中，α1t也就是從start=y1到stop=y1過程中，所有可能序列的非規範化概率之和。因此，每個αi是start=y1到stop=yi的規範化因子Zi。這樣就能看出與HMM特別不同了，一個應用矩陣乘法，一個應用條件概率公式。
我理解的大概就是這個樣子，不知道能不能寫清楚，接下來看下後向算法的計算過程。從公式(11.31)開始：
具體到轉換過程中（考慮矩陣乘法的過程）：
於是，βt(yi|x)可以表示從t時刻yt:start=y1到yn+1:stop=y1，所有路徑上的非規範化概率之和(共T-t個結點狀態的序列)。前向算法也好，後向算法也好，這裏的箭頭指向僅表示乘的方向，不是有向圖結構。
與HMM類似的，接下來看幾個概率計算。
公式(11.32)和公式(11.33)還是好理解的，看一下示意圖：
通過示意圖，先來看一下Z(X)，Z(X)既可以通過前向向量，又可以通過後向向量來求。實際上，不管前向向量αn也好，後向向量β1也好，Z(X)的計算矩陣過程，實際上是把m個值加和，也就是得到所有狀態序列的規範化因子。
分開看公式(11.32)分子部分，我覺得是兩個值(α、β)進行了相乘。第一個α值，代表了從0時刻start=y1到t時刻stop=yi的非規範化概率；第二個β值，代表了從t時刻start=yi到n+1時刻stop=y1的非規範化概率。公式(11.33)是類似分析方法。
再來看一下幾個期望的計算，就不具體分析了：
條件隨機場的學習問題
學習問題實際上討論的是在給定訓練數據集上估計模型參數的問題。條件隨機場模型實際上定義在時序數據上的對數線性模型（是不是與LR像），學習方法包括極大似然估計等，具體的有改進的迭代尺度法IIS、梯度下降法及擬牛頓法。
具體的方法目前先不弄了（有大概了解，但了解的程度，不足以寫出來），趕趕刷題的進度去了…等找着工作了，準備畢業的時候再把這些方法整理上~
話說這章的代碼沒寫，因為不會…不知道從什麼地方下手。
條件隨機場的預測問題
同HMM，大名鼎鼎的維特比算法。
PASS
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能
※台北網頁設計公司這麼多該如何選擇?
※智慧手機時代的來臨，RWD網頁設計為架站首選
※評比南投搬家公司費用收費行情懶人包大公開
※回頭車貨運收費標準
