-
維特比算法
鎖定
維特比算法來源
維特比算法由安德魯·維特比(Andrew Viterbi)於1967年提出,用於在數字通信鏈路中解卷積以消除噪音。 此算法被廣泛應用於CDMA和GSM數字蜂窩網絡、撥號調制解調器、衞星、深空通信和802.11無線網絡中解卷積碼。現今也被常常用於語音識別、關鍵字識別、計算語言學和生物信息學中。例如在語音(語音識別)中,聲音信號作為觀察到的事件序列,而文本字符串,被看作是隱含的產生聲音信號的原因,因此可對聲音信號應用維特比算法尋找最有可能的文本字符串。
[1]
維特比算法算法
假設給定隱式馬爾可夫模型(HMM)狀態空間 S,共有k個狀態,初始狀態i的概率為
,從狀態 i 到狀態 j 的轉移概率為
。 令觀察到的輸出為
。 產生觀察結果的最有可能的狀態序列
由遞推關係給出:
此處
是前 t 個最終狀態為 k 的觀測結果最有可能對應的狀態序列的概率。 通過保存向後指針記住在第二個等式中用到的狀態 x 可以獲得維特比路徑。聲明一個函數
,它返回若
時計算
用到的 x 值 或若
時的 k,這樣:
維特比算法算法基礎
維特比算法的基礎可以概括成下面三點:
1.如果概率最大的路徑p(或者説最短路徑)經過某個點,比如途中的X22,那麼這條路徑上的起始點S到X22的這段子路徑Q,一定是S到X22之間的最短路徑。否則,用S到X22的最短路徑R替代Q,便構成一條比P更短的路徑,這顯然是矛盾的。證明了滿足最優性原理。
2.從S到E的路徑必定經過第i個時刻的某個狀態,假定第i個時刻有k個狀態,那麼如果記錄了從S到第i個狀態的所有k個節點的最短路徑,最終的最短路徑必經過其中一條,這樣,在任意時刻,只要考慮非常有限的最短路即可。
3. 結合以上兩點,假定當我們從狀態i進入狀態i+1時,從S到狀態i上各個節的最短路徑已經找到,並且記錄在這些節點上,那麼在計算從起點S到第i+1狀態的某個節點Xi+1的最短路徑時,只要考慮從S到前一個狀態i所有的k個節點的最短路徑,以及從這個節點到Xi+1,j的距離即可。
[1]
維特比算法C++代碼實現
#include <iostream>#include <string>#include <list>using namespace std;int main(){ double pi[3] = { 0.2, 0.4, 0.4 }; double C[3][3] = { 0.5, 0.2, 0.3, 0.3, 0.5, 0.2, 0.2, 0.3, 0.5 }; double E[3][2] = { 0.5, 0.5, 0.4, 0.6, 0.7, 0.3 }; string output[4] = { "R", "W", "R","W" }; int state[3] = { 1, 2, 3 }; int row = 3; int column = 3; //開闢數組空間 double **delta = new double *[row]; int **path = new int *[row]; int i, j,k; for (i = 0; i < 3; i++) { delta[i] = new double[3]; path[i] = new int[3]; } //將輸出狀態轉為數組 int outnum[4]; for (i = 0; i < row; i++) { if (output[i] == "R") outnum[i] = 0; else if (output[i] == "W") outnum[i] = 1; } //初始化 for (i = 0; i < column; i++) { path[i][0] = 0; delta[i][0] = pi[i] * E[i][0]; cout << delta[i][0] << endl; } //遞歸 for (j = 1; j < row; j++)//序列遍歷,矩陣列遍歷 { for (k = 0; k < column; k++)//狀態遍歷 { double pro = 0; int sta = 0; for (i = 0; i < column; i++)//矩陣行遍歷 { double temp = delta[i][j - 1] *C[i][k]* E[k][outnum[j]] ;//delta[i][j-1]*轉移概率*發射概率 cout << delta[i][j - 1] << " " << E[k][outnum[j]] << endl; cout << temp << endl; if (temp > pro) { pro = temp; sta = i;//記錄路徑信息 } } delta[k][j] = pro; path[k][j]= sta; } } //終止,找到概率最大值 double max = 0; int sta = 0; for (i = 0; i < column; i++) { if (delta[i][row - 1] > max) { max = delta[i][row - 1]; sta = i; } } //回溯,找到最大路徑及其對應的狀態值 list<int> listPath; listPath.push_back(sta+1); for (j = row - 1; j > 0; j--) { sta = path[sta][j]; listPath.push_back(sta+1); } //輸出 cout << "max probability: " << max << endl; list<int> ::iterator itepath; for (itepath = listPath.begin(); itepath != listPath.end(); itepath++) cout << *itepath << " ";}