viterbi算法_HMM（一）：Graphical Model，HMM，Viterbi

HMM是一类时序模型，在说HMM之前先简单介绍一下Graphical Model 以便于更好理解HMM。

一、Graphical Models

从上图可以看到HMM其可以理解为一个Bayesian Network的一个特例。

1. 有向图的概率表示

对于有向图而言，使用条件概率表示起来比较容易，写成公式如下：

这样每个节点都可以用条件概率的形式表示出来， 整个图就是所有节点的 Joint Probablity。

2. 无相图的概率表示

无向图的概率表示就不那么直观了，主要原因是你并不知道节点之间谁和谁到底是什么关系，你只知道他们之间是有关系的。因此就需要一组函数作用在图中的 Clique上表示他们的关系， 这组函数也被成为

Compatibility Function

或者

Potential Function。 假设表示下图：

每个红圈表示一个

Clique，

整个概率图表示形式如下：

Z

: 表示为normalization term, 由于每一个

得到的只是一个

Clique

关系紧密程度的打分，并不是真正意义上的概率值，需要一个全局的归一化，把这一切变成概率值，满足下面两个条件。

: 表示一个

Compatibility Function

用来衡量一个

Clique

中节点之间的关系， 需要自行定义。

由此可见， 概率图事实上表示的是一个关系， 无论有向图还是无向图都是用各种手段来表示这个关系。

二、HMM 相关的四个问题

之前在学习EM算法时候提到了投硬币实验，当时为了简化问题， 把A，B两枚硬币投掷的次序当是相互独立的事件。 在HMM中，重新看一下这个例子。 假设我们有A，B两个硬币，他们正反面的概率分别为

。 这个过程如下图表示， H，T 表示正反面：

在这个过程中，存在着几组需要关注的值和参数：

变量

：

（1）Z: 隐变量（状态)， 这里表示到底是A硬币还是B硬币。

（2）X: 可观测数据， 这里代表硬币正反面。

模型参数

（3）

：2x2 状态转移矩阵， 两个状态A，B之间两两转移概率分布。

（4）

： 表示两个状态A，B生成T，H的概率矩阵。

对于模型中变量和参数， 在使用HMM的过程中可能遇到下面三个问题：

1. 模型参数

   

   已知， X可观测时， 求Z，就是个 Inference 问题， 使用Viterbi算法。
2. 模型参数

   

   已知，Z已知， 求

   

   ， 需要使用DP算法得到

   

3. 模型参数

   

   未知，X，Z 已知时， 可以通过 MLE 进行模型参数估计。
4. 模型参数

   

   未知，X已知， Z未知时， 由于隐变量Z未知，需要使用 EM-style 进行参数估计。

HMM 本质上是一个生成模型，用硬币的例子来说， 如果A， B 抛出顺序可知， 参数可知， 那么生成观察值的分布就可知了。 用模型的参数可以采样出符合这个分布的各种观察值序列。

三、 Viterbi算法，使用训练好的HMM参数，预测最好的隐变量Z

HMM在应用过程中其中一个比较重要的问题就是在观测值已知的情况下使用训练好的模型参数来预测隐变量Z，比较经典的应用是NLP领域中词性标注。 给定句子的每个词通过HMM来预测每个词的词性标签。 而这个过程用到的算法就是Viterbi算法。 再说Viterbi算法之前，先重新定义一下HMM参数的结构。

1. 模型和参数

变量定义：

： 隐藏状态， 假设有

个状态，

: 可观测到的序列数据， 共有

中可能性，序列长度为

参数定义：

：状态概率转移矩矩阵，维度

：发射概率转移矩阵，维度

: 初始状态概率矩阵, 维度

2. Viterbi 算法的原理和应用场景。

假如我们的应用是一个词性标注任务，使用上面定义好的模型HMM模型 ， 参数

已经训练好，

是词性，

是词表大小，

是词性的个数。给定一个长度为

新的词序列

，如何找到最优的词性序列

呢？ 如果使用暴力穷举的方法，我们可以通过参数找到所有的可能的状态

到给定

的概率，并找到最大的那个

的组合。 由于我们有

中可能的状态，长度有

个词，需要遍历的搜索空间就是

这么多。

除此之外我们有更好的方法解决这个问题，那就是Viterbi算法。 Viterbi算法本质上就是一种动态规划方法， 我们在搜索空间中寻找最优解的过程等同于寻找一条符合要求的最优路径。 如下图所示：

是每一种可能的状态生成这当前时间步骤的可能性,

是序列长度， 目标是找一条序列穿越

个时间步骤，并且概率得分最大， 概率得分为概率值取

，防止underflow的问题， 动态规划算法最重要的是定义子问题， 那么这里的子问题就是每个格子的得分和计算方法。

上图定义了任意一个格子的得分函数，第

得分定义为：

， 它有

种方式获得， 即为前一个状态有

种可能性。 即为：

其中

可以从

转移矩阵中找到，

可以再发射矩阵

中找到。第一列由于是起始状态，直接可以用发射概率填补。

按照上面的结构把表格里的每个元素填完整并且，存储从哪一个状态转移过来的信息，类似下面的形式。

这样就可以追溯到任意一个末端的路径， 这就可以序列结束的时候整体找到最优路径。 这个算法的算法复杂度为

，要比暴力搜索要快很多。

OK第一篇HMM就整理这么多， 后续在陆续整理，参数估计，CRF等内容。