【笔记】隐马尔可夫

隐马尔可夫模型

核心结构

1. 状态序列(隐型，不可见) I

2. 观测序列 O

3. 初始概率分布 pi

4. 状态转移概率分布 A

5. 观测概率分布 B

   假设有三个骰子，分别是四面、六面、八面。现在每次随机选择一枚骰子投掷，进行十次，得到的一串数字即为观测序列，对应的每次选择的骰子为状态序列。

   因为是随机选，所以三个骰子被选的概率相同，即初始概率分布为[1/3, 1/3, 1/3]

   因为每次选择是独立的，所以若第一次选取第一枚骰子，下一次选取三枚骰子的概率分别为[1/3, 1/3, 1/3],假设行向量分别对应这三枚骰子，则

       A = {
           [1/3, 1/3, 1/3],
           [1/3, 1/3, 1/3],
           [1/3, 1/3, 1/3],
       }
   

   对于一枚骰子，投掷结果的概率对应观测概率分布，即

           B = {
               [1/4, 1/4, 1/4, 1/4],
               [1/6, 1/6, 1/6, 1/6, 1/6, 1/6, ]
               ...
           }
   

要解决的问题

1. 概率计算问题

   • 描述：已知(pi, A, B)，求给定O出现的概率。
   • 解决方案：
     1. 前向算法
        • 前向概率：对于第t层的状态i，出现(O[1], O[2], ..., O[t])的概率，考虑t-1层的所有状态的影响。
        • 同维特比算法思想类似，属于动态规划。下一层的状态由上一层的推出，区别在于求上一层的累加值而非最大值。“dpT[j]”代表观测序列为{o1, o2, ..., oT}且此时隐状态为I[j]的概率，所以dpT[j] * A[j][i]代表上式又追加到了隐状态I[i]。进而，遍历(j = 1, 2, .. , N)得到第上一层所有的隐状态跳转到下一层的隐状态i的概率和。再进而，对上述求和式乘以Bi(o[T+1]),就得到该层(t + 1)的状态i观测到状态O[t + 1]的概率。
          此时时间复杂度是O(T * N)，计算完了第一个隐状态。一共有N种隐状态，所以全部计算加和的时间复杂度是O(T * N ^ 2)
     2. 后向算法
        • 后向概率：对于第t层的状态i，出现(O[t + 1], O[t + 2], ..., O[N])的概率，考虑对第t + 1层的所有状态的影响。
        • 后向算法同前向算法相同，区别在于前者是向后看，后者是向前看。不再赘述。

2. 学习问题

   • 描述: 已知O，求参数(pi, A, B)，使得在这组参数下出现O的概率最高。
   • 解决方案
     • 监督学习：传统概率计算
     • 非监督学习：Baum-Welch算法(EM算法)

3. 预测问题

   • 描述：已知(pi, A, B, O)，求最有可能对应的状态序列(隐状态)。
   • 解决方案：
     1. 近似算法
        穷举所有可能的序列，对每一种计算概率，选出最大的。
     2. 维特比算法
        是一种动态规划的思想，下一层最大值依赖上一层的最大值，且不会影响上一层(下一层由上一层递推得出)，因此“dp[i]”代表在第i层选择的节点，可使从首层到第i层的概率最大。
        下面是借鉴的@hankcs的代码实现。

     """
     维特比算法思想
     长度为n的观测序列，对应一个[len(state), n]维的矩阵，每一个列向量是一层。
     假设当前处理到第i层，则要：
         1. 借用第i-1层的结果，得到该层最大的概率。
         2. 记录路径。记录 使第i层第j个状态概率最大的 第i-1层的状态q。即原先的path[q]加上q
     """
     
     
     states = ('Rainy', 'Sunny')
     observations = ('walk', 'shop', 'clean')
     start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
     transition_probability = {
         'Rainy': {'Rainy': 0.7, 'Sunny': 0.3},
         'Sunny': {'Rainy': 0.4, 'Sunny': 0.6},
     }
     emission_probability = {
         'Rainy': {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
         'Sunny': {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
     }
     
     
     def viterbi(obs, states, start_p, trans_p, emit_p):
         """
     
         :param obs:观测序列
         :param states:隐状态
         :param start_p:初始概率（隐状态）
         :param trans_p:转移概率（隐状态）
         :param emit_p: 发射概率 （隐状态表现为显状态的概率）
         :return:
         """
         # 路径概率表 V[时间][隐状态] = 概率
         V = [{}]
         # 一个中间变量，代表当前状态是哪个隐状态
         path = {}
     
         # 初始化初始状态 (t == 0)
         for y in states:
             V[0][y] = start_p[y] * emit_p[y][obs[0]]
             path[y] = [y]
         print(path)
     
         # 对 t > 0 跑一遍维特比算法
         for t in range(1, len(obs)):
             V.append({})
             newpath = {}
     
             for y in states:
                 # max函数中第二个参数y0，存储返回的隐状态state
                 # 概率 隐状态 =    前状态是y0的概率 * y0转移到y的概率 * y表现为当前状态的概率
                 (prob, state) = max([(V[t - 1][y0] * trans_p[y0][y] * emit_p[y][obs[t]], y0) for y0 in states])
                 # 记录最大概率
                 V[t][y] = prob
                 # 记录路径
                 newpath[y] = path[state] + [y]
     
             # 更新路径
             path = newpath
     
         # 输出到达第i层的隐状态路径
         # print(newpath)
         (prob, state) = max([(V[len(obs) - 1][y], y) for y in states])
         return (prob, path[state])
     
     
     def example():
         return viterbi(observations,
                     states,
                     start_probability,
                     transition_probability,
                     emission_probability)
     
     
     if __name__ == "__main__":
         print(example())