《马尔可夫》隐马尔可夫链模型的概率计算问题

Ddcc 2018年8月22日 13:54 1021916684@qq.com
概率计算问题 前向算法 HMM

如需转载请注明出处:http://zczzxz.top,整理不易请谅解。

一、 概率计算问题

给定模型λ=(A,B,π)和观测序列O={o1,o2,...,oT},计算在模型λ下观测序列O出现的概率P(O|λ)。
二、 穷举法
假设有如下网络:观察序列o1,o2,o3,隐状态q1,q2,q3
 
利用穷举搜索(相当于将所有的t1-t3的所有路径搜索一遍):
 
隐状态集合数为N,显状态长度为T,任一t时刻有N种隐状态,所以时间的复杂度为O(NT),当T很大时,会出现“指数爆炸”的问题。那么有没有其他可以计算简单些的方法,前向算法被Baum提出来。
三、 前向算法
3.1先看t1时刻的显状态o1
 
计算t1时刻显状态为o1的概率:
 
其中:
 
其中:
 ,即隐状态q1转化为o1的概率。
3.2再看t2时刻的显状态o2
 
计算t2时刻显状态为o2的概率:
 

其中:

 其中A(1,1)代表q1转化为q1的概率,以此类推,最终获得P(O|λ):
 

一共有T步,每步N2次,时间复杂度为O(N2T)

附上python代码:


class HMMForward(object):

    def __int__(self):
        pass

    def Forward(self, A, B, O, pi):
        N, T = np.shape(A)[0], np.shape(O)[0]
        alpha = np.zeros((N, T))
        for t in range(T):
            if 0 == t:
                alpha[:, t] = np.multiply(pi.T, B[:, O[t]])
            else:
                for n in range(N):
                    alpha_temp = np.multiply(alpha[:, t-1], A[:, n]) * B[n, O[t]]
                    alpha[n, t] = sum(alpha_temp)
        return sum(alpha[:, t])

if __name__ == '__main__':
    # 隐马尔可夫模型A参数
    A = np.array([[0.9, 0.05, 0.05],
                  [0.3, 0.5, 0.2],
                  [0.2, 0.3, 0.5]])
    # 隐马尔可夫模型B参数
    B = np.array([[0.9, 0.1],
                  [0.4, 0.6],
                  [0.7, 0.3]])
    # 初始状态概率分布pi
    pi = np.array([[0.2],
                   [0.4],
                   [0.4]])
    # 所有可能的观测序列
    O = [[1, 1], [1, 0], [0, 1], [0, 0]]
    hmm = HMMForward()
    for row in range(np.shape(O)[0]):
        prob = hmm.Forward(A, B, O[row], pi)
        print('\n观测序列:', O[row], '\n出现的概率为:', prob)