概述

• 本质上是有向图
• 与有向图对比
  • 添加了时间维度（序列化？）
  • xi之间不独立同分布

马尔科夫过程

隐马尔可夫模型(HMM)

• 概述
  • 隐马尔可夫模型 (Hidden Markov Model) 是一种统计模型，用来描述一个含有隐含未知参数的马尔可夫过程。
  • 它是结构最简单的动态贝叶斯网，这是一种著名的有向图模型，主要用于时序数据建模，在语音识别、自然语言处理等领域有广泛应用。
• 组成部分
  • 初始状态概率向量π ：初始可能的状态，以及每个状态对应的概率
  • 状态转移矩阵A
  • 观察矩阵B
    • bi(ot)：指的是在隐状态 q = i 的情况下，观察到的值 o 的概率
• 假设前提
  • 齐次马尔可夫假设：任意时刻t的状态只与前一时刻t − 1的状态有关，而与其他时刻状态、观测记忆时刻无关。
  • 观测独立性假设： 任意时刻的观察状态只与该时刻马尔可夫链的状态有关

隐马尔可夫模型(HMM) — 三大问题

• 给定模型，如何有效计算产生观测序列的概率？换言之，如何评估模型与观测序列之间的匹配程度？
  • 问题
    • 根据隐马尔科夫模型得到一个可观察状态序列的概率
  • 样例
    • 已知整个模型，我观测到连续三天做的事情是：散步，购物，收拾。那么，根据模型，计算产生这些行为的概率是多少。
  • 算法
    • 直接计算法O(T * N ^ T)
      • 计算出所有的组合序列，然后把每一种组合序列都算一遍
    • 向前算法(Forward Algorithm)（T * N ^ 2）
      • 先计算 T0 的状态 O（N）
      • T1的状态，是基于T0计算了 O（N^2）
    • 向后算法(Backward Algorithm)
• 给定观测序列，如何调整模型参数使得该序列出现的概率最大？换言之，如何训练模型使其能最好地描述观测数据？
  • 问题
    • 根据一个可以观察到的状态序列集产生一个隐马尔科夫模型。即求模型λ = ( π , A , B )的参数
  • 样例
    • 最复杂的，我只知道这三天做了这三件事儿，而其他什么信息都没有。我得建立一个模型，晴雨转换概率，第一天天气情况的概率分布，根据天气情况选择做某事的概率分布。
  • 算法
    • 监督学习
      • 假设给定训练集包含了观测序列O和状态序列I（长度均为T），即{ ( O1 , I1 ) , ( O2 , I2 ) , . . . , ( OS , IS ) }。那么模型λ = ( π , A , B ) 参数的求得可以根据伯努利大数定理的结论 “频率的极限是概率”来给出HMM的参数。当n趋近于无穷的时候，频率等于概率。
      • 即当样本足够大的时候，直接通过观察到的概率计算模型的参数
    • 非监督学习
      • 问题
        • 由于监督学习需要使用训练数据，而人工标注训练数据往往代价很高，有时就会利用非监督学习的方法。
      • 概述
        • 如果训练数据只有观测序列而没有状态序列，即{ O1 , O2 , . . . , OS } 此时HMM的学习就得使用EM算法了，这是非监督学习。
      • 算法
        • 鲍姆-韦尔奇算法(Baum-Welch Algorithm) (约等于EM算法)
• 给定模型和观测序列，如何找到与此观测序列最匹配的状态序列？换言之，如何根据观测序列推断出隐藏的模型状态？
  • 问题
    • 找到一个隐藏状态的序列使得这个序列产生一个可观察状态序列的概率最大
    • 延伸问题
      • 预测问题
        • p(i(t + 1) | O(1),O(2) … O(t))
      • 滤波问题 - online
        • 模型
          • p(i(t) | O(1),O(2) … O(t))
        • 算法
          • 前向算法
      • Smoothing - offline
        • 模型
          • p(i(t) | O(1),O(2) … O(t))
        • 算法
          • 前向 - 后向 算法
  • 样例
    • 同样知晓这个模型，同样是这三件事，我想猜，这三天的天气是怎么样的。
  • 算法
    • 近似算法
      • 近似算法的思想是，在每个时刻 t 选择最有可能的状态 it ，t 从1开始直到T，所以可以求出状态序列 I= ( i1* , i2*, . . . , iT*)，将 I* 作为预测结果。
      • 该算法简单，但是不能保证整体是最有可能的预测状态序列。
    • 维特比算法(Viterbi Algorithm)：维特比算法实际上是用动态规划（dp）来求解HMM预测问题。
      • 概述
        • 维特比算法由安德鲁·维特比(Andrew Viterbi)于1967年提出，用于在数字通信链路中解卷积以消除噪音。