維特比算法

維特比算法是一種動態規劃算法用於尋找最有可能產生觀測事件序列的-維特比路徑-隱含狀態序列，特別是在馬爾可夫信息源上下文和隱馬爾可夫模型中。術語“維特比路徑”和“維特比算法”也被用於尋找觀察結果最有可能解釋相關的動態規划算法。例如在統計句法分析中動態規划算法可以被用於發現最可能的上下文無關的派生(解析)的字元串，有時被稱為“維特比分析”。

基本介紹

• 中文名：維特比算法
• 外文名：Viterbi Algorithm
• 提出時間：1967年
• 提出者：安德魯·維特比
• 套用領域：CDMA和GSM數字蜂窩網路等

來源

維特比算法由安德魯·維特比(Andrew Viterbi)於1967年提出，用於在數字通信鏈路中解卷積以消除噪音。 此算法被廣泛套用於CDMA和GSM數字蜂窩網路、撥號數據機、衛星、深空通信和802.11無線網路中解卷積碼。現今也被常常用於語音識別、關鍵字識別、計算語言學和生物信息學中。例如在語音(語音識別)中，聲音信號作為觀察到的事件序列，而文本字元串，被看作是隱含的產生聲音信號的原因，因此可對聲音信號套用維特比算法尋找最有可能的文本字元串。

算法

假設給定隱式馬爾可夫模型（HMM）狀態空間 S，共有k個狀態，初始狀態i的機率為 ，從狀態 i 到狀態 j 的轉移機率為 。 令觀察到的輸出為 。 產生觀察結果的最有可能的狀態序列 由遞推關係給出：

此處 是前 t 個最終狀態為 k 的觀測結果最有可能對應的狀態序列的機率。 通過保存向後指針記住在第二個等式中用到的狀態 x 可以獲得維特比路徑。聲明一個函式 ，它返回若 時計算 用到的 x 值 或若 時的 k，這樣:

這裡我們使用了arg max的標準定義 算法複雜度為 。

算法基礎

維特比算法的基礎可以概括成下面三點：

1.如果機率最大的路徑p(或者說最短路徑)經過某個點，比如途中的X₂₂，那么這條路徑上的起始點S到X₂₂的這段子路徑Q，一定是S到X₂₂之間的最短路徑。否則，用S到X₂₂的最短路徑R替代Q，便構成一條比P更短的路徑，這顯然是矛盾的。證明了滿足最優性原理。

數學之美維特比算法

2.從S到E的路徑必定經過第i個時刻的某個狀態，假定第i個時刻有k個狀態，那么如果記錄了從S到第i個狀態的所有k個節點的最短路徑，最終的最短路徑必經過其中一條，這樣，在任意時刻，只要考慮非常有限的最短路即可。

3. 結合以上兩點，假定當我們從狀態i進入狀態i+1時，從S到狀態i上各個節的最短路徑已經找到，並且記錄在這些節點上，那么在計算從起點S到第i+1狀態的某個節點X_i+1的最短路徑時，只要考慮從S到前一個狀態i所有的k個節點的最短路徑，以及從這個節點到X_i+1，j的距離即可。

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 << " ";}