维特比算法

維特比演算法（英語：Viterbi algorithm）是一種動態規劃演算法。它用於尋找最有可能產生觀測事件序列的維特比路徑——隱含狀態序列，特別是在馬可夫資訊源上下文和隱藏式馬可夫模型中。
術語「維特比路徑」和「維特比演算法」也被用於尋找觀察結果最有可能解釋相關的動態規划算法。例如在統計句法分析中動態規划算法可以被用於發現最可能的上下文無關的衍生（解析）的字串，有時被稱為「維特比分析」。
維特比演算法由安德魯·維特比（Andrew Viterbi）於1967年提出，用於在數字通訊鏈路中解摺積以消除噪音。 此演算法被廣泛應用於CDMA和GSM數字蜂巢式網路、撥號數據機、衛星、深空通訊和802.11無線網路中解摺積碼。現今也被常常用於語音辨識、關鍵字辨識、計算語言學和生物資訊學中。例如在語音（語音辨識）中，聲音訊號做為觀察到的事件序列，而文字字串，被看作是隱含的產生聲音訊號的原因，因此可對聲音訊號應用維特比演算法尋找最有可能的文字字串。

例子

想像一個鄉村診所。村民有著非常理想化的特性，要麼健康要麼發燒。他們只有問診所的醫生的才能知道是否發燒。 聰明的醫生通過詢問病人的感覺診斷他們是否發燒。村民只回答他們感覺正常、頭暈或冷。
假設一個病人每天來到診所並告訴醫生他的感覺。醫生相信病人的健康狀況如同一個離散馬可夫鏈。病人的狀態有兩種「健康」和「發燒」，但醫生不能直接觀察到，這意味著狀態對他是「隱含」的。每天病人會告訴醫生自己有以下幾種由他的健康狀態決定的感覺的一種：正常、冷或頭暈。這些是觀察結果。 整個系統為一個隱藏式馬可夫模型(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%的可能感覺到頭暈。
病人連續三天看醫生，醫生發現第一天他感覺正常，第二天感覺冷，第三天感覺頭暈。 於是醫生產生了一個問題：怎樣的健康狀態序列最能夠解釋這些觀察結果。維特比演算法解答了這個問題。
# Helps visualize the steps of Viterbi.def print_dptable(V):
    print "    ",
    for i in range(len(V)): print "%7d" % i,
    print

    for y in V[0].keys():
        print "%.5s: " % y,
        for t in range(len(V)):
            print "%.7s" % ("%f" % V[t][y]),
        printdef viterbi(obs, states, start_p, trans_p, emit_p):
    V = [{}]
    path = {}

    # Initialize base cases (t == 0)
    for y in states:
        V[0][y] = start_p[y] * emit_p[y][obs[0]]
        path[y] = [y]

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

        for y in states:
            (prob, state) = max([(V[t-1][y0] * trans_p[y0][y] * emit_p[y][obs[t]], y0) for y0 in states])
            V[t][y] = prob
            newpath[y] = path[state] + [y]

        # Don't need to remember the old paths
        path = newpath

    print_dptable(V)
    (prob, state) = max([(V[len(obs) - 1][y], y) for y in states])
    return (prob, path[state])
函式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']產生。 換句話說，對於觀察到的活動, 病人第一天感到正常，第二天感到冷時都是健康的，而第三天發燒了。
維特比演算法的計算過程可以直觀地由格圖表示。 維特比路徑本質上是穿過格式結構的最長路徑。 診所例子的格式結構如下, 黑色加粗的是維特比路徑：
在實現維特比演算法時需注意許多程式語言使用浮點數計算，當 p 很小時可能會導致結果下限溢位。 避免這一問題的常用技巧是在整個計算過程中使用對數機率，在對數系統中也使用了同樣的技巧。 當演算法結束時，可以通過適當的冪運算獲得精確結果。