viterbi算法與實(shí)現(xiàn)(注釋版)

1、Viterbi算法Viterbi算法算法是一種動態(tài)規(guī)劃算法算法，用來尋找由觀測信息產(chǎn)生(ObservedEvent)的最可能隱狀態(tài)序列(Viterbi路徑路徑)，這種方法通常用在隱馬爾可夫模型中。向前算法算法是一個類似的算法算法，用來計(jì)算一串觀測事件發(fā)生的概率。這些算法算法都屬于信息論的范疇。這個算法算法做一連串的假設(shè)。首先，觀測事件和隱事件必須處于序列中。這個序列通常是關(guān)于時間的。第二，這兩個序列需要對應(yīng)，一個觀測事件的實(shí)例必須與一個

2、隱事件相關(guān)聯(lián)。第三，計(jì)算在特定時間點(diǎn)t的最可能隱序列必須只依賴于位于t的觀測事件，和t1處的最可能序列。這些假設(shè)在一階隱馬爾可夫模型中都要被滿足。Viterbi路徑路徑和Viterbi算法算法同時遵循尋找單一最可能觀測解釋的相關(guān)動態(tài)規(guī)劃算法算法。例如，在統(tǒng)計(jì)分析中的動態(tài)規(guī)劃算法算法能應(yīng)用于尋找一個字符串的單個最相似上下文無關(guān)推導(dǎo)，即“Viterbi推導(dǎo)”。Viterbi算法算法是由rewViterbi在1967年提出的，是一種用于有噪聲

3、的數(shù)據(jù)鏈路中錯誤糾正的模型，并廣泛應(yīng)用在卷積碼的解碼中，例如CDMAGSM數(shù)字蜂窩，撥號調(diào)制解調(diào)器，衛(wèi)星通信，深空通信和802.11無線局域網(wǎng)等?，F(xiàn)在也廣泛的應(yīng)用在語言理解，關(guān)鍵詞匹配，計(jì)算機(jī)語言學(xué)，生物信息學(xué)等。例如，在語音理解中，聽覺信號被認(rèn)為是觀測事件的序列，文字串被認(rèn)為是“潛在的原因”。Viterbi算法算法能夠找到對應(yīng)聽覺信號的最可能文字序列。概要概要前面提到的假設(shè)可以被如下概括。Viterbi算法算法在一個狀態(tài)機(jī)的假設(shè)上做操

4、作。也就是說，在任何時間系統(tǒng)被抽象為一些狀態(tài)。這些狀態(tài)是有限的，盡管很大。每個狀態(tài)被表示為一個節(jié)點(diǎn)。多個狀態(tài)的序列(路徑路徑)往往都能產(chǎn)生同一個給定的狀態(tài)，但其中只有一條是最可能產(chǎn)生這個狀態(tài)的，被稱作“生存路徑路徑”。這是一個最基礎(chǔ)的假設(shè)，因?yàn)檫@個算法算法會檢測所有的可能路徑路徑并只保留一個最可能的路徑路徑。這種策略并不需要計(jì)算所有的路徑路徑，只需要一個狀態(tài)一個路徑路徑而已。第二個關(guān)鍵的假設(shè)是前一個狀態(tài)到一個新狀態(tài)的轉(zhuǎn)移被一個遞增的度量

5、描述，通常是一個數(shù)字。這種轉(zhuǎn)移是從實(shí)踐中計(jì)算而來的。第三個假設(shè)是事件在一個路徑路徑上是累加的。所以整個算法算法的關(guān)鍵是計(jì)算每個狀態(tài)的數(shù)值。當(dāng)發(fā)生了一個事件，算法算法結(jié)合上一個可能狀態(tài)與轉(zhuǎn)換產(chǎn)生的增量度量，并從中選擇一個最優(yōu)的，據(jù)此來檢測向前的新狀態(tài)。增量度量由事件觸發(fā)，并由舊狀態(tài)與新狀態(tài)間的轉(zhuǎn)換決定。例如，在數(shù)據(jù)交換中，可能發(fā)生一半的符號由奇狀態(tài)轉(zhuǎn)換，而另一半由偶狀態(tài)開始轉(zhuǎn)換。同時，在很多例子中，狀態(tài)轉(zhuǎn)換圖是不連續(xù)的。一個簡單的例子，一

6、個汽車有三個狀態(tài)，向前，停止和向后，狀態(tài)從向前倒向后是不允許的。他必須先進(jìn)入停止?fàn)顟B(tài)。在計(jì)算出增量度量和和狀態(tài)度量后，只有最好的幸存，而其他的被舍棄。這種基礎(chǔ)算法算法有一個改進(jìn)，允許向前搜索和向后搜索。foutputinobs:#第一層循環(huán)用來遍歷序列U=fnext_stateinstates:#第二層循環(huán)total=0argmax=Nonevalmax=0fsource_stateinstates:#第三層循環(huán)結(jié)合第二層循環(huán)，找到當(dāng)前

7、行動下(比如walk時)，每種狀態(tài)下的最優(yōu)路徑，概率等信息。(probv_pathv_prob)=T[source_state]p=emit_p[source_state][output]trans_p[source_state][next_state]prob=pv_prob=ptotal=probifv_probvalmax:argmax=v_path[next_state]valmax=v_probU[next_state]=(t

8、otalargmaxvalmax)#當(dāng)前行動下，某個狀態(tài)的最優(yōu)路徑和最大概率。T=U#更新記錄，為下次計(jì)算做準(zhǔn)備。##applysummaxtothefinalstates:total=0argmax=Nonevalmax=0fstateinstates:(probv_pathv_prob)=T[state]total=probifv_probvalmax:argmax=v_pathvalmax=v_probreturn(totalar

9、gmaxvalmax)函數(shù)“fward_viterbi”需要如下幾個輸入?yún)?shù)，“obs”是觀測序列，比如[`walk``shop``clean`]“states”是隱狀態(tài)的集合；“start_p”是初始的概率，“trans_p”是轉(zhuǎn)移概率；“emit_p”是產(chǎn)生概率。這個算法算法在位圖T和U上做操作，每個都是一個從一個狀態(tài)到一個三元組(probv_pathv_prob)的映射，其中prob表示從開始到現(xiàn)在這個狀態(tài)的概率之和；v_path