条件随机场学习
前戲：一起走進條件隨機場
作者：白寧超
2016年8月2日13:59:46
【摘要】：條件隨機場用于序列標注，數(shù)據(jù)分割等自然語言處理中，表現(xiàn)出很好的效果。在中文分詞、中文人名識別和歧義消解等任務中都有應用。本文源于筆者做 ，對條件隨機場的了解，逐步研究基于自然語言處理方面的應用。成文主要源于自然語言處理、機器學習、統(tǒng)計學習方法和部分網(wǎng)上資料對CRF介紹的相關(guān)的相關(guān)，最后進行大量研究整理匯總成體系知識。文章布局如下：第一節(jié)介紹CRF相關(guān)的基礎(chǔ)統(tǒng)計知識；第二節(jié)介紹基于自然語言角度的CRF介紹；第三節(jié)基于機器學習角度對CRF介紹，第四節(jié)基于統(tǒng)計學習角度對相關(guān)知識介紹；第五節(jié)對統(tǒng)計學習深度介紹CRF，可以作為了解內(nèi)容。（本文原創(chuàng)，轉(zhuǎn)載請注明出處：漫步條件隨機場系列文章。)
目錄
【自然語言處理：漫步條件隨機場系列文章（一）】：前戲：一起走進條件隨機場 【自然語言處理：漫步條件隨機場系列文章（二）】：基于自然語言處理角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（三）】：基于機器學習角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（四）】：基于統(tǒng)計學習角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（五）】：條件隨機場知識擴展 1 機器學習中的生產(chǎn)模型與判別模型
生產(chǎn)式模型與判別式模型簡述，條件隨機場是哪種模型？ 有監(jiān)督機器學習方法可以分為生成方法和判別方法： 1）生產(chǎn)式模型：直接對聯(lián)合分布進行建模，如：混合高斯模型、隱馬爾科夫模型、馬爾科夫隨機場等 2）判別式模型：對條件分布進行建模，如：條件隨機場、支持向量機、邏輯回歸等。 生成模型優(yōu)缺點介紹： 優(yōu)點： 1）生成給出的是聯(lián)合分布，不僅能夠由聯(lián)合分布計算條件分布（反之則不行），還可以給出其他信息。如果一個輸入樣本的邊緣分布很小的話，那么可以認為學習出的這個模型可能不太適合對這個樣本進行分類，分類效果可能會不好。 2）生成模型收斂速度比較快，即當樣本數(shù)量較多時，生成模型能更快地收斂于真實模型。 3）生成模型能夠應付存在隱變量的情況，比如混合高斯模型就是含有隱變量的生成方法。 缺點： 1）天下沒有免費午餐，聯(lián)合分布是能提供更多的信息，但也需要更多的樣本和更多計算，尤其是為了更準確估計類別條件分布，需要增加樣本的數(shù)目，而且類別條件概率的許多信息是我們做分類用不到，因而如果我們只需要做分類任務，就浪費了計算資源。 2）另外，實踐中多數(shù)情況下判別模型效果更好。 判別模型優(yōu)缺點介紹： 優(yōu)點： 1）與生成模型缺點對應，首先是節(jié)省計算資源，另外，需要的樣本數(shù)量也少于生成模型。 2）準確率往往較生成模型高。 3）由于直接學習，而不需要求解類別條件概率，所以允許我們對輸入進行抽象（比如降維、構(gòu)造等），從而能夠簡化學習問題。 缺點： 1）是沒有生成模型的上述優(yōu)點。 2 簡單易懂的解釋條件隨機場
線性鏈的條件隨機場跟線性鏈的隱馬爾科夫模型一樣，一般推斷用的都是維特比算法。這個算法是一個最簡單的動態(tài)規(guī)劃。 首先我們推斷的目標是給定一個X，找到使P(Y|X)最大的那個Y嘛。然后這個Z(X)，一個X就對應一個Z，所以X固定的話這個項是常量，優(yōu)化跟他沒關(guān)系（Y的取值不影響Z）。然后exp也是單調(diào)遞增的，也不帶他，直接優(yōu)化exp里面。所以最后優(yōu)化目標就變成了里面那個線性和的形式，就是對每個位置的每個特征加權(quán)求和。比如說兩個狀態(tài)的話，它對應的概率就是從開始轉(zhuǎn)移到第一個狀態(tài)的概率加上從第一個轉(zhuǎn)移到第二個狀態(tài)的概率，這里概率是只exp里面的加權(quán)和。那么這種關(guān)系下就可以用維特比了，首先你算出第一個狀態(tài)取每個標簽的概率，然后你再計算到第二個狀態(tài)取每個標簽得概率的最大值，這個最大值是指從狀態(tài)一哪個標簽轉(zhuǎn)移到這個標簽的概率最大，值是多 少，并且記住這個轉(zhuǎn)移（也就是上一個標簽是啥）。然后你再計算第三個取哪個標簽概率最大，取最大的話上一個標簽應該是哪個。以此類推。整條鏈計算完之后， 你就知道最后一個詞去哪個標簽最可能，以及去這個標簽的話上一個狀態(tài)的標簽是什么、取上一個標簽的話上上個狀態(tài)的標簽是什么，醬。這里我說的概率都是 exp里面的加權(quán)和，因為兩個概率相乘其實就對應著兩個加權(quán)和相加，其他部分都沒有變。 學習 這是一個典型的無條件優(yōu)化問題，基本上所有我知道的優(yōu)化方法都是優(yōu)化似然函數(shù)。典型的就是梯度下降及其升級版（牛頓、擬牛頓、BFGS、L-BFGS），這里版本最高的就是L-BFGS了吧，所以一般都用L-BFGS。除此之外EM算法也可以優(yōu)化這個問題。 3 概率無向圖與馬爾科夫隨機場前世今生
概率無向圖模型又稱為馬爾科夫隨機場，是一個可以由無向圖表示的聯(lián)合概率分布。 圖是由結(jié)點和連接結(jié)點的邊組成的集合，（這部分知識學過數(shù)據(jù)結(jié)構(gòu)或者算法的同學都比較了解，不作為深入講解。） 注意：無向圖是指邊上沒有方向的圖，既然邊沒有方向，其權(quán)值是有方向的，諸如轉(zhuǎn)移概率中，“我”到“愛”的轉(zhuǎn)移概率0.5. 概率圖模型是由圖表示的概率分布，沒有聯(lián)合概率分布P(Y)，Y∈{y}是一組隨機變量由無向圖G=<V,E>表示概率分布P(Y)，即在圖G中，結(jié)點v∈V表示一個隨機變量? ；邊e∈E表示隨機變量之間的概率依賴關(guān)系，這點在第一章有詳細介紹。 給定一個聯(lián)合概率分布P（Y）和表示它的無向圖G，無向圖表示的隨機變量之間的成對馬爾科夫性，局部馬爾科夫性，全局馬爾科夫性的如何區(qū)別？ 1） 成對馬爾科夫性表示 ?? 2）局部馬爾科夫性表示 ? 3）全局馬爾科夫性表示 ???????????????? 概率無向圖模型的定義 設(shè)有聯(lián)合概率分布P(Y)，由無向圖G=<V,E>表示，在圖G中，結(jié)點表示隨機變量，邊表示隨機變量之間關(guān)系（加權(quán)概率），如果聯(lián)合概率分布P（Y）滿足成對/局部/全局馬爾科夫性，就稱此聯(lián)合為概率無向圖模型或者馬爾科夫隨機場。 4 計算聯(lián)合概率分布：概率無向圖模型的因子分解
對給定概率無向圖模型下，本質(zhì)就是要求聯(lián)合概率可以將其改變成若干子聯(lián)合概率乘積的形式，也就是將聯(lián)合概率進行因子分解。首先介紹兩個概念：團與最大團。 ? 團：無向圖G中任何兩個結(jié)點均有邊連接的節(jié)點子集成為團。 最大團：若C是無向圖G的一個團，并且不能再加進任何一個G的節(jié)點使其成為一個更大的團，則稱此C為最大團。 注意：{y1,y2,y3,y4}不是一個團，因為y1與y4無邊相連 概率無向圖模型的因子分解： 將概率無向圖模型的聯(lián)合概率分布表示，其最大團上的隨機變量的函數(shù)的乘積形式的操作，即 的聯(lián)合概率是 ?這樣不免太復雜，倘若 為10000個結(jié)點以上呢？（每個結(jié)點是一個漢字，假設(shè)最大團以是篇章，本書假設(shè)10章，則是十個最大團之積。） 概率無向圖模型的聯(lián)合概率分布P(Y)的公式化表示： 給定概率無向圖模型，設(shè)其無向圖為G，C為G上的最大團，YC表示C對應的隨機變量。那么概率無向圖模型的聯(lián)合概率分布P(Y)可寫作圖中所有最大團C上的函數(shù)ΨC(YC)的乘積形式，即： ?其中， 為勢函數(shù)，C為最大團，Z是規(guī)范化因子 規(guī)范化因子保證P(Y)構(gòu)成一個概率分布。 因為要求勢函數(shù)ΨC(YC)是嚴格正的，于是通常定義為指數(shù)函數(shù)： ? 5?參考文獻
【1】?數(shù)學之美?吳軍?著 【2】?機器學習??周志華?著 【3】?統(tǒng)計自然語言處理 宗成慶 著（第二版） 【4】?統(tǒng)計學習方法（191---208） 李航 【5】?知乎?網(wǎng)絡(luò)資源 6?自然語言相關(guān)系列文章
【自然語言處理】：【NLP】揭秘馬爾可夫模型神秘面紗系列文章 【自然語言處理】：【NLP】大數(shù)據(jù)之行，始于足下：談談語料庫知多少 【自然語言處理】：【NLP】驀然回首：談談學習模型的評估系列文章 【自然語言處理】：【NLP】快速了解什么是自然語言處理 【自然語言處理】：【NLP】自然語言處理在現(xiàn)實生活中運用 聲明：關(guān)于此文各個篇章，本人采取梳理扼要，順暢通明的寫作手法。系統(tǒng)閱讀相關(guān)書目和資料總結(jié)梳理而成，旨在技術(shù)分享，知識沉淀。在此感謝原著無私的將其匯聚成書，才得以引薦學習之用。其次，本人水平有限，權(quán)作知識理解積累之用，難免主觀理解不當，造成讀者不便，基于此類情況，望讀者留言反饋，便于及時更正。本文原創(chuàng)，轉(zhuǎn)載請注明出處：前戲：一起走進條件隨機場。? http://www.cnblogs.com/baiboy 【摘要】：條件隨機場用于序列標注，數(shù)據(jù)分割等自然語言處理中，表現(xiàn)出很好的效果。在中文分詞、中文人名識別和歧義消解等任務中都有應用。本文源于筆者做語句識別序列標注過程中，對條件隨機場的了解，逐步研究基于自然語言處理方面的應用。成文主要源于自然語言處理、機器學習、統(tǒng)計學習方法和部分網(wǎng)上資料對CRF介紹的相關(guān)的相關(guān)，最后進行大量研究整理匯總成體系知識。文章布局如下：第一節(jié)介紹CRF相關(guān)的基礎(chǔ)統(tǒng)計知識；第二節(jié)介紹基于自然語言角度的CRF介紹；第三節(jié)基于機器學習角度對CRF介紹，第四節(jié)基于統(tǒng)計學習角度對相關(guān)知識介紹；第五節(jié)對統(tǒng)計學習深度介紹CRF，可以作為了解內(nèi)容。（本文原創(chuàng)，轉(zhuǎn)載請注明出處：基于自然語言處理角度談談CRF。) 目錄
【自然語言處理：漫步條件隨機場系列文章（一）】：前戲：一起走進條件隨機場 【自然語言處理：漫步條件隨機場系列文章（二）】：基于自然語言處理角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（三）】：基于機器學習角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（四）】：基于統(tǒng)計學習角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（五）】：條件隨機場知識擴展 1 條件隨機場（Condition Random Fields），簡稱CRFs
條件隨機場概念：條件隨機場就是對給定的輸出標識序列Y和觀察序列X，條件隨機場通過定義條件概率P(X|Y)，而不是聯(lián)合概率分布P(X,Y)來描述模型。 概念解析： 標注一篇文章中的句子，即語句標注，使用標注方法BIO標注，B代表句子的開始，I代表句子中間，O代表句子結(jié)束。則觀察序列X就是一個語料庫（此處假設(shè)一篇文章，x代表文章中的每一句，X是x的集合），標識序列Y是BIO，即對應X序列的識別，從而可以根據(jù)條件概率P(標注|句子)，推測出正確的句子標注，顯然，這里針對的是序列狀態(tài)，即CRF是用來標注或劃分序列結(jié)構(gòu)數(shù)據(jù)的概率化結(jié)構(gòu)模型，其在自然語言處理和圖像處理領(lǐng)域得到廣泛的應用，CRF可以看作無向圖模型或者馬爾科夫隨機場。 2 條件隨機場的形式化表示
?設(shè)G=(V,E)為一個無向圖，V為結(jié)點的集合，E為無向邊的集合， ，即V中的每個結(jié)點對應一個隨機變量Yv，其取值范圍為可能的標記集合{Y}.如果觀察序列X為條件，每一個隨機變量 都滿足以下馬爾科夫特性: ，其中，w – v表示兩個結(jié)點在圖G中是鄰近結(jié)點，那么，（X,Y）為條件隨機變量。 以語句識別的案例理解條件隨機場的形式化表示。 ?G=（V,E表示識別語句：【我愛中國】的標注是一個無向圖，X我觀察序列，Y為標注序列，V是每個標注狀態(tài)的結(jié)點，E的無向邊，邊上的權(quán)值為概率值。 表示每個X的Y的標注，如:X1:我，y1：O，y2：I，y3：B；取值范圍 ，而 中w—v表示我與愛是相鄰的結(jié)點，這樣的（X,Y）為一個條件隨機場，真正的標注再采用Viterbi算法，如： 尋求最大概率即 ，記錄下我的標注路徑，同理可知： ? 如上便是對條件隨機場與Viterbi算法的綜合運用，其中Viterbi標注問題本質(zhì)是隱馬爾科夫模型三大問題之解碼問題算法模型，具體參考（揭秘馬爾科夫模型系列文章） 3 深度理解條件隨機場
理論上標記序列描述一定條件的獨立性，G圖結(jié)構(gòu)任意的，對序列進行建模可形成最簡單，最普通的鏈式結(jié)構(gòu)圖，結(jié)點對應標記序列X中元素，CRF鏈式圖如下： ? 如上圖兩種表示是一致的，其中圖鏈式句子標注是圖鏈式2的實例化，讀者可能問為什么上面圖是這種而不是廣義的圖，這是因為觀察序列X的元素之間并不存在圖結(jié)構(gòu)，沒有做獨立性假設(shè)，這點也非常容易理解，諸如圖中，我愛中國，其中b表示反射概率而t是轉(zhuǎn)移概率，線上的數(shù)值表示權(quán)值即概率值。如圖3，我的發(fā)射概率0.7，我到愛的轉(zhuǎn)移概率0.5，通俗講，我和愛兩個字是有關(guān)聯(lián)的，并非獨立的。 4 公式化表示條件隨機場
在給定的觀察序列X時，某個待定標記序列Y的概率可以定義為 其中 是轉(zhuǎn)移概率， 是狀態(tài)函數(shù)，表示觀察序列X其中i的位置的標記概率， 和 分別是t和s的權(quán)重，需要從訓練樣本中估計出來。 實例解析： 我愛中國，其中x2是愛字， 表示在觀察狀態(tài)2中，我到愛的轉(zhuǎn)移概率，其中j∈{B,I,O}，可知 的生成概率或者發(fā)射概率的特征函數(shù).觀察序列{0,1}二值特征b（x,i）來表示訓練樣本中某些分布特征，其中采用{0,1}二值特征即符合條件標為1，反之為0； 為了便于描述，可以將狀態(tài)函數(shù)書寫以下形式： ?
特征函數(shù)： ? 其中每個局部 特征表示狀態(tài)特征， 或者專業(yè)函數(shù) ，由此條件隨機場的定義條件概率如下： ， 其中分母為歸一化因子： ? 5?本節(jié)總結(jié)
條件隨機場模型也需要解決三個基本問題：特征的選擇，參數(shù)訓練和解碼。其中參數(shù)訓練過程在訓練數(shù)據(jù)集上基于對數(shù)似然函數(shù)最大化進行。 CRF優(yōu)點：相對于HMM，CRF主要優(yōu)點是它的條件隨機性，只需要考慮當前出現(xiàn)的觀察狀態(tài)的特性，沒有獨立性嚴格要求，CRF具有MEMM一切優(yōu)點。 CRF與MEMM區(qū)別: MEMM：使用每一個狀態(tài)的指數(shù)模型來計算給定前一個狀態(tài)下當前狀態(tài)的條件概率。 CRF：用單個指數(shù)模型計算給定觀察序列與整個標記序列聯(lián)合概率。 《統(tǒng)計自然語言處理》P128頁有關(guān)于隨機場模型的實現(xiàn)工具。 ?? 6 參考文獻
【1】?數(shù)學之美?吳軍?著 【2】?機器學習??周志華?著 【3】?統(tǒng)計自然語言處理 宗成慶 著（第二版） 【4】?統(tǒng)計學習方法（191---208） 李航 【5】?知乎?網(wǎng)絡(luò)資源 7?自然語言相關(guān)系列文章
【自然語言處理】：【NLP】揭秘馬爾可夫模型神秘面紗系列文章 【自然語言處理】：【NLP】大數(shù)據(jù)之行，始于足下：談談語料庫知多少 【自然語言處理】：【NLP】驀然回首：談談學習模型的評估系列文章 【自然語言處理】：【NLP】快速了解什么是自然語言處理 【自然語言處理】：【NLP】自然語言處理在現(xiàn)實生活中運用 聲明：關(guān)于此文各個篇章，本人采取梳理扼要，順暢通明的寫作手法。系統(tǒng)閱讀相關(guān)書目和資料總結(jié)梳理而成，旨在技術(shù)分享，知識沉淀。在此感謝原著無私的將其匯聚成書，才得以引薦學習之用。其次，本人水平有限，權(quán)作知識理解積累之用，難免主觀理解不當，造成讀者不便，基于此類情況，望讀者留言反饋，便于及時更正。本文原創(chuàng)，轉(zhuǎn)載請注明出處：基于自然語言處理角度談談CRF。? 1 條件隨機場（可以看作給定觀察值的馬爾科隨機場）
CRF是一種判別式無向圖模型 CRF試圖對多個變量在給定觀測值后的條件概率進行建模，具體來說，若令 為觀察序列， 為與之對應的標記序列，則CRF的目標是構(gòu)建條件概率模型P(Y|X)。 注意：標記變量y是結(jié)構(gòu)型變量，如在自然語言處理的句子標注任務中，觀測數(shù)據(jù)為句子，標記為相應的詞性序列，具有線性序列結(jié)構(gòu)，在語法分析中，輸出標記是語法樹，具有樹形結(jié)構(gòu)。
令G=<V，E>表示結(jié)點與標記變量y中元素一一對應的無向圖， 表示與結(jié)點v對應標記變量，n（v）表示結(jié)點v的領(lǐng)結(jié)點，若圖G的每一個變量 都滿足馬爾科夫性，即 ? ，則（y，x）構(gòu)成一個CRF。 上面形式化在第二章已經(jīng)通過實例解析介紹過。 2 鏈式條件隨機場
如上面句子標注，因為現(xiàn)象應用中，對標記序列建模時，常有鏈式結(jié)構(gòu)（具體鏈式結(jié)構(gòu)前面有介紹） 與馬爾科夫隨機場定義聯(lián)合概率概率的方式類似，CRF使用勢函數(shù)和圖結(jié)構(gòu)上的團來定義條件概率P(y|x)給定觀察序列X，所謂團即單個標記變量{}以及相鄰標記變量 選擇合適的勢函數(shù)，即形如： 的條件概率定義，其中 與Q對應的勢函數(shù)， 為規(guī)范因子，實際中，往往Z不需要獲得精確值。 在CRF中，通過選用勢函數(shù)并引入特征函數(shù)，條件概率定義如下： 如上參數(shù)在第二章有詳細講解。 特征函數(shù)： 句子標注為例的轉(zhuǎn)移特征函數(shù) 表示第i個觀察值為“愛”時，相對的標記分別是B，I，其狀態(tài)特征函數(shù)如下： ? 表示觀察值x為單字“愛”時，它對應的標注很可能為I 3?參考文獻
【1】?數(shù)學之美?吳軍?著 【2】?機器學習??周志華?著 【3】?統(tǒng)計自然語言處理 宗成慶 著（第二版） 【4】?統(tǒng)計學習方法（191---208） 李航 【5】?知乎?網(wǎng)絡(luò)資源 4?自然語言相關(guān)系列文章
【自然語言處理】：【NLP】揭秘馬爾可夫模型神秘面紗系列文章 【自然語言處理】：【NLP】大數(shù)據(jù)之行，始于足下：談談語料庫知多少 【自然語言處理】：【NLP】驀然回首：談談學習模型的評估系列文章 【自然語言處理】：【NLP】快速了解什么是自然語言處理 【自然語言處理】：【NLP】自然語言處理在現(xiàn)實生活中運用 聲明：關(guān)于此文各個篇章，本人采取梳理扼要，順暢通明的寫作手法。系統(tǒng)閱讀相關(guān)書目和資料總結(jié)梳理而成，旨在技術(shù)分享，知識沉淀。在此感謝原著無私的將其匯聚成書，才得以引薦學習之用。其次，本人水平有限，權(quán)作知識理解積累之用，難免主觀理解不當，造成讀者不便，基于此類情況，望讀者留言反饋，便于及時更正。本文原創(chuàng)，轉(zhuǎn)載請注明出處：基于機器學習角度談談CRF。? http://www.cnblogs.com/baiboy 分類:?NLP 【摘要】：條件隨機場用于序列標注，數(shù)據(jù)分割等自然語言處理中，表現(xiàn)出很好的效果。在中文分詞、中文人名識別和歧義消解等任務中都有應用。本文源于筆者做語句識別序列標注過程中，對條件隨機場的了解，逐步研究基于自然語言處理方面的應用。成文主要源于自然語言處理、機器學習、統(tǒng)計學習方法和部分網(wǎng)上資料對CRF介紹的相關(guān)的相關(guān)，最后進行大量研究整理匯總成體系知識。文章布局如下：第一節(jié)介紹CRF相關(guān)的基礎(chǔ)統(tǒng)計知識；第二節(jié)介紹基于自然語言角度的CRF介紹；第三節(jié)基于機器學習角度對CRF介紹，第四節(jié)基于統(tǒng)計學習角度對相關(guān)知識介紹；第五節(jié)對統(tǒng)計學習深度介紹CRF，可以作為了解內(nèi)容。（本文原創(chuàng)，轉(zhuǎn)載請注明出處：基于統(tǒng)計學習方法角度談談CRF。) 目錄
【自然語言處理：漫步條件隨機場系列文章（一）】：前戲：一起走進條件隨機場 【自然語言處理：漫步條件隨機場系列文章（二）】：基于自然語言處理角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（三）】：基于機器學習角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（四）】：基于統(tǒng)計學習角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（五）】：條件隨機場知識擴展 引子
條件隨機場（CRF）：是給定一組輸入隨機變量條件下，另一組輸出隨機變量的條件概率分布模型，其特點是假設(shè)輸出隨機變量構(gòu)成馬爾科夫隨機場，條件隨機場可用于不同預測問題，由輸入序列對輸出序列預測的判別式模型，形式為對數(shù)線性模型，其學習方法通常是極大似然估計。 1 條件隨機場(CRF)的定義與形式
簡單的說，條件隨機場(CRF)類似于MRF，只不過CRF比MRF多了一個觀察集合，或者說，CRF本質(zhì)上就是給定了觀察值集合的MRF。 條件隨機場：設(shè)G=(V,E)是一個無向圖，Y={Yv|v∈V}是以G中節(jié)點v為索引的隨機變量Yv構(gòu)成的集合。在給定X的條件下，如果每個隨機變量Yv服從馬爾可夫性，即 ，則條件概率分布P(Y|X)就是一個條件隨機場。上式中的w ~ v表示在圖G=(V, E)中與節(jié)點v有邊連接的所有節(jié)點，w≠v表示v以外的所有節(jié)點，Yv,Yu, Yw為w對節(jié)點v，u，w對應的隨機變量。 線性鏈條件隨機場：?? 設(shè)X = (X1, X2,..., Xn), Y = (Y1, Y2, ..., Yn)均為線性鏈表示的隨機變量序列，若在給定隨機變量序列X的條件下，隨機變量序列Y的條件概率分布P(Y|X)構(gòu)成條件隨機場，即滿足馬爾可夫性(見本文最開始的“模型定義”部分)： P(Yi| X, Y1, ..., Yi-1, Yi+1, ...., Yn)= P(Yi?| X, Yi-1, Yi+1)??i= 1, 2, ..., n (在i=1和n時只考慮單邊)，則稱P(Y|X)為線性鏈條件隨機場。 注意：在標注問題中，X表示輸入觀測序列，Y表示對應的輸出標記序列或狀態(tài)序列。 2 條件隨機場的參數(shù)化形式
P(Y|X)為線性鏈條件隨機場，則在隨機變量X取值為x的條件下，隨機變量Y取值為y的條件概率具有如下形式： ? 其中， 式中，tk和sl是特征函數(shù)，λk和μl是對應的權(quán)值。Z(x)是規(guī)范化因子，求和時在所有可能的輸出序列上進行的。 通常：特征函數(shù)t和s取值是1或0，當滿足特征條件取值1，反之取值0，條件隨機場完全由特征函數(shù)t，s和對應的數(shù)值λ，μ確定。 注意：線性CRF也是對數(shù)性模型。 實例解析： 設(shè)有一個天氣預測問題：輸入觀察序列（連續(xù)三天的天氣情況）為X = (X1, X2, X3)，輸出標記序列（每天對應天氣熱冷的預測）為 Y = (Y1, Y2, Y3)， Y1, Y2, Y3 的取值于y= {H, C},其中H表示天熱，C表示天冷。假設(shè)特征tk,sl和對應的權(quán)值λk，μl如下： 其中，上式代表著特征值為H的條件，即：yi-1= H, yi=C, x, i = 2, 3 時特征值取1。而特征值取0的條件被省略了。 PS：如果寫全的話是這樣： 于是對給定的觀測序列x，求標記序列為y =(y1, y2, y3) = (H, C, C),即第一天熱，第二天第三天連續(xù)冷的非規(guī)范化條件概率（即沒有除以規(guī)范化因子的條件概率） 實例分析： 由以上問題可知，觀察序列是天數(shù)的集合，標記序列是對應天氣熱冷的集合，由此分析顯然是隨機條件場的編碼問題，基于隨機條件場，可以將上述情形轉(zhuǎn)換為圖形化形式分析，然后進行模型構(gòu)建，算法實現(xiàn)，算法優(yōu)化和結(jié)果分析即可。本節(jié)重點實現(xiàn)分析，圖形表示，模型構(gòu)建。 天氣預測問題轉(zhuǎn)化為圖形表示如下： 如圖所示，橫坐標x1，x2，x3分別對應天，是觀察序列具備時序性，縱坐標是標記序列即可能隱藏的所有標記情況，start和end表示開始和結(jié)束狀態(tài)（這點參照筆者Viterbi算法一節(jié)的介紹），其中t表示轉(zhuǎn)移概率，t=0.5有具體權(quán)值的，標注轉(zhuǎn)移概率是50%機會。X對應的s表示發(fā)射概率或者生產(chǎn)概率，顯然，如上滿足條件隨機場，回顧下條件隨機場模型，線性鏈條件隨機場模型為： 于是對給定的觀測序列x，標記序列y=(H,C,C)的非規(guī)范化條件概率為 上式數(shù)值計算，參照已知條件和圖形分析，很容易計算，這里具體計算過程省略。 3 條件隨機場的簡化形式
將局部特征轉(zhuǎn)化為一個全局特征函數(shù)，可將CRF寫成權(quán)值向量和特征向量的內(nèi)積形式即是條件隨機場的簡化形式，具體參見如下筆記： ①?將轉(zhuǎn)移特征和狀態(tài)特征以及其數(shù)值用統(tǒng)一符號表示，設(shè)有K1個轉(zhuǎn)移貼紙，K2個狀態(tài)特征，K=K1+K2，記： ②?對轉(zhuǎn)移狀態(tài)各個位置i求和，記作： ③?用wk表示特征fk(y,x)的權(quán)值，即： ??????????? ④?于是，條件隨機場可表示為 ??????????????????????? ⑤?以w表示權(quán)值向量，即 ?????????????????????? ⑥?以F(y, x)表示全局特征向量，即 ?????????????????? 則條件隨機場可以寫成向量w與F(y, x)的內(nèi)積的形勢： ? 4 條件隨機場預測算法
?形式化描述： 條件隨機場的預測問題是給定義條件隨機場P(Y|X)和輸入序列(觀測序列)x，求條件概率最大的輸出序列(標記序列)y*，即對觀測序列進行標注。 條件隨機場的預測算法是著名的維特比算法。 你對維特比算法是什么就有概念了吧，下面來看看其數(shù)學描述。維特比算法不做深入講解，如果讀者還不清楚，參考本人系列文章之揭秘馬爾科夫模型系統(tǒng)文章，有專門章節(jié)詳細介紹viterbi算法。 ???? 這里，路徑表示標記序列，其中 ??????????? 注意，這時只需計算非規(guī)范化概率，而不必計算概論，可以大大提高效率。 為了求解最優(yōu)路徑，將式寫成如下形式： ???????????? 其中 ???????????????? 就是局部特征向量。 下面敘述維特比算法。 實例解析 用維特比算法求給定的輸入序列(觀測序列)x對應的輸出序列(標記序列)y* = (y1*, y2*, y3*)； 解析： 1)第一步初始化：因為y1=1和y1=2是最初，所以就不用考慮轉(zhuǎn)移的情況了(實際上也沒有“表達從y0轉(zhuǎn)移到y(tǒng)1的情況”的t函數(shù)(轉(zhuǎn)移函數(shù)))，直接從狀態(tài)函數(shù)(s函數(shù)中找)，發(fā)現(xiàn)，s1和s2分別對應y1=1和y1=2，說明y1=1和y1=2這個狀態(tài)都是存在的，而s1和s2的權(quán)值分別是1和0.5，且上面列出的s函數(shù)們和t函數(shù)們值都為1，所以y1=1和y2=1的可能性分別是1和0.5。所以，到達y1的非規(guī)范化概率最大值為：δ1(1) = 1，δ1(2) = 0.5。 2)第二步遞推：i=2(達第二處目的地集合{y2=1, y2=2})：首先是路線(僅說明到達y2=1的情況)： 上圖可知，到達y2=1的路線有如下幾條： ?路線1：從y1=1出發(fā) ----(經(jīng)過t2)---->到達y2=1； ?路線2：從y1=2出發(fā) ----(經(jīng)過t4)---->到達y2=1； ?接著是狀態(tài)(僅說明到達y2=1的情況)： 根據(jù)題目可知：i=2時的狀態(tài)函數(shù)只有s2和s3，而y2=1對應的函數(shù)是s3 所以到達y2=1的非規(guī)范化概率最大值為：δ2(1) = max{1+λ2t2?+ u3s3,0.5 + λ4t4?+ u3s3}= 2.4 非規(guī)范化概率最大值的路徑為：?ψ2(1) = 1 δ2(2)同理。 i=3也一樣（只不過對于δ3(1)中的u5s5，我認為應該是u3s3，先不說s3對應的是y3=1的情況，而且原題中根本沒有s5函數(shù)）。 3)第三步終止：這步就簡單了，在δ3(l)中δ3(1) = 4.3最大，所以y3中取1的可能性最大，即y3*=1。 4)第四步返回：然后反著推： 從y2的哪個值到y(tǒng)3可能性最大呢？在第二部已經(jīng)解出：ψ3(1) = 2，即y2到達y3=1的路線中權(quán)值最大的是y2=2，即y2*=2。 同理，從y1=1到y(tǒng)2=2的可能性最大，即y1*=1。 5)就得到標記序列:*= (y1*, y2*, y3*)= (1, 2, 1) 5?參考文獻
【1】?數(shù)學之美?吳軍?著 【2】?機器學習??周志華?著 【3】?統(tǒng)計自然語言處理 宗成慶 著（第二版） 【4】?統(tǒng)計學習方法（191---208） 李航 【5】?知乎?網(wǎng)絡(luò)資源 6?自然語言相關(guān)系列文章
【自然語言處理】：【NLP】揭秘馬爾可夫模型神秘面紗系列文章 【自然語言處理】：【NLP】大數(shù)據(jù)之行，始于足下：談談語料庫知多少 【自然語言處理】：【NLP】驀然回首：談談學習模型的評估系列文章 【自然語言處理】：【NLP】快速了解什么是自然語言處理 【自然語言處理】：【NLP】自然語言處理在現(xiàn)實生活中運用 聲明：關(guān)于此文各個篇章，本人采取梳理扼要，順暢通明的寫作手法。系統(tǒng)閱讀相關(guān)書目和資料總結(jié)梳理而成，旨在技術(shù)分享，知識沉淀。在此感謝原著無私的將其匯聚成書，才得以引薦學習之用。其次，本人水平有限，權(quán)作知識理解積累之用，難免主觀理解不當，造成讀者不便，基于此類情況，望讀者留言反饋，便于及時更正。本文原創(chuàng)，轉(zhuǎn)載請注明出處：基于統(tǒng)計學習方法角度談談CRF。? http://www.cnblogs.com/baiboy 好文要頂?關(guān)注我?收藏該文? ? 伏草惟存 關(guān)注 - 6 粉絲 - 263 +加關(guān)注 0 0 ??上一篇：【NLP】基于機器學習角度談談CRF（三） ??下一篇：【NLP】條件隨機場知識擴展延伸（五） posted @?2016-08-03 10:35?伏草惟存?閱讀(212) 評論(0)?編輯?收藏 1 隨機場的矩陣形式
矩陣表示形式前提條件：假設(shè)P（y|x）是線性鏈條件隨機場，給定觀測序列x，相應的標記序列y的條件概率。引進特殊的起點和終點狀態(tài)標記y0?= start，yn+1?= stop，這時Pw(y|x) 可以通過矩陣形式表示。（實際上，特殊點的引用大家都有接觸，諸如學習隱含馬爾科夫模型中向前算法解決了似然度問題，viterbi算法解決解碼問題，向前向后算法解決學習參數(shù)。） 對觀測序列x的每一個位置i=1, 2,..., n+1，定義一個m階矩陣(m是標記yi取值的個數(shù)) ????????????????????????????????? 這樣給定觀測序列x，標記序列y的非規(guī)范化概率可以通過n+1個矩陣的乘積 ?????????????? 表示。于是，條件概率Pw(y|x)是 ? 中，Zw(x)為規(guī)范化因子，是n+1個矩陣的乘積的(start,stop)元素： 注意，y0= start，yn+1?= stop表示開始狀態(tài)與終止狀態(tài)，規(guī)范化因子Zw(x)是以start為起點stop為重點通過狀態(tài)的所有路徑y(tǒng)1y2...yn的非規(guī)范化概率 ?????????? 之和。 下面通過一個例子來說明“范化因子Zw(x)是以start為起點stop為重點通過狀態(tài)的所有路徑y(tǒng)1y2...yn的非規(guī)范化概率之和”這個事實 實例解析 ?????????????? 給定一個如上圖所示的線性鏈條件隨機場，觀測序列x，狀態(tài)序列y，i=1,2,3，n=3，標記yi∈{1,2}，假設(shè)y0=start=1，y4=stop=1，各個位置的隨機矩陣M1(x)，M2(x)，M3(x)，M4(x)分別是 ?????????????? 試求狀態(tài)序列y以start為起點stop為終點所有路徑的非規(guī)范化概率及規(guī)范化因子。 實例解答： 從start到stop對應于y=(1,1,1),y=(1,1,2), ..., y=(2,2,2)個路徑的非規(guī)范化概率分別是： ??????????????????????????? a01b11c11，a01b11c12，a01b12c21，a01b12c22 ??????????????????????????? a02b21c11，a01b21c12，a02b22c21，a02b22c22 然后按式11.12求規(guī)范化因子，通過計算矩陣乘積M1(x) M2(x) M3(x) M4(x)可知，其第一行第一列的元素為a01b11c11+ a01b11c12?+ a01b12c21+ a01b12c22+a02b21c11?+ a01b21c12+ a02b22c21?+ a02b22c22，恰好等于從start到stop的所有路徑的非規(guī)范化概率之和，即規(guī)范化因子Z(x)。 在之前的介紹中我們已近知道，條件隨機場的概率計算問題是給定條件隨機場P(Y|X)，輸入序列x和輸出序列y，計算條件概率P(Yi=yi?| x)，P(Yi-1?=yi-1, Yi=yi?| x)以及相應數(shù)學期望的問題。為了方便起見，像隱馬爾可夫模型那樣，引進前向-后向向量，遞歸的計算以上概率及期望值。這樣的算法稱為前向-后向算法。 2 前向-后向算法
對每個指標i =0,1,...,n+1，定義前向向量ai(x)： ???? 遞推公式為 ?????????? 又可表示為 ??????? ai(yi|x)表示在位置i的標記是yi并且到位置i的前部分標記序列的非規(guī)范化概率，若yi可取的值有m個，那ai(x)就是m維的列向量。同樣，對每個指標i =0,1,...,n+1，定義后向向量βi(x)： ???????????? 又可表示為 ??????????????? βi(yi|x)表示在位置i的標記為yi并且從i+1到n的后部分標記序列的非規(guī)范化的概率。 由前向-后向定義不難得到： ??????????? 這里，若ai(x)是m維的列向量，那1就是元素均為1的m維列向量。 概率計算 按照前向-后向向量的定義，很容易計算標記序列在位置i是標記yi的條件概率和在位置i-1與i是標記yi-1和yi的條件概率： 其中，?? Z(x)= anT(x)·1 ?期望值計算 利用前向-后向向量，可以計算特征函數(shù)關(guān)于聯(lián)合分布P(X, Y)和條件分布P(Y | X)的數(shù)學期望。特征函數(shù)fk關(guān)于條件分布P(Y |X)的數(shù)學期望是 其中，Z(x)= anT(x)·1 則特征函數(shù)fk關(guān)于聯(lián)合分布P(X, Y)的數(shù)學期望是 ???? 其中，?Z(x)= anT(x)·1 特征函數(shù)數(shù)學期望的一般計算公式。對于轉(zhuǎn)移貼紙tk(yi-1, yi, x, i)，k=1,2,...,K1，可以將式中的fk換成tk；對于狀態(tài)特征，可以將式中的fk換成si，表示sl(yi, x, i)，k = K1?+1，l = 1,2,...,K2。有了式11.32 ~11.35，對于給定的觀測序列x和標記序列y，可以通過一次前向掃描計算ai及Z(x)，通過一次后向掃描計算βi，從而計算所有的概率和特征的期望。 ?3 CRF的學習算法
條件隨機場模型實際上是定義在時序數(shù)據(jù)上的對數(shù)線性模型，其學習方法包括極大似然估計和正則化的極大似然估計。 具體的優(yōu)化實現(xiàn)算法有改進的迭代尺度法IIS、梯度下降法以及擬牛頓法。 1）進的迭代尺度法(IIS) 已知訓練數(shù)據(jù)集，由此可知經(jīng)驗概率分布 ?? 可以通過極大化訓練數(shù)據(jù)的對數(shù)似然函數(shù)來求模型參數(shù)。訓練數(shù)據(jù)的對數(shù)似然函數(shù)為 ?? 當Pw是一個由 給出的條件隨機場模型時，對數(shù)似然函數(shù)為 ?????????????? IIS通過迭代的方法不斷優(yōu)化對數(shù)似然函數(shù)改變量的下界，達到極大化對數(shù)似然函數(shù)的目的。 假設(shè)模型的當前參數(shù)向量為w=(w1,w2, ..., wK)T，向量的增量為δ=(δ1,δ2, ..., δK)T，更新參數(shù)向量為w +δ=(w1+δ1, w2?+δ2, ..., wk+δk)T。在每步迭代過程中，IIS通過一次求解下面的11.36和11.37，得到δ=(δ1,δ2, ..., δK)T。關(guān)于轉(zhuǎn)移特征tk的更新方程為： 關(guān)于狀態(tài)特征sl的更新方程為： 這里T(x, y)是在數(shù)據(jù)(x, y)中出現(xiàn)所有特征數(shù)的綜合： ????????? 于是算法整理如下。 算法：條件隨機場模型學習的改進的迭代尺度法 輸入：特征函數(shù)t1,t2, ..., tK1，s1, s2, ..., sK2；經(jīng)驗分布 輸出：參數(shù)估計值? ；模型 。 過程： 2）擬牛頓法 對于條件隨機場模型 ? 學習的優(yōu)化目標函數(shù)是 其梯度函數(shù)是 ? 擬牛頓法的BFGS算法如下：算法：條件隨機場模型學習的BFGS算法 4?基于條件隨機場CRF的中文命名實體識別效率如何？
【知乎】北京航空航天大學 計算機專業(yè)博士在讀33?人贊同 大致命名實體識別的方法可以可以分為四個大類型： 有監(jiān)督學習方法： HMM?http://www.nlpr.labs.gov.cn/2005papers/gjhy/gh71.pdf SVM?Biomedical named entity recognition using two-phase model based on SVMs CRF?http://psb.stanford.edu/psb11/conference-materials/proceedings%201996-2010/psb08/leaman.pdf 當然還有決策樹最大熵等方法。基本每個模型都會在這個問題上試一遍的。 無監(jiān)督學習方法：Unsupervised named-entity extraction from the Web: An experimental study 半監(jiān)督學習方法：Minimally-supervised extraction of entities from text advertisements 混合方法：多種模型結(jié)合?Recognizing named entities in tweets 主要介紹三種主流算法，CRF，字典法和混合方法。 CRF： 用過CRF的都知道，CRF是一個序列標注模型，指的是把一個詞序列的每個詞打上一個標記。一般通過，在詞的左右開一個小窗口，根據(jù)窗口里面的詞，和待標注詞語來實現(xiàn)特征模板的提取。最后通過特征的組合決定需要打的tag是什么。 而在CRF for Chinese NER這個任務中，提取的特征大多是該詞是否為中國人名姓氏用字，該詞是否為中國人名名字用字之類的，True or false的特征。所以一個可靠的百家姓的表就十分重要啦~在國內(nèi)學者做的諸多實驗中，效果最好的人名可以F1測度達到90%，最差的機構(gòu)名達到85%。 基于條件隨機場的中文命名實體識別特征比較研究--《第四屆全國信息檢索與內(nèi)容安全學術(shù)會議論文集（上）》2008年 字典法： 字典法需要掌握的是一種快速搜索算法trie-tree，我相信很多人應該對這個算法已經(jīng)有所了解。在NER中就是把每個字都當開頭的字放到trie-tree中查一遍，查到了就是NE。中文的trie-tree需要進行哈希，因為中文字符太多了，不像英文就26個。 混合法： 對六類不同的命名實體采取不一樣的手段進行處理，例如對于人名，進行字級別的條件概率計算。 例如我們需要算 其中Sur代表中國人姓氏，Dgb代表中國人名首字，Dge代表中國人名尾字。 而機構(gòu)則在詞級別進行此概率計算。 我知道的系統(tǒng)有： 中文 1、哈工大?語言云（語言技術(shù)平臺云 LTP-Cloud） 2、上海交大?趙海 主頁 分詞 自然語言 計算語言學 機器學習 英文： Stanford NER BANNER（生物醫(yī)學） Minor Third 5 條件隨機場（crf）是否可以將分類問題都當作序列標注問題解決？
【知乎】標注看上去好像就是在序列上做分類。 然而實際上標注跟分類最大的區(qū)別就是：標注采的特征里面有上下文分類結(jié)果，這個結(jié)果你是不知道的，他在“分類”的時候是跟上下文一起"分類的"。因為你要確定這個詞的分類得先知道上一個詞的分類，所以這個得整句話的所有詞一起解，沒法一個詞一個詞解。 而分類是根據(jù)當前特征確定當前類別，分類的時候不需要考慮上下文的分類結(jié)果，但可以引入上下文的特征。 比如說命名實體識別，你采的特征如果是：{當前詞，當前詞性，當前詞語義角色，上一個詞，上一個詞的詞性} 那這樣跟分類沒有什么區(qū)別。如果你采的特征是：{當前詞，當前詞性，當前詞語義角色，上一個詞，上一個詞的標簽，上一個詞的詞性}
【自然語言處理：漫步條件隨機場系列文章（一）】：前戲：一起走進條件隨機場 【自然語言處理：漫步條件隨機場系列文章（二）】：基于自然語言處理角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（三）】：基于機器學習角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（四）】：基于統(tǒng)計學習角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（五）】：條件隨機場知識擴展 1 機器學習中的生產(chǎn)模型與判別模型
生產(chǎn)式模型與判別式模型簡述，條件隨機場是哪種模型？ 有監(jiān)督機器學習方法可以分為生成方法和判別方法： 1）生產(chǎn)式模型：直接對聯(lián)合分布進行建模，如：混合高斯模型、隱馬爾科夫模型、馬爾科夫隨機場等 2）判別式模型：對條件分布進行建模，如：條件隨機場、支持向量機、邏輯回歸等。 生成模型優(yōu)缺點介紹： 優(yōu)點： 1）生成給出的是聯(lián)合分布，不僅能夠由聯(lián)合分布計算條件分布（反之則不行），還可以給出其他信息。如果一個輸入樣本的邊緣分布很小的話，那么可以認為學習出的這個模型可能不太適合對這個樣本進行分類，分類效果可能會不好。 2）生成模型收斂速度比較快，即當樣本數(shù)量較多時，生成模型能更快地收斂于真實模型。 3）生成模型能夠應付存在隱變量的情況，比如混合高斯模型就是含有隱變量的生成方法。 缺點： 1）天下沒有免費午餐，聯(lián)合分布是能提供更多的信息，但也需要更多的樣本和更多計算，尤其是為了更準確估計類別條件分布，需要增加樣本的數(shù)目，而且類別條件概率的許多信息是我們做分類用不到，因而如果我們只需要做分類任務，就浪費了計算資源。 2）另外，實踐中多數(shù)情況下判別模型效果更好。 判別模型優(yōu)缺點介紹： 優(yōu)點： 1）與生成模型缺點對應，首先是節(jié)省計算資源，另外，需要的樣本數(shù)量也少于生成模型。 2）準確率往往較生成模型高。 3）由于直接學習，而不需要求解類別條件概率，所以允許我們對輸入進行抽象（比如降維、構(gòu)造等），從而能夠簡化學習問題。 缺點： 1）是沒有生成模型的上述優(yōu)點。 2 簡單易懂的解釋條件隨機場
線性鏈的條件隨機場跟線性鏈的隱馬爾科夫模型一樣，一般推斷用的都是維特比算法。這個算法是一個最簡單的動態(tài)規(guī)劃。 首先我們推斷的目標是給定一個X，找到使P(Y|X)最大的那個Y嘛。然后這個Z(X)，一個X就對應一個Z，所以X固定的話這個項是常量，優(yōu)化跟他沒關(guān)系（Y的取值不影響Z）。然后exp也是單調(diào)遞增的，也不帶他，直接優(yōu)化exp里面。所以最后優(yōu)化目標就變成了里面那個線性和的形式，就是對每個位置的每個特征加權(quán)求和。比如說兩個狀態(tài)的話，它對應的概率就是從開始轉(zhuǎn)移到第一個狀態(tài)的概率加上從第一個轉(zhuǎn)移到第二個狀態(tài)的概率，這里概率是只exp里面的加權(quán)和。那么這種關(guān)系下就可以用維特比了，首先你算出第一個狀態(tài)取每個標簽的概率，然后你再計算到第二個狀態(tài)取每個標簽得概率的最大值，這個最大值是指從狀態(tài)一哪個標簽轉(zhuǎn)移到這個標簽的概率最大，值是多 少，并且記住這個轉(zhuǎn)移（也就是上一個標簽是啥）。然后你再計算第三個取哪個標簽概率最大，取最大的話上一個標簽應該是哪個。以此類推。整條鏈計算完之后， 你就知道最后一個詞去哪個標簽最可能，以及去這個標簽的話上一個狀態(tài)的標簽是什么、取上一個標簽的話上上個狀態(tài)的標簽是什么，醬。這里我說的概率都是 exp里面的加權(quán)和，因為兩個概率相乘其實就對應著兩個加權(quán)和相加，其他部分都沒有變。 學習 這是一個典型的無條件優(yōu)化問題，基本上所有我知道的優(yōu)化方法都是優(yōu)化似然函數(shù)。典型的就是梯度下降及其升級版（牛頓、擬牛頓、BFGS、L-BFGS），這里版本最高的就是L-BFGS了吧，所以一般都用L-BFGS。除此之外EM算法也可以優(yōu)化這個問題。 3 概率無向圖與馬爾科夫隨機場前世今生
概率無向圖模型又稱為馬爾科夫隨機場，是一個可以由無向圖表示的聯(lián)合概率分布。 圖是由結(jié)點和連接結(jié)點的邊組成的集合，（這部分知識學過數(shù)據(jù)結(jié)構(gòu)或者算法的同學都比較了解，不作為深入講解。） 注意：無向圖是指邊上沒有方向的圖，既然邊沒有方向，其權(quán)值是有方向的，諸如轉(zhuǎn)移概率中，“我”到“愛”的轉(zhuǎn)移概率0.5. 概率圖模型是由圖表示的概率分布，沒有聯(lián)合概率分布P(Y)，Y∈{y}是一組隨機變量由無向圖G=<V,E>表示概率分布P(Y)，即在圖G中，結(jié)點v∈V表示一個隨機變量? ；邊e∈E表示隨機變量之間的概率依賴關(guān)系，這點在第一章有詳細介紹。 給定一個聯(lián)合概率分布P（Y）和表示它的無向圖G，無向圖表示的隨機變量之間的成對馬爾科夫性，局部馬爾科夫性，全局馬爾科夫性的如何區(qū)別？ 1） 成對馬爾科夫性表示 ?? 2）局部馬爾科夫性表示 ? 3）全局馬爾科夫性表示 ???????????????? 概率無向圖模型的定義 設(shè)有聯(lián)合概率分布P(Y)，由無向圖G=<V,E>表示，在圖G中，結(jié)點表示隨機變量，邊表示隨機變量之間關(guān)系（加權(quán)概率），如果聯(lián)合概率分布P（Y）滿足成對/局部/全局馬爾科夫性，就稱此聯(lián)合為概率無向圖模型或者馬爾科夫隨機場。 4 計算聯(lián)合概率分布：概率無向圖模型的因子分解
對給定概率無向圖模型下，本質(zhì)就是要求聯(lián)合概率可以將其改變成若干子聯(lián)合概率乘積的形式，也就是將聯(lián)合概率進行因子分解。首先介紹兩個概念：團與最大團。 ? 團：無向圖G中任何兩個結(jié)點均有邊連接的節(jié)點子集成為團。 最大團：若C是無向圖G的一個團，并且不能再加進任何一個G的節(jié)點使其成為一個更大的團，則稱此C為最大團。 注意：{y1,y2,y3,y4}不是一個團，因為y1與y4無邊相連 概率無向圖模型的因子分解： 將概率無向圖模型的聯(lián)合概率分布表示，其最大團上的隨機變量的函數(shù)的乘積形式的操作，即 的聯(lián)合概率是 ?這樣不免太復雜，倘若 為10000個結(jié)點以上呢？（每個結(jié)點是一個漢字，假設(shè)最大團以是篇章，本書假設(shè)10章，則是十個最大團之積。） 概率無向圖模型的聯(lián)合概率分布P(Y)的公式化表示： 給定概率無向圖模型，設(shè)其無向圖為G，C為G上的最大團，YC表示C對應的隨機變量。那么概率無向圖模型的聯(lián)合概率分布P(Y)可寫作圖中所有最大團C上的函數(shù)ΨC(YC)的乘積形式，即： ?其中， 為勢函數(shù)，C為最大團，Z是規(guī)范化因子 規(guī)范化因子保證P(Y)構(gòu)成一個概率分布。 因為要求勢函數(shù)ΨC(YC)是嚴格正的，于是通常定義為指數(shù)函數(shù)： ? 5?參考文獻
【1】?數(shù)學之美?吳軍?著 【2】?機器學習??周志華?著 【3】?統(tǒng)計自然語言處理 宗成慶 著（第二版） 【4】?統(tǒng)計學習方法（191---208） 李航 【5】?知乎?網(wǎng)絡(luò)資源 6?自然語言相關(guān)系列文章
【自然語言處理】：【NLP】揭秘馬爾可夫模型神秘面紗系列文章 【自然語言處理】：【NLP】大數(shù)據(jù)之行，始于足下：談談語料庫知多少 【自然語言處理】：【NLP】驀然回首：談談學習模型的評估系列文章 【自然語言處理】：【NLP】快速了解什么是自然語言處理 【自然語言處理】：【NLP】自然語言處理在現(xiàn)實生活中運用 聲明：關(guān)于此文各個篇章，本人采取梳理扼要，順暢通明的寫作手法。系統(tǒng)閱讀相關(guān)書目和資料總結(jié)梳理而成，旨在技術(shù)分享，知識沉淀。在此感謝原著無私的將其匯聚成書，才得以引薦學習之用。其次，本人水平有限，權(quán)作知識理解積累之用，難免主觀理解不當，造成讀者不便，基于此類情況，望讀者留言反饋，便于及時更正。本文原創(chuàng)，轉(zhuǎn)載請注明出處：前戲：一起走進條件隨機場。? http://www.cnblogs.com/baiboy 【摘要】：條件隨機場用于序列標注，數(shù)據(jù)分割等自然語言處理中，表現(xiàn)出很好的效果。在中文分詞、中文人名識別和歧義消解等任務中都有應用。本文源于筆者做語句識別序列標注過程中，對條件隨機場的了解，逐步研究基于自然語言處理方面的應用。成文主要源于自然語言處理、機器學習、統(tǒng)計學習方法和部分網(wǎng)上資料對CRF介紹的相關(guān)的相關(guān)，最后進行大量研究整理匯總成體系知識。文章布局如下：第一節(jié)介紹CRF相關(guān)的基礎(chǔ)統(tǒng)計知識；第二節(jié)介紹基于自然語言角度的CRF介紹；第三節(jié)基于機器學習角度對CRF介紹，第四節(jié)基于統(tǒng)計學習角度對相關(guān)知識介紹；第五節(jié)對統(tǒng)計學習深度介紹CRF，可以作為了解內(nèi)容。（本文原創(chuàng)，轉(zhuǎn)載請注明出處：基于自然語言處理角度談談CRF。) 目錄
【自然語言處理：漫步條件隨機場系列文章（一）】：前戲：一起走進條件隨機場 【自然語言處理：漫步條件隨機場系列文章（二）】：基于自然語言處理角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（三）】：基于機器學習角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（四）】：基于統(tǒng)計學習角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（五）】：條件隨機場知識擴展 1 條件隨機場（Condition Random Fields），簡稱CRFs
條件隨機場概念：條件隨機場就是對給定的輸出標識序列Y和觀察序列X，條件隨機場通過定義條件概率P(X|Y)，而不是聯(lián)合概率分布P(X,Y)來描述模型。 概念解析： 標注一篇文章中的句子，即語句標注，使用標注方法BIO標注，B代表句子的開始，I代表句子中間，O代表句子結(jié)束。則觀察序列X就是一個語料庫（此處假設(shè)一篇文章，x代表文章中的每一句，X是x的集合），標識序列Y是BIO，即對應X序列的識別，從而可以根據(jù)條件概率P(標注|句子)，推測出正確的句子標注，顯然，這里針對的是序列狀態(tài)，即CRF是用來標注或劃分序列結(jié)構(gòu)數(shù)據(jù)的概率化結(jié)構(gòu)模型，其在自然語言處理和圖像處理領(lǐng)域得到廣泛的應用，CRF可以看作無向圖模型或者馬爾科夫隨機場。 2 條件隨機場的形式化表示
?設(shè)G=(V,E)為一個無向圖，V為結(jié)點的集合，E為無向邊的集合， ，即V中的每個結(jié)點對應一個隨機變量Yv，其取值范圍為可能的標記集合{Y}.如果觀察序列X為條件，每一個隨機變量 都滿足以下馬爾科夫特性: ，其中，w – v表示兩個結(jié)點在圖G中是鄰近結(jié)點，那么，（X,Y）為條件隨機變量。 以語句識別的案例理解條件隨機場的形式化表示。 ?G=（V,E表示識別語句：【我愛中國】的標注是一個無向圖，X我觀察序列，Y為標注序列，V是每個標注狀態(tài)的結(jié)點，E的無向邊，邊上的權(quán)值為概率值。 表示每個X的Y的標注，如:X1:我，y1：O，y2：I，y3：B；取值范圍 ，而 中w—v表示我與愛是相鄰的結(jié)點，這樣的（X,Y）為一個條件隨機場，真正的標注再采用Viterbi算法，如： 尋求最大概率即 ，記錄下我的標注路徑，同理可知： ? 如上便是對條件隨機場與Viterbi算法的綜合運用，其中Viterbi標注問題本質(zhì)是隱馬爾科夫模型三大問題之解碼問題算法模型，具體參考（揭秘馬爾科夫模型系列文章） 3 深度理解條件隨機場
理論上標記序列描述一定條件的獨立性，G圖結(jié)構(gòu)任意的，對序列進行建模可形成最簡單，最普通的鏈式結(jié)構(gòu)圖，結(jié)點對應標記序列X中元素，CRF鏈式圖如下： ? 如上圖兩種表示是一致的，其中圖鏈式句子標注是圖鏈式2的實例化，讀者可能問為什么上面圖是這種而不是廣義的圖，這是因為觀察序列X的元素之間并不存在圖結(jié)構(gòu)，沒有做獨立性假設(shè)，這點也非常容易理解，諸如圖中，我愛中國，其中b表示反射概率而t是轉(zhuǎn)移概率，線上的數(shù)值表示權(quán)值即概率值。如圖3，我的發(fā)射概率0.7，我到愛的轉(zhuǎn)移概率0.5，通俗講，我和愛兩個字是有關(guān)聯(lián)的，并非獨立的。 4 公式化表示條件隨機場
在給定的觀察序列X時，某個待定標記序列Y的概率可以定義為 其中 是轉(zhuǎn)移概率， 是狀態(tài)函數(shù)，表示觀察序列X其中i的位置的標記概率， 和 分別是t和s的權(quán)重，需要從訓練樣本中估計出來。 實例解析： 我愛中國，其中x2是愛字， 表示在觀察狀態(tài)2中，我到愛的轉(zhuǎn)移概率，其中j∈{B,I,O}，可知 的生成概率或者發(fā)射概率的特征函數(shù).觀察序列{0,1}二值特征b（x,i）來表示訓練樣本中某些分布特征，其中采用{0,1}二值特征即符合條件標為1，反之為0； 為了便于描述，可以將狀態(tài)函數(shù)書寫以下形式： ?
特征函數(shù)： ? 其中每個局部 特征表示狀態(tài)特征， 或者專業(yè)函數(shù) ，由此條件隨機場的定義條件概率如下： ， 其中分母為歸一化因子： ? 5?本節(jié)總結(jié)
條件隨機場模型也需要解決三個基本問題：特征的選擇，參數(shù)訓練和解碼。其中參數(shù)訓練過程在訓練數(shù)據(jù)集上基于對數(shù)似然函數(shù)最大化進行。 CRF優(yōu)點：相對于HMM，CRF主要優(yōu)點是它的條件隨機性，只需要考慮當前出現(xiàn)的觀察狀態(tài)的特性，沒有獨立性嚴格要求，CRF具有MEMM一切優(yōu)點。 CRF與MEMM區(qū)別: MEMM：使用每一個狀態(tài)的指數(shù)模型來計算給定前一個狀態(tài)下當前狀態(tài)的條件概率。 CRF：用單個指數(shù)模型計算給定觀察序列與整個標記序列聯(lián)合概率。 《統(tǒng)計自然語言處理》P128頁有關(guān)于隨機場模型的實現(xiàn)工具。 ?? 6 參考文獻
【1】?數(shù)學之美?吳軍?著 【2】?機器學習??周志華?著 【3】?統(tǒng)計自然語言處理 宗成慶 著（第二版） 【4】?統(tǒng)計學習方法（191---208） 李航 【5】?知乎?網(wǎng)絡(luò)資源 7?自然語言相關(guān)系列文章
【自然語言處理】：【NLP】揭秘馬爾可夫模型神秘面紗系列文章 【自然語言處理】：【NLP】大數(shù)據(jù)之行，始于足下：談談語料庫知多少 【自然語言處理】：【NLP】驀然回首：談談學習模型的評估系列文章 【自然語言處理】：【NLP】快速了解什么是自然語言處理 【自然語言處理】：【NLP】自然語言處理在現(xiàn)實生活中運用 聲明：關(guān)于此文各個篇章，本人采取梳理扼要，順暢通明的寫作手法。系統(tǒng)閱讀相關(guān)書目和資料總結(jié)梳理而成，旨在技術(shù)分享，知識沉淀。在此感謝原著無私的將其匯聚成書，才得以引薦學習之用。其次，本人水平有限，權(quán)作知識理解積累之用，難免主觀理解不當，造成讀者不便，基于此類情況，望讀者留言反饋，便于及時更正。本文原創(chuàng)，轉(zhuǎn)載請注明出處：基于自然語言處理角度談談CRF。? 1 條件隨機場（可以看作給定觀察值的馬爾科隨機場）
CRF是一種判別式無向圖模型 CRF試圖對多個變量在給定觀測值后的條件概率進行建模，具體來說，若令 為觀察序列， 為與之對應的標記序列，則CRF的目標是構(gòu)建條件概率模型P(Y|X)。 注意：標記變量y是結(jié)構(gòu)型變量，如在自然語言處理的句子標注任務中，觀測數(shù)據(jù)為句子，標記為相應的詞性序列，具有線性序列結(jié)構(gòu)，在語法分析中，輸出標記是語法樹，具有樹形結(jié)構(gòu)。
令G=<V，E>表示結(jié)點與標記變量y中元素一一對應的無向圖， 表示與結(jié)點v對應標記變量，n（v）表示結(jié)點v的領(lǐng)結(jié)點，若圖G的每一個變量 都滿足馬爾科夫性，即 ? ，則（y，x）構(gòu)成一個CRF。 上面形式化在第二章已經(jīng)通過實例解析介紹過。 2 鏈式條件隨機場
如上面句子標注，因為現(xiàn)象應用中，對標記序列建模時，常有鏈式結(jié)構(gòu)（具體鏈式結(jié)構(gòu)前面有介紹） 與馬爾科夫隨機場定義聯(lián)合概率概率的方式類似，CRF使用勢函數(shù)和圖結(jié)構(gòu)上的團來定義條件概率P(y|x)給定觀察序列X，所謂團即單個標記變量{}以及相鄰標記變量 選擇合適的勢函數(shù)，即形如： 的條件概率定義，其中 與Q對應的勢函數(shù)， 為規(guī)范因子，實際中，往往Z不需要獲得精確值。 在CRF中，通過選用勢函數(shù)并引入特征函數(shù)，條件概率定義如下： 如上參數(shù)在第二章有詳細講解。 特征函數(shù)： 句子標注為例的轉(zhuǎn)移特征函數(shù) 表示第i個觀察值為“愛”時，相對的標記分別是B，I，其狀態(tài)特征函數(shù)如下： ? 表示觀察值x為單字“愛”時，它對應的標注很可能為I 3?參考文獻
【1】?數(shù)學之美?吳軍?著 【2】?機器學習??周志華?著 【3】?統(tǒng)計自然語言處理 宗成慶 著（第二版） 【4】?統(tǒng)計學習方法（191---208） 李航 【5】?知乎?網(wǎng)絡(luò)資源 4?自然語言相關(guān)系列文章
【自然語言處理】：【NLP】揭秘馬爾可夫模型神秘面紗系列文章 【自然語言處理】：【NLP】大數(shù)據(jù)之行，始于足下：談談語料庫知多少 【自然語言處理】：【NLP】驀然回首：談談學習模型的評估系列文章 【自然語言處理】：【NLP】快速了解什么是自然語言處理 【自然語言處理】：【NLP】自然語言處理在現(xiàn)實生活中運用 聲明：關(guān)于此文各個篇章，本人采取梳理扼要，順暢通明的寫作手法。系統(tǒng)閱讀相關(guān)書目和資料總結(jié)梳理而成，旨在技術(shù)分享，知識沉淀。在此感謝原著無私的將其匯聚成書，才得以引薦學習之用。其次，本人水平有限，權(quán)作知識理解積累之用，難免主觀理解不當，造成讀者不便，基于此類情況，望讀者留言反饋，便于及時更正。本文原創(chuàng)，轉(zhuǎn)載請注明出處：基于機器學習角度談談CRF。? http://www.cnblogs.com/baiboy 分類:?NLP 【摘要】：條件隨機場用于序列標注，數(shù)據(jù)分割等自然語言處理中，表現(xiàn)出很好的效果。在中文分詞、中文人名識別和歧義消解等任務中都有應用。本文源于筆者做語句識別序列標注過程中，對條件隨機場的了解，逐步研究基于自然語言處理方面的應用。成文主要源于自然語言處理、機器學習、統(tǒng)計學習方法和部分網(wǎng)上資料對CRF介紹的相關(guān)的相關(guān)，最后進行大量研究整理匯總成體系知識。文章布局如下：第一節(jié)介紹CRF相關(guān)的基礎(chǔ)統(tǒng)計知識；第二節(jié)介紹基于自然語言角度的CRF介紹；第三節(jié)基于機器學習角度對CRF介紹，第四節(jié)基于統(tǒng)計學習角度對相關(guān)知識介紹；第五節(jié)對統(tǒng)計學習深度介紹CRF，可以作為了解內(nèi)容。（本文原創(chuàng)，轉(zhuǎn)載請注明出處：基于統(tǒng)計學習方法角度談談CRF。) 目錄
【自然語言處理：漫步條件隨機場系列文章（一）】：前戲：一起走進條件隨機場 【自然語言處理：漫步條件隨機場系列文章（二）】：基于自然語言處理角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（三）】：基于機器學習角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（四）】：基于統(tǒng)計學習角度談談CRF 【自然語言處理：漫步條件隨機場系列文章（五）】：條件隨機場知識擴展 引子
條件隨機場（CRF）：是給定一組輸入隨機變量條件下，另一組輸出隨機變量的條件概率分布模型，其特點是假設(shè)輸出隨機變量構(gòu)成馬爾科夫隨機場，條件隨機場可用于不同預測問題，由輸入序列對輸出序列預測的判別式模型，形式為對數(shù)線性模型，其學習方法通常是極大似然估計。 1 條件隨機場(CRF)的定義與形式
簡單的說，條件隨機場(CRF)類似于MRF，只不過CRF比MRF多了一個觀察集合，或者說，CRF本質(zhì)上就是給定了觀察值集合的MRF。 條件隨機場：設(shè)G=(V,E)是一個無向圖，Y={Yv|v∈V}是以G中節(jié)點v為索引的隨機變量Yv構(gòu)成的集合。在給定X的條件下，如果每個隨機變量Yv服從馬爾可夫性，即 ，則條件概率分布P(Y|X)就是一個條件隨機場。上式中的w ~ v表示在圖G=(V, E)中與節(jié)點v有邊連接的所有節(jié)點，w≠v表示v以外的所有節(jié)點，Yv,Yu, Yw為w對節(jié)點v，u，w對應的隨機變量。 線性鏈條件隨機場：?? 設(shè)X = (X1, X2,..., Xn), Y = (Y1, Y2, ..., Yn)均為線性鏈表示的隨機變量序列，若在給定隨機變量序列X的條件下，隨機變量序列Y的條件概率分布P(Y|X)構(gòu)成條件隨機場，即滿足馬爾可夫性(見本文最開始的“模型定義”部分)： P(Yi| X, Y1, ..., Yi-1, Yi+1, ...., Yn)= P(Yi?| X, Yi-1, Yi+1)??i= 1, 2, ..., n (在i=1和n時只考慮單邊)，則稱P(Y|X)為線性鏈條件隨機場。 注意：在標注問題中，X表示輸入觀測序列，Y表示對應的輸出標記序列或狀態(tài)序列。 2 條件隨機場的參數(shù)化形式
P(Y|X)為線性鏈條件隨機場，則在隨機變量X取值為x的條件下，隨機變量Y取值為y的條件概率具有如下形式： ? 其中， 式中，tk和sl是特征函數(shù)，λk和μl是對應的權(quán)值。Z(x)是規(guī)范化因子，求和時在所有可能的輸出序列上進行的。 通常：特征函數(shù)t和s取值是1或0，當滿足特征條件取值1，反之取值0，條件隨機場完全由特征函數(shù)t，s和對應的數(shù)值λ，μ確定。 注意：線性CRF也是對數(shù)性模型。 實例解析： 設(shè)有一個天氣預測問題：輸入觀察序列（連續(xù)三天的天氣情況）為X = (X1, X2, X3)，輸出標記序列（每天對應天氣熱冷的預測）為 Y = (Y1, Y2, Y3)， Y1, Y2, Y3 的取值于y= {H, C},其中H表示天熱，C表示天冷。假設(shè)特征tk,sl和對應的權(quán)值λk，μl如下： 其中，上式代表著特征值為H的條件，即：yi-1= H, yi=C, x, i = 2, 3 時特征值取1。而特征值取0的條件被省略了。 PS：如果寫全的話是這樣： 于是對給定的觀測序列x，求標記序列為y =(y1, y2, y3) = (H, C, C),即第一天熱，第二天第三天連續(xù)冷的非規(guī)范化條件概率（即沒有除以規(guī)范化因子的條件概率） 實例分析： 由以上問題可知，觀察序列是天數(shù)的集合，標記序列是對應天氣熱冷的集合，由此分析顯然是隨機條件場的編碼問題，基于隨機條件場，可以將上述情形轉(zhuǎn)換為圖形化形式分析，然后進行模型構(gòu)建，算法實現(xiàn)，算法優(yōu)化和結(jié)果分析即可。本節(jié)重點實現(xiàn)分析，圖形表示，模型構(gòu)建。 天氣預測問題轉(zhuǎn)化為圖形表示如下： 如圖所示，橫坐標x1，x2，x3分別對應天，是觀察序列具備時序性，縱坐標是標記序列即可能隱藏的所有標記情況，start和end表示開始和結(jié)束狀態(tài)（這點參照筆者Viterbi算法一節(jié)的介紹），其中t表示轉(zhuǎn)移概率，t=0.5有具體權(quán)值的，標注轉(zhuǎn)移概率是50%機會。X對應的s表示發(fā)射概率或者生產(chǎn)概率，顯然，如上滿足條件隨機場，回顧下條件隨機場模型，線性鏈條件隨機場模型為： 于是對給定的觀測序列x，標記序列y=(H,C,C)的非規(guī)范化條件概率為 上式數(shù)值計算，參照已知條件和圖形分析，很容易計算，這里具體計算過程省略。 3 條件隨機場的簡化形式
將局部特征轉(zhuǎn)化為一個全局特征函數(shù)，可將CRF寫成權(quán)值向量和特征向量的內(nèi)積形式即是條件隨機場的簡化形式，具體參見如下筆記： ①?將轉(zhuǎn)移特征和狀態(tài)特征以及其數(shù)值用統(tǒng)一符號表示，設(shè)有K1個轉(zhuǎn)移貼紙，K2個狀態(tài)特征，K=K1+K2，記： ②?對轉(zhuǎn)移狀態(tài)各個位置i求和，記作： ③?用wk表示特征fk(y,x)的權(quán)值，即： ??????????? ④?于是，條件隨機場可表示為 ??????????????????????? ⑤?以w表示權(quán)值向量，即 ?????????????????????? ⑥?以F(y, x)表示全局特征向量，即 ?????????????????? 則條件隨機場可以寫成向量w與F(y, x)的內(nèi)積的形勢： ? 4 條件隨機場預測算法
?形式化描述： 條件隨機場的預測問題是給定義條件隨機場P(Y|X)和輸入序列(觀測序列)x，求條件概率最大的輸出序列(標記序列)y*，即對觀測序列進行標注。 條件隨機場的預測算法是著名的維特比算法。 你對維特比算法是什么就有概念了吧，下面來看看其數(shù)學描述。維特比算法不做深入講解，如果讀者還不清楚，參考本人系列文章之揭秘馬爾科夫模型系統(tǒng)文章，有專門章節(jié)詳細介紹viterbi算法。 ???? 這里，路徑表示標記序列，其中 ??????????? 注意，這時只需計算非規(guī)范化概率，而不必計算概論，可以大大提高效率。 為了求解最優(yōu)路徑，將式寫成如下形式： ???????????? 其中 ???????????????? 就是局部特征向量。 下面敘述維特比算法。 實例解析 用維特比算法求給定的輸入序列(觀測序列)x對應的輸出序列(標記序列)y* = (y1*, y2*, y3*)； 解析： 1)第一步初始化：因為y1=1和y1=2是最初，所以就不用考慮轉(zhuǎn)移的情況了(實際上也沒有“表達從y0轉(zhuǎn)移到y(tǒng)1的情況”的t函數(shù)(轉(zhuǎn)移函數(shù)))，直接從狀態(tài)函數(shù)(s函數(shù)中找)，發(fā)現(xiàn)，s1和s2分別對應y1=1和y1=2，說明y1=1和y1=2這個狀態(tài)都是存在的，而s1和s2的權(quán)值分別是1和0.5，且上面列出的s函數(shù)們和t函數(shù)們值都為1，所以y1=1和y2=1的可能性分別是1和0.5。所以，到達y1的非規(guī)范化概率最大值為：δ1(1) = 1，δ1(2) = 0.5。 2)第二步遞推：i=2(達第二處目的地集合{y2=1, y2=2})：首先是路線(僅說明到達y2=1的情況)： 上圖可知，到達y2=1的路線有如下幾條： ?路線1：從y1=1出發(fā) ----(經(jīng)過t2)---->到達y2=1； ?路線2：從y1=2出發(fā) ----(經(jīng)過t4)---->到達y2=1； ?接著是狀態(tài)(僅說明到達y2=1的情況)： 根據(jù)題目可知：i=2時的狀態(tài)函數(shù)只有s2和s3，而y2=1對應的函數(shù)是s3 所以到達y2=1的非規(guī)范化概率最大值為：δ2(1) = max{1+λ2t2?+ u3s3,0.5 + λ4t4?+ u3s3}= 2.4 非規(guī)范化概率最大值的路徑為：?ψ2(1) = 1 δ2(2)同理。 i=3也一樣（只不過對于δ3(1)中的u5s5，我認為應該是u3s3，先不說s3對應的是y3=1的情況，而且原題中根本沒有s5函數(shù)）。 3)第三步終止：這步就簡單了，在δ3(l)中δ3(1) = 4.3最大，所以y3中取1的可能性最大，即y3*=1。 4)第四步返回：然后反著推： 從y2的哪個值到y(tǒng)3可能性最大呢？在第二部已經(jīng)解出：ψ3(1) = 2，即y2到達y3=1的路線中權(quán)值最大的是y2=2，即y2*=2。 同理，從y1=1到y(tǒng)2=2的可能性最大，即y1*=1。 5)就得到標記序列:*= (y1*, y2*, y3*)= (1, 2, 1) 5?參考文獻
【1】?數(shù)學之美?吳軍?著 【2】?機器學習??周志華?著 【3】?統(tǒng)計自然語言處理 宗成慶 著（第二版） 【4】?統(tǒng)計學習方法（191---208） 李航 【5】?知乎?網(wǎng)絡(luò)資源 6?自然語言相關(guān)系列文章
【自然語言處理】：【NLP】揭秘馬爾可夫模型神秘面紗系列文章 【自然語言處理】：【NLP】大數(shù)據(jù)之行，始于足下：談談語料庫知多少 【自然語言處理】：【NLP】驀然回首：談談學習模型的評估系列文章 【自然語言處理】：【NLP】快速了解什么是自然語言處理 【自然語言處理】：【NLP】自然語言處理在現(xiàn)實生活中運用 聲明：關(guān)于此文各個篇章，本人采取梳理扼要，順暢通明的寫作手法。系統(tǒng)閱讀相關(guān)書目和資料總結(jié)梳理而成，旨在技術(shù)分享，知識沉淀。在此感謝原著無私的將其匯聚成書，才得以引薦學習之用。其次，本人水平有限，權(quán)作知識理解積累之用，難免主觀理解不當，造成讀者不便，基于此類情況，望讀者留言反饋，便于及時更正。本文原創(chuàng)，轉(zhuǎn)載請注明出處：基于統(tǒng)計學習方法角度談談CRF。? http://www.cnblogs.com/baiboy 好文要頂?關(guān)注我?收藏該文? ? 伏草惟存 關(guān)注 - 6 粉絲 - 263 +加關(guān)注 0 0 ??上一篇：【NLP】基于機器學習角度談談CRF（三） ??下一篇：【NLP】條件隨機場知識擴展延伸（五） posted @?2016-08-03 10:35?伏草惟存?閱讀(212) 評論(0)?編輯?收藏 1 隨機場的矩陣形式
矩陣表示形式前提條件：假設(shè)P（y|x）是線性鏈條件隨機場，給定觀測序列x，相應的標記序列y的條件概率。引進特殊的起點和終點狀態(tài)標記y0?= start，yn+1?= stop，這時Pw(y|x) 可以通過矩陣形式表示。（實際上，特殊點的引用大家都有接觸，諸如學習隱含馬爾科夫模型中向前算法解決了似然度問題，viterbi算法解決解碼問題，向前向后算法解決學習參數(shù)。） 對觀測序列x的每一個位置i=1, 2,..., n+1，定義一個m階矩陣(m是標記yi取值的個數(shù)) ????????????????????????????????? 這樣給定觀測序列x，標記序列y的非規(guī)范化概率可以通過n+1個矩陣的乘積 ?????????????? 表示。于是，條件概率Pw(y|x)是 ? 中，Zw(x)為規(guī)范化因子，是n+1個矩陣的乘積的(start,stop)元素： 注意，y0= start，yn+1?= stop表示開始狀態(tài)與終止狀態(tài)，規(guī)范化因子Zw(x)是以start為起點stop為重點通過狀態(tài)的所有路徑y(tǒng)1y2...yn的非規(guī)范化概率 ?????????? 之和。 下面通過一個例子來說明“范化因子Zw(x)是以start為起點stop為重點通過狀態(tài)的所有路徑y(tǒng)1y2...yn的非規(guī)范化概率之和”這個事實 實例解析 ?????????????? 給定一個如上圖所示的線性鏈條件隨機場，觀測序列x，狀態(tài)序列y，i=1,2,3，n=3，標記yi∈{1,2}，假設(shè)y0=start=1，y4=stop=1，各個位置的隨機矩陣M1(x)，M2(x)，M3(x)，M4(x)分別是 ?????????????? 試求狀態(tài)序列y以start為起點stop為終點所有路徑的非規(guī)范化概率及規(guī)范化因子。 實例解答： 從start到stop對應于y=(1,1,1),y=(1,1,2), ..., y=(2,2,2)個路徑的非規(guī)范化概率分別是： ??????????????????????????? a01b11c11，a01b11c12，a01b12c21，a01b12c22 ??????????????????????????? a02b21c11，a01b21c12，a02b22c21，a02b22c22 然后按式11.12求規(guī)范化因子，通過計算矩陣乘積M1(x) M2(x) M3(x) M4(x)可知，其第一行第一列的元素為a01b11c11+ a01b11c12?+ a01b12c21+ a01b12c22+a02b21c11?+ a01b21c12+ a02b22c21?+ a02b22c22，恰好等于從start到stop的所有路徑的非規(guī)范化概率之和，即規(guī)范化因子Z(x)。 在之前的介紹中我們已近知道，條件隨機場的概率計算問題是給定條件隨機場P(Y|X)，輸入序列x和輸出序列y，計算條件概率P(Yi=yi?| x)，P(Yi-1?=yi-1, Yi=yi?| x)以及相應數(shù)學期望的問題。為了方便起見，像隱馬爾可夫模型那樣，引進前向-后向向量，遞歸的計算以上概率及期望值。這樣的算法稱為前向-后向算法。 2 前向-后向算法
對每個指標i =0,1,...,n+1，定義前向向量ai(x)： ???? 遞推公式為 ?????????? 又可表示為 ??????? ai(yi|x)表示在位置i的標記是yi并且到位置i的前部分標記序列的非規(guī)范化概率，若yi可取的值有m個，那ai(x)就是m維的列向量。同樣，對每個指標i =0,1,...,n+1，定義后向向量βi(x)： ???????????? 又可表示為 ??????????????? βi(yi|x)表示在位置i的標記為yi并且從i+1到n的后部分標記序列的非規(guī)范化的概率。 由前向-后向定義不難得到： ??????????? 這里，若ai(x)是m維的列向量，那1就是元素均為1的m維列向量。 概率計算 按照前向-后向向量的定義，很容易計算標記序列在位置i是標記yi的條件概率和在位置i-1與i是標記yi-1和yi的條件概率： 其中，?? Z(x)= anT(x)·1 ?期望值計算 利用前向-后向向量，可以計算特征函數(shù)關(guān)于聯(lián)合分布P(X, Y)和條件分布P(Y | X)的數(shù)學期望。特征函數(shù)fk關(guān)于條件分布P(Y |X)的數(shù)學期望是 其中，Z(x)= anT(x)·1 則特征函數(shù)fk關(guān)于聯(lián)合分布P(X, Y)的數(shù)學期望是 ???? 其中，?Z(x)= anT(x)·1 特征函數(shù)數(shù)學期望的一般計算公式。對于轉(zhuǎn)移貼紙tk(yi-1, yi, x, i)，k=1,2,...,K1，可以將式中的fk換成tk；對于狀態(tài)特征，可以將式中的fk換成si，表示sl(yi, x, i)，k = K1?+1，l = 1,2,...,K2。有了式11.32 ~11.35，對于給定的觀測序列x和標記序列y，可以通過一次前向掃描計算ai及Z(x)，通過一次后向掃描計算βi，從而計算所有的概率和特征的期望。 ?3 CRF的學習算法
條件隨機場模型實際上是定義在時序數(shù)據(jù)上的對數(shù)線性模型，其學習方法包括極大似然估計和正則化的極大似然估計。 具體的優(yōu)化實現(xiàn)算法有改進的迭代尺度法IIS、梯度下降法以及擬牛頓法。 1）進的迭代尺度法(IIS) 已知訓練數(shù)據(jù)集，由此可知經(jīng)驗概率分布 ?? 可以通過極大化訓練數(shù)據(jù)的對數(shù)似然函數(shù)來求模型參數(shù)。訓練數(shù)據(jù)的對數(shù)似然函數(shù)為 ?? 當Pw是一個由 給出的條件隨機場模型時，對數(shù)似然函數(shù)為 ?????????????? IIS通過迭代的方法不斷優(yōu)化對數(shù)似然函數(shù)改變量的下界，達到極大化對數(shù)似然函數(shù)的目的。 假設(shè)模型的當前參數(shù)向量為w=(w1,w2, ..., wK)T，向量的增量為δ=(δ1,δ2, ..., δK)T，更新參數(shù)向量為w +δ=(w1+δ1, w2?+δ2, ..., wk+δk)T。在每步迭代過程中，IIS通過一次求解下面的11.36和11.37，得到δ=(δ1,δ2, ..., δK)T。關(guān)于轉(zhuǎn)移特征tk的更新方程為： 關(guān)于狀態(tài)特征sl的更新方程為： 這里T(x, y)是在數(shù)據(jù)(x, y)中出現(xiàn)所有特征數(shù)的綜合： ????????? 于是算法整理如下。 算法：條件隨機場模型學習的改進的迭代尺度法 輸入：特征函數(shù)t1,t2, ..., tK1，s1, s2, ..., sK2；經(jīng)驗分布 輸出：參數(shù)估計值? ；模型 。 過程： 2）擬牛頓法 對于條件隨機場模型 ? 學習的優(yōu)化目標函數(shù)是 其梯度函數(shù)是 ? 擬牛頓法的BFGS算法如下：算法：條件隨機場模型學習的BFGS算法 4?基于條件隨機場CRF的中文命名實體識別效率如何？
【知乎】北京航空航天大學 計算機專業(yè)博士在讀33?人贊同 大致命名實體識別的方法可以可以分為四個大類型： 有監(jiān)督學習方法： HMM?http://www.nlpr.labs.gov.cn/2005papers/gjhy/gh71.pdf SVM?Biomedical named entity recognition using two-phase model based on SVMs CRF?http://psb.stanford.edu/psb11/conference-materials/proceedings%201996-2010/psb08/leaman.pdf 當然還有決策樹最大熵等方法。基本每個模型都會在這個問題上試一遍的。 無監(jiān)督學習方法：Unsupervised named-entity extraction from the Web: An experimental study 半監(jiān)督學習方法：Minimally-supervised extraction of entities from text advertisements 混合方法：多種模型結(jié)合?Recognizing named entities in tweets 主要介紹三種主流算法，CRF，字典法和混合方法。 CRF： 用過CRF的都知道，CRF是一個序列標注模型，指的是把一個詞序列的每個詞打上一個標記。一般通過，在詞的左右開一個小窗口，根據(jù)窗口里面的詞，和待標注詞語來實現(xiàn)特征模板的提取。最后通過特征的組合決定需要打的tag是什么。 而在CRF for Chinese NER這個任務中，提取的特征大多是該詞是否為中國人名姓氏用字，該詞是否為中國人名名字用字之類的，True or false的特征。所以一個可靠的百家姓的表就十分重要啦~在國內(nèi)學者做的諸多實驗中，效果最好的人名可以F1測度達到90%，最差的機構(gòu)名達到85%。 基于條件隨機場的中文命名實體識別特征比較研究--《第四屆全國信息檢索與內(nèi)容安全學術(shù)會議論文集（上）》2008年 字典法： 字典法需要掌握的是一種快速搜索算法trie-tree，我相信很多人應該對這個算法已經(jīng)有所了解。在NER中就是把每個字都當開頭的字放到trie-tree中查一遍，查到了就是NE。中文的trie-tree需要進行哈希，因為中文字符太多了，不像英文就26個。 混合法： 對六類不同的命名實體采取不一樣的手段進行處理，例如對于人名，進行字級別的條件概率計算。 例如我們需要算 其中Sur代表中國人姓氏，Dgb代表中國人名首字，Dge代表中國人名尾字。 而機構(gòu)則在詞級別進行此概率計算。 我知道的系統(tǒng)有： 中文 1、哈工大?語言云（語言技術(shù)平臺云 LTP-Cloud） 2、上海交大?趙海 主頁 分詞 自然語言 計算語言學 機器學習 英文： Stanford NER BANNER（生物醫(yī)學） Minor Third 5 條件隨機場（crf）是否可以將分類問題都當作序列標注問題解決？
【知乎】標注看上去好像就是在序列上做分類。 然而實際上標注跟分類最大的區(qū)別就是：標注采的特征里面有上下文分類結(jié)果，這個結(jié)果你是不知道的，他在“分類”的時候是跟上下文一起"分類的"。因為你要確定這個詞的分類得先知道上一個詞的分類，所以這個得整句話的所有詞一起解，沒法一個詞一個詞解。 而分類是根據(jù)當前特征確定當前類別，分類的時候不需要考慮上下文的分類結(jié)果，但可以引入上下文的特征。 比如說命名實體識別，你采的特征如果是：{當前詞，當前詞性，當前詞語義角色，上一個詞，上一個詞的詞性} 那這樣跟分類沒有什么區(qū)別。如果你采的特征是：{當前詞，當前詞性，當前詞語義角色，上一個詞，上一個詞的標簽，上一個詞的詞性}
總結(jié)
- 上一篇： c语言b6=1什么意思,简谱中1=C表示
- 下一篇： 在Puppet中用ERB模板来自动配置N