vertibi python 實現(xiàn)

zhangyucha0 發(fā)布于2019-07-30 17:15 / 2626人閱讀

摘要：題目闡釋算法實現(xiàn)。用實現(xiàn)的和表現(xiàn)層的轉(zhuǎn)移動態(tài)規(guī)劃問題，歸結(jié)到相鄰兩個之間存在轉(zhuǎn)移概率，轉(zhuǎn)移概率。難點三層循環(huán)，為了保留，計算每個的的概率，所以要嵌套在之外。

題目闡釋：

viterbi算法實現(xiàn)。 用python實現(xiàn)viterbi的hidden state 和 表現(xiàn)層的轉(zhuǎn)移
動態(tài)規(guī)劃問題，歸結(jié)到
    相鄰兩個step之間存在 state轉(zhuǎn)移概率，state2emibission轉(zhuǎn)移概率。
    計算后可以得到每個step的每個state max_probablity
    由于step_n依賴于 step_n-1,跟 step_n-2無關(guān)，所以可以一直如此往復(fù)，得到最后的max_prob
整個問題抽象為，下一個step依賴于上一個step的所有state，所以只需要計算每一層step的所有state的prbo即可。

難點：

三層for循環(huán)，為了保留，計算每個step的state的概率，所以要 next_state 嵌套在 source_state之外。

states=["Rainy","Sunny"]
observations=["walk","shop","clean"]
observations=("walk","clean","walk")

emission_probability={"Rainy":{"walk":0.1,"shop":0.4,"clean":0.5},
                   "Sunny": {"walk": 0.6, "shop": 0.3, "clean": 0.1}
                    }
trans_probability={"Rainy":{"Rainy":0.7,"Sunny":0.3},
                     "Sunny":{"Rainy":0.4,"Sunny":0.6}
                     }
start_probability={"Rainy":0.6,"Sunny":0.4}

def vertibi(states,objservations,start_prob,trans_prob,emi_prob):
    T={state:[start_prob[state],[state],start_prob[state]] for state in states}
    for objservation in objservations:
        U={}
        for next_state in states:
            total=0
            argmax=None
            valmax=0
            for source_state in states:
                prob,v_path,v_prob=T[source_state]
                p=emi_prob[source_state][objservation]*trans_prob[source_state][next_state]
                prob*=p
                v_prob*=p

                if v_prob>valmax:
                    valmax=v_prob
                    argmax=v_path+[next_state]
                    total+=prob
            U[next_state]=[total,argmax,valmax]
        T=U

    total = 0
    argmax = None
    valmax = 0
    for state in states:
        prob, v_path, v_prob=T[state]
        if v_prob>valmax:
            argmax=v_path
            total=prob
            valmax=v_prob
    return total,argmax,valmax

total,argmax,valmax=vertibi(states,observations,start_probability,trans_probability,emission_probability)
print(total)
print(argmax)
print(valmax)