隐马尔可夫模型HMM

隐马尔可夫模型(HiddenMarkovModel，HMM)最初由L.E.Baum和其它一些学者发表在一系列的统计学论文中，随后在语言识别，自然语言处理以及生物信息等领域体现了很大的价值。平时，经常能接触到涉及HMM的相关文章，一直没有仔细研究过，都是蜻蜓点水，因此，想花一点时间梳理下，加深理解，在此特别感谢52nlp对HMM的详细介绍。考虑下面交通灯的例子，一个序列可能是红-红/橙-绿-橙-红。这个序列可以画成一个状态机，不同的状态按照这个状态机互相交替，每一个状态都只依赖于前一个状态，如果当前的是绿灯，那么接下来就是橙灯，这是一个确定性系统，因此更容易理解和分析，只要这些状态转移都是已知的。但是在实际当中还存在许多不确定性系统。在日常生活当中，我们总是希望根据当前天气的情况来预测未来天气情况，和上面的交通灯的例子不同，我们不能依靠现有知识确定天气情况的转移，但是我们还是希望能得到一个天气的模式。一种办法就是假设这个模型的每个状态都只依赖于前一个的状态，这个假设被称为马尔科夫假设，这个假设可以极大简化这个问题。显然，这个假设也是一个非常糟糕的假设，导致很多重要的信息都丢失了。当涉及到天气的时候，马尔科夫假设描述为，假设如果我们知道之前一些天的天气信息，那么我们就能预测今天的天气。当然，这个例子也是有些不合实际的。但是，这样一个简化的系统可以有利于我们的分析，所以我们通常接受这样的假设，因为我们知道这样的系统能让我们获得一些有用的信息，尽管不是十分准确的。谈到HMM，首先简单介绍一下马尔可夫过程(MarkovProcess)，它因俄罗斯数学家安德烈·马尔可夫而得名，代表数学中具有马尔可夫性质的离散随机过程。该过程中，每个状态的转移只依赖于之前的n个状态，这个过程被称为1个n阶的模型，其中n是影响转移状态的数目。最简单的马尔科夫过程就是一阶过程，每一个状态的转移只依赖于其之前的那一个状态。注意这和确定性系统不一样，因为这种转移是有概率的，而不是确定性的。马尔可夫链是随机变量X1,…,Xn的一个数列。这些变量的范围，即他们所有可能取值的集合，被称为“状态空间”，而Xn的值则是在时间n的状态。如果Xn+1对于过去状态的条件概率分布仅是Xn的一个函数，则这里x为过程中的某个状态。上面这个恒等式可以被看作是马尔可夫性质。马尔可夫链的在很多应用中发挥了重要作用，例如，谷歌所使用的网页排序算法（PageRank）就是由马尔可夫链定义的。下图展示了天气这个例子中所有可能的一阶转移：注意一个含有N个状态的一阶过程有N2个状态转移。每一个转移的概率叫做状态转移概率(statetransitionprobability)，就是从一个状态转移到另一个状态的概率。这所有的N2个概率可以用一个状态转移矩阵来表示，其表示形式如下：对该矩阵有如下约束条件：下面就是海藻例子的状态转移矩阵：这个矩阵表示，如果昨天是晴天，那么今天有50%的可能是晴天，37.5%的概率是阴天，12.5%的概率会下雨，很明显，矩阵中每一行的和都是1。为了初始化这样一个系统，我们需要一个初始的概率向量：这个向量表示第一天是晴天。到这里，我们就为上面的一阶马尔科夫过程定义了以下三个部分：状态：晴天、阴天和下雨初始向量：定义系统在时间为0的时候的状态的概率状态转移矩阵：每种天气转换的概率所有的能被这样描述的系统都是一个马尔科夫过程。然而，当马尔科夫过程不够强大的时候，我们又该怎么办呢？在某些情况下，马尔科夫过程不足以描述我们希望发现的模式。例如，一个隐居的人可能不能直观的观察到天气的情况，但是民间传说告诉我们海藻的状态在某种概率上是和天气的情况相关的。在这种情况下我们有两个状态集合，一个可以观察到的状态集合（海藻的状态）和一个隐藏的状态（天气状况）。我们希望能找到一个算法可以根据海藻的状况和马尔科夫假设来预测天气的状况。一个更现实的例子是语音识别，我们听到的声音是声带、喉咙和一起其他的发音器官共同作用的结果。这些因素相互作用，共同决定了每一个单词的声音，而一个语音识别系统检测的声音（可以观察的状态）是人体内部各种物理变化（隐藏的状态、引申一个人真正想表达的意思）产生的。某些语音识别设备把内部的发音机制作为一个隐藏的状态序列，把最后的声音看成是一个和隐藏的状态序列十分相似的可以观察到的状态的序列。在这两个例子中，一个非常重要的地方是隐藏状态的数目和可以观察到的状态的数目可能是不一样的。在一个有3种状态的天气系统（sunny、cloudy、rainy）中，也许可以观察到4种潮湿程度的海藻（dry、dryish、damp、soggy）。在语音识别中，一个简单的发言也许只需要80个语素来描述，但是一个内部的发音机制可以产生不到80或者超过80种不同的声音。在上面的这些情况下，可以观察到的状态序列和隐藏的状态序列是概率相关的。于是我们可以将这种类型的过程建模为有一个隐藏的马尔科夫过程和一个与这个隐藏马尔科夫过程概率相关的并且可以观察到的状态集合。这就是本文重点介绍的隐马尔可夫模型。隐马尔可夫模型(HiddenMarkovModel)是一种统计模型，用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数，然后利用这些参数来作进一步的分析。下图是一个三个状态的隐马尔可夫模型状态转移图，其中x表示隐含状态，y表示可观察的输出，a表示状态转换概率，b表示输出概率。下图显示了天气的例子中隐藏的状态和可以观察到的状态之间的关系。我们假设隐藏的状态是一个简单的一阶马尔科夫过程，并且他们两两之间都可以相互转换。对HMM来说，有如下三个重要假设，尽管这些假设是不现实的。假设1：马尔可夫假设（状态构成一阶马尔可夫链）假设2：不动性假设（状态与具体时间无关）假设3：输出独立性假设（输出仅与当前状态有关）隐藏的状态和可观察到的状态之间有一种概率上的关系，也就是说某种隐藏状态H被认为是某个可以观察的状态O1是有概率的，假设为P(O1|H)。如果可以观察的状态有3种，那么很显然P(O1|H)+P(O2|H)+P(O3|H)=1。这样，我们也可以得到一个另一个矩阵，称为混淆矩阵(confusionmatrix)。这个矩阵的内容是某个隐藏的状态被分别观察成几种不同的可以观察的状态的概率，在天气的例子中，这个矩阵如下图：上边的图示都强调了HMM的状态变迁。而下图则明确的表示出模型的演化，其中绿色的圆圈表示隐藏状态，紫色圆圈表示可观察到状态，箭头表示状态之间的依存概率，一个HMM可用一个5元组{N,M,π，A，B}表示，其中N表示隐藏状态的数量，我们要么知道确切的值，要么猜测该值，M表示可观测状态的数量，可以通过训练集获得，π={πi}为初始状态概率，A={aij}为隐藏状态的转移矩阵Pr(xt(i)|xt-1(j))，B={bik}表示某个时刻因隐藏状态而可观察的状态的概率，即混淆矩阵，Pr(ot(i)|xt(j))。在状态转移矩阵和混淆矩阵中的每个概率都是时间无关的，即当系统演化时，这些矩阵并不随时间改变。对于一个N和M固定的HMM来说，用λ={π,A,B}表示HMM参数。在正常的马尔可夫模型中，状态对于观察者来说是直接可见的。这样状态的转换概率便是全部的参数。而在隐马尔可夫模型中，状态并不是直接可见的，但受状态影响的某些变量则是可见的。每一个状态在可能输出的符号上都有一概率分布。因此输出符号的序列能够透露出状态序列的一些信息。在HMM中有三个典型问题：（一）已知模型参数，计算某一给定可观察状态序列的概率假设我们已经有一个特定的隐马尔科夫模型λ和一个可观察状态序列集。我们也许想知道在所有可能的隐藏状态序列下，给定的可观察状态序列的概率。当给定如下一个隐藏状态序列：那么在HMM和这个隐藏状态序列的条件下，可观察状态序列的概率为：而隐藏状态序列在HMM条件下的概率为：因此，隐藏状态序列和可观察状态序列的联合概率为：那么所有可能的隐藏状态序列上，可观察状态序列的概率为：例如，我们也许有一个海藻的“Summer”模型和一个“Winter”模型，因为海藻在夏天和冬天的状态应该是不同的，我们希望根据一个可观察状态（海藻的潮湿与否）序列来判断现在是夏天还是冬天。我们可以使用前向算法来计算在某个特定的HMM下一个可观察状态序列的概率，然后据此找到最可能的模型。这种类型的应用通常出现在语音设别中，通常我们会使用很多HMM，每一个针对一个特别的单词。一个可观察状态的序列是从一个可以听到的单词向前得到的，然后这个单词就可以通过找到满足这个可观察状态序列的最大概率的HMM来识别。下面介绍一下前向算法(ForwardAlgorithm)如何计算一个可观察序列的概率？1.穷举搜索给定一个HMM，我们想计算出某个可观察序列的概率。考虑天气的例子，我们知道一个描述天气和海藻状态的HMM，而且我们还有一个海藻状态的序列。假设这个状态中的某三天是（dry，damp，soggy），在这三天中的每一天，天气都可能是晴朗，多云或者下雨，我们可以用下图来描述观察序列和隐藏序列：在这个图中的每一列表示天气的状态可能，并且每个状态都指向相邻的列的每个状态，每个状态转换在状态转移矩阵中都有一个概率。每一列的下面是当天的可观察的海藻的状态，在每种状态下出现这种可观察状态的概率是由混淆矩阵给出的。一个可能的计算可观察概率的方法是找到每一个可能的隐藏状态的序列，这里有32=27种，这个时候的可观察序列的概率就是Pr(dry,damp,soggy|HMM)=Pr(dry,damp,soggy|sunny,sunny,sunny)+....+Pr(dry,damp,soggy|rainy,rainy,rainy)。很显然，这种计算的效率非常低，尤其是当模型中的状态非常多或者序列很长的时候。事实上，我们可以利用概率不随时间变化这个假设来降低时间的开销。2.使用递归来降低复杂度我们可以考虑给定HMM的情况下，递归的计算一个可观察序列的概率。我们可以首先定义一个部分概率，表示达到某个中间状态的概率。接下来我们将看到这些部分概率是如何在time=1和time=n(n1)的时候计算的。假设一个T时间段的可观察序列是：1)部分概率下面这张图表示了一个观察序列（dry，damp，soggy）的一阶转移我们可以通过计算到达某个状态的所有路径的概率和来计算到达某个中间状态的概率。比如说，t=2时刻，cloudy的概率用三条路径的概率之和来表示：我们用αt(j)来表示在t时刻是状态j的概率，αt(j)=Pr(观察状态|隐藏状态j)xPr(t时刻到达状态j的所有路径)。最后一个观察状态的部分概率就表示了整个序列最后达到某个状态的所有可能的路径的概率和，比如说在这个例子中，最后一列的部分状态是通过下列路径计算得到的：因为最后一列的部分概率是所有可能的路径的概率和，所以就是这个观察序列在给定HMM下的概率了。2)计算t=1时候的部分概率当t=1的时候，没有路径到某个状态，所以这里是初始概率，Pr(状态j|t=0)=π(状态j)，这样我们就可以计算t=1时候的部分概率为：因为在初始的时候，状态j的概率不仅和这个状态本身相关，还和观察状态有关，所以这里用到了混淆矩阵的值，k1表示第一个观察状态，bjk1表示隐藏状态是j，但是观察成k1的概率。3)计算t1时候的部分概率还是看计算部分概率的公式是：αt(j)=Pr(观察状态|隐藏状态j)xPr(t时刻到达状态j的所有路径)。这个公式的左边是从混淆矩阵中已知的，我只需要计算右边部分，很显然右边是所有路径的和：需要计算的路径数是和观察序列的长度的平方相关的，但是t时刻的部分概率已经计算过了之前的所有路径，所以在t+1时刻只需要根据t时刻的概率来计算就可以了：这里简单解释下，bjk(t+1)就是在t+1时刻的第j个隐藏状态被认为是当前的观察状态的概率，后面一部分是所有t时刻的隐藏状态到t+1时候的隐藏状态j的转移的概率的和。这样我们每一步的计算都可以利用上一步的结果，节省了很多时间。4)公式推导5)降低计算复杂度我们可以比