1.隐马尔可夫模型简介

隐马尔可夫模型由一个状态序列，一个观测序列组成，其中状态序列是不可观测的，因此叫做隐马尔可夫模型（HMM）。
几个重要的参数：Q,V,A,B,O, π \pi π,
Q是所有可能出现的状态的集合（可能的状态由N个），V是所有可能出现的观测结果的集合（可能的观测结果由M个），A是状态转移概率矩阵，是一个NN维的方针，B是一个观测概率矩阵，是一个NM维度的矩阵，O是观测序列，长度为T， π \pi π是初始的状态概率向量，是一个N*1的向量。

2.python代码实现

在这部分的代码中包含了HMM的3个算法：前向，后向以及viterbi算法。
其中viterbi算法适合于求解最优路径，适合动态路径规划的求解。

# 定义马尔可夫类
# 包含前向、后向以及维特比三个算法
# 难点是循环部分的代码，书中的公式是求和，这里可以直接用矩阵的内积简单计算
# 在计算时，维度要对齐
import numpy as np 
class HMM:
    def __init__(self):
        self.alpha = None
        self.farward_p = None
        self.back_p = None

    def farward(self,Q,V,A,B,O,PI):
        N = len(Q)
        M = len(O)
        alpha = np.zeros((N,M))

        T= M
        for t in range(T):
            index = V.index(O[t])
             ## 接下来是遍历每一个状态
             ## 先是遍历每一个时刻，接下来是遍历每一个状态
            for i in range(N):
                if t == 0:
                    alpha[i][t] = PI[t][i]*B[i][index]  # PI这里的索引存在疑问
                    print('alnpha1(%d) = p%db%db(o1) = %f' %
                          (i + 1, i, i, alpha[i][t]))
                else:
                    alpha[i][t] = np.dot(alpha[:,t-1],A[:,i]) * B[i][index]
                    print('alpha%d(%d) = [sigma alpha%d(i)ai%d]b%d(o%d) = %f' %
                          (t + 1, i + 1, t - 1, i, i, t, alpha[i][t]))
        self.farward_p = np.sum(alpha[:,-1])
        self.alpha = alpha
        print('==========================================')
        print('Backward P(O|lambda): %.6f' % self.farward_p)
        print('==========================================')

    def backward(self,Q,V,A,B,O,PI):
        # 后向算法过程用到了一个后向排序的过程
        # for i in range(M - 2, -1, -1)
        N = len(Q)
        M = len(O)
        beta = np.zeros((N,M))        
        T = M
        for t in range(T-1,-1,-1):            
            for i in range(N):
                if t == M-1:
                    beta[i,-1] = 1
                    print('Beta[%d][%d]= %f' % (t+1,i+1,beta[i,-1]))
                else:
                    index = V.index(O[t+1])
                    beta[i][t] = np.dot(np.multiply(A[i,:],B[:,index]),beta[:,t+1])
                    print('Beta[%d][%d]= %f' % (t+1,i+1,beta[i,t]))

        index_1 = V.index(O[0])
        back_p = [B[i][index_1]*PI[0][i]*beta[i][0] for i in range(N)]
        # print(np.sum(back_p))
        self.back_p = np.sum(back_p)
        print('==========================================')
        print('Backward P(O|lambda): %.6f' % self.back_p)
        print('==========================================')

    def viterbi(self,Q,V,A,B,O,PI):
        N = len(Q)
        M = len(O)
        T = M
        delta =np.zeros((N,T))  
        phai = np.zeros((N,T))

        # 遍历每一个时刻，相当于前向传播的计算
        for t in range(T):
            for i in range(N):
                if t == 0:
                    index = V.index(O[t])
                    delta[i][t] = PI[0][i] * B[i,index]
                    phai[i][t] = 0
                else:
                    index = V.index(O[t])
                    delta[i][t] = np.max(np.multiply(delta[:,t-1],A[:,i]))*B[i,index]
                    phai[i][t] = np.argmax(np.multiply(delta[:,t-1],A[:,i]))

        p_star = np.max(delta[:,-1])
        i_T = np.argmax(delta[:,-1])
        path = np.zeros(T)
        path[-1] = i_T+1
        # 第四步是最优路径的回溯，返回去寻找最优的路径
        for t in range(T-2,-1,-1):
            i_t = phai[int(i_T),t+1]
            path[t] = i_t + 1
            i_T = i_t        
        print('==========================================')
        print('Viterbi P(O|lambda): %.6f' % p)
        print('The best path is: %s-->%s-->%s-->%s' % (int(path[0]),int(path[1]),int(path[2]),int(path[3])))
        # print('Backward Algorithm P(O|lambda): %.6f' % p)
        print('==========================================')

结合李航《统计学习方法》书中的p13课后习题1，下面分别实现前向、后向以及维特比算法。

if __name__ == '__main__':
    #习题10.1
    Q = [1, 2, 3]
    V = ['红', '白'] ## 一共有几种观测结果，表示的只是不同结果的个数
    ## 3个不同的盒子就是3个不同的状态；
    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]])

    # O = ['红', '白', '红', '红', '白', '红', '白', '白']
    O = ['红', '白', '红','白',]    #习题10.1的例子
    PI = [[0.2, 0.4, 0.4]]
    my_hmm = HMM()
    my_hmm.farward(Q,V,A,B,O,PI)
    my_hmm.backward(Q,V,A,B,O,PI)
    my_hmm.viterbi(Q,V,A,B,O,PI)

前向算法结果：

后向算法结果：

维特比算法结果：