概率图模型3：隐马尔科夫(3)

本节主要实现隐马尔可夫模型的预测算法：Viterbi algorithm
李航，《统计学习方法》

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
"""
@author: XiangguoSun
@contact: sunxiangguodut@qq.com
@file: Viterbi.py
@time: 2017/3/27 12:40
@software: PyCharm
"""
import numpy as np


def Viterbi(Observe,model):
    A = model[0]
    B = model[1]
    pi = model[2]
    T = Observe.size
    N = B.shape[0]
    delta = np.zeros((T,N))
    F = np.zeros((T,N))

    for i in xrange(0,N):
        delta[0,i]=pi[i]*B[i,Observe[0]]

    for t in xrange(1,T):
        for i in xrange(0,N):
            delta[t, i] = np.max(delta[t-1,:]*A[:,i])*B[i,Observe[t]]
            F[t,i] = np.argmax(delta[t-1,:]*A[:,i])

    IT=np.zeros((T,),dtype=int)
    IT[T-1]=np.argmax(delta[-1,:])

    for t in xrange(T-2,-1,-1):
        IT[t] = F[t+1,IT[t+1]]

    return IT,delta,F


if __name__ == '__main__':

    A = np.array([[0.5, 0.2, 0.3],
                  [0.3, 0.5, 0.2],
                  [0.2, 0.3, 0.5]])
    B = np.array([[0.5, 0.5],
                  [0.4, 0.6],
                  [0.7, 0.3]])
    pi = np.array([0.2, 0.4, 0.4])
    model = (A, B, pi)

    Observe = np.array([0,1,0])
    States = np.array([1,2,3])

    IT, delta, F = Viterbi(Observe, model)
    print IT,'
',delta,'
',F