維特比演算法

維特比演算法（英語：Viterbi algorithm）是一種動態規劃演算法。它用於尋找最有可能產生觀測事件序列的維特比路徑——隱含狀態序列，特別是在馬可夫資訊源上下文和隱藏式馬可夫模型中。

術語「維特比路徑」和「維特比演算法」也被用於尋找觀察結果最有可能解釋相關的動態規劃演算法。例如在統計句法分析中動態規劃演算法可以被用於發現最可能的上下文無關的衍生（解析）的字串，有時被稱為「維特比分析」。

維特比演算法由安德魯·維特比於1967年提出，用於在數字通訊鏈路中解摺積以消除噪音。^[1] 此演算法被廣泛應用於CDMA和GSM數字蜂巢式網路、撥號數據機、衛星、深空通訊和802.11無線網路中解摺積碼。現今也被常常用於語音辨識、關鍵字辨識、計算語言學和生物資訊學中。例如在語音（語音辨識）中，聲音訊號做為觀察到的事件序列，而文字字串，被看作是隱含的產生聲音訊號的原因，因此可對聲音訊號應用維特比演算法尋找最有可能的文字字串。

演算法[編輯]

假設給定隱式馬可夫模型（HMM）狀態空間 $S$ ，共有k個狀態，初始狀態 $i$ 的機率為 $\pi _{i}$ ，從狀態 $i$ 到狀態 $j$ 的轉移機率為 $a_{i,j}$ 。令觀察到的輸出為 $y_{1},\dots ,y_{T}$ 。產生觀察結果的最有可能的狀態序列 $x_{1},\dots ,x_{T}$ 由遞迴關係給出：^[2]

{\begin{array}{rcl}V_{1,k}&=&\mathrm {P} {\big (}y_{1}\ |\ k{\big )}\cdot \pi _{k}\\V_{t,k}&=&\max _{x\in S}\left(\mathrm {P} {\big (}y_{t}\ |\ k{\big )}\cdot a_{x,k}\cdot V_{t-1,x}\right)\end{array}}

此處 $V_{t,k}$ 是前 $t$ 個最終狀態為 $k$ 的觀測結果最有可能對應的狀態序列的機率。通過儲存向後指標記住在第二個等式中用到的狀態 $x$ 可以獲得維特比路徑。聲明一個函式 $\mathrm {Ptr} (k,t)$ ，它返回若 $t>1$ 時計算 $V_{t,k}$ 用到的 $x$ 值或若 $t=1$ 時的 $k$ . 這樣:

{\begin{array}{rcl}x_{T}&=&\arg \max _{x\in S}(V_{T,x})\\x_{t-1}&=&\mathrm {Ptr} (x_{t},t)\end{array}}

這裡我們使用了arg max（英語：arg max）的標準定義演算法複雜度為 $O(T\times \left|{S}\right|^{2})$

例子[編輯]

想像一個鄉村診所。村民有著非常理想化的特性，要麼健康要麼發燒。他們只有問診所的醫生的才能知道是否發燒。聰明的醫生通過詢問病人的感覺診斷他們是否發燒。村民只回答他們感覺正常、頭暈或冷。

假設一個病人每天來到診所並告訴醫生他的感覺。醫生相信病人的健康狀況如同一個離散馬可夫鏈。病人的狀態有兩種「健康」和「發燒」，但醫生不能直接觀察到，這意味著狀態對他是「隱含」的。每天病人會告訴醫生自己有以下幾種由他的健康狀態決定的感覺的一種：正常、冷或頭暈。這些是觀察結果。整個系統為一個隱藏式馬可夫模型(HMM)。

醫生知道村民的母體健康狀況，還知道發燒和沒發燒的病人通常會抱怨什麼症狀。換句話說，醫生知道隱藏式馬可夫模型的參數。這可以用Python語言表示如下:

states = ('Healthy', 'Fever')
 
observations = ('normal', 'cold', 'dizzy')
 
start_probability = {'Healthy': 0.6, 'Fever': 0.4}
 
transition_probability = {
   'Healthy' : {'Healthy': 0.7, 'Fever': 0.3},
   'Fever' : {'Healthy': 0.4, 'Fever': 0.6},
   }
 
emission_probability = {
   'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
   'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
   }

在這段代碼中, 起始機率start_probability 表示病人第一次到訪時醫生認為其所處的HMM狀態，他唯一知道的是病人傾向於是健康的。這裡用到的特定機率分布不是均衡的,如轉移機率大約是{'Healthy': 0.57, 'Fever': 0.43}。轉移機率transition_probability表示潛在的馬可夫鏈中健康狀態的變化。在這個例子中，當天健康的病人僅有30%的機會第二天會發燒。放射機率emission_probability表示每天病人感覺的可能性。假如他是健康的，50%會感覺正常。如果他發燒了，有60%的可能感覺到頭暈。

病人連續三天看醫生，醫生發現第一天他感覺正常，第二天感覺冷，第三天感覺頭暈。於是醫生產生了一個問題：怎樣的健康狀態序列最能夠解釋這些觀察結果。維特比演算法解答了這個問題。

def viterbi(obs, states, start_p, trans_p, emit_p):
    V = [{}]
    path = {}

    # Initialize
    for st in states:
        V[0][st] = start_p[st] * emit_p[st][obs[0]]
        path[st] = [st]

    # Run Viterbi when t > 0
    for t in range(1,len(obs)):
        V.append({})
        newpath = {}

        for curr_st in states:
            paths_to_curr_st = []
            for prev_st in states:
                paths_to_curr_st.append((V[t-1][prev_st] * trans_p[prev_st][curr_st] * emit_p[curr_st][obs[t]], prev_st))
            curr_prob, prev_state = max(paths_to_curr_st)
            V[t][curr_st] = curr_prob
            newpath[curr_st] = path[prev_state] + [curr_st]

        # No need to keep the old paths
        path = newpath

    for line in dptable(V):
        print(line)
    prob, end_state = max([(V[-1][st], st) for st in states])
    return prob, path[end_state]

def dptable(V):
    # Print a table of steps from dictionary
    yield ' ' * 4 + '    '.join(states)
    for t in range(len(V)):
        yield '{}   '.format(t) + '    '.join(['{:.4f}'.format(V[t][state]) for state in V[0]])

函式viterbi 具有以下參數: obs 為觀察結果序列, 例如 ['normal', 'cold', 'dizzy']； states 為一組隱含狀態； start_p 為起始狀態機率; trans_p 為轉移機率; 而 emit_p 為放射機率。為了簡化代碼，我們假設觀察序列 obs 非空且 trans_p[i][j] 和 emit_p[i][j] 對所有狀態 i,j 有定義。

在執行的例子中正向/維特比演算法使用如下:

def example():
    return viterbi(observations,
                   states,
                   start_probability,
                   transition_probability,
                   emission_probability)
print(example())

維特比演算法揭示了觀察結果 ['normal', 'cold', 'dizzy'] 最有可能由狀態序列 ['Healthy', 'Healthy', 'Fever']產生。換句話說，對於觀察到的活動, 病人第一天感到正常，第二天感到冷時都是健康的，而第三天發燒了。

維特比演算法的計算過程可以直觀地由格圖表示。維特比路徑本質上是穿過格式結構的最長路徑。診所例子的格式結構如下, 黑色加粗的是維特比路徑：

Animation of the trellis diagram for the Viterbi algorithm. After Day 3, the most likely path is ['Healthy', 'Healthy', 'Fever'] — Animation of the trellis diagram for the Viterbi algorithm. After Day 3, the most likely path is `['Healthy', 'Healthy', 'Fever']`

在實現維特比演算法時需注意許多程式語言使用浮點數計算，當 p 很小時可能會導致結果算術下溢。避免這一問題的常用技巧是在整個計算過程中使用對數機率，在對數系統中也使用了同樣的技巧。當演算法結束時，可以通過適當的冪運算獲得精確結果。

虛擬碼[編輯]

首先是一些問題必要的設定。設觀察值空間為 $O=\{o_{1},o_{2},\dots ,o_{N}\}$ 、狀態空間為 $S=\{s_{1},s_{2},\dots ,s_{K}\}$ 、觀察值序列為 $Y=\{y_{1},y_{2},\ldots ,y_{T}\}$ , $A$ 為 $K\times K$ 轉移矩陣，其中 $A_{ij}$ 為從狀態 $s_{i}$ 轉移到 $s_{j}$ 的轉移機率、 $B$ 為 $K\times N$ 放射矩陣(emission matrix)，其中 $B_{ij}$ 為在狀態 $s_{i}$ 觀察到 $o_{j}$ 的機率、大小為 $K$ 的初始機率陣列 $\pi$ ， $\pi _{i}$ 為 $x_{1}==s_{i}$ 的機率。我們稱路徑 $X=\{x_{1},x_{2},\ldots ,x_{T}\}$ 為生成觀察值 $Y=\{y_{1},y_{2},\ldots ,y_{T}\}$ 的狀態序列。

在這個動態規劃問題中, 我們構造了兩個大小為 $K\times T$ 的二維表 $T_{1},T_{2}$ 。 $T_{1}$ 的每個元素, $T_{1}[i,j]$ ，儲存生成 $Y=\{y_{1},y_{2},\ldots ,y_{j}\}$ 時最有可能的路徑 ${\hat {X}}=\{{\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j}\}$ ， ${\hat {x}}_{j}=s_{i}$ 的機率。 $T_{2}$ 的每個元素, $T_{2}[i,j]$ ，儲存最有可能路徑 ${\hat {X}}=\{{\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}\}$ , $\forall j,2\leq j\leq T$ 的 ${\hat {x}}_{j-1}$ 。

我們按 $K\cdot j+i$ 增序填充兩個表 $T_{1}[i,j],T_{2}[i,j]$ 。

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

,

T_{2}[i,j]=\arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

輸入

觀察空間 $O=\{o_{1},o_{2},\dots ,o_{N}\}$ ，
狀態 $S=\{s_{1},s_{2},\dots ,s_{K}\}$ ，
觀察序列 $Y=\{y_{1},y_{2},\ldots ,y_{T}\}$ 若在 $t$ 時間觀察值為 $o_{i}$ ，則 $y_{t}==i$ ,
大小為 $K\cdot K$ 的轉移矩陣 $A$ ， $A_{ij}$ 為從狀態 $s_{i}$ 到 $s_{j}$ 的轉移機率，
大小為 $K\cdot N$ 的放射矩陣 $B$ ， $B_{ij}$ 為狀態 $s_{i}$ 觀察到 $o_{j}$ 的機率，
大小為 $K$ 的初始機率陣列 $\pi$ ， $\pi _{i}$ 為 $x_{1}==s_{i}$ 的機率，

輸出

最有可能的隱含狀態序列 $X=\{x_{1},x_{2},\ldots ,x_{T}\}$

 function VITERBI(  $O, S, π, Y, A, B$  ) :  $X$ 
     for each state  $s i$  do
          $T 1 [i,1] \leftarrow π i \cdot B iy 1$ 
          $T 2 [i,1] \leftarrow 0$ 
     end for
     for  $i \leftarrow 2, 3,..., T$  do
         for each state  $s j$  do
              $T_{1}[j,i]\gets \max _{k}{(T_{1}[k,i-1]\cdot A_{kj}\cdot B_{jy_{i}})}$ 
              $T_{2}[j,i]\gets \arg \max _{k}{(T_{1}[k,i-1]\cdot A_{kj}\cdot B_{jy_{i}})}$ 
         end for
     end for
      $z_{T}\gets \arg \max _{k}{(T_{1}[k,T])}$ 
      $x T \leftarrow s z T$ 
     for  $i \leftarrow T, T-1,..., 2$  do
          $z i-1 \leftarrow T 2 [z i,i]$ 
          $x i-1 \leftarrow s z i-1$ 
     end for
     return  $X$ 
 end function

使用動態規劃的演算法[編輯]

注釋[編輯]

^ 29 Apr 2005, G. David Forney Jr: The Viterbi Algorithm: A Personal History. [2012-11-23]. （原始內容存檔於2016-06-02）.
^ Xing E, slide 11

參考資料[編輯]

Viterbi AJ. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory. April 1967, 13 (2): 260–269 [2012-11-23]. doi:10.1109/TIT.1967.1054010. （原始內容存檔於2020-07-29）. (note: the Viterbi decoding algorithm is described in section IV.) Subscription required.

[1] 29 Apr 2005, G. David Forney Jr: The Viterbi Algorithm: A Personal History. [2012-11-23]. （原始內容存檔於2016-06-02）.

[2] Xing E, slide 11

[1]

[2]