隐马尔科夫模型HMM自学

介绍

崔晓源 翻译

我们通常都习惯寻找一个事物在一段时间里的变化规律。在很多领域我们都希望找到这个规律，比如计算机中的指令顺序，句子中的词顺序和语音中的词顺序等等。一个最适用的例子就是天气的预测。

首先，本文会介绍声称概率模式的系统，用来预测天气的变化

然后，我们会分析这样一个系统，我们希望预测的状态是隐藏在表象之后的，并不是我们观察到的现象。比如，我们会根据观察到的植物海藻的表象来预测天气的状态变化。

最后，我们会利用已经建立的模型解决一些实际的问题，比如根据一些列海藻的观察记录，分析出这几天的天气状态。

Generating Patterns

有两种生成模式：确定性的和非确定性的。

确定性的生成模式 ：就好比日常生活中的红绿灯，我们知道每个灯的变化规律是固定的。我们可以轻松的根据当前的灯的状态，判断出下一状态。

非确定性的生成模式： 比 如说天气晴、多云、和雨。与红绿灯不同，我们不能确定下一时刻的天气状态，但是我们希望能够生成一个模式来得出天气的变化规律。我们可以简单的假设当前的 天气只与以前的天气情况有关，这被称为马尔科夫假设。虽然这是一个大概的估计，会丢失一些信息。但是这个方法非常适于分析。

马尔科夫过程就是当前的状态只与前n个状态有关。这被称作n阶马尔科夫模型。最简单的模型就当n=1时的一阶模型。就当前的状态只与前一状态有关。（这里要注意它和确定性生成模式的区别，这里我们得到的是一个概率模型）。下图是所有可能的天气转变情况：

对于有M个状态的一阶马尔科夫模型，共有M*M个状态转移。每一个状态转移都有其一定的概率，我们叫做转移概率，所有的转移概率可以用一个矩阵表示。在整个建模的过程中，我们假设这个转移矩阵是不变的。

该矩阵的意义是：如果昨天是晴，那么今天是晴的概率为0.5，多云的概率是0.25，雨的概率是0.25。注意每一行和每一列的概率之和为1。

另外，在一个系统开始的时候，我们需要知道一个初始概率，称为 向量。

到现在，我们定义了一个一阶马尔科夫模型，包括如下概念：

状态：晴、多云、雨

状态转移概率

初始概率

马尔科夫模型也需要改进！

崔晓源 翻译

当 一个隐士不能通过直接观察天气状态来预测天气时，但他有一些水藻。民间的传说告诉我们水藻的状态与天气有一定的概率关系。也就是说，水藻的状态与天气时紧 密相关的。此时，我们就有两组状态：观察状态（水藻的状态）和隐含状态（天气状态）。因此，我们希望得到一个算法可以为隐士通过水藻和马尔科夫过程，在没 有直接观察天气的情况下得到天气的变化情况。

更容易理解的一个应用就是语音识别，我们的问题定义就是如何通过给出的语音信号预测出原来的文字信息。在这里，语音信号就是观察状态，识别出的文字就是隐含状态。

这里需要注意的是，在任何一种应用中，观察状态的个数与隐含状态的个数有可能不一样的。下面我们就用隐马尔科夫模型HMM来解决这类问题。

HMM

下图是天气例子中两类状态的转移图，我们假设隐状态是由一阶马尔科夫过程描述，因此他们相互连接。

隐状态和观察状态之间的连线表示：在给定的马尔科夫过程中，一个特定的隐状态对应的观察状态的概率。我们同样可以得到一个矩阵：

注意每一行（隐状态对应的所有观察状态）之和为1。

到此，我们可以得到HMM的所有要素：两类状态和三组概率

两类状态：观察状态和隐状态；

三组概率：初始概率、状态转移概率和两态对应概率（confusion matrix）

HMM 定义

崔晓源 翻译

HMM是一个三元组 ( ,A,B).

 the vector of the initial state probabilities;

  the state transition matrix; 

  the confusion matrix; 

这其中，所有的状态转移概率和混淆概率在整个系统中都是一成不变的。这也是HMM中最不切实际的假设。

HMM的应用

有三个主要的应用：前两个是模式识别后一个作为参数估计

(1) 评估

根据已知的HMM找出一个观察序列的概率。

这 类问题是假设我们有一系列的HMM模型，来描述不同的系统（比如夏天的天气变化规律和冬天的天气变化规律），我们想知道哪个系统生成观察状态序列的概率最 大。反过来说，把不同季节的天气系统应用到一个给定的观察状态序列上，得到概率最大的哪个系统所对应的季节就是最有可能出现的季节。（也就是根据观察状态 序列，如何判断季节）。在语音识别中也有同样的应用。

我们会用forward algorithm 算法来得到观察状态序列对应于一个HMM的概率。

(2) 解码

根据观察序列找到最有可能出现的隐状态序列

回想水藻和天气的例子，一个盲人隐士只能通过感受水藻的状态来判断天气状况，这就显得尤为重要。我们使用viterbi algorithm 来解决这类问题。

viterbi算法也被广泛的应用在自然语言处理领域。比如词性标注。字面上的文字信息就是观察状态，而词性就是隐状态。通过HMM我们就可以找到一句话上下文中最有可能出现的句法结构。

(3) 学习

从观察序列中得出HMM

这是最难的HMM应用。也就是根据观察序列和其代表的隐状态，生成一个三元组HMM ( ,A,B)。使这个三元组能够最好的描述我们所见的一个现象规律。

我们用forward-backward algorithm 来解决在现实中经常出现的问题--转移矩阵和混淆矩阵不能直接得到的情况。

总结 HMM可以解决的三类问题

1.Matching the most likely system to a sequence of observations -evaluation, solved using the forward algorithm;

2.determining the hidden sequence most likely to have generated a sequence of observations - decoding, solved using the Viterbi algorithm;

3.determining the model parameters most likely to have generated a sequence of observations - learning, solved using the forward-backward algorithm. 

找到观察序列的概率

崔晓源 翻译

Finding the probability of an observed sequence

1、穷举搜索方法

对于水藻和天气的关系，我们可以用穷举搜索方法的到下面的状态转移图（trellis）：

图中，每一列于相邻列的连线由状态转移概率决定，而观察状态和每一列的隐状态则由混淆矩阵决定。如果用穷举的方法的到某一观察状态序列的概率，就要求所有可能的天气状态序列下的概率之和，这个trellis有3*3=27个可能的序列。

Pr(dry,damp,soggy | HMM) = Pr(dry,damp,soggy | sunny,sunny,sunny) + Pr(dry,damp,soggy | sunny,sunny ,cloudy) + Pr(dry,damp,soggy | sunny,sunny ,rainy) + . . . . Pr(dry,damp,soggy | rainy,rainy ,rainy)

可见计算复杂度是很大，特别是当状态空间很大，观察序列很长时。我们可以利用概率的时间不变性 解决复杂度。

2、采用递归方法降低复杂度

我们采用递归的方式计算观察序列的概率，首先定义部分概率 为到达trellis中某一中间状态的概率。在后面的文章里，我们把长度为T的观察状态序列表示为：

2a. Partial probabilities, ( 's)

在计算trellis中某一中间状态的概率时，用所有可能到达该状态的路径之和表示。

比如在t=2时间，状态为cloudy的概率可以用下面的路径计算：

用 t ( j ) 表示在时间t时 状态j的部分概率。计算方法如下：

 t ( j )= Pr( observation | hidden state is j ) * Pr(all paths to state j at time t)

最后的观察状态的部分概率表示，这些状态所经过的所有可能路径的概率。比如：

这表示最后的部分概率的和即为trellis中所有可能路径的和，也就是当前HMM下观察序列的概率。

Section 3  会给出一个动态效果介绍如何计算概率。

2b.计算初始状态的部分概率

我们计算部分概率的公式为:

 t ( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t)

但是在初始状态，没有路径到达这些状态。那么我们就用probability乘以associated observation probability计算：

这样初始时刻的状态的部分概率就只与其自身的概率和该时刻观察状态的概率有关