C09. EM 算法及推广

• 学习基础
  • 概率论 : 期望
  • 最大似然估计或极大后验估计
  • 梯度下降
• EM 算法是对含有隐变量的概率模型进行极大似然估计或者极大后验估计的迭代算法。
  • E 步，求期望；利用数据和假设的初值，求得一个隐变量的条件概率分布的期望，即 “Q 函数”。 ( 因为无法求得条件概率分布的具体值 )
  • M 步，求极值。利用 “Q 函数” 来求极值，这个极值可以帮助拟合的概率分布更加逼近真实分布。
  • Q 函数的定义 ( 理解 Q 函数的涵义可以更好地推广到应用中，开始不理解也没关系，可以在应用中慢慢加深 )
  • EM 算法的推导 ( 如果书上的无法理解，还可以参考本文中的其他文献 )
    • EM 算法是收敛的，但是有可能收敛到局部最小值。
    • EM 算法可以看成利用凸函数进行概率密度逼近；
    • 如果原概率密度函数有多个极值，初值的不同就可能逼近到不同的极值点，所以无法保证全局最优。
  • EM 算法的应用 ( 下面的两个应用都是重点，但是无法从本书中完全理解，可以在未来的应用继续探索 )
    • 高斯混合模型
    • HMM(隐Markov模型) ( Ch 10 )
  • EM 算法的推广 ( 建议跳过，对了解 EM 算法帮助不大，只有深入理解和研究 EM 算法才需要 )
    • F 函数的极大 - 极大算法
    • 广义 EM 算法 ( GEM )
• 学习总结
• EM 算法的详细推导。[^Borman,2004], 或者 Determined22 的 EM 算法简述及简单示例(三个硬币的模型)
• EM 算法的概率分析。[^Friedman,2001], 或者苏剑林的 梯度下降和 EM 算法
• EM 算法的深入理解。可以参考史春奇的 Hinton 和 Jordan 理解的 EM 算法

C10. 隐 Markov 模型 ( HMM ) 的算法及推广

• 学习基础
  • 随机过程 : 用于理解 Markov 链的数学含义
  • EM 算法 : 用于计算 HMM 的学习问题
• Markov 链的定义
  • 随机过程
    • 研究对象是随时间演变的随机现象。[^盛骤，2015] C12
    • 设 T 是一无限实数集，对依赖于参数 t ( t 属于 T ) 的一族 ( 无限多个 ) 随机变量称为随机过程。
    • 我的理解
      • 随机过程在任一个时刻 t, 被观测到的状态是随机的，但是这个随机状态是由一个确定的函数控制的。
      • 例如 : 有 3 块金属放在箱子里面，任一个时刻 t 取出的金属是随机的，但是每块金属衰退的速度是由这块金属自身的函数控制的。
      • 随机变量刻画的是数值的随机性 ( 某个数出现的概率 ) ，随机过程刻画的是函数的随机性 ( 某个函数出现的概率 )
  • Markov 过程
    • Markov 性或无后效性 : 过程 ( 或系统 ) 在时刻 t_0 所处的状态为已知的条件下，过程在时刻 t>t_0 所处状态的条件分布与过程在时刻 t_0 之前所处的状态无关。即在已经知道过程“现在”的条件下，其“将来”不依赖于“过去”。[^盛骤，2015] C13
    • Markov 过程 : 具有 Markov 性的随机过程，称为 Markov 过程。
  • Markov 链
    • 时间和状态都是离散的 Markov 过程称为 Markov 链，简称马氏链。
    • 深入理解可参考 [^Rabiner,1989]
  • HMM
    • 关于时序的概率模型
    • 用于描述一个被观测到的随机序列，这个随机序列是由不可观测的状态随机序列生成的，这个状态随机序列是由隐藏的 Markov 链随机生成的。
      • 状态序列 Q : 隐藏的 Markov 链随机生成的状态序列；
      • 观测序列 O : 每个状态生成一个观测，一个状态序列就会生成一个观测序列。
      • 序列的每一个位置都可以看作一个时刻。
• HMM 的基本假设
  • 齐次 Markov 假设，即假设隐藏的 Markov 链在任意时刻 t 的状态只依赖于前一个时刻的状态，而与其他时刻的状态及观测无关，也与时刻 t 无关；
  • 观测独立性假设，即假设任意时刻 t 的观测只依赖于该时刻的 Markov 链的状态，与其他观测与状态无关。
• HMM 的基本元素
  • N，模型的状态数；
  • M，每个状态生成的可观测的标志数；
  • A，转移概率矩阵，a_{ij} 表示从状态 i 转移到状态 j 的概率；
  • B，观测概率矩阵，b_{j} (k) 表示状态 j 产生标志 k 的概率；
  • π，初始状态分布，π_i 表示一开始系统在状态 i 的概率。
  • HMM 参数的数学表示 : λ=(A, B, π)
• HMM 的三个基本问题
  • 概率计算问题
    • 给定观测序列 O 和模型参数 λ，计算基于这个模型下观测序列出现的概率 P(O|λ) ；
  • 预测问题
    • 给定观测序列 O 和模型参数 λ，寻找能够解释这个观测序列的状态序列，这个状态序列的可能性最大；
    • 除非是退化的模型，否则不会有“正确”的状态序列，因为每个状态序列都有可以生成观测序列；
    • 只可能是依据某个优化准则，使找到的状态序列尽可能的逼近真实的状态序列。
  • 学习问题
    • 给定观测序列 O，寻找能够解释这个观测序列的模型参数 λ，使得 P(O|λ) 最大。
    • 评测哪个模型能最好地解释观测序列。
• HMM 的三个基本问题的解决方案
  • 概率计算问题 : 前向算法；
    • 先了解直接计算法，理解 HMM 需要计算的概率的方法和目的，同时明白直接计算法存在的问题；
    • 再了解前向算法，如果利用栅格方法叠加前面计算的成果，从而降低直接计算法的庞大计算量。
  • 预测问题 : Viterbi 算法；
  • 学习问题 : 前向 + 后向算法 +EM 算法。
    • 利用前向 + 后向算法计算转移概率矩阵；
    • 再基于 MLE 理论构造 P(O|λ) 函数；
    • 因为函数中有三个参数不可知，无法直接计算得到，因为采用 EM 算法迭代求解。
• HMM 的基本类型
  • 基本的 HMM 类型
    • 4 状态遍历 HMM；其他类型都是遍历 HMM 的特例。
    • 4 状态从左到右 HMM；
    • 6 状态从左到右并行路径 HMM。
  • 观测序列的密度是连续函数的 HMM : 增加了混合高斯作为约束；
  • 自回归的 HMM : 很适合语音处理；
  • 无输出的 HMM : 即某些状态转移时无观测输出，主要用于语音识别；
  • 一组状态到另一组状态转换 : 组内状态无转移；
  • 优化准则 : 利用概率理论 ( ML ) 或信息理论 ( MMI，MDI ) 刻画；
  • 比较 HMM 模型 : 用于模型的测度和选择，常用的测度 ( 交叉熵或散度或判别信息 )
• HMM 算法的具体实现方法
  • 观测数据的尺度化，方便计算机处理，防止溢出；
  • HMM 模型的训练 : 通过多个观测序列进行训练，估计模型的参数；
  • HMM 模型参数的初始值设定，没有形式化方法，只能凭借经验；
  • 观测数据数量过少，或者观测数据不完整
    • 扩大用于训练的观测集的大小 ( 现实不可操作 ) ；
    • 减少 HMM 模型的参数个数，即减小 HMM 模型的规模；
    • 利用插值的方法补齐或者增加数据。
  • HMM 模型的选择
    • 确定 HMM 模型的状态 ( 模型状态数，模型路径数 )
    • 确定 HMM 观测的标志 ( 连续还是离散，单个还是混合 )
    • 无形式化方法，依赖于具体的应用。
• 学习总结
  • 随机过程和 HMM 算法的基本概念的理解，特别是语音识别和语言处理方向的研究极为重要；
  • HMM 算法的计算过程的了解，虽然可以调用成熟的模块，但是了解这个计算过程对于 HMM 计算的调优可能会有帮助；
  • HMM 算法的学习极力推荐 [^Rabiner,1989]，本章的框架就是基于这篇文章写的。