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]，本章的框架就是基于这篇文章写的。

C11. 条件随机场 ( CRF ) 的算法及推广

• 条件随机场 ( Conditional Random Field, CRF ) 的基本概念
  • 概率模型
    • 提供了一种描述框架，将学习任务归结于计算变量的概率分布。
    • 推断 : 利用已知变量推测未知变量的分布，核心是如何基于可观测变量推测出未知变量的条件分布。
  • 生成模型与判别模型
    • 生成 (generative) 模型
      • 考虑联合分布，是所有变量的全概率模型；
      • 由状态序列决定观测序列，因此可以模拟 ( “生成” ) 所有变量的值。
      • 具有严格的独立性假设；
      • 特征是事先给定的，并且特征之间的关系直接体现在公式中。
      • 优点
        • 处理单类问题比较灵活；
        • 模型变量之间的关系比较清楚；
        • 模型可以通过增量学习获得；
        • 可以应用于数据不完整的情况。
      • 缺点 : 模型的推导和学习比较复杂。
      • 应用
        • n 元语法模型
        • HMM
        • Markov 随机场
        • Naive Bayes 分类器
        • 概率上下文无关文法
    • 判别 (discriminative) 模型
      • 考虑条件分布，认为由观测序列决定状态序列，直接对后验概率建模；
      • 从状态序列中提取特征，学习模型参数，使得条件概率符合一定形式的最优。
      • 特征可以任意给定，一般利用函数进行表示。
      • 优点 : 模型简单，容易建立与学习；
      • 缺点 : 描述能力有限，变量之间的关系不清晰，只能应用于有监督学习。
      • 应用
        • 最大熵模型
        • 条件随机场
        • 最大熵 Markov 模型 (maximum-entropy Markov model, MEMM)
        • 感知机
  • 概率图模型 : 是一类用图来表达变量相关关系的概率模型，
    • 有向图模型 ( Bayes 网 ) : 使用有向无环图表示变量间的依赖关系，如 : 推导关系
      • 静态 Bayes 网络
      • 动态 Bayes 网络 : 适合处理一般图问题
        • 隐 Markov 模型 : 结构最简单的动态 Bayes 网，适合处理线性序列问题，可用于时序数据建模，主要应用领域为语音识别、自然语言处理等。
    • 无向图模型 ( Markov 网 ) : 使用无向图表示变量间的依赖关系，如 : 循环关系
      • Markov 随机场 : 典型的 Markov 网
      • Boltzman 机
      • 通用条件随机场 : 适合处理一般图问题
        • 线性链式条件随机场 : 适合处理线性序列问题
  • 随机场 :
• 概率图模型
  • 在概率模型的基础上，使用了基于图的方法来表示概率分布 ( 或者概率密度、密度函数 ) ，是一种通用化的不确定性知识表示和处理的方法。
  • 图是表示工具
    • 结点表示一个或者一组随机变量
    • 结点之间的边表示变量间的概率依赖关系，即“变量关系图”。
• Bayes 网络 ( 信念网，信度网，置信网 )
  • 目的 : 通过概率推理处理不确定性和不完整性问题
  • 构造 Bayes 网络的主要问题
    • 表示 : 在某一随机变量的集合上给出其联合概率分布。
    • 推断 : 因为模型完整描述了变量及其关系，可以推断变量的各种问题。
      • 精确推理方法 : 变量消除法和团树法
      • 近似推理方法 : 重要性抽样法、MCMC 模拟法、循环信念传播法和泛化信念传播法等
    • 学习 : 决定变量之间相互关联的量化关系，即储存强度估计。
      • 参数学习常用方法 : MLE、MAP、EM 和 Bayes 估计法。
      • 结构学习 :
• Markov 随机场 (Markov Random Field, MRF)
  • 定义
    • 是一组有 Markov 性质的随机变量的联合概率分布模型，
    • 联合概率分布满足成对、局部和全局 Markov 性。
    • 由一个无向图 G 和定义 G 上的势函数组成。
  • 基本概念
    • 团 (clique) : 是图中结点的一个子集，团内任意两个结点都有边相连。也称为完全子图 (complete subgraph)。
    • 极大团 (maximal clique) : 若在一个团 C 中加入任何一个结点都不再形成团，就说那个团 C 是最大团。极大团就是不能被其他团所包含的团。
    • 因子分解 (factorization) : 将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式的操作。
    • 分离集 (separating set) : 若从结点集 A 中的结点到结点集 B 中的结点都必须经过结点集 C 中的结点，则称结点集 A 和 B 被结点集 C 所分离。
    • 全局 Markov 性 : 给定两个变量子集的分离集，则这两个变量子集条件独立
      • 局部 Markov 性 : 给定某变量的邻接变量，则该变量独立于其他变量
      • 成对 Markov 性 : 给定所有其他变量，两个非邻接变量条件独立 。
    • 势函数
      • 用于将模型进行参数化的参数化因子，称为团势能或者团势能函数，简称势函数。
      • 定义在变量子集上的非负实函数，主要用于定义概率分布函数，亦称“因子”。
      • 多个变量之间的联合概率可以基于团分解为多个因子的乘积。
      • 指数函数经常被用于定义势函数。
• 条件随机场 (Conditional Random Field, CRF)
  • 用来处理标注和划分序列结构数据的概率化结构模型。
  • 是给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型
    • 假设输出随机变量构成 Markov 随机场。
  • 线性链条件随机场
    • 输入序列对输出序列预测的判别模型
    • 形式为对数线性模型
  • 构造 CRF 的主要问题
    • 特征的选取
    • 参数训练
    • 解码
  • 优点 : 相比于 HMM 没有独立性要求，相比于条件 Markov 模型没有标识偏置问题。
• 学习总结
  • 本书的描述概念性内容过少，不利于理解，建议阅读 [^周志华，2018] C14
  • 以概率图模型为基础来理解条件随机场会更加容易，也能够保证知识相互之间的联系，还可以加深对 HMM 的理解。
  • CRF 的主要应用是自然语言处理，因此结合自然语言处理来理解概念也会更加深刻。 [^宗成庆，2018] C06
  • 虽然国内几本书都写的不错，但是 CRF 都不是他们书中的重点，若想深入学习 CRF 还是请参考 [^Sutton,2012]

C12. 统计学习方法总结

10 种统计学习方法特点的概括总结