Viterbi algorithm

HMM（隐馬爾可夫模型）是用來描述隐含未知參數的統計模型

任何一個HMM都可以通過下列五元組來描述：

:param obs:觀測序列
:param states:隐狀态
:param start_p:初始機率（隐狀态）
:param trans_p:轉移機率（隐狀态）
:param emit_p: 發射機率 （隐狀态表現為顯狀态的機率）
           

而Viterbi算法是解決隐馬第三問題（求觀察序列的最可能标注序列）。

算法大概就是通過已知的可以觀察到的序列，和一些已知的狀态轉換之間的機率情況，通過綜合狀态之間的轉移機率和前一個狀态的情況計算出機率最大的狀态轉換路徑，進而推斷出隐含狀态的序列的情況。

維基百科的這個例子的動态圖

問題描述來源知乎

隐含的身體狀态 = { 健康 , 發燒 }
可觀察的感覺狀态 = { 正常 , 冷 , 頭暈 }
月兒預判的阿驢身體狀态的機率分布 = { 健康：0.6 , 發燒： 0.4 }
月兒認為的阿驢身體健康狀态的轉換機率分布 = {健康->健康： 0.7 ,健康->發燒： 0.3 ,發燒->健康：0.4 ,發燒->發燒： 0.6}
月兒認為的在相應健康狀況條件下，阿驢的感覺的機率分布 = {健康，正常：0.5 ，冷 ：0.4 ，頭暈： 0.1 ；發燒，正常：0.1 ，冷 ：0.3 ，頭暈： 0.6 }

阿驢連續三天的身體感覺依次是： 正常、冷、頭暈 。
           

利用五元組來描述問題

states = ('Health', 'Fever')
observations = ('normal', 'cold', 'dizzy') 
start_probability = {'Health': , 'Fever': }
transition_probability = {
        'Health' : {'Health': , 'Fever': },
        'Fever' : {'Health': , 'Fever': },
        }
emission_probability = {
        'Health' : {'normal': , 'cold': , 'dizzy': },
        'Fever' : {'normal': , 'cold': , 'dizzy': },
        }
           

代碼實作Viterbe算法

import numpy
def Viterbi () :
    #已知條件
    states = ('Health', 'Fever')
    observations = ('normal', 'cold', 'dizzy') 
    start_probability = {'Health': , 'Fever': }
    transition_probability = {
        'Health' : {'Health': , 'Fever': },
        'Fever' : {'Health': , 'Fever': },
        }
    emission_probability = {
        'Health' : {'normal': , 'cold': , 'dizzy': },
        'Fever' : {'normal': , 'cold': , 'dizzy': },
    }
    day = 
    s = len(states)
    V = []      

    Wether = []
    Temp = []
    #求解初始狀态可能
    for j in list(range(s)):
        Temp.append(start_probability.get(states[j]) * emission_probability.get(states[j])[observations[]])
    V.append(Temp)
    #根據初始狀态求解
    Wether.append(states[V[].index(max(V[]))]);

    #求解第2 - day 狀态轉換機率
    prob = []
    for d in [i +  for i in list(range( day - ))]:
        prob = []
        pp = -
        for j in list(range(s)):
            Temp = []
            for k in list(range(s)):
                np = V[d-][j] * transition_probability.get(states[j])[states[k]] * emission_probability.get(states[k])[observations[d]]
                Temp.append(np)
                #記錄路徑
                if np > pp:
                    m1 = j
                    m2 = k
                    pp = np
            prob.append(Temp)

        print('Compute_Probability:')
        print(prob)
        Wether.append(states[m2])
        V.append(prob[m1])
        print('Large_One:')
        print(prob[m1])

    print(V)
    print(Wether)

if __name__ == '__main__':
    Viterbi()
           

運作結果