條件隨機(jī)場-詳細(xì)

1、條件隨機(jī)場conditional random fields條件隨機(jī)場模型是Lafferty于2001年，在最大熵模型和隱馬爾科夫模型的基礎(chǔ)上，提出的一種判別式概率無向圖學(xué)習(xí)模型，是一種用于標(biāo)注和切分有序數(shù)據(jù)的條件概率模型。條件隨機(jī)場概述CRF最早是針對(duì)序列數(shù)據(jù)分析提出的，現(xiàn)已成功應(yīng)用于自然語言處理(Natural Language Processing，NLP） 、生物信息學(xué)、機(jī)器視覺及網(wǎng)絡(luò)智能等領(lǐng)域。序列標(biāo)注標(biāo)注：人名 地名 組織名觀察序列：毛澤東標(biāo)注：名詞 動(dòng)詞 助詞 形容詞 副詞 觀察序列：今天天氣非常好！實(shí)體命名識(shí)別漢語詞性標(biāo)注四、隱馬爾可夫模型（Hidden Markov Mode

2、l，HMM）一、產(chǎn)生式模型和判別式模型（Generative model vs. Discriminative model）二、概率圖模型（Graphical Models）五、最大熵模型（Maximum Entropy Model，MEM）七、條件隨機(jī)場（conditional random fields，CRF）三、樸素貝葉斯分類器（ Naive Bayes Classier）六、最大熵馬爾可夫模型（MEMM）一、產(chǎn)生式模型和判別式模型（Generative model vs. Discriminative model） 產(chǎn)生式模型：構(gòu)建o和s的聯(lián)合分布p(s,o)，因可以根據(jù)聯(lián)合概率來生

3、成樣本，如HMM，BNs，MRF。產(chǎn)生式模型：無窮樣本 = 概率密度模型 = 產(chǎn)生模型 =預(yù)測判別式模型：有限樣本 = 判別函數(shù) = 預(yù)測模型 =預(yù)測 判別式模型：構(gòu)建o和s的條件分布p(s|o)，因?yàn)闆]有s的知識(shí)，無法生成樣本，只能判斷分類，如SVM，CRF，MEMM 。o和s分別代表觀察序列和標(biāo)記序列一個(gè)舉例：(1,0), (1,0), (2,0), (2, 1)產(chǎn)生式模型：P (x, y)：P(1, 0) = 1/2, P(1, 1) = 0, P(2, 0) = 1/4, P(2, 1) = 1/4.判別式模型：P (y | x)：P(0|1) = 1, P(1|1) = 0, P(0

4、|2) = 1/2, P(1|2) = 1/2兩種模型比較：Generative model ：從統(tǒng)計(jì)的角度表示數(shù)據(jù)的分布情況，能夠反映同類數(shù)據(jù)本身的相似度，不關(guān)心判別邊界。 優(yōu)點(diǎn):實(shí)際上帶的信息要比判別模型豐富，研究單類問題比判別模型靈活性強(qiáng)能更充分的利用先驗(yàn)知識(shí)模型可以通過增量學(xué)習(xí)得到缺點(diǎn)：學(xué)習(xí)過程比較復(fù)雜在目標(biāo)分類問題中易產(chǎn)生較大的錯(cuò)誤率 Discriminative model：尋找不同類別之間的最優(yōu)分類面，反映的是異類數(shù)據(jù)之間的差異。優(yōu)點(diǎn):分類邊界更靈活，比使用純概率方法或生產(chǎn)模型得到的更高級(jí)。能清晰的分辨出多類或某一類與其他類之間的差異特征在聚類、viewpoint changes

5、, partial occlusion and scale variations中的效果較好適用于較多類別的識(shí)別缺點(diǎn)：不能反映訓(xùn)練數(shù)據(jù)本身的特性。能力有限，可以告訴你的是1還是2，但沒有辦法把整個(gè)場景描述出來。 二者關(guān)系：由生成模型可以得到判別模型，但由判別模型得不到生成模型。 二、概率圖模型（Graphical Models）頂點(diǎn)/節(jié)點(diǎn)，表示隨機(jī)變量邊/弧兩個(gè)節(jié)點(diǎn)鄰接：兩個(gè)節(jié)點(diǎn)之間存在邊，記為 ，不存在邊，表示條件獨(dú)立路徑：若對(duì)每個(gè)i，都有 ，則稱序列 為一條路徑概率圖模型：是一類用圖的形式表示隨機(jī)變量之間條件依賴關(guān)系的概率模型，是概率論與圖論的結(jié)合。圖中的節(jié)點(diǎn)表示隨機(jī)變量，缺少邊表示條件獨(dú)

6、立假設(shè)。根據(jù)圖中邊有無方向，常用的概率圖模型分為兩類：有向圖：最基本的是貝葉斯網(wǎng)絡(luò)(Bayesian Networks ,BNs)舉例有向圖模型的聯(lián)合概率分解每個(gè)節(jié)點(diǎn)的條件概率分布表示為：P(當(dāng)前節(jié)點(diǎn)|它的父節(jié)點(diǎn))聯(lián)合分布：無向圖：馬爾可夫隨機(jī)場(Markov Random Fields, MRF)馬爾可夫隨機(jī)場模型中包含了一組具有馬爾可夫性質(zhì)的隨機(jī)變量，這些變量之間的關(guān)系用無向圖來表示馬爾科夫性：舉例團(tuán)(clique) ：任何一個(gè)全連通（任意兩個(gè)頂點(diǎn)間都有邊相連）的子圖最大團(tuán)(maximal clique)：不能被其它團(tuán)所包含的團(tuán)X1X2X3X4例如右圖的團(tuán)有C1=X1, X2, X3和C2

7、=X2, X3, X4無向圖模型的聯(lián)合概率分解勢函數(shù)（potential function）是關(guān)于 上 隨機(jī)變量的函數(shù)設(shè)x是一個(gè)類別未知的數(shù)據(jù)樣本，Y為類別集合，若數(shù)據(jù)樣本x屬于一個(gè)特定的類別yj，那么分類問題就是決定P(yj|x)，即在獲得數(shù)據(jù)樣本x時(shí)，確定x的最佳分類。所謂最佳分類，一種辦法是把它定義為在給定數(shù)據(jù)集中不同類別yj先驗(yàn)概率的條件下最可能的分類。貝葉斯理論提供了計(jì)算這種可能性的一種直接方法。三、樸素貝葉斯分類器（ Naive Bayes Classier）如果沒有這一先驗(yàn)知識(shí)，那么可以簡單地將每一候選類別賦予相同的先驗(yàn)概率。不過通常我們可以用樣例中屬于yj的樣例數(shù)|yj|比上總

8、樣例數(shù)|D|來近似，即P(yj)代表還沒有訓(xùn)練數(shù)據(jù)前，yj擁有的初始概率。P(yj)常被稱為yj的先驗(yàn)概率(prior probability) ，它反映了我們所擁有的關(guān)于yj是正確分類機(jī)會(huì)的背景知識(shí)，它應(yīng)該是獨(dú)立于樣本的。 是聯(lián)合概率，指當(dāng)已知類別為yj的條件下，看到樣本x出現(xiàn)的概率。 若設(shè)則條件獨(dú)立性：在給定隨機(jī)變量C時(shí)，a，b條件獨(dú)立。假定：在給定目標(biāo)值 yj 時(shí)，x的屬性值之間相互條件獨(dú)立。 P(yj|x )被稱為Y的后驗(yàn)概率（posterior probability），因?yàn)樗从沉嗽诳吹綌?shù)據(jù)樣本x后yj成立的置信度。 是后驗(yàn)概率，即給定數(shù)據(jù)樣本x時(shí)yj成立的概率，而這正是我們所感興

9、趣的。后驗(yàn)概率基本假設(shè)樸素貝葉斯分類器的概率圖表示隱馬爾可夫模型的概率圖表示三、隱馬爾可夫模型（Hidden Markov Model,HMM）馬爾可夫模型：是一個(gè)三元組 =(S, , A)其中 S是狀態(tài)的集合，是初始狀態(tài)的概率, A是狀態(tài)間的轉(zhuǎn)移概率。一階馬爾可夫鏈晴 云 雨一階馬爾可夫模型的例子問題：假設(shè)今天是晴天，請(qǐng)問未來三天的天氣呈現(xiàn)云雨晴的概率是多少？隱馬爾可夫模型(HMM)HMM是一個(gè)五元組 = (Y, X, , A, B) ，其中 Y是隱狀態(tài)（輸出變量）的集合，）X是觀察值（輸入）集合， 是初始狀態(tài)的概率，A是狀態(tài)轉(zhuǎn)移概率矩陣，B是輸出觀察值概率矩陣。HMM實(shí)例實(shí)驗(yàn)進(jìn)行方式如下：

10、根據(jù)初始概率分布，隨機(jī)選擇N個(gè)缸中的一個(gè)開始實(shí)驗(yàn)根據(jù)缸中球顏色的概率分布，隨機(jī)選擇一個(gè)球，記球的顏色為x1，并把球放回缸中根據(jù)缸的轉(zhuǎn)移概率分布，隨機(jī)選擇下一口缸，重復(fù)以上步驟。Urn NUrn 1Urn 2Observed Ball Sequence最后得到一個(gè)描述球的顏色的序列x1,x2,稱為觀察值序列X。 問題2：給定觀察序列 以及模型，如何選擇一個(gè)對(duì)應(yīng)的狀態(tài)序列 ，使得Y能夠最為合理的解釋觀察序列X？問題1：給定觀察序列 以及模型 , 計(jì)算問題3：給定觀察序列 ，調(diào)整模型參數(shù) , 使 最大？ 評(píng)價(jià)問題解碼問題參數(shù)學(xué)習(xí)問題0.60.40.90.1RG120.30.20.70.8 =0.5

11、0.5TRRG基本算法：問題1：給定觀察序列 以及模型 , 計(jì)算終結(jié)：遞歸：定義前向變量：初始化：前向算法：前向算法舉例：.6.2.2.2.5.3.0.3.7RGB123.5.6.4.4.1 =1 0 0TRRGB1231.6.60.2.00.0.0.5.6.18.6.2.048.0.4.2.1.0.4.0.5.2.018.6.5.0504.01116.4.5.1.3.4.3.5.2.0018.6.3.01123.01537.4.3.1.7.4.7 1 . t t+1 .a1jat1yN.yi.yj.y1atNatiaNjaij前向法示意圖后向法定義后向變量終結(jié)：遞歸：初始化：問題2：給定觀察

12、序列 以及模型，如何選擇一個(gè)對(duì)應(yīng)的狀態(tài)序列 ，使得Y能夠最為合理的解釋觀察序列X？定義：要找的就是T時(shí)刻 所代表的那個(gè)狀態(tài)序列Viterbi 算法：Viterbi 算法：初始化遞歸結(jié)束得到最優(yōu)路徑.6.2.2.2.5.3.0.3.7RGB123.5.6.4.4.1 =1 0 0TRRGB.61.60.2.00.0.0.5.2.018.6.5.036.00576.4.5.1.3.4.3.5.6.18.6.2.048.0.4.2.1.0.4.0.5.2.0018.4.3.00648.1.7.01008.6.3.4.7Viterbi 算法舉例：思想：給定一個(gè)模型和輸出字符序列，任意設(shè)定初始參數(shù)值，通

13、過不斷循環(huán)更新參數(shù)的方法，設(shè)法達(dá)到最優(yōu)。Baum 1970算法步驟：2. 基于 0 以及觀察值序列X，訓(xùn)練新模型 ；1. 初始模型（待訓(xùn)練模型）0,3. 如果 logP(X| ) - log(P(X| 0) Delta，說明訓(xùn)練已經(jīng)達(dá)到預(yù)期效果， 算法結(jié)束。4. 否則，令 0 ，繼續(xù)第2步工作 問題3：給定觀察序列 ，調(diào)整模型參數(shù) , 使 最大？ Baum-Welch算法定義：重新估計(jì)該算法又稱為向前向后算法（Forward-backward algorithm）經(jīng)常得到局部最優(yōu)解HMMs等生產(chǎn)式模型存在的問題：1.由于生成模型定義的是聯(lián)合概率，必須列舉所有觀察序列的可能值，這對(duì)多數(shù)領(lǐng)域來說是

14、比較困難的。2.基于觀察序列中的每個(gè)元素都相互條件獨(dú)立。即在任何時(shí)刻觀察值僅僅與狀態(tài)（即要標(biāo)注的標(biāo)簽）有關(guān)。對(duì)于簡單的數(shù)據(jù)集，這個(gè)假設(shè)倒是合理。但大多數(shù)現(xiàn)實(shí)世界中的真實(shí)觀察序列是由多個(gè)相互作用的特征和觀察序列中較長范圍內(nèi)的元素之間的依賴而形成的。 四、最大熵模型（Maximum Entropy Model，MEM） 最大熵的原理認(rèn)為，從不完整的信息（例如有限數(shù)量的訓(xùn)練數(shù)據(jù)）推導(dǎo)出的唯一合理的概率分布應(yīng)該在滿足這些信息提供的約束條件下?lián)碛凶畲箪刂?。求解這樣的分布是一個(gè)典型的約束優(yōu)化問題。 最大熵模型主要是在已有的一些限制條件下估計(jì)未知的概率分布。熵的計(jì)算公式：熵的性質(zhì)： 其中X在離散分布時(shí)是隨機(jī)

15、變量的個(gè)數(shù)； 當(dāng)X為確定值，即沒有變化的可能時(shí)，左邊等式成立； 可以證明，當(dāng)X服從均勻分布時(shí)，右邊等式成立，即均勻分布時(shí)熵最大。定義條件熵模型目的定義特征函數(shù)約束條件（1）（2）該條件約束優(yōu)化問題的Lagrange函數(shù)最大熵模型：最大熵模型的概率圖2 不同之處無向圖模型因子是勢函數(shù)，需要全局歸一有向圖模型因子是概率分布、無需全局歸一有向圖模型和無向圖模型的對(duì)比1 共同之處將復(fù)雜的聯(lián)合分布分解為多個(gè)因子的乘積3 優(yōu)缺點(diǎn)無向圖模型中勢函數(shù)設(shè)計(jì)不受概率分布約束，設(shè)計(jì)靈活，但全局歸一代價(jià)高有向圖模型無需全局歸一、訓(xùn)練相對(duì)高效序列序列HMMsMEMs？NBsMEMM：用一個(gè)P(yi | yi-1 ,xi

16、)分布來替代HMM中的兩個(gè)條件概率分布，它表示從先前狀態(tài)，在觀察值下得到當(dāng)前狀態(tài)的概率，即根據(jù)前一狀態(tài)和當(dāng)前觀察預(yù)測當(dāng)前狀態(tài)。每個(gè)這樣的分布函數(shù)都是一個(gè)服從最大熵的指數(shù)模型。HMM：狀態(tài)集合Y，觀察值集合X， 兩個(gè)狀態(tài)轉(zhuǎn)移概率：從yi-1到y(tǒng)i的條件概率分布P(yi | yi-1)，狀態(tài)yi的輸出觀察值概率P (xi| yi)，初始概率P0(y).HMMMEMM六、最大熵馬爾可夫模型（MEMM）參數(shù)學(xué)習(xí)目的：通過學(xué)習(xí)a使得MEMM中的每個(gè)轉(zhuǎn)換函數(shù)達(dá)到最大熵。GIS（Generalized Iterative Scaling）算法編碼問題Viterbi算法的思想MEMM存在的問題：標(biāo)記偏見（ L

17、abel Bias Problem）問題序列序列HMMsMEMslinear-chain CRFNBs五、條件隨機(jī)場（conditional random fields，CRF）簡單地講，隨機(jī)場可以看成是一組隨機(jī)變量的集合（這組隨機(jī)變量對(duì)應(yīng)同一個(gè)樣本空間）。當(dāng)給每一個(gè)位置按照某種分布隨機(jī)賦予一個(gè)值之后，其全體就叫做隨機(jī)場。當(dāng)然，這些隨機(jī)變量之間可能有依賴關(guān)系，一般來說，也只有當(dāng)這些變量之間有依賴關(guān)系的時(shí)候，我們將其單獨(dú)拿出來看成一個(gè)隨機(jī)場才有實(shí)際意義。馬爾科夫隨機(jī)場（MRF）對(duì)應(yīng)一個(gè)無向圖。這個(gè)無向圖上的每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)隨機(jī)變量，節(jié)點(diǎn)之間的邊表示節(jié)點(diǎn)對(duì)應(yīng)的隨機(jī)變量之間有概率依賴關(guān)系。因此，M

18、RF的結(jié)構(gòu)本質(zhì)上反應(yīng)了我們的先驗(yàn)知識(shí)哪些變量之間有依賴關(guān)系需要考慮，而哪些可以忽略。具有馬爾科夫性質(zhì)：離當(dāng)前因素比較遙遠(yuǎn)(這個(gè)遙遠(yuǎn)要根據(jù)具體情況自己定義）的因素對(duì)當(dāng)前因素的性質(zhì)影響不大?，F(xiàn)在，如果給定的MRF中每個(gè)隨機(jī)變量下面還有觀察值，我們要確定的是給定觀察集合下，這個(gè)MRF的分布，也就是條件分布，那么這個(gè)MRF就稱為CRF。它的條件分布形式完全類似于MRF的分布形式，只不過多了一個(gè)觀察集合x。最通用角度來看，CRF本質(zhì)上是給定了觀察值 (observations)集合的MRF。CRF定義：設(shè)G=（V，E）是一個(gè)無向圖，是以G中節(jié)點(diǎn)v為索引的隨機(jī)變量構(gòu)成的集合。在給定 的條件下，如果每個(gè)隨機(jī)

19、變量 服從馬爾可夫?qū)傩?，即則 就構(gòu)成一個(gè)條件隨機(jī)場。 最簡單且最常用的是一階鏈?zhǔn)浇Y(jié)構(gòu)，即線性鏈結(jié)構(gòu)（Linear-chain CRFs）Linear-chain CRFs 模型：令 表示觀察序列， 是有限狀態(tài)的集合，根據(jù)隨機(jī)場的基本理論：對(duì)于觀察序列的標(biāo)記位置i-1與i之間的轉(zhuǎn)移特征函數(shù)觀察序列的i位置的狀態(tài)特征函數(shù)將兩個(gè)特征函數(shù)統(tǒng)一為：關(guān)鍵問題1.特征函數(shù)的選擇2.參數(shù)估計(jì)3.模型推斷特征函數(shù)的選取直接關(guān)系模型的性能。從已經(jīng)標(biāo)注好的訓(xùn)練數(shù)據(jù)集學(xué)習(xí)條件隨機(jī)場模型的參數(shù)，即各特征函數(shù)的權(quán)重向量。在給定條件隨機(jī)場模型參數(shù)下，預(yù)測出最可能的狀態(tài)序列。1.特征函數(shù)的選擇CRFs模型中特征函數(shù)的形式定義

20、：在定義特征函數(shù)的時(shí)候，首先構(gòu)建觀察值上的真實(shí)特征b(x,i)的集合，即所有i時(shí)刻的觀察值x的真實(shí)特征，結(jié)合其對(duì)應(yīng)的標(biāo)注結(jié)果，就可以獲得模型的特征函數(shù)集。它是狀態(tài)特征函數(shù)和轉(zhuǎn)移特征函數(shù)的統(tǒng)一形式表示。特征函數(shù)通常是二值函數(shù)，取值要么為1要么為0。如果時(shí)刻 i 觀察值x是大寫開頭否則2.參數(shù)估計(jì)極大似然估計(jì)（Maximum Likelihood Estimation，MLE)假定對(duì)于訓(xùn)練數(shù)據(jù)有一組樣本集合 樣本是相互獨(dú)立的， 為訓(xùn)練樣本中(x,y)的經(jīng)驗(yàn)概率，取對(duì)數(shù)形式：對(duì)于某個(gè)條件模型 ，訓(xùn)練數(shù)據(jù)D的似然函數(shù)公式為：CRFs模型中極大似然函數(shù)：對(duì) 求導(dǎo)：模型分布中特征的期望等于經(jīng)驗(yàn)分布中的期望

21、值最大熵原理令上式等于0，求Lafferty提出兩個(gè)迭代縮放的算法用于估計(jì)條件隨機(jī)場的極大似然參數(shù) GIS算法（Generalised Iterative Scaling） IIS算法（Improved Iterative Scaling）迭代縮放是一種通過更新規(guī)則以更新模型中的參數(shù)，通過迭代改善聯(lián)合或條件模型分布的方法。更新規(guī)則如下：其中更新值 使得新的值 比原來的值 更接近極大似然值。1、迭代縮放迭代縮放的基本原理假定我們有一個(gè)以 為參數(shù)的模型并且要找到一組新的參數(shù)：使得在該參數(shù)條件下的模型具有更高的對(duì)數(shù)似然值。通過迭代，使之最終達(dá)到收斂。對(duì)于條件隨機(jī)場對(duì)數(shù)似然值的變化可以表示為：引入輔助

22、函數(shù)：定義為在觀察序列和標(biāo)記序列為(x,y)的條件下，特征值為1的特征的個(gè)數(shù)。根據(jù)尋找使 最大化的，使用迭代算法計(jì)算最大似然參數(shù)集。（A）將每個(gè) 設(shè)初始值；（B）對(duì)于每個(gè) ，計(jì)算 ， 即迭代過程：應(yīng)用更新規(guī)則 ，更新每個(gè)參數(shù)，直到收斂。GIS算法：GIS是迭代縮放的一種，為了確保參數(shù)收斂的結(jié)果達(dá)到全局最優(yōu)，GIS需要對(duì)特征集進(jìn)行約束，即令每個(gè)訓(xùn)練數(shù)據(jù)中的事件 。定義了一個(gè)全局修正特征S(x,y)：其中C是訓(xùn)練語料中所有的x和y情況下T(x,y)的最大值，即等于最大可能的特征個(gè)數(shù)，特征S(x,y)的加入確保了T(x,y)=C。假定對(duì)于所有的事件，條件隨機(jī)場選定的特征的總和是常量C。更新值按下式計(jì)

23、算1.GIS算法的收斂速度由計(jì)算更新值的步長確定。C值越大，步長越小，收斂速度就越慢；反之C值越小，步長越大，收斂的速度也就越快。問題：2.GIS算法是依賴于一個(gè)額外的全局修正特征S(x,y)，以確保對(duì)于每個(gè)(x,y)對(duì)的有效特征的總和是一個(gè)常量。但是一旦加入這個(gè)新的特征，就認(rèn)為這個(gè)特征和特征集中所有其他的特征之間是相互獨(dú)立的，并且它的參數(shù)也需要使用上式來更新。計(jì)算期望需要對(duì)所有可能的標(biāo)記序列求和，這將是一個(gè)指數(shù)級(jí)的計(jì)算過程。IIS算法：重新定義：將每個(gè)對(duì)觀察序列和標(biāo)記序列對(duì)(x,y)起作用的特征值的和近似等于對(duì)于觀察序列x的最大可能的觀察特征的和使用牛頓一拉夫森方法求解L-BFGS算法：Jo

24、rge Nocedal用Fortran語言實(shí)現(xiàn)了L-BFGS工具包來進(jìn)行條件隨機(jī)場的參數(shù)估計(jì)與訓(xùn)練，該數(shù)學(xué)工具包可從/nocedal/下載。另外，Taku Kudo實(shí)現(xiàn)了L-BFGS算法的c語言版本，該工具集成在了其開發(fā)的CRF+工具包中，網(wǎng)址為/taku/software/CRF+/。Dong C. Liu and Jorge Nocedal : 【On The Limited Memory BFGS Method For Large Scale Optimization】2、梯度算法3.模型推斷第二個(gè)問題通過Viterbi算法解決。Viterbi算法是一種動(dòng)態(tài)規(guī)劃算法，其思想精髓在于將全局

25、最佳解的計(jì)算過程分解為階段最佳解的計(jì)算。二、對(duì)于未標(biāo)記的序列，求其最可能的標(biāo)記。常見的兩個(gè)問題：一、在模型訓(xùn)練中，需要邊際分布 和 ；第一個(gè)問題采用前向后向法解決；最大熵馬爾科夫模型舉例基于文本的網(wǎng)絡(luò)地址信息抽取任務(wù)：完成地址，電話，傳真，E-mail 等信息的識(shí)別和抽取流程圖頁面預(yù)處理頁面文本中加入#用于保留結(jié)構(gòu)信息和頁面內(nèi)容的自然劃分，便于對(duì)文本頁面的進(jìn)一步處理。模型建立確定狀態(tài)集合Y ，觀察值（特征）集合 X狀態(tài)集合包含：郵編、電話、電郵、地址、聯(lián)系人、賬號(hào)、手機(jī)、網(wǎng)址、傳真，對(duì)于其他可能出現(xiàn)的狀態(tài)定義了“other”來代表。特征集合包含：“具有符號(hào)”“最大數(shù)字串長度為6”“最大數(shù)字串長

26、度為11”“最大數(shù)字長度大于15”“最大數(shù)字長度小于6，字符串總長度介于8到30”“最大數(shù)字長度小于6， 字符串總長度小于6”，“最大數(shù)字串長度介于6到11”“最大數(shù)字長度小于6，字符串總長度大于30”特征函數(shù) 表示數(shù)據(jù)集的特性：如果x只含有6位數(shù)字&y=郵編其他進(jìn)一步引入一系列的特征函數(shù)參數(shù)學(xué)習(xí)用上述的狀態(tài)和特征集對(duì)初步抽取樣本進(jìn)行統(tǒng)計(jì)，得到每個(gè)狀態(tài)所對(duì)應(yīng)的樣本集，通過對(duì)于每個(gè)這樣的樣本集合采用 GIS算法進(jìn)行參數(shù)學(xué)習(xí)，最終得到 MEMM。說明：GIS算法要求對(duì)于每一個(gè),特征之和達(dá)到一個(gè)常數(shù)C，即有如果不滿足，則令并加入一個(gè)修正函數(shù)，使得1.初始2.(a)計(jì)算每個(gè)特征的(b)(c)用當(dāng)前的

27、值計(jì)算(d)更新(e)滿足收斂條件，結(jié)束；否則轉(zhuǎn)到(b)GIS算法的步驟：通過GIS算法得到狀態(tài)轉(zhuǎn)移函數(shù)，這些狀態(tài)轉(zhuǎn)移函數(shù)的集合組成了MEMM模型識(shí)別和抽?。?）輸入觀察值序列（2）遞歸（3）結(jié)束改進(jìn)的Viterbi算法評(píng)測指標(biāo)召回率（Recall）=正確識(shí)別出的實(shí)體個(gè)數(shù)標(biāo)準(zhǔn)結(jié)果中實(shí)體的總數(shù)精確率（Precision）=正確識(shí)別出的實(shí)體個(gè)數(shù)識(shí)別出的實(shí)體總數(shù)關(guān)鍵：特征的選擇100%100%在中文信息處理領(lǐng)域，命名實(shí)體識(shí)別是各種自然語言處理技術(shù)的重要基礎(chǔ)。命名實(shí)體：人名、地名、組織名三類條件隨機(jī)場模型舉例中文命名實(shí)體識(shí)別模型形式關(guān)鍵：特征函數(shù)的確定適用于人名的特征模板“上下文”，指的是包括當(dāng)前詞w

28、0及其前后若干個(gè)詞的一個(gè)“觀察窗口”(w-n，w-n+1，w0，wn)。理論上來說，窗口越大，可利用的上下文信息越多，但窗口開得過大除了會(huì)嚴(yán)重降低運(yùn)行效率，還會(huì)產(chǎn)生過擬合現(xiàn)象；而窗口過小，特征利用的就不夠充分，會(huì)由于過于簡單而丟失重要信息。通過一些模板來篩選特征。模板是對(duì)上下文的特定位置和特定信息的考慮。還建立了若干個(gè)資源列表，包括：中國人名姓氏用表、中國人名名字用表、歐美俄人名常用字表、日本人名常用字表?！叭嗣闹附缭~”：主要包括稱謂詞、動(dòng)詞和副詞等，句首位置和標(biāo)點(diǎn)符號(hào)也可。根據(jù)指界詞與人名同現(xiàn)的概率的大小，將人名的左右指界詞各分為兩級(jí)，生成4個(gè)人名指界詞列表：定義了用于人名識(shí)別特征的原子模

29、板，每個(gè)模板都只考慮了一種因素：當(dāng)特征函數(shù)取特定值時(shí)，特征模板被實(shí)例化就可以得到具體的特征?！爱?dāng)前詞的前一個(gè)詞w-1在人名1級(jí)左指界詞列表中出現(xiàn)”If PBW1(w-1)=ture and y=personelse類似的，做地名、組織名的特征提取和選擇，并將其實(shí)例化，得到所有的特征函數(shù)。模型訓(xùn)練流程圖評(píng)測指標(biāo)正確識(shí)別的命名實(shí)體首部（尾部）的個(gè)數(shù)標(biāo)準(zhǔn)結(jié)果中命名實(shí)體首部（尾部）的的總數(shù)召回率（Recall）=100%精確率（Precision）=正確識(shí)別的命名實(shí)體首部（尾部）的個(gè)數(shù)識(shí)別出的命名實(shí)體首部（尾部）的總數(shù)100%F-值=2 精確率 召回率精確率+召回率整體評(píng)價(jià)：優(yōu)點(diǎn)：條件隨機(jī)場模型既具有

30、判別式模型的優(yōu)點(diǎn)，又具有產(chǎn)生式模型考慮到上下文標(biāo)記間的轉(zhuǎn)移概率，以序列化形式進(jìn)行全局參數(shù)優(yōu)化和解碼的特點(diǎn)，解決了其他判別式模型(如最大熵馬爾科夫模型)難以避免的標(biāo)記偏見問題。缺點(diǎn)：模型訓(xùn)練時(shí)收斂速度比較慢2007年，Charles Sutton，Andrew McCallum【Dynamic Conditional Random Fields: Factorized Probabilistic Models for Labeling and Segmenting Sequence Data】Asela Gunawardana等人【Hidden Conditional Random Fields for Phone Classification】2001 年，卡耐基梅隆大學(xué)的 Lafferty 教授針對(duì)序列數(shù)據(jù)處理提出了 CRF 模型?！綜onditi