標籤：

如何用簡單易懂的例子解釋條件隨機場（CRF）模型？它和HMM有什麼區別？

11-24

看到一個同樣問題問HMM，感覺答案都很好

from Sutton, Charles, and Andrew McCallum. "An introduction to conditional random fields." Machine Learning 4.4 (2011): 267-373.

搬磚狗強答一發...才疏學淺，不對求批評指正。
閱讀前說明：
- 本人閱讀的材料來主要來自於李航的《統計學習方法》第十一章和之前有人貼出的"An introduction to conditional random fields" (90頁太多沒讀完= _ =)
- 這段文字主要從兩個方面描述了CRF公式的由來和其他模型的關係。
- 閱讀前默認讀者已了解HMM。知道大致流程是訓練，最大似然，然後預測，知道特徵函數的定義等細節。
- 自己感覺，如果只要使用模型的話，只要知道公式，parameter estimate和inference就可以了，要弄清楚整個probability graph model是個不小的工作量。
- 公式貌似太多，要是有人願意閱讀，本學渣跪謝您的耐心。
正文：
一般可以從兩個方面來理解CRF模型：
一個從一般的graphical model來的(可以看成logistic回歸的擴展)。
另一個方面是linear chain CRF與HMM有類似的結構，而分別是discriminative model和generative model。
直接扔出CRF的公式會給人一種wtf的感覺，我閱讀的材料都是從無向圖模型開始說起，從這個模型開始呢，可以理解公式怎麼來的，那我們就從這個模型說起吧。

- 概率無向圖模型（probabilistic undirected graphical model）
首先我們有無向圖G=(V,E)，V是節點，E是邊， 圖G中每個節點v上都有一個隨機變數y，這樣所有的節點上的隨機變數就構成一組隨機變數Y，圖G上有聯合概率分布P(Y)。邊e表示相鄰節點的變數存在某種神秘的聯繫。
圖G上的隨機變數Y滿足馬爾科夫性，即兩個不相鄰的節點上的隨機變數yi，yj條件獨立。
這個模型的定義就這麼簡單，它又叫馬爾科夫隨機場(MRF)，這個名字貌似響亮一些。
再稍微介紹一下最大團(maximal clique) 如下圖

圖中{Y1,Y2,Y3}和{Y3,Y2,Y4}是最大團，包含的任何節點都兩兩相連被稱作團。最大團就是不能再添加節點。

然後呢，有個定理叫Hammersley-Clifford定理，給出了無向圖模型P(Y)的公式。
- Hammersley-Clifford定理：
概率無向圖模型的聯合概率分布P(Y)可以表示為如下形式：
P(Y)=frac{1}{Z} prod_{C}Psi_{C}(Y_{C}) Z=sum_{Y}prod_{C}Psi_{C}(Y_{C})
其中C是無向圖最大團，Yc是C的節點對應的隨機變數，Psi_{C}(Y_{C})是一個嚴格正勢函數，乘積（因式分解）是在無向圖所有最大團上進行的。
另外，勢函數這東西呢是Gibbs分布的，這個定理意義就是用Gibbs概率分布來計算馬爾科夫隨機場。一般來說勢函數取對數線性，這樣方便計算。
好了，這東西就介紹完了，接下來就是CRF。

- 條件隨機場(conditional random field)
定義：（和上面的模型比較就是多了一個X。）
設X與Y是隨機變數，P(Y|X)是給定條件X的條件下Y的條件概率分布，若隨機變數Y構成一個由無向圖G=(V,E)表示的馬爾科夫隨機場。則稱條件概率分布P(X|Y)為條件隨機場。
雖然定義裡面沒有要求，我們還是默認X和Y結構一致，這是general CRF，然後看看linear chain CRF，線性鏈就是X和Y都是一串序列，線性鏈裡面呢，最大團就是相鄰的兩項，y_i和y_i+1。
由Hammersley-Clifford定理寫出linear chain CRF的公式。
P(Y|X)=frac{1}{Z}prod_{i=0}^{n-1}Psi_{i}(Y_{i},Y_{i+1}|X)
勢函數取 對數線性，就得到了第一次見讓本學渣雲里霧裡的公式。（懶得輸了貼個圖）

再詳細點：

就是linear chain CRF常見的兩種特徵函數指數和的形式。
注意點！！！高潮來了！！如果我們把上式中的特徵函數t_{k}去掉，得到就是自變數X關於Y的logistic回歸（加上一個normalizer函數Z(x)），每個Y和X之間對數線性關係。本學渣看到這裡的時候真是amazing了一下。

好了，那麼是不是可以說linear chain CRF是logistic回歸，再加上了有關相鄰項某種神秘聯繫的參數呢？看起來是這樣的，我也不敢確定= =、、
之後呢，再從HMM的角度看。

- HMM和linear chain CRF
HMM的概率分布可以寫成這樣的形式：

右邊取對數變成和的形式，再加上歸一化的Z(x) 得到

嗯，這樣一看就和前面的CRF長的很像了，就是一個是條件概率，一個是聯合概率，
這也是discriminative model和generative model的區別。
注意Z(x)是遍歷所有y的全局歸一化，寫在乘積符號裡面的是local歸一化，得到的是MEMM。
其實generative和discriminative的差別是很大的，因為假設不一樣，結果和參數訓練的方法都不同，線性的CRF不需要EM演算法，稍微簡單一些，最大似然訓練集之後，梯度下降加上vertebi演算法就可以了。

最後貼上參考資料上一張圖

嗯，所以說我們就是從這兩條路走到了線性的CRF，general的CRF也是從MRF來的，公式是最大團的乘積形式，計算上麻煩一些，會用到loopy belief propagation。

一部分區別在於概率歸一化的時候。CRF的歸一化在模型上更加合理（但是在計算的時候可能導致計算量增加），而HMM的歸一化會導致label bias問題

MEMM(可以看做是HMM與log-linear model結合的一種方式)

CRF

注意兩個模型歸一化的位置的不同。參考：http://web.donga.ac.kr/yjko/usefulthings/MEMMCRF.pdf

題主說要用簡單易懂的例子來說明，那我就來強答一發。
理解條件隨機場最好的辦法就是用一個現實的例子來說明它。但是目前中文的條件隨機場文章鮮有這樣乾的，可能寫文章的人都是大牛，不屑於舉例子吧。於是乎，這件事只能由我這樣的機器學習小白來幹了。希望對其他的小白同學有所幫助。

最近在刷李航的《統計學習方法》，翻閱目錄，發現就後三章內容沒有接觸過，分別是EM演算法、隱馬爾可夫模型和條件隨機場，其他內容在林軒田的兩門公開課里都學過。以我的尿性，必須是先攻克後三章！EM演算法和隱馬爾可夫模型不費太大勁就理解了，在我乘勝前進，準備一舉拿下條件隨機場時，我懵逼了！這本書講解得TTMD精鍊了，上來就是卡卡卡的公式，背景、例子等人民群眾喜聞樂見的東西一個沒有！這對沒有相關知識背景的我來說，簡直就是滅絕人性！


後來，在全球最大的同性互動交友平台上，找到了一篇文章，雖然也是英文，但是相比100多頁的文章，算是很短的了，關鍵是，這篇文章就是用一個活生生的例子來說明條件隨機場的，十分的通俗易懂！甚合我意！看完之後，再去看李航的書，頓時感覺神清氣爽！

於是，我果斷決定翻譯這篇文章。原文在這裡

[Introduction to Conditional Random Fields]

想直接看英文的朋友可以直接點進去了。我在翻譯時並沒有拘泥於原文，許多地方都加入了自己的理解，用學術點的話說就是意譯。（畫外音：裝什麼裝，快點開始吧。）好的，下面開始翻譯！

假設你有許多小明同學一天內不同時段的照片，從小明提褲子起床到脫褲子睡覺各個時間段都有（小明是照片控！）。現在的任務是對這些照片進行分類。比如有的照片是吃飯，那就給它打上吃飯的標籤；有的照片是跑步時拍的，那就打上跑步的標籤；有的照片是開會時拍的，那就打上開會的標籤。問題來了，你準備怎麼干？

一個簡單直觀的辦法就是，不管這些照片之間的時間順序，想辦法訓練出一個多元分類器。就是用一些打好標籤的照片作為訓練數據，訓練出一個模型，直接根據照片的特徵來分類。例如，如果照片是早上6:00拍的，且畫面是黑暗的，那就給它打上睡覺的標籤;如果照片上有車，那就給它打上開車的標籤。

這樣可行嗎？

乍一看可以！但實際上，由於我們忽略了這些照片之間的時間順序這一重要信息，我們的分類器會有缺陷的。舉個例子，假如有一張小明閉著嘴的照片，怎麼分類？顯然難以直接判斷，需要參考閉嘴之前的照片，如果之前的照片顯示小明在吃飯，那這個閉嘴的照片很可能是小明在咀嚼食物準備下咽，可以給它打上吃飯的標籤；如果之前的照片顯示小明在唱歌，那這個閉嘴的照片很可能是小明唱歌瞬間的抓拍，可以給它打上唱歌的標籤。

所以，為了讓我們的分類器能夠有更好的表現，在為一張照片分類時，我們必須將與它相鄰的照片的標籤信息考慮進來。這——就是條件隨機場(CRF)大顯身手的地方！

#從例子說起——詞性標註問題
-----

啥是詞性標註問題？

非常簡單的，就是給一個句子中的每個單詞註明詞性。比如這句話：「Bob drank coffee at Starbucks」，註明每個單詞的詞性後是這樣的：「Bob (名詞) drank(動詞) coffee(名詞) at(介詞) Starbucks(名詞)」。

下面，就用條件隨機場來解決這個問題。

以上面的話為例，有5個單詞，我們將：**(名詞，動詞，名詞，介詞，名詞)**作為一個標註序列，稱為l，可選的標註序列有很多種，比如l還可以是這樣：**（名詞，動詞，動詞，介詞，名詞）**，我們要在這麼多的可選標註序列中，挑選出一個**最靠譜**的作為我們對這句話的標註。

怎麼判斷一個標註序列靠譜不靠譜呢？

就我們上面展示的兩個標註序列來說，第二個顯然不如第一個靠譜，因為它把第二、第三個單詞都標註成了動詞，動詞後面接動詞，這在一個句子中通常是說不通的。

假如我們給每一個標註序列打分，打分越高代表這個標註序列越靠譜，我們至少可以說，凡是標註中出現了**動詞後面還是動詞**的標註序列，要給它**減分！！**

上面所說的**動詞後面還是動詞**就是一個特徵函數，我們可以定義一個特徵函數集合，用這個特徵函數集合來為一個標註序列打分，並據此選出最靠譜的標註序列。也就是說，每一個特徵函數都可以用來為一個標註序列評分，把集合中所有特徵函數對同一個標註序列的評分綜合起來，就是這個標註序列最終的評分值。

#定義CRF中的特徵函數

現在，我們正式地定義一下什麼是CRF中的特徵函數，所謂特徵函數，就是這樣的函數，它接受四個參數：

- 句子s（就是我們要標註詞性的句子）
- i，用來表示句子s中第i個單詞
- l_i，表示要評分的標註序列給第i個單詞標註的詞性
- l_i-1，表示要評分的標註序列給第i-1個單詞標註的詞性

它的輸出值是0或者1,0表示要評分的標註序列不符合這個特徵，1表示要評分的標註序列符合這個特徵。

**Note:**這裡，我們的特徵函數僅僅依靠當前單詞的標籤和它前面的單詞的標籤對標註序列進行評判，這樣建立的CRF也叫作線性鏈CRF，這是CRF中的一種簡單情況。為簡單起見，本文中我們僅考慮線性鏈CRF。

#從特徵函數到概率
定義好一組特徵函數後，我們要給每個特徵函數f_j賦予一個權重λ_j。現在，只要有一個句子s，有一個標註序列l，我們就可以利用前面定義的特徵函數集來對l評分。

上式中有兩個相加，外面的相加用來相加每一個特徵函數f_j，裡面的相加用來相加句子中每個位置的單詞的的特徵值。

對這個分數進行**指數化和標準化**，我們就可以得到標註序列l的概率值**p(l|s)**，如下所示：

#幾個特徵函數的例子
前面我們已經舉過特徵函數的例子，下面我們再看幾個具體的例子，幫助增強大家的感性認識。

當l_i是「副詞」並且第i個單詞以「ly」結尾時，我們就讓f1 = 1，其他情況f1為0。不難想到，f1特徵函數的權重λ1應當是正的。而且λ1越大，表示我們越傾向於採用那些把以「ly」結尾的單詞標註為「副詞」的標註序列

如果i=1，l_i=動詞，並且句子s是以「？」結尾時，f2=1，其他情況f2=0。同樣，λ2應當是正的，並且λ2越大，表示我們越傾向於採用那些把問句的第一個單詞標註為「動詞」的標註序列。

當l_i-1是介詞，l_i是名詞時，f3 = 1，其他情況f3=0。λ3也應當是正的，並且λ3越大，說明我們越認為介詞後面應當跟一個名詞。

如果l_i和l_i-1都是介詞，那麼f4等於1，其他情況f4=0。這裡，我們應當可以想到λ4是負的，並且λ4的絕對值越大，表示我們越不認可介詞後面還是介詞的標註序列。好了，一個條件隨機場就這樣建立起來了，讓我們總結一下：
為了建一個條件隨機場，我們首先要定義一個特徵函數集，每個特徵函數都以整個句子s，當前位置i，位置i和i-1的標籤為輸入。然後為每一個特徵函數賦予一個權重，然後針對每一個標註序列l，對所有的特徵函數加權求和，必要的話，可以把求和的值轉化為一個概率值。

來來來，這兩天正好在複習CRF，我從頭給你說。。。

模型
------
首先什麼是隨機場呢，一組隨機變數，他們樣本空間一樣，那麼就是隨機場。當這些隨機變數之間有依賴關係的時候，對我們來說才是有意義的。

我們利用這些隨機變數之間的關係建模實際問題中的相關關係，實際問題中我們可能只知道這兩個變數之間有相關關係，但並不知道具體是多少，我們想知道這些依賴關係具體是什麼樣的，於是就把相關關係圖畫出來，然後通過實際數據訓練去把具體的相關關係訓練出來嵌入到圖裡，然後用得到的這個圖去進行預測、去進行reference等很多事情。

那麼為了簡化某些為問題來說，也為了這個圖畫出來能用，我們會在畫圖的時候要遵循一些假設和規則，比如馬爾科夫獨立性假設。按照這個假設和規則來畫圖，畫出來的圖會滿足一系列方便的性質便於使用。

馬爾可夫獨立性假設是說：對一個節點，在給定他所連接的所有節點的前提下，他與外接是獨立的。就是說如果你觀測到了這個節點直接連接的那些節點的值的話，那他跟那些不直接連接他的點就是獨立的。形式上，我們是想把他設計成這個樣子的，邊可以傳遞信息，點與點之間通過邊相互影響，如果觀測到一個節點的取值或者這個節點的取值是常量，那麼別的節點就無法通過這個節點來影響其他節點。所以對一個節點來說，如果用來連接外界的所有節點都被鎖住了，那他跟外界就無法傳遞信息，就獨立了。這比貝葉斯網路就直觀多了，貝葉斯網路要判斷兩點之間獨立還要看有沒有v-structure，還要看邊的指向。

吶，滿足馬爾可夫獨立性的隨機場，就叫馬爾可夫隨機場。它不僅具有我剛才說的那些性質，除此之外，還等價于吉布斯分布。

這些邊具體是如何建模的呢，以什麼形式記錄這些概率信息的？貝葉斯網路每一條邊是一個條件概率分布，P(X|Y)，條件是父節點、結果是子節點。他有一個問題，就是當我知道A、B、C三個變數之間有相關關係，但是不知道具體是誰依賴誰，或者我不想先假設誰依賴誰，這個時候貝葉斯就畫不出來圖了。因為貝葉斯網路是通過變數之間的條件分布來建模整個網路的，相關關係是通過依賴關係（條件分布）來表達的。而馬爾可夫隨機場是這樣，我不想知道這三個變數間到底是誰依賴誰、誰是條件誰是結果，我只想用聯合分布直接表達這三個變數之間的關係。比如說兩個變數A、B，這兩個變數的聯合分布是：

| A, B | P(A, B) |
|--------------+---------|
| A = 0, B = 0 | 100 |
| A = 0, B = 1 | 10 |
| A = 1, B = 0 | 20 |
| A = 1, B = 1 | 200 |

這個分布表示，這條邊的功能是使它連接的兩點（A和B）趨同，當A = 0的時候B更可能等於0不太可能等於1，當A =
1的時候B更可能等於1不太可能等於0。這樣一來你知道了三個變數之間的聯合分布，那他們兩兩之間的條件分布自然而然就在裡面。

這樣出來的圖是等價于吉布斯分布的，就是說，你可以只在每個最大子團上定義一個聯合分布（而不需要對每個邊定義一個聯合分布），整個圖的聯合概率分布就是這些最大子團的聯合概率分布的乘積。當然這裡最大子團的聯合概率並不是標準的聯合概率形式，是沒歸一化的聯合概率，叫factor（因子），整個圖的聯合概率乘完之後下面再除一個歸一化因子和就歸一化了，最終是一個聯合概率，每個子團記載的都是因子，是沒歸一化的概率，嚴格大於零，可以大於一。但關鍵是依賴關係、這些相關關係已經encode在裡面了。

這是馬爾科夫隨機場。

條件隨機場是指這個圖裡面一些點我已經觀測到了，求，在我觀測到這些點的前提下，整張圖的分布是怎樣的。就是given觀測點，你去map inference也好你去做之類的事情，你可能不求具體的分散式什麼。這裡還要注意的是，馬爾科夫隨機場跟貝葉斯網路一樣都是產生式模型，條件隨機場才是判別式模型。

這是條件隨機場，NER（命名實體識別）這個任務用到的是線性鏈條件隨機場。

線性鏈條件隨機場的形式是這樣的，觀測點是你要標註的這些詞本身和他們對應的特徵，例如說詞性是不是專有名詞、語義角色是不是主語之類的。隱節點，是這些詞的標籤，比如說是不是人名結尾，是不是地名的開頭這樣。這些隱節點（就是這些標籤），依次排開，相鄰的節點中間有條邊，跨節點沒有邊（線性鏈、二階）。然後所有觀測節點（特徵）同時作用於所有這些隱節點（標籤）。至於觀測節點之間有沒有依賴關係，這些已經不重要了，因為他們已經被觀測到了，是固定的。

這是線性鏈條件隨機場的形式。

吶，這些特徵是怎麼表達的呢？是這樣，他有兩種特徵，一種是轉移特徵，就是涉及到兩個狀態之間的特徵。另一種就是簡單的狀態特徵，就是只涉及到當前狀態的特徵。特徵表達形式比較簡單，就是你是否滿足我特徵所說的這個配置，是就是1，不是就是。比如說，上一個狀態是地名的中間，且當前詞是"國"（假設他把中國分詞
拆成兩個了），且當前詞的詞性是專有名詞、且上一個詞的詞性也是專有名詞，如果滿足這個配置、輸出就是1、不滿足就輸出0。然後這些特徵每個都有一個權
重，我們最後要學的就是這些權重。特徵跟權重乘起來再求和，外面在套個exp，出來就是這個factor的形式。這是一個典型的對數線性模型的表達方式。這種表達方式非常常見，有很多好處，比如為什麼要套一個exp呢？一方面，要保證每一個factor是正的，factor可以大於一也可以不歸一化，但一定要是正的。另一方面，我們最後要通過最大似然函數優化的，似然值是這些
factor的累乘，對每一個最大子團累乘。這麼多項相乘沒有人直接去優化的，都是取log變成對數似然，然後這些累乘變成累加了嘛，然後優化這個累加。無論是算梯度用梯度下降，還是另導數為零求解析解都很方便了（這個表達形態下的目標函數是凸的）。你套上exp之後，再取對數，那麼每個因子就變成一堆特徵乘權重的累積，然後整個對數似然就是三級累積，對每個樣本、每個團、每個特徵累積。這個形式就很有利了，你是求導還是求梯度還是怎樣，你面對的就是一堆項的和，每個和是一個1或者一個0乘以一個
權重。當然後面還要減一個log(Z)，不過對於map inference來說，給定Z之後log(Z)是常量，優化可以不帶這一項。

推斷
------
線性鏈的條件隨機場跟線性鏈的隱馬爾科夫模型一樣，一般推斷用的都是維特比演算法。這個演算法是一個最簡單的動態規劃。

首先我們推斷的目標是給定一個X，找到使P(Y|X)最大的那個Y嘛。然後這個Z(X)，一個X就對應一個Z，所以X固定的話這個項是常量，優化跟他沒關係（Y的取值不影響Z）。然後
exp也是單調遞增的，也不帶他，直接優化exp裡面。所以最後優化目標就變成了裡面那個線性和的形式，就是對每個位置的每個特徵加權求和。比如說兩個狀態的話，它對應的概率就是從開始轉移到第一個狀態的概率加上從第一個轉移到第二個狀態的概率，這裡概率是只exp裡面的加權和。那麼這種關係下就可以用維特比了，首先你算出第一個狀態取每個標籤的概率，然後你再計算到第二個狀態取每個標籤得概率的最大值，這個最大值是指從狀態一哪個標籤轉移到這個標籤的概率最大，值是多
少，並且記住這個轉移（也就是上一個標籤是啥）。然後你再計算第三個取哪個標籤概率最大，取最大的話上一個標籤應該是哪個。以此類推。整條鏈計算完之後，
你就知道最後一個詞去哪個標籤最可能，以及去這個標籤的話上一個狀態的標籤是什麼、取上一個標籤的話上上個狀態的標籤是什麼，醬。這裡我說的概率都是
exp裡面的加權和，因為兩個概率相乘其實就對應著兩個加權和相加，其他部分都沒有變。

學習
------
這是一個典型的無條件優化問題，基本上所有我知道的優化方法都是優化似然函數。典型的就是梯度下降及其升級版（牛頓、擬牛頓、BFGS、L-BFGS），這裡版本最高的就是L-BFGS了吧，所以一般都用L-BFGS。除此之外EM演算法也可以優化這個問題。

才疏學淺，難免有紕漏，大家指正。

基本符號：Y是序列的標註，X是序列的特徵

兩者的建模方式不同：

  • 對於CRF，直接用最大熵準則建模p(Y|X)的概率。
  • 而HMM，是在做了markov假設下去建模p(Y,X)（即一切觀察量的聯合概率分布）。

這裡借用 @li Eta 同學答案里的公式，我把i變成t，要注意：

  1. CRF是用最大熵準則建模p(Y|X)，從而得到一個指數歸一化的函數形式，但是分子上應該是exp(sum_i{w_i*f_i(Y,X)}) 而不是f_i(yt,yt+1,X). 把f(Y,X)變到f(yt,yt+1,X)其實是做了一個markov假設的CRF，而不是General形式的CRF. 當然實際應用中，我們甚至把特徵簡化為只能是f(yt,X)和f(yt,yt+1)（注意此時f裡面沒X了)，進一步減小特徵數和加快訓練和推斷速度。這種叫linear chain CRF。
  2. HMM是生成模型，而@li Eta同學貼的實際上是MEMM(最大熵馬爾科夫模型),它建模的也是p(Y|X), 而不是一般我們講的用來建模p(Y,X)的HMM生成模型。HMM生成模型，求和號里是p(yt|yt-1)p(xt|yt)而不是p(yt|yt-1,X).此時p(yt|yt-1)一般就是個多項分布，而p(xt|yt)則可以是任意你用來建模世界的分布。把@li Eta同學裡面的MEMM的X到Y的箭頭倒過來指（變成Y指向X)，才是HMM.

CRF: 最大熵準則建模條件概率
HMM:假設出變數間的概率分布，建模所有觀察到的變數的聯合分布。在Y變數間做了markov假設。

再次注意CRF跟markov沒關係！linear chain CRF才和markov有關。

而linear chain CRF和MEMM的分母在求和號裡面外面的區別，並不是CRF和HMM的區別。
至於CRF和HMM，要先把CRF約束成linear chain CRF，然後linear chain CRF和HMM的區別：是判別式模型和生成模型的區別，是函數擬合和概率模型的區別。


這裡再多說點，HMM叫hidden markov model， markov上面已經說了，而hidden是什麼意思呢？在上面的例子里，Y是序列的標註，是可見的觀察量。但是HMM的標準介紹裡面，Y是未知量，HMM建模的是p(X) = sum_Y P(Y,X) 而不是 P(Y,X),注意要對Y求和的。搞語音識別的同學一般接觸的是這個HMM，這個是帶有hidden的真身，而搞自然語言處理的同學接觸的多是Y是可見量的那個HMM，但其實是閹割版的HMM，因為根本沒有hidden的變數啊，沒有了hidden變數的hmm就不需要EM來訓練，很不好玩的。學hmm的時候不學EM，很可惜，EM是ML領域最神奇的演算法。


CRF叫condition random field，為啥這麼叫呢，我猜呢，是一般無向圖模型大家就叫markov random field，CRF呢是個二部圖，一部分是Y一部分是X，最後建模的是P(Y|X)是個條件概率，所以叫condition random field. 我就這麼一猜，確實有點不負責任，這個名字的來源我一直么研究過，這段要是說錯了請見諒。

首先題主你想問的應該是HMM和linear chain CRF的區別。因為這兩個模型是在解決同樣的問題，只是用不同的方法。 他們的關係就像naive bayes 和 logistic regression的關係一樣，相愛相殺。

我會盡量少用公式進行我的回答，這樣我想讀者讀起來也會輕鬆一些。但是代價就是我只能提供一些相對high level的分析和解答。如果有人對這篇Charles Sutton寫的CRF的tutorial文章[1] 里的任何一個公式有問題，可以給我留言，我一定有針對性地儘力給你回答。

下面開始正式回答。

建立一個隨機模型，尤其是貝葉斯模型，一般大體上分三步。

第一步，modeling，設計一個大的概率分布，描述所有隨機變數之間的關係。 圖模型的精髓是把一個大的，包含很多隨機變數的複雜分布，寫成若干個小的，相對簡單的factor的乘積，其中每個factor僅僅包含一小部分隨機變數。 想想高票答案裡面的那個類比圖（tutorial里的Fig 2.4），每個節點代表什麼？有向圖的每一個邊代表什麼？無向圖呢？裡面的小黑方塊是什麼意思？

第二步，training，parameter estimation, 也就是根據數據，找到模型的參數的最佳估計。這是一個將模型fit進data的過程。我們在第一步中定義了一些變數，假設了這些變數之間的關係，比如我們假設A和B是線性關係，但在training之前，我們並不知道A是B的多少倍。請回憶線性回歸的參數估計是怎麼做的。從更電子工程的角度來說，這一步驟可以理解為一個system identification的過程。

第三步， inference，prediction, 作預測，在這個已經確定好參數的系統里，有了新的輸入，那麼輸出該服從什麼樣的分布呢？

下面我從以上的三個方面來說說HMM和linear chain CRF（下面簡稱CRF）的關係。

他們倆都在解決一個已知x，如何估計y的問題。想像我們已經觀測到了很多（x，y）這樣一對一對的樣本，現在需要解決兩個問題。

a）找到x和y的隨機關係，y的後驗概率， p(y|x)

b）當知道新的x，卻不知道新的y的時候，能不能對y做出預測。特別的，當y是一個高維向量的時候，能不能找到 p(y_k | x) ，其中 y_k 代表y向量的第 k 個元素。


這兩個模型都用他們各自的方式，都能回答上面的兩個問題。

1。從model的角度來說，HMM是generative的，什麼意思呢？意思是說HMM描述的是已知量和未知量的一個聯合概率分布，p（x,y）。而CRF是discriminative的，是在描述p（y|x）。經過一番推導，tutorial裡面的definition 2.2 給出了p（y|x）的顯式表達形式。

2。從training的角度來說，HMM的參數估計是

hat{ heta} = arg_{ heta} max prod_i p(x^{i}, y^{i}, heta )

而CRF的參數估計則是

hat{ heta} = arg_{ heta} max prod_i p(y^{i}| x^{i}; heta )

其中 x^{i}, y^{i} 代表第 i 個訓練樣本。


看出來了么？HMM是在擬合聯合概率分布的參數，而CRF是直接在擬合後驗概率的參數。這樣就算在建模的時候可以用貝葉斯定律將p（x,y）和p（y|x）進行等價的轉換，當這樣定義參數估計之後，兩個模型就有了本質上的不同。


3。inference過程，從 p(y|x) 到 p(y_k|x) ，這只是一個marginalization的過程，兩個模型並沒有什麼區別。有很多辦法可以利用變數之間的條件獨立性，提高marginalization的效率，比如message passing 演算法。


[1] Sutton, Charles, and Andrew McCallum. "An introduction to conditional random fields." Foundations and Trends? in Machine Learning 4.4 (2012): 267-373. http://homepages.inf.ed.ac.uk/csutton/publications/crftut-fnt.pdf


##################

我胡亂答了一個評論清華韓博士的問題，結果一堆人點贊，還多了很多關注我的人。我慌了，決定找個我能答的技術性問題，好好回答回答。這個題我算是認真回答的，真的。認真臉。

貝葉斯是生成模型，並且假設變數之間相互獨立。那麼對於像NLP中NER這樣的任務是肯定不行的。HMM的出現，拓展了貝葉斯的圖關係，model了觀測變數的markov性，但是，始終表達能力不夠，沒有context。CRF不model輸出與單個變數之間的關係了，而是與LR類似，model y 與 向量x之間的關係，加上圖的local function的表達能力使得context信息和feature擴展能力變強。於是CRF得到了很不錯的應用。

這裡先簡單敘述下條件隨機場的幾個基本概念，方便後續理解。首先，【條件隨機場】其實分為兩個關鍵詞【條件】和【隨機場】，他倆需要明確區分，咱們分別敘述下。【條件】對應於【條件概率】，說起條件概率，我們就需要扯一扯【聯合概率】，所以待會先來談談【聯合概率】問題。其次，【隨機場】對我來說是一個全新的概念，參考相關資料發現，它是單獨定義的。所以，條件+隨機場 = 條件隨機場。

條件隨機場的由來
如果參看《統計學習方法》第11章節的話，你會發現一個很有趣的現象。書中首先提到的是圖，圖有個很有趣的特性，你會發現每個節點都是平鋪在一個平面上的，所以每個節點都有可能與另外一個結點闡述【聯繫】，也就是所謂的【E or 邊】。有了圖的定義，便開始定義【聯合概率】分布下，各隨機變數的圖結構，並對每個節點進行約束，所謂的三種性質【成對馬爾科夫性】、【局部馬爾科夫性】和【全局馬爾科夫性】，節點的約束一步步增強。定義完這些後，便在此基礎上有了馬爾科夫隨機場的概念，我就呵呵了，你給我一堆定義，我怎麼知道誰和誰是【組合】，誰是誰的【遞進】關係啊。

好吧，還是按照自己的思路來重新梳理下吧。之前學習過隱馬爾可夫模型的話，我們知道它是一個時間序列模型。起初對這個【時間】不以為然，隱馬爾可夫模型中的節點，不就是一個個狀態么，何必叫時間序列模型，還不如更名為狀態序列模型。學到條件隨機場，發現了HMM和CRF的一個顯著區別，即節點與節點之間的邊，HMM是有向的，而CRF是無向的。而時間序列，能很好的表達當前狀態與之前狀態有關而和後續狀態無關這一特性，即在圖中的有向性，因此時間序列模型相比狀態模型更合適。而CRF則可以成為一個HMM的擴展，稱為狀態序列模型更合適，從【有向邊】升級到【無向邊】。

隱馬爾可夫模型隱馬爾可夫模型


條件隨機場條件隨機場
這張圖很好的描述了HMM和CRF之間的差異，暫且不去關注底下的公式和隨機變數X，單獨看Y1～Yn的聯合概率在圖中的表現形式。是不是很有愛，有數學之美。

對於條件隨機場是不有個簡單的認識了，再來看看wiki上關於Random Field的定義。

A random field is a generalization of a stochastic process such that the underlying parameter need no longer be a simple real or integer valued 「time」, but can instead take values that are multidimensional vectors, or points on some manifold.

注意我標黑的字詞，我這裡就大膽猜測下概率論研究的一個階段成果，無實際根據，純屬個人臆想。在Demon同學的世界裡，概率論現分為兩個階段，有向概率論和無向概率論。起初，為了研究現實生活中大量的【數據現象】，諸如統計歐洲黑死病每年死亡人數，通過數據判斷黑死病是否逐年嚴重or維持在某個穩定狀態。在那個時代，統計學者們收集到的大量數據，都存在一個明顯的特徵即隨機變數的先後順序，所以從維度上來看，對這些數據的研究，完全可以映射到二維的橫軸和縱軸，橫軸表示隨機變數，而縱軸表示當前隨機變數的出現概率。所以對概率密度函數的積分，你也會發現，它一定是從負無窮累加到當前時間點t，而不會繼續積下去了。它對隨機變數時間的統計是有向的。

這是一張經典的隱馬爾可夫模型圖，我們關注隱含狀態的序列，你會發現在同一時刻，只有一個狀態指向下一個狀態，不會出現多個狀態同時指向一個狀態的情況發生，這是因為隱馬爾可夫模型做了一個基本假設，即在同一時刻，不存在兩個或者多個狀態同時發生的情況，起初這的確合理，比如擲骰子的過程，一定是一次次投擲得出的結果，但對一維的時間如此，但對二維空間就一定是這樣子么？

參看《統計學習方法》詞性標註的例子

輸入：At Microsoft Research, we have an insatiable curiosity and the desire to create new technology that will help define the computing experience.
輸出：At/O Microsoft/B Research/E, we/O have/O an/O insatiable/B curiosity/E and/O the/O desire/BE to/O create/O new/B technology/E that/O will/O help/O define/O the/O computing/B experience/E.

這一內容在博文【隱馬爾可夫學習筆記（一）】引出過，這裡就不在詳細敘述了。HMM所做的就是統計當前狀態與前一狀態在整個序列中出現的頻次，從而估算出轉移概率矩陣。它有個很明顯的特徵在於，假設語句是按時間順序一個一個生成的，所以可以不用考慮當前單詞與下一單詞的關係，而只需統計與上一單詞的聯繫。但在真正的訓練過程當中，所有句子的訓練集，並非單純的一維時間啊，我們完全可以映射到二維空間中去，統計當前單詞和上一單詞以及前一單詞的關係，這是完全可以做到的，因為程序在訓練語料時，它把握了全局信息，而且從語義上來看，更加符合句子的構成。

所以說，條件隨機場是隱馬爾可夫模型的加強版，無非從原先的【時間維度】上升到了【空間維度】，而後者更加合理，每個狀態所依賴的信息更多。

在這裡引用博文【隨機場（Random field）】中關於馬爾科夫隨機場的形象例子，它說

隨機場包含兩個要素：位置（site），相空間（phase space）。當給每一個位置中按照某種分布隨機賦予相空間的一個值之後，其全體就叫做隨機場。我們不妨拿種地來打個比方。「位置」好比是一畝畝農田； 「相空間」好比是種的各種莊稼。我們可以給不同的地種上不同的莊稼，這就好比給隨機場的每個「位置」，賦予相空間里不同的值。所以，俗氣點說，隨機場就是在哪塊地里種什麼莊稼的事情。
好了，明白了上面兩點，就可以講馬爾可夫隨機場了。還是拿種地打比方，如果任何一塊地里種的莊稼的種類僅僅與它鄰近的地里種的莊稼的種類有關，與其它地方的莊稼的種類無關，那麼這些地里種的莊稼的集合，就是一個馬爾可夫隨機場。
馬爾可夫隨機場，描述了具有某種特性的集合。拿種地打比方，如果任何一塊地里種的莊稼的種類僅僅與它鄰近的地里種的莊稼的種類有關，與其它地方的莊稼的種類無關，那麼這些地里種的莊稼的集合，就是一個馬爾可夫隨機場。

簡單總結下概念，什麼是馬爾科夫隨機場，首先隨機變數由圖中各節點表示，每個節點至少有一條邊與其另一個節點相連（不會出現孤立節點，孤立節點毫無意義）。那麼整個圖由Y1,Y2,...,Yn 節點，圖所代表的物理含義為P(Y1,Y2,...,Yn) 的聯合概率，一定是聯合概率，否則表示成圖也沒有任何意義。馬爾科夫性在於當前節點只與相鄰節點有關，它的概率受鄰居影響。何謂隨機場？從隨機變數【一維時間序列】上升到了隨機變數【二維空間圖結構】，【有向】到【無向】的飛躍在於維度的上升，個人覺得拿它做區分欠妥，容易產生誤解。

so far till now, 我還沒見到過將CRF講的個明明白白的。一個都沒。md就不能不抄來抄去嗎？

我打算搞一個這樣的版本，無門檻理解的。

都看了一遍 還是有點蒙

條件隨機場的用途就是用由事物本身的觀測值（x)，位置（相鄰節點對它的影響）和意義(y或標籤）組成的訓練集訓練，推斷出下次出現在這個位置的相同值的節點（x")的意義(y")。

P(y|x)

=P(x,y)/P(x)

=P(x,y)/Σ_y"P(x,y")

=1/ZΠ_Cψ_C(x_C,y_C)/

1/ZΣ_y"Π_Cψ_C(x_C,y"_C)

=Π_Cψ_C(x_C,y_C)/

Σ_y"Π_Cψ_C(x_C,y"_C)

=Π_Cψ_C(x_C,y_C)/Z_x

=概率權重(x,y)/Σ_y"概率權重(x,y") // 從準確概率比P(x,y)/Σ_y"P(x,y"),轉變為了權重比.

我是將勢函數理解為沒有歸一的概率權重才理解的.

概率權重(x,y)=所有最大團的概率權重 的 乘積.

每個最大團的概率權重 = exp{觀察特徵的線性和}.
這步有點像線性回歸中, 我們對於不知道的模型, 直觀上都是假定最終結果和特徵是線性關係. 比如披薩價格, 本來是和面積成正比, 但觀察到很多特徵時, 可能先直接把直徑作為一個特徵塞到式子里.

鏈式crf可以看成每個最大團結構相同, 那就只要觀察一個最大團的特徵了. 特徵是指樣本中經常共現的現象: 如"我"後面經常跟著"們".

CRF捨棄掉了HMM的有限歷史性假設、輸出獨立性假設，由生成模型轉變為判別模型，由概率圖轉變為函數擬合。

CRF只需要考慮當前觀測狀態的特性，不像HMM有嚴格的獨立性的要求。
從圖的角度來看，就是觀測序列的元素之間並不存在圖結構。
從建立模型的角度來看，CRF只考慮觀測序列X整體，而HMM是將每一個時刻的狀態都考慮在內，並且對觀測序列做出了馬爾科夫獨立性假設。
正是因為CRF不做獨立性假設，這就是「條件隨機」的含義。

參考網上的mail list和wiki memm介紹，memm label "effectively ignore their
observations",這句話對應論文里p(2/1,o),因為訓練里沒有數據，帶入歸一化公式，exp內部為0，概率就為1了，與觀測o沒關係，per—instance—normslization vs per—sequence—normslization,局部歸一，而crf全局歸一，hmm不存在label bias,因為觀測是生成模型，始終和觀測相關。這理解的對嗎

推薦閱讀：

※在 Caffe 中如何計算卷積？
※卷積神經網路工作原理直觀的解釋？
※在與 AlphaGo（包括 Master） 的對局中是否出現了一些人類歷史上從未想到過的著法、技巧？
※如何理解感知機學習演算法的對偶形式？
※計算機圖形學與機器學習（深度學習）怎麼結合起來？

TAG:機器學習 |