維特比演算法

維特比演算法是一種動態規劃演算法。它用於尋找最有可能產生觀測事件序列的維特比路徑——隱含狀態序列，特別是在馬爾可夫資訊源上下文和隱馬爾可夫模型中。術語“維特比路徑”和“維特比演算法”也被用於尋找觀察結果最有可能解釋相關的動態規劃演算法。例如在統計句法分析中動態規劃演算法可以被用於發現最可能的上下文無關的派生的字串，有時被稱為“維特比分析”。維特比演算法由安德魯·維特比於1967年提出，用於在數字通訊鏈路中解卷積以消除噪音。 此演算法被廣泛應用於CDMA和GSM數字蜂窩網路、撥號調變解調器、衛星、深空通訊和802.11無線網路中解卷積碼。現今也被常常用於語音識別、關鍵字識別、計算語言學和生物資訊學中。例如在語音中，聲音訊號做為觀察到的事件序列，而文字字串，被看作是隱含的產生聲音訊號的原因，因此可對聲音訊號應用維特比演算法尋找最有可能的文字字串。演算法.假設給定隱式馬爾可夫模型狀態空間 formula_1，共有k個狀態，初始狀態 formula_2 的機率為 formula_3 ，從狀態 formula_2 到狀態 formula_5 的轉移機率為 formula_6。 令觀察到的輸出為 formula_7。 產生觀察結果的最有可能的狀態序列 formula_8 由遞推關係給出：formula_9此處 formula_10 是前 formula_11 個最終狀態為 formula_12 的觀測結果最有可能對應的狀態序列的機率。 透過儲存向後指標記住在第二個等式中用到的狀態 formula_13 可以獲得維特比路徑。宣告一個函式 formula_14 ，它返回若 formula_15時計算 formula_10 用到的 formula_13 值 或若 formula_18時的formula_12 . 這樣:formula_20這裡我們使用了的標準定義演算法複雜度為 formula_21例子.想象一個鄉村診所。村民有著非常理想化的特性，要麼健康要麼發燒。他們只有問診所的醫生的才能知道是否發燒。 聰明的醫生透過詢問病人的感覺診斷他們是否發燒。村民只回答他們感覺正常、頭暈或冷。假設一個病人每天來到診所並告訴醫生他的感覺。醫生相信病人的健康狀況如同一個離散馬爾可夫鏈。病人的狀態有兩種“健康”和“發燒”，但醫生不能直接觀察到，這意味著狀態對他是“隱含”的。每天病人會告訴醫生自己有以下幾種由他的健康狀態決定的感覺的一種：正常、冷或頭暈。這些是觀察結果。 整個系統為一個隱馬爾可夫模型(HMM)。醫生知道村民的總體健康狀況，還知道發燒和沒發燒的病人通常會抱怨什麼症狀。 換句話說，醫生知道隱馬爾可夫模型的引數。 這可以用Python語言表示如下:states = ('Healthy', 'Fever')observations = ('normal', 'cold', 'dizzy')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},在這段程式碼中, 起始機率codice_1 表示病人第一次到訪時醫生認為其所處的HMM狀態，他唯一知道的是病人傾向於是健康的。這裡用到的特定機率分佈不是均衡的,如轉移機率大約是codice_2。 轉移機率codice_3表示潛在的馬爾可夫鏈中健康狀態的變化。在這個例子中，當天健康的病人僅有30%的機會第二天會發燒。放射機率codice_4表示每天病人感覺的可能性。假如他是健康的，50%會感覺正常。如果他發燒了，有60%的可能感覺到頭暈。病人連續三天看醫生，醫生發現第一天他感覺正常，第二天感覺冷，第三天感覺頭暈。 於是醫生產生了一個問題：怎樣的健康狀態序列最能夠解釋這些觀察結果。維特比演算法解答了這個問題。def viterbi(obs, states, start_p, trans_p, emit_p):V = [{}]# Initializefor st in states:V[0][st] = start_p[st] * emit_p[st][obs[0]]path[st] = [st]# Run Viterbi when t &gt; 0for t in range(1,len(obs)):V.append({})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_probnewpath[curr_st] = path[prev_state] + [curr_st]# No need to keep the old pathspath = newpathfor 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 dictionaryyield ' ' * 4 + ' '.join(states)for t in range(len(V)):yield '{} '.format(t) + ' '.join(['{:.4f}'.format(V[t][state]) for state in V[0]])函式codice_5 具有以下引數: codice_6 為觀察結果序列, 例如 codice_7； codice_8 為一組隱含狀態； codice_9 為起始狀態機率; codice_10 為轉移機率; 而 codice_11 為放射機率。 為了簡化程式碼，我們假設觀察序列 codice_6 非空且 codice_13 和 codice_14 對所有狀態 i,j 有定義。在執行的例子中正向/維特比演算法使用如下:def example():return viterbi(observations,states,start_probability,transition_probability,emission_probability)print(example())維特比演算法揭示了觀察結果 codice_7 最有可能由狀態序列 codice_16產生。 換句話說，對於觀察到的活動, 病人第一天感到正常，第二天感到冷時都是健康的，而第三天發燒了。維特比演算法的計算過程可以直觀地由格圖表示。 維特比路徑本質上是穿過格式結構的最長路徑。 診所例子的格式結構如下, 黑色加粗的是維特比路徑：在實現維特比演算法時需注意許多程式語言使用浮點數計算，當 p 很小時可能會導致結果算術下溢。 避免這一問題的常用技巧是在整個計算過程中使用對數機率，在對數系統中也使用了同樣的技巧。 當演算法結束時，可以透過適當的冪運算獲得精確結果。虛擬碼.首先是一些問題必要的設定。 設觀察值空間為 formula_22、 狀態空間為 formula_23、 觀察值序列為 formula_24, formula_25 為 formula_26轉移矩陣，其中 formula_27 為從狀態 formula_28 轉移到 formula_29 的轉移機率、 formula_30 為 formula_31 放射矩陣(emission matrix)，其中 formula_32 為在狀態 formula_28 觀察到 formula_34 的機率、 大小為 formula_35 的初始機率陣列 formula_36 ， formula_37 為 formula_38 的機率。 我們稱路徑 formula_39 為生成觀察值 formula_24 的狀態序列。在這個動態規劃問題中, 我們構造了兩個大小為 formula_41 的二維表 formula_42 。 formula_43 的每個元素, formula_44 ，儲存生成 formula_45 時最有可能的路徑 formula_46 ， formula_47 的機率。 formula_48 的每個元素, formula_49，儲存最有可能路徑 formula_50 , formula_51 的 formula_52。我們按 formula_53 增序填充兩個表 formula_54。formula_55,formula_56function "VITERBI"( Xfor each state "si" do"T"1["i",1] ← "πi"·"B""iy"1"T"2["i",1] ← 0end forfor "i" ← "2","3"...,"T" dofor each state "sj" doformula_78formula_79end forend forformula_80"xT" ← szTfor "i" ← "T","T-1"...,"2" do"zi-1" ← "T"2["z"i,i]"xi-1" ← "szi-1"end forreturn Xend function