隐马尔科夫模型算法

㈠ 隐式马尔科夫模型 及 Python + HMMlearn的使用

hmmlearn

隐式马尔科夫模型Hidden Markov Models(HMMs) 是一种通用的概率模型。一个可观测的变量X的序列被一个内部的隐藏状态Z所生成。其中，隐藏状态Z无法被直接观测。在隐藏状态之间的转移被假设是通过 马尔科夫链(Markov chain) 的形式。
模型可以表示为 起始概率向量 和转移概率矩阵 . 一个观测量生成的概率可以是关于 的任意分布， 基于当前的隐藏状态。

HMMs的3个基本问题:

hmmlearn 是Python支持HMMs的包。原来是sklearn的一部分，后来由于接口不一致分成单独的包了。不过使用起来和sklearn的其他模型类似。

构造HMM model:

初始化的参数主要有 n_components , covariance_type , n_iter 。每个参数的作用我还没有研究。

通过 fit 方法。
输入是一个矩阵，包含拼接的观察序列concatenated sequences of observation (也就是samples)，和序列的长度。

EM算法是背后拟合模型的算法。基于梯度优化的方法。通常会卡到一个局部极优值上。通常用户需要用不同的初始化跑多次 fit ，然后选择分数最高的模型。

分数通过 score 方法计算。
推导出的最优的隐藏状态可以调用 predict 方法获得。 predict 方法可以指定解码器算法。当前支持的有 viterbi （Vierbi algorithm）和 map (posteriori estimation)。

㈡ 隐马尔可夫模型

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测从而产生观测随机序列的过程。

隐马尔可夫模型的形式定义如下：

设 是所有可能 状态的集合 ， 是所有可能 观测的集合 ：

其中 为可能状态数， 为可能观测数。

是长度为 的 状态序列 ， 是对应的 观测序列 ：

是 状态转移概率矩阵 ：

其中：

是 观测概率矩阵 ：

其中：

是 初始状态概率向量 ：

其中：

隐马尔可夫模型由初始状态概率向量 、状态转移概率矩阵 和观测概率矩阵 决定。 因此隐马尔可夫模型 可表示为：

具体来说，长度为 的观测序列的生成过程如下：按照初始状态分布 产生状态 ，按状态 的观测概率分布 生成 ，按状态 的状态转移概率分布 产生状态 ，依次递推。

（1） 齐次马尔可夫性假设 ，即隐藏的马尔科夫链在任意时刻 的状态只依赖于其前一时刻的状态，与其他时刻状态及观测无关，也与时刻 无关。

（2） 观测独立性假设 ，即任意时刻的观测只依赖于该时刻的马尔科夫链状态，与其它观测状态无关。

（1） 概率计算问题 ：给定模型 和观测序列 ，计算在模型 下序列 出现的概率 。

（2） 学习问题 ：已知观测序列 ，估计模型 参数，使得在该模型下观测序列 最大。

（3） 预测问题 ：已知模型 和观测序列 ，求使得 最大的状态序列 。

接下来分别阐述这三个问题的解决方法。

状态 的概率是：

对固定的 观测序列 的概率是：

同时出现的联合概率为：

从而：

可以看到，上式是对所有可能的 序列求和，而长度为 的 序列的数量是 数量级的，而 的计算量是 级别的，因此计算量为 ，非常大， 这种算法在实际中不可行 。

首先定义 前向概率 ：给定隐马尔可夫模型 ，定义到时刻 部分观测序列为 且状态为 的概率为前向概率，记作：

观测序列概率的前向算法 如下：

（1）初值：

（2）递推，对 ：

（3）终止：

前向算法高效的关键是 局部计算前向概率，然后利用路径结构将前向概率递推到全局，得到 。前向概率算法计算量是 级别的。

首先定义 后向概率 ：给定隐马尔可夫模型 ，定义在时刻 状态为 的条件下，从 到 部分观测序列为 的概率为后向概率，记作：

观测序列概率的后向算法 如下：

（1）初值：

（2）递推，对 ：

（3）终止：

若有 个长度相同观测序列和对应状态序列 则可利用极大似然估计得到隐马尔可夫模型参数：

设样本中时刻 处于状态 时刻 转移到状态 的频数为 ，那么状态转移概率 的估计为：

设样本中状态为 观测为 的频数为 ，那么观测概率 的估计为：

初始状态 的估计 为 个样本中初始状态为 的频率。

假设给定训练数据只包含 个长度为 的观测序列 而没有对应状态序列，我们可以把状态数据看作不可观测的隐数据 ，则隐马尔可夫模型事实上是一个含有隐变量的概率模型：

其参数可由EM算法实现。

近似算法的思想是，在每个时刻 选择在该时刻最有可能出现的状态 ，从而得到一个状态序列 。

近似算法的优点是计算简单，缺点是不能保证预测的状态序列整体是最有可能的状态序列，因为预测的状态序列可能有实际不发生的部分，比如存在转移概率为0的相邻状态。尽管如此，近似算法还是有用的。

维特比算法实际上是用动态规划解隐马尔可夫模型预测问题，即用动态规划求概率最大路径（最优路径），此路径对应一个状态序列。

定义 在时刻 状态为 的所有单个路径 中概率最大值 为：

由定义得递推式：

定义 在时刻 状态为 的所有单个路径 中概率最大路径的第 个结点 为：

维特比算法 如下：

（1）初始化：

（2）递推，对 :

（3）终止：

（4）回溯，对 ：

最优路径为

㈢ 隐马尔可夫模型的基本问题

1. 评估问题。
给定观测序列 O=O1O2O3…Ot和模型参数λ=(A,B,π)，怎样有效计算某一观测序列的概率，进而可对该HMM做出相关评估。例如，已有一些模型参数各异的HMM，给定观测序列O=O1O2O3…Ot，我们想知道哪个HMM模型最可能生成该观测序列。通常我们利用forward算法分别计算每个HMM产生给定观测序列O的概率，然后从中选出最优的HMM模型。
这类评估的问题的一个经典例子是语音识别。在描述语言识别的隐马尔科夫模型中，每个单词生成一个对应的HMM，每个观测序列由一个单词的语音构成，单词的识别是通过评估进而选出最有可能产生观测序列所代表的读音的HMM而实现的。
2.解码问题
给定观测序列 O=O1O2O3…Ot 和模型参数λ=(A,B,π)，怎样寻找某种意义上最优的隐状态序列。在这类问题中，我们感兴趣的是马尔科夫模型中隐含状态，这些状态不能直接观测但却更具有价值，通常利用Viterbi算法来寻找。
这类问题的一个实际例子是中文分词，即把一个句子如何划分其构成才合适。例如，句子“发展中国家”是划分成“发展-中-国家”，还是“发展-中国-家”。这个问题可以用隐马尔科夫模型来解决。句子的分词方法可以看成是隐含状态，而句子则可以看成是给定的可观测状态，从而通过建HMM来寻找出最可能正确的分词方法。
3. 学习问题。
即HMM的模型参数λ=(A,B,π)未知，如何调整这些参数以使观测序列O=O1O2O3…Ot的概率尽可能的大。通常使用Baum-Welch算法以及Reversed Viterbi算法解决。
怎样调整模型参数λ=(A,B,π)，使观测序列 O=O1O2O3…Ot的概率最大？

㈣ 条件随机场和隐马尔科夫模型最大区别在哪里

隐马尔可夫模型（Hidden Markov Model，HMM），最大熵马尔可夫模型（Maximum Entropy Markov Model，MEMM）以及条件随机场（Conditional Random Field，CRF）是序列标注中最常用也是最基本的三个模型。HMM首先出现，MEMM其次，CRF最后。三个算法主要思想如下：HMM模型是对转移概率和表现概率直接建模，统计共现概率。MEMM模型是对转移概率和表现概率建立联合概率，统计时统计的是条件概率，但MEMM容易陷入局部最优，是因为MEMM只在局部做归一化。CRF模型中，统计了全局概率，在 做归一化时，考虑了数据在全局的分布，而不是仅仅在局部归一化，这样就解决了MEMM中的标记偏置（label bias）的问题。举个例子，对于一个标注任务，“我爱北京天安门“， 标注为” s s b e b c e”对于HMM的话，其判断这个标注成立的概率为 P= P(s转移到s)*P(‘我’表现为s)* P(s转移到b)*P(‘爱’表现为s)* …*P().训练时，要统计状态转移概率矩阵和表现矩 阵。对于MEMM的话，其判断这个标注成立的概率为 P= P(s转移到s|’我’表现为s)*P(‘我’表现为s)* P(s转移到b|’爱’表现为s)*P(‘爱’表现为s)*..训练时，要统计条件状态转移概率矩阵和表现矩阵。对于CRF的话，其判断这个标注成立的概率为 P= F(s转移到s,’我’表现为s)….F为一个函数，是在全局范围统计归一化的概率而不是像MEMM在局部统计归一化的概率。当前，最后出现的CRF在多项任务上达到了统治级的表现，所以如果重头搞应用的话，大家可以首选CRF。

本质上，CRF有以下三个优点：

CRF没有HMM那样严格的独立性假设条件，因而可以容纳任意的上下文信息。特征设计灵活（与ME一样） ————与HMM比较

同时，由于CRF计算全局最优输出节点的条件概率，它还克服了最大熵马尔可夫模型标记偏置（Label-bias）的缺点。 ­­————与MEMM比较

CRF是在给定需要标记的观察序列的条件下，计算整个标记序列的联合概率分布，而不是在给定当前状态条件下，定义下一个状态的状态分布。

凡事都有两面，正由于这些优点，CRF需要训练的参数更多，与MEMM和HMM相比，它存在训练代价大、复杂度高的缺点。