CRF(条件随机场)与Viterbi(维特比)算法原理详解
摘自：https://mp.weixin.qq.com/s/GXbFxlExDtjtQe-OPwfokA
? ? ? ? ? ?https://www.cnblogs.com/zhibei/p/9391014.html
CRF（Conditional Random Field），即條件隨機場。經(jīng)常被用于序列標(biāo)注，其中包括詞性標(biāo)注，分詞，命名實體識別等領(lǐng)域。
Viterbi算法，即維特比算法。是一種動態(tài)規(guī)劃算法用于最可能產(chǎn)生觀測時間序列的-維特比路徑-隱含狀態(tài)序列，特別是在馬爾可夫信息源上下文、隱馬爾科夫模型、條件隨機場中
一、CRF基本概念
我們以命名實體識別NER為例，先介紹下NER的概念：
?
?
這里的label_alphabet中的b代表一個實體的開始，即begin；m代表一個實體的中部，即mid；e代表一個實體的結(jié)尾，即end；o代表不是實體，即None；<start>和<pad>分表代表這個標(biāo)注label序列的開始和結(jié)束，類似于機器翻譯的<SOS>和<EOS>。
?
?
這個就是word和label數(shù)字化后變成word_index，label_index。最終就變成下面的形式：
?
?
因為label有7種，每一個字被預(yù)測的label就有7種可能，為了數(shù)字化這些可能，我們從word_index到label_index設(shè)置一種分?jǐn)?shù)，叫做發(fā)射分?jǐn)?shù)emit：
?
?
看這個圖，有word_index 的 1 -> 到label_index 的 4的小紅箭頭，像不像發(fā)射過來的？此時的分?jǐn)?shù)就記作emit[1][4]。
另外，我們想想，如果單單就這個發(fā)射分?jǐn)?shù)來評價，太過于單一了，因為這個是一個序列，比如前面的label為o，那此時的label被預(yù)測的肯定不能是m或s，所以這個時候就需要一個分?jǐn)?shù)代表前一個label到此時label的分?jǐn)?shù)，我們叫這個為轉(zhuǎn)移分?jǐn)?shù)，即T：
?
?
如圖，橫向的label到label箭頭，就是由一個label到另一個label轉(zhuǎn)移的意思，此時的分?jǐn)?shù)為T[4][4]。
?
此時我們得出此時的word_index=1到label_index=4的分?jǐn)?shù)為emit[1][4]+T[4][4]。但是，CRF為了全局考慮，將前一個的分?jǐn)?shù)也累加到當(dāng)前分?jǐn)?shù)上，這樣更能表達(dá)出已經(jīng)預(yù)測的序列的整體分?jǐn)?shù)，最終的得分score為：
?
score[1][4] = score[0][4]+emit[1][4]+T[4][4]
?
所以整體的score就為：
?
?
最后的公式為這樣的：
?
?
其中X為word_index序列，y為預(yù)測的label_index序列。
?
因為這個預(yù)測序列有很多種，種類為label的排列組合大小。其中只有一種組合是對的，我們只想通過神經(jīng)網(wǎng)絡(luò)訓(xùn)練使得對的score的比重在總體的所有score的越大越好。而這個時候我們一般softmax化，即：
?
?
其中分子中的s為label序列為正確序列的score，分母s為每中可能的score。
?
這個比值越大，我們的預(yù)測就越準(zhǔn)，所以，這個公式也就可以當(dāng)做我們的loss，可是loss一般都越小越好，那我們就對這個加個負(fù)號即可，但是這個最終結(jié)果手機趨近于1的，我們實驗的結(jié)果是趨近于0的，這時候log就派上用場了，即：
?
?
當(dāng)然這個log也有平滑結(jié)果的功效。
?
二、計算過程
就是為了求得所有預(yù)測序列可能的得分和。我們第一種想法就是每一種可能都求出來，然后累加即可。可是，比如word長為10，那么總共需要計算累加10^7次，這樣的計算太耗時間了。那么怎么計算的時間快呢？這里有一種方法：
?
?
因為剛開始為<start>即為5，然后word_index為0的時候的所有可能的得分，即s[0][0],s[0][1]...s[0][6]中間的那部分。然后計算word_index為1的所有s[1][0],s[1][1]...s[1][6]的得分，這里以s[1][0]為例，即紅箭頭的焦點處：這里表示所有路徑到這里的得分總和。
?
?
這里每個節(jié)點，都表示前面的所有路徑到當(dāng)前節(jié)點路徑的所有得分之和。所以，最后的s[4][6]即為最終的得分之和，即：
?
?
?
計算gold分?jǐn)?shù)，即：S(X,y)?這事只要通過此時的T和emit函數(shù)計算就能得出，計算公式上面已經(jīng)給出了：
?
?
然后就是重復(fù)上述的求解所有路徑的過程，將總和和gold的得分都求出來，得到loss，然后進(jìn)行更新T，emit即可。（實現(xiàn)的話，其實emit是隱層輸出，不是更新的對象，之后的實現(xiàn)會講）
解碼過程，就是動態(tài)規(guī)劃，但是在這種模型中，通常叫做維特比算法。如圖：
?
?
大概思路就是這次的每個節(jié)點不是求和，而是求max值和記錄此max的位置。就是這樣：
?
?
最后每個節(jié)點都求了出來，結(jié)果為：
?
?
最后，根據(jù)最后的節(jié)點，向前選取最佳的路徑。過程為：、
?
?
?
三、Viterbi(維特比)算法原理詳解
維特比算法是一種動態(tài)規(guī)劃算法用于最可能產(chǎn)生觀測時間序列的-維特比路徑-隱含狀態(tài)序列，特別是在馬爾可夫信息源上下文和隱馬爾科夫模型中。術(shù)語“維特比路徑”和“維特比算法”也被用于尋找觀察結(jié)果最有可能解釋的相關(guān)動態(tài)規(guī)劃算法。例如在統(tǒng)計句法分析中動態(tài)規(guī)劃可以被用于發(fā)現(xiàn)最有可能的上下文無關(guān)的派生的字符串，有時被稱為“維特比分析”。
利用動態(tài)規(guī)劃尋找最短路徑
動態(tài)規(guī)劃是運籌學(xué)的一個分支，是求解決策過程最優(yōu)化的數(shù)學(xué)方法，通常情況下應(yīng)用于最優(yōu)化的問題，這類問題一般有很多可行的解，每個解有一個值，而我們希望從中找到最優(yōu)的答案。
在計算機科學(xué)領(lǐng)域，應(yīng)用動態(tài)規(guī)劃的思想解決的最基本的一個問題就是：尋找有向無環(huán)圖（籬笆網(wǎng)絡(luò)）當(dāng)中兩個點之間的最短路徑（實際應(yīng)用于地圖導(dǎo)航、語音識別、分詞、機器翻譯等等）
下面舉一個比較簡單的例子做說明：求S到E的最短路徑，如下圖（各點之間距離不相同）：
?
?
我們知道，要找到S到E之間最短路徑，最容易想到的方法就是窮舉法。也就是把所有可能的路徑都例舉出來。從S走向A層共有4種走法，從A層走向B層又有4種走法，從B層走向C層又有4種走法，然后C層走向E點只有一種選擇。所以最終我們窮舉出了4*4*4=64種可能。顯然，這種方法必定可行，但在實際的應(yīng)用當(dāng)中，對于數(shù)量及其龐大的節(jié)點數(shù)和邊數(shù)的圖，其計算復(fù)雜度也將會變得非常大，而計算效率也會隨之降低。
?
?
因此，這里選擇適用一種基于動態(tài)規(guī)劃的方式來尋找最佳路徑。
所謂動態(tài)規(guī)劃。其核心就是“動態(tài)”的概念，把大的問題細(xì)分為多個小的問題，基于每一步的結(jié)果再去尋找下一步的策略，通過每一步走過之后的局部最優(yōu)去尋找全局最優(yōu)，這樣解釋比較抽象，下面直接用回剛剛的例子說明。如下圖：
?
?
首先，我們假設(shè)S到E之間存在一條最短路徑（紅色），且這條路徑經(jīng)過C2點，那么我們便一定能夠確定從S到C2的64條（4*4*4=64）子路經(jīng)當(dāng)中，該子路經(jīng)一定最短。（證明：反證法。如果S到C2之間存在一條更短的子路經(jīng)，那么便可以用它來替代原先的路徑，而原來的路徑顯然就不是最短了，這與原假設(shè)自相矛盾）。
同理，我們也可以得出從S到B2點為兩點間最短子路經(jīng)的結(jié)論。這時候，真相便慢慢浮出水面：既然如此，我們計算從S點出發(fā)到點C2的最短路徑，是不是只要考慮從S出發(fā)到B層所有節(jié)點的最短路徑就可以了？答案是肯定的！因為，從S到E的“全局最短”路徑必定經(jīng)過這些“局部最短”子路經(jīng)。沒錯！這就是上面提及到的通過局部最優(yōu)的最優(yōu)去尋找全局最優(yōu)，問題的規(guī)模被不斷縮小！
接下來，要揭曉答案了！繼續(xù)看下圖：
?
?
回顧之前的分析：我們計算從S到C2點的最短路徑時候只需要考慮從S出發(fā)到B層所有節(jié)點的最短路徑，B層也是。對B2來說，一共有4條路線可達(dá)，分別是A1->B2,A2->B2,A3->B2, A4->B2。我們需要做的就是A2->B2這條路線保留，而其他3條刪掉（因為根據(jù)以上的分析，他們不可能構(gòu)成全程的最短路線）。Ok，來到這里，我們會發(fā)現(xiàn)一個和小“漏洞”，這段S->A2->B2->C2->E的路線只是我一廂情愿的假設(shè)，最短路徑下不一定是經(jīng)過以上這些點。所以，我們要把每層的每個節(jié)點都考慮進(jìn)來。
以下是具體做法：
step1：從點S出發(fā)。對于第一層的4個節(jié)點，算出他們的距離d(S,A1),d(S,A2),d(S,A3),d(S,A4),因為只有一步，所以這些距離都是S到它們各自的最短距離
step2:對于B層的所有節(jié)點(B1,B2,B3,B4),要計算出S到他們的最短距離。我們知道，對于特定的節(jié)點B2，從S到它的路徑可以經(jīng)過A層的任何一個節(jié)點(A1,A2,A3,A4)。對應(yīng)的路徑長就是d(S,B2)=d(S,Ai)+d(Ai,B2)（其中i=1，2，3，4）。由于A層有4個節(jié)點（即i有4個取值），我們要一一計算，然后找到最小值。這樣，對于B層的每個節(jié)點，都需要進(jìn)行4次運算，而B層有4個節(jié)點，所以共有4*4=16次運算。
step3:這一步是該算法的核心。我們從step2計算得出的階段結(jié)果只保留4個最短路徑值（每個節(jié)點保留一個）。那么，若從B層走向C層來說，該步驟的級數(shù)已經(jīng)不再是4*4，而是變成4！也就是說，從B層到C層的最短路徑只需要基于B層得出的4個結(jié)果來計算。這種方法一直持續(xù)到最后一個狀態(tài)，每一步計算的復(fù)雜度為相鄰兩層的計算復(fù)雜度為4*4乘積的正比！再通俗點說，連接著兩兩相鄰層的計算符合變成了“+”號，取代了原先的“*”號。用這種方法，只需要進(jìn)行4*4*2=32次計算！
其實上述的算法就是著名的維特比算法，事實上非常簡單！
若假設(shè)整個網(wǎng)格的寬度為D，網(wǎng)格長度為N，那么弱適用窮舉法整個最短路徑的算法復(fù)雜度為O(D^N),而適用這種算法的計算復(fù)雜度為O（ND^2）.試想一下，弱D與N都非常大，適用維特比算法的效率將會提高幾個數(shù)量級！、
?
---------------------
作者：Data_driver
來源：CSDN
原文：https://blog.csdn.net/qq_42189083/article/details/89350890
版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請附上博文鏈接！
總結(jié)
以上是生活随笔為你收集整理的CRF(条件随机场)与Viterbi(维特比)算法原理详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： BiLSTM-CRF学习笔记（原理和理解
- 下一篇： 条件随机场(CRF) - 4 - 学习方