統計學習方法；機器學習；條件随機場
今天是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