簡介

鑒于維特比算法可解決多步驟中每步多選擇模型的最優(yōu)選擇問題，本文簡要介紹了維特比算法的基本理論，并從源代碼角度對維特比算法進(jìn)行剖析，并對源碼中涉及的要點(diǎn)進(jìn)行了解讀，以便能快速應(yīng)用該算法解決自然語言處理中的問題。

理論

維特比算法是一個(gè)特殊但應(yīng)用最廣的動(dòng)態(tài)規(guī)劃算法，利用動(dòng)態(tài)規(guī)劃，可以解決任何一個(gè)圖中的最短路徑問題。而維特比算法是針對一個(gè)特殊的圖——籬笆網(wǎng)絡(luò)的有向圖(Lattice )的最短路徑問題而提出的。 凡是使用隱含馬爾可夫模型描述的問題都可以用它來解碼，包括今天的數(shù)字通信、語音識(shí)別、機(jī)器翻譯、拼音轉(zhuǎn)漢字、分詞等。——摘自《數(shù)學(xué)之美》

給定某一個(gè)觀察者序列Y= {y1, y2, ..., yn}， 而產(chǎn)生它們的隱含狀態(tài)為X={x1, x2, ..., xn}， 其中在任意時(shí)刻t(即觀察者)下，其對應(yīng)的隱含狀態(tài)存在多種可能；若將每個(gè)觀察者視為一步，則每步是一個(gè)多選擇問題。如圖-1所示為維特比算法的數(shù)學(xué)表達(dá)式， 其目標(biāo)即為獲取最大概率值下的隱含狀態(tài)序列：

圖-1 維比特算法數(shù)學(xué)表達(dá)式

此外，若將上述隱含狀態(tài)序列按值進(jìn)行展開，則會(huì)得到常見的籬笆網(wǎng)絡(luò)結(jié)構(gòu)，如圖-2所示：

圖-2 籬笆網(wǎng)絡(luò)

維特比算法利用動(dòng)態(tài)規(guī)劃思想求解概率最大路徑(可理解為求圖最短路徑問題)， 其時(shí)間復(fù)雜度為O(N*L*L)，其中N為觀察者序列長度，L為隱含狀態(tài)大小。該算法的核心思想是：通過綜合狀態(tài)之間的轉(zhuǎn)移概率和前一個(gè)狀態(tài)的情況計(jì)算出概率最大的狀態(tài)轉(zhuǎn)換路徑，從而推斷出隱含狀態(tài)的序列的情況，即在每一步的所有選擇都保存了前繼所有步驟到當(dāng)前步驟當(dāng)前選擇的最小總代價(jià)(或者最大價(jià)值)以及當(dāng)前代價(jià)的情況下后續(xù)步驟的選擇。依次計(jì)算完所有步驟后，通過回溯的方法找到最優(yōu)選擇路徑。

簡單來說，在計(jì)算第t+1時(shí)刻的最短路徑時(shí)，只需要考慮從開始到當(dāng)前t時(shí)刻下k個(gè)狀態(tài)值的最短路徑和當(dāng)前狀態(tài)值到第t+1狀態(tài)值的最短路徑即可。如求t=3時(shí)的最短路徑，等于求t=2時(shí)的所有狀態(tài)結(jié)點(diǎn)x2t(見上圖-2所示)的最短路徑再加上t=2到t=3的各節(jié)點(diǎn)的最短路徑。

以下將從源代碼的角度，對維比特算法進(jìn)行剖析，分別從wikipedia、HanLP以及個(gè)人冗余代碼3種實(shí)現(xiàn)方式進(jìn)行剖析。

源碼之Wiki(有改動(dòng))

public classViterbi {private static classTNode {public int[] v_path; //節(jié)點(diǎn)路徑

public double v_prob; //概率累計(jì)值

public TNode( int[] v_path, doublev_prob) {this.v_path =copyIntArray(v_path);this.v_prob =v_prob;

}

}private static int[] copyIntArray(int[] ia) { //數(shù)組拷貝

int[] newIa = new int[ia.length];

System.arraycopy(ia,0, newIa, 0, ia.length); //較wiki源碼有改動(dòng)

returnnewIa;

}private static int[] copyIntArray(int[] ia, int newInt) { //數(shù)組拷貝

int[] newIa = new int[ia.length + 1];

System.arraycopy(ia,0, newIa, 0, ia.length); //較wiki的源碼稍有改動(dòng)

newIa[ia.length] =newInt;returnnewIa;

}//forwardViterbi(observations, states, start_probability,//transition_probability, emission_probability)

public int[] forwardViterbi(String[] y, String[] X, double[] sp,double[][] tp, double[][] ep) {

TNode[] T= newTNode[X.length];for (int state = 0; state < X.length; state++) {int[] intArray = new int[1];

intArray[0] =state;

T[state]= new TNode(intArray, sp[state] * ep[state][0]);

}for (int output = 1; output < y.length; output++) {

TNode[] U= newTNode[X.length];for (int next_state = 0; next_state < X.length; next_state++) {int[] argmax = new int[0];double valmax = 0;for (int state = 0; state < X.length; state++) {int[] v_path =copyIntArray(T[state].v_path);double v_prob =T[state].v_prob;double p = ep[next_state][output] *tp[state][next_state];

v_prob*= p; //核心元語

if (v_prob > valmax) { //每一輪會(huì)增加節(jié)點(diǎn)

if (v_path.length == y.length) { //最終截止

argmax =copyIntArray(v_path);

}else{

argmax= copyIntArray(v_path, next_state); //增加新的節(jié)點(diǎn)

}

valmax=v_prob;

}

}//the number 3 for

U[next_state] = newTNode(argmax, valmax);

}//the number 2 for

T =U;

}//apply sum/max to the final states:

int[] argmax = new int[0];double valmax = 0;for (int state = 0; state < X.length; state++) {int[] v_path =copyIntArray(T[state].v_path);double v_prob =T[state].v_prob;if (v_prob >valmax) {

argmax=copyIntArray(v_path);

valmax=v_prob;

}

}returnargmax;

}

}

該算法的核心在于，內(nèi)部類TNode中維護(hù)了一個(gè)動(dòng)態(tài)數(shù)組v_path， 它隨著每一輪的迭代，即觀察者序列按序迭代時(shí)，其路徑長度在動(dòng)態(tài)遞增；同時(shí)伴隨著概率累積值v_prob在更新。由于v_path中是按照正序維護(hù)了觀察者序列按序到達(dá)最終節(jié)點(diǎn)中的局部概率最大值所對應(yīng)的隱含狀態(tài)序列，因此該算法不需要進(jìn)行回溯求解路徑。

源碼之HanLP

public classViterbi {/*** 求解HMM模型

*@paramobs 觀測序列

*@paramstates 隱狀態(tài)

*@paramstart_p 初始概率(隱狀態(tài))

*@paramtrans_p 轉(zhuǎn)移概率(隱狀態(tài))

*@paramemit_p 發(fā)射概率 (隱狀態(tài)表現(xiàn)為顯狀態(tài)的概率)

*@return最可能的序列*/

public static int[] compute(int[] obs, int[] states,double[] start_p, double[][] trans_p, double[][] emit_p) {double[][] V = new double[obs.length][states.length];int[][] path = new int[states.length][obs.length];for (inty : states) {

V[0][y] = start_p[y] * emit_p[y][obs[0]];

path[y][0] =y;

}for (int t = 1; t < obs.length; ++t) {int[][] newpath = new int[states.length][obs.length];for (inty : states) {double prob = -1;intstate;for (inty0 : states) {double nprob = V[t - 1][y0] * trans_p[y0][y]

* emit_p[y][obs[t]]; //核心元語

if (nprob >prob) {

prob=nprob;

state=y0;

V[t][y]= prob; //記錄最大概率

System.arraycopy(path[state], 0, newpath[y], 0, t); //記錄路徑

newpath[y][t] =y;

}

}

}

path=newpath;

}double prob = -1;int state = 0;for (inty : states) {if (V[obs.length - 1][y] >prob) {

prob= V[obs.length - 1][y];

state=y;

}

}returnpath[state];

}

}

從上述代碼可知，HanLP與Wiki中的實(shí)現(xiàn)比較類似，按照正序維護(hù)了最大概率所對應(yīng)的路徑，因此也無需進(jìn)行回溯。

源碼之冗余代碼

public static List Viterbi(int[] obState, String[] termList,double[] hiddenState, double[][]transitionMatrix, double[][]emitterMatrix) {int len =obState.length;int labelSize =hiddenState.length;double[][] result = new double[len][labelSize];int[][] max = new int[len][labelSize];double tmp = 0;//初始化

for (int i = 0; i < labelSize; i++) {

result[0][i] = hiddenState[i] * emitterMatrix[i][obState[0]]; //對初始行進(jìn)行賦值

}//迭代

for (int i = 1; i < len; i++) {for (int j = 0; j < labelSize; j++) {

tmp= result[i-1][0] * transitionMatrix[0][j] *emitterMatrix[j][obState[i]];

max[i][j]= 0;for (int k = 1; k < labelSize; k++) { //初始值時(shí)從0開始，則此處從1開始

double prob = result[i-1][k] * transitionMatrix[k][j]

* emitterMatrix[j][obState[i]]; //核心元語

if (prob >tmp) {

tmp=prob;

max[i][j]= k; //保存路徑節(jié)點(diǎn)

}

result[i][j]=tmp;

}

}

}//從結(jié)束點(diǎn)開始

List adjList = new ArrayList();int maxNode = 0;double maxValue = result[len-1][0];for (int k = 1; k < labelSize; k++) { //maxValue 默認(rèn)從0開始, 則此處從1開始

if (result[len-1][k] >maxValue) {

maxValue= result[len-1][k];

maxNode=k;

}

}

adjList.add(maxNode);//回溯

for (int i = len-1; i > 0; i--) {

maxNode=max[i][maxNode];

adjList.add(maxNode);

}//獲取結(jié)果

List retList = new ArrayList();for (int i = adjList.size()-1; i >= 0; i--) {

retList.add(adjList.get(i));

}returnretList;

}

該部分冗余代碼為個(gè)人所寫，從代碼流程來看，它從初始化到回溯整個(gè)過程都進(jìn)行詳細(xì)的闡述。尤其需要注意注釋中“默認(rèn)從0開始, 則此處從1開始”的部分，其中更多的從代碼簡化的角度進(jìn)行了一定的優(yōu)化工作。

總結(jié)

上述3種實(shí)現(xiàn)，均可以在實(shí)際工程中應(yīng)用，個(gè)人強(qiáng)烈推薦采用第1和第2，第3種作為學(xué)習(xí)可以參考。維特比算法只是解決隱馬爾科夫第三個(gè)問題(求觀察序列的最可能的標(biāo)注序列)的一種實(shí)現(xiàn)方式，因此維特比算法和隱馬爾科夫模型不能等價(jià)。涉及多步驟每步多選擇模型的最優(yōu)選擇問題，可采用該算法來解決。

參考內(nèi)容：

1) 吳軍. 數(shù)學(xué)之美.

2) HanLP-Viterbi:?https://github.com/hankcs/Viterbi/blob/master/src/com/hankcs/algorithm/Viterbi.java

3) Wikipedia-Viterbi：https://en.wikibooks.org/wiki/Algorithm_Implementation/Viterbi_algorithm

4)?http://www.cnblogs.com/ryuham/p/4686496.html

如果，您認(rèn)為閱讀這篇博客讓您有些收獲，不妨點(diǎn)擊一下右下角的【推薦】。

如果，您希望更容易地發(fā)現(xiàn)我的新博客，不妨點(diǎn)擊一下左下角的【關(guān)注我】。

如果，您對我的博客所講述的內(nèi)容有興趣，請繼續(xù)關(guān)注我的后續(xù)博客，我是【志青云集】。

本文版權(quán)歸作者和博客園共有，歡迎轉(zhuǎn)載，但未經(jīng)作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則將依法追究法律責(zé)任。

總結(jié)

以上是生活随笔為你收集整理的语音识别维特比解码_自然语言处理之维特比算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。