隐马尔科夫链简析.doc

隐马尔可夫模型?(Hidden Markov Model，HMM) 最初由 L. E. Baum 和其它一些学者发表在一系列的统计学论文中，随后在语言识别，自然语言处理以及生物信息等领域体现了很大的价值。平时，经常能接触到涉及?HMM?的相关文章，一直没有仔细研究过，都是蜻蜓点水，因此，想花一点时间梳理下，加深理解，在此特别感谢 52nlp 对 HMM 的详细介绍。 　　考虑下面交通灯的例子，一个序列可能是红-红/橙-绿-橙-红。这个序列可以画成一个状态机，不同的状态按照这个状态机互相交替，每一个状态都只依赖于前一个状态，如果当前的是绿灯，那么接下来就是橙灯，这是一个确定性系统，因此更容易理解和分析，只要这些状态转移都是已知的。但是在实际当中还存在许多不确定性系统。 　　在日常生活当中，我们总是希望根据当前天气的情况来预测未来天气情况，和上面的交通灯的例子不同，我们不能依靠现有知识确定天气情况的转移，但是我们还是希望能得到一个天气的模式。一种办法就是假设这个模型的每个状态都只依赖于前一个的状态，这个假设被称为马尔科夫假设，这个假设可以极大简化这个问题。显然，这个假设也是一个非常糟糕的假设，导致很多重要的信息都丢失了。 　　当涉及到天气的时候，马尔科夫假设描述为，假设如果我们知道之前一些天的天气信息，那么我们就能预测今天的天气。当然，这个例子也是有些不合实际的。但是，这样一个简化的系统可以有利于我们的分析，所以我们通常接受这样的假设，因为我们知道这样的系统能让我们获得一些有用的信息，尽管不是十分准确的。 　　谈到?HMM，首先简单介绍一下马尔可夫过程?(Markov Process)，它因俄罗斯数学家安德烈·马尔可夫而得名，代表数学中具有马尔可夫性质的离散随机过程。该过程中，每个状态的转移只依赖于之前的 n 个状态，这个过程被称为1个 n 阶的模型，其中 n 是影响转移状态的数目。最简单的马尔科夫过程就是一阶过程，每一个状态的转移只依赖于其之前的那一个状态。注意这和确定性系统不一样，因为这种转移是有概率的，而不是确定性的。 　　马尔可夫链是随机变量 X1, … ,?Xn?的一个数列。这些变量的范围，即他们所有可能取值的集合，被称为“状态空间”，而?Xn ?的值则是在时间?n?的状态。如果 Xn+1 对于过去状态的条件概率分布仅是?Xn?的一个函数，则 　　马尔可夫链的在很多应用中发挥了重要作用，例如，谷歌所使用的网页排序算法（PageRank）就是由马尔可夫链定义的。 　　下图展示了天气这个例子中所有可能的一阶转移： 　　注意一个含有 N 个状态的一阶过程有 N2?个状态转移。每一个转移的概率叫做状态转移概率 (state transition probability)，就是从一个状态转移到另一个状态的概率。这所有的 N2?个概率可以用一个状态转移矩阵来表示，其表示形式如下： 　　对该矩阵有如下约束条件： 　　下面就是海藻例子的状态转移矩阵： 　　这个矩阵表示，如果昨天是晴天，那么今天有50%的可能是晴天，37.5%的概率是阴天，12.5%的概率会下雨，很明显，矩阵中每一行的和都是1。 　　为了初始化这样一个系统，我们需要一个初始的概率向量： 　　这个向量表示第一天是晴天。 　　到这里，我们就为上面的一阶马尔科夫过程定义了以下三个部分： 　　状态：晴天、阴天和下雨 　　初始向量：定义系统在时间为0的时候的状态的概率 　　状态转移矩阵：每种天气转换的概率 　　所有的能被这样描述的系统都是一个马尔科夫过程。 　　然而，当马尔科夫过程不够强大的时候，我们又该怎么办呢？在某些情况下，马尔科夫过程不足以描述我们希望发现的模式。 　　例如，一个隐居的人可能不能直观的观察到天气的情况，但是民间传说告诉我们海藻的状态在某种概率上是和天气的情况相关的。在这种情况下我们有两个状态集合，一个可以观察到的状态集合（海藻的状态）和一个隐藏的状态（天气状况）。我们希望能找到一个算法可以根据海藻的状况和马尔科夫假设来预测天气的状况。 　　一个更现实的例子是语音识别，我们听到的声音是声带、喉咙和一起其他的发音器官共同作用的结果。这些因素相互作用，共同决定了每一个单词的声音，而一个语音识别系统检测的声音（可以观察的状态）是人体内部各种物理变化（隐藏的状态、引申一个人真正想表达的意思）产生的。 　　某些语音识别设备把内部的发音机制作为一个隐藏的状态序列，把最后的声音看成是一个和隐藏的状态序列十分相似的可以观察到的状态的序列。在这两个例子中，一个非常重要的地方是隐藏状态的数目和可以观察到的状态的数目可能是不一样的。在一个有3种状态的天气系统（sunny、cloudy、rainy）中，也许可以观察到4种潮湿程度的海藻（dry、dry