HMM算法python实现

基础介绍，后5项为基础5元素

Q = ['q0', 'q1', 'q2', 'q3']              # 状态集合 States，共 N 种状态
V = ['v0', 'v1']                          # 观测集合 Observations，共 M 种观测值
I = [ 'i{}'.format(i) for i in range(5) ] # 某个长度为 T 的状态序列，i_t 属于Q
O = [ 'o{}'.format(i) for i in range(5) ] # 状态序列对应的观测值序列，o_t 属于 V
A = [ a_ij ]                              # 转移概率 Transition Problity, a_ij = P( i_t+1 = q_j | i_t = q_i ) N*N
B = [ bj(o_t) ]                           # 发射概率 Emission Problity，b_ij = P( o_t = v_k |  i_t = q_j ) N*M
Pi = [ P_i ]                              # 初识状态概率 P_i = P( i_1 = q_i )

基础5元素对应初始化

# Q = ['盒1', '盒2', '盒3']
Q = ['盒1', '盒2']

V = [ '红' , '黑' ]
# A = [ [ 0.2  , 0.3 , 0.5 ] ,      
#       [ 0    , 0.5 , 0.5 ] , 
#       [ 0.4  , 0.2 , 0.2 ]]
A = [ [ 0.5 , 0.5 ] ,      
      [ 0.5 , 0.5 ]]
B = [ [ 0.3 , 0.7 ] ,
      [ 0.5 , 0.5 ] ]
Pi = [ 0.5 , 0.5 ]

def label_2_id(target):
    dt = { v:k for k,v in enumerate(V)}
    return [ dt[item] for item in target ]
# target = label_2_id( ['红','红','黑','红'] )
target = label_2_id( ['红','红'] )

BruteForce暴力算法，计算复杂度：

# 路径展示角度
def brute_force_algorithm( target = [] ,path = '' ,prob ='' , pre = -1):
    ret = []
    path_tmp = ''
    prob_tmp = ''
    for k,v in enumerate(Q):
        path_tmp =  '{}/{}'.format(path , v)
        if prob == '':
            prob_tmp = '{}/{},{}'.format(prob , Pi[k] , B[k][target[0]] )
        else:
            prob_tmp = '{}/{},{}'.format( prob , A[pre][k] , B[k][target[0]] )
        if len(target) > 1:
            tmp = brute_force_algorithm(target[1:] , path_tmp ,prob_tmp , pre = k )
            ret.extend( tmp )
        elif len(target) == 1:
            ret.append([path_tmp , prob_tmp])
    return ret 
# 总概率展示角度
def brute_force_algorithm( target = [] ,path = '' ,prob = 0 , pre = -1):
    ret = 0
    for k,v in enumerate(Q):
        prob_tmp = prob
        path_tmp =  '{}/{}'.format(path , v)
        if pre == -1 :
            prob_tmp += Pi[k] * B[k][target[0]]  # joint 联合概率局部
        else:
            prob_tmp *= A[pre][k] * B[k][target[0]] 
        if len(target) > 1:
            ret += brute_force_algorithm(target[1:] , path_tmp ,prob_tmp , pre = k )
        elif len(target) == 1:
            ret += prob_tmp
    return ret 

Forward 前向算法，时间复杂度：

def forward_algorithm( target = [] ):
    prob = [ [ 0 for i in Q] for j in target ]
    for t ,o in enumerate(target):
        if t == 0 :
            for i in range( len(Q) ):
                prob[0][i] = Pi[i] * B[i][o]
        else:
            for id , q in enumerate(Q):
                for k,v in enumerate(prob[t-1]):
                    print(  v ,  A[k][id] , prob , prob[t][id] )
                    prob[t][id] += (v * A[k][id] * B[id][o]  )
    print(prob)
    return prob

Backend后向算法，计算复杂度：

def backend_algorithm( target = [] ):
    prob = [ [ 0.0 for i in Q] for j in target ]
    length = len(target)
    for t in range( length-1 , -1 , -1):
        if t == length-1 :
            for i in range( len(Q) ):   # 后向计算有点问题
                prob[t][i] = 1
        else:
            o = target[t+1]
            for id , q in enumerate(Q):
                if t == 0:
                    for k,v in enumerate(prob[t+1]):
                        prob[t][id] *= 1000 
                        prob[t][id] += ( v * A[id][k] * B[k][o] ) * 1000
                        prob[t][id] /= 1000 
                else:
                    for k,v in enumerate(prob[t+1]):
                        prob[t][id] += v * A[id][k] * B[k][o]
    for k,v in enumerate(prob[0]):    
        prob[0][k] = v * Pi[k] * B[k][target[0]]
    return prob