隐马尔可夫是生成模型吗（简单孤独的隐马尔可夫模型）

隐马尔可夫是生成模型吗（简单孤独的隐马尔可夫模型）对于HMM来说，关键点是X1->X2-> ••• ->Xn，只要中间有一处阻塞，X1影响不到Xn。如果遍历Q，计算复杂度将是O(N^T)，N表示Q的空间大小，T表示序列长度；如果采用前向算法，则时间复杂度降到O(N^2 * T)。HMM主要包含以下几点：Jurafsky & Martin 《Speech and Language Processing》Jurafsky & Martin 《Speech and Language Processing》

HMM

Hidden Markov Models：隐马尔可夫模型。
隐马尔可夫模型是一个包含隐变量的时序模型，可以从马尔可夫假设角度概率推导：

也可以从概率图(简单紧凑的概率图模型)角度理解依赖关系：

本文结合概率基础，主要从概率图角度理解HMM。

如图即为一个简单的贝叶斯网络，O表示观察值，Q表示隐变量，经常使用的符号还有O-S、X-Y等。
HMM通过建模p(O Q)预测p(Q|S)，属于生成式模型。

HMM主要包含以下几点：

1. 三个基本问题
   评估、解码及学习。
   模型的符号标记为λ，指的也就是状态转移矩阵A、发射概率B等参数。

Jurafsky & Martin 《Speech and Language Processing》

2. 两个需要学习的矩阵
   状态转移概率矩阵及发射概率矩阵。

Jurafsky & Martin 《Speech and Language Processing》

3. 四个动态规划算法
   前向算法(The Forward Algorithm)、后向算法(the backward probability)、前向后向算法(the forward-backward/Baum-Welch algorithm)及维特比算法(The Viterbi Algorithm)。
   需要注意的是动态规划算法只是递归形式的数学运算，能够有效降低计算复杂度，但其本身和模型学习没有必然联系。
   比如计算似然：

如果遍历Q，计算复杂度将是O(N^T)，N表示Q的空间大小，T表示序列长度；如果采用前向算法，则时间复杂度降到O(N^2 * T)。

4. EM最优化方法
   the Expectation-Maximization algorithm。

几个重要的概率公式

d-分离

对于HMM来说，关键点是X1->X2-> ••• ->Xn，只要中间有一处阻塞，X1影响不到Xn。

Koller and Friendman PGM

前向算法

The Forward Algorithm，应用于评估问题，求解p(O|λ)。

关于α的定义及递归关系，在概率图上，一目了然。

Jurafsky & Martin 《Speech and Language Processing》

算法流程：

Jurafsky & Martin 《Speech and Language Processing》

维特比算法

The Viterbi Algorithm，应用于解码问题，给定模型λ=(A，B)及观察值O=o1o2•••ot，求解最优序列q1q2•••qt。

与前向算法形式一致，替换求和(Σ)为最大(max)即可。

Jurafsky & Martin 《Speech and Language Processing》

算法流程：

Jurafsky & Martin 《Speech and Language Processing》

EM算法

一种最优化方法：

1. 求解隐变量的期望
2. 已知隐变量，优化最大似然

Andrew NG CS229

后向算法

the backward probability，前向后向算法的一部分，辅助解决学习问题。

算法流程：

Jurafsky & Martin 《Speech and Language Processing》

根据d-分离，似然可以表示为：

前向后向算法

the Baum-Welch algorithm，解决模型学习问题，给定观察值序列O及隐状态集合，学习矩阵A和B。

采用EM算法，CS229 Daniel Ramage 给出了证明，假定隐变量期望给定，采用拉格朗日乘子法最优化最大似然，然后根据求解结果，确定实际需要求解的隐变量期望相关变量。

Daniel Ramage CS229 Hidden Markov Models Fundamentals

隐变量期望相关变量示意图：

Jurafsky & Martin 《Speech and Language Processing》

注意由EM算法可知，期望本身应该是p(z|x)，更严谨的写法是：

Jurafsky & Martin 《Speech and Language Processing》

• 批数据
  以上介绍的是给定单条数据O，实际使用中，一般有很多观察集合{O1 O2 •••Ok}，这时候需要估计期望p(z|x)：

LAWRENCE R. RABINER A Tutorial on HMM and Selected Applications in Speech Recogniti

监督学习 vs 非监督学习

对HMM模型来说：

• 监督学习是指数据有隐变量Q的标签，此时只需要求解最大似然确定A、B。
• 非监督学习是指只有隐变量的取值集合，数据本身没有隐变量标签，此时需要通过上文中的前向后向/EM算法学习A、B；注意此时的状态转移矩阵对机器来说只是一个编号，并不能直接对应真实的状态标签，类似聚类出的类别，只代表有这些类但不知道具体是什么类。

应用案例

词性标注：

Jurafsky & Martin 《Speech and Language Processing》

GMM-HMM：

A Learning-Based Approach for Lane Departure Warning Systems With a Personalized Driver Model

DNN-HMM：

总结

HMM是一个有向概率图/贝叶斯网络模型，能够通过序列观察值，推测更能表达事物本质的隐状态。
HMM是通过对p(O Q)建模推测P(Q|O)，是生成式模型，当前状态只和上一时刻状态有关的马尔可夫假设，使模型捕捉上下文信息有所欠缺。
HMM是机器学习非常经典的算法，深度学习时代，对序列建模，采用更多的是RNN、LSTM等。