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

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

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

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

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

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

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

7、行動(dòng)下(比如walk時(shí))，每種狀態(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)前行動(dòng)下，某個(gè)狀態(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”需要如下幾個(gè)輸入?yún)?shù)，“obs”是觀測(cè)序列，比如[`walk``shop``clean`]“states”是隱狀態(tài)的集合；“start_p”是初始的概率，“trans_p”是轉(zhuǎn)移概率；“emit_p”是產(chǎn)生概率。這個(gè)算法算法在位圖T和U上做操作，每個(gè)都是一個(gè)從一個(gè)狀態(tài)到一個(gè)三元組(probv_pathv_prob)的映射，其中prob表示從開始到現(xiàn)在這個(gè)狀態(tài)的概率之和；v_path