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

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

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的概率最大？

2. 马尔科夫的隐马尔可夫模型

隐马尔可夫模型（Hidden Markov Model，HMM）是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如模式识别。

3. 隐马尔可夫模型的基本概述

一种HMM可以呈现为最简单的动态贝叶斯网络。隐马尔可夫模型背后的数学是由LEBaum和他的同事开发的。它与早期由RuslanL.Stratonovich提出的最优非线性滤波问题息息相关，他是第一个提出前后过程这个概念的。在简单的马尔可夫模型（如马尔可夫链），所述状态是直接可见的观察者，因此状态转移概率是唯一的参数。在隐马尔可夫模型中，状态是不直接可见的，但输出依赖于该状态下，是可见的。每个状态通过可能的输出记号有了可能的概率分布。因此，通过一个HMM产生标记序列提供了有关状态的一些序列的信息。注意，“隐藏”指的是，该模型经其传递的状态序列，而不是模型的参数；即使这些参数是精确已知的，我们仍把该模型称为一个“隐藏”的马尔可夫模型。隐马尔可夫模型以它在时间上的模式识别所知，如语音，手写，手势识别，词类的标记，乐谱，局部放电和生物信息学应用。隐马尔可夫模型可以被认为是一个概括的混合模型中的隐藏变量（或变量），它控制的混合成分被选择为每个观察，通过马尔可夫过程而不是相互独立相关。最近，隐马尔可夫模型已推广到两两马尔可夫模型和三重态马尔可夫模型，允许更复杂的数据结构的考虑和非平稳数据建模。

4. 隐马尔可夫模型的模型表达

隐马尔可夫模型（HMM）可以用五个元素来描述，包括2个状态集合和3个概率矩阵：1. 隐含状态 S这些状态之间满足马尔可夫性质，是马尔可夫模型中实际所隐含的状态。这些状态通常无法通过直接观测而得到。（例如S1、S2、S3等等)2. 可观测状态 O在模型中与隐含状态相关联，可通过直接观测而得到。(例如O1、O2、O3等等，可观测状态的数目不一定要和隐含状态的数目一致。）3. 初始状态概率矩阵 π表示隐含状态在初始时刻t=1的概率矩阵，(例如t=1时，P(S1)=p1、P(S2)=P2、P(S3)=p3，则初始状态概率矩阵 π=[ p1 p2 p3 ].4. 隐含状态转移概率矩阵 A。描述了HMM模型中各个状态之间的转移概率。其中Aij = P( Sj | Si ),1≤i,,j≤N.表示在 t 时刻、状态为 Si 的条件下，在 t+1 时刻状态是 Sj 的概率。5. 观测状态转移概率矩阵 B （英文名为Confusion Matrix，直译为混淆矩阵不太易于从字面理解）。令N代表隐含状态数目，M代表可观测状态数目，则：Bij = P( Oi | Sj ), 1≤i≤M,1≤j≤N.表示在 t 时刻、隐含状态是 Sj 条件下，观察状态为 Oi 的概率。总结：一般的，可以用λ=(A,B,π)三元组来简洁的表示一个隐马尔可夫模型。隐马尔可夫模型实际上是标准马尔可夫模型的扩展，添加了可观测状态集合和这些状态与隐含状态之间的概率关系。

5. 隐马尔可夫模型（基础）

假设t时刻的状态只与t-1时刻的状态有关，与更早的时刻无关，这一假设称为一阶马尔可夫假设。如果状态有n种取值，在t时刻取任何一个值与t-1时刻取任何一个值的条件概率构成了一个n×n的矩阵A，称为状态转移概率矩阵。无论t时刻的状态值是什么，在下一时刻一定会转向n个状态种一个，因此他们的转移概率和必须为1。
  
 在实际应用种，人们不能直接观察到状态的值，即状态的值是隐含的，只能得到观测的值。因此对模型进行扩充，得到隐马模型。
  
 观测序列是能得到的值。
  
 状态序列是因，观测序列是果，因为处于某种状态才有了某一观测值。
  
 定义状态观测矩阵B，表示t时刻状态值为s时的观测值为v的概率
  
 t时刻的状态z=i的概率最大状态序列中，t-1时刻的状态值，有了这两个变量，就可以得到维特比算法。
  
 训练时给定一组样本，确定状态转移矩阵和观测矩阵，通过最大似然估计实现。如果已知训练样本集中每个观测序列对应的状态序列，给定初始状态如：p0=[0.5, 0.2, 0.3], k步转化过程为：p0=p0*pk。计算机程序需要利用迭代变量，借助循环实现。经过多步转化p0收敛于固定值(稳态)。可以通过最大似然估计得到模型参数。
  
 
  
  
 状态空间：隐状态S的取值范围
  
 观测空间：观测状态O的取值范围
  
 转移概率：矩阵各元素都是用概率表示。其值非负，并且各行元素之和等于1。在一定条件下是互相转移的，故称为转移概率矩阵。矩阵中的行数与列数可以相等，也可以不等。当它们相等时，矩阵就是一个方阵。由转移概率组成的矩阵就是转移概率矩阵。也就是说构成转移概率矩阵的元素是一个个的转移概率不同状态之间的转移概率，可以用转移矩阵表示，记做a
  
 发射概率：初始状态的概率分布，在知道当前标签的情况下，发射的概率，记做π
                                          
 输出概率：基于当前状态，不同输出的概率分布，记做b
  
 模型参数λ = (a, b, π)
  
 1、 齐次假设：即马尔科夫假设
  
 2、 观测独立性假设：观测值只取决于对应的状态值，与其他状态无关
  
 （1）首先, HMM模型表示为: lambda = HMM(A, B, pi), 其中A, B, pi都是模型的参数, 分别称作: 转移概率矩阵, 发射概率矩阵和初始概率矩阵.
  
 （2）接着, 我们开始训练HMM模型, 语料就是事先准备好的一定数量的观测序列及其对应的隐含序列, 通过极大似然估计求得一组参数, 使由观测序列到对应隐含序列的概率最大.
  
 （3）在训练过程中, 为了简化计算, 马尔可夫提出一种假设: 隐含序列中每个单元的可能性只与上一个单元有关. 这个假设就是著名的隐含假设.
  
 （4）训练后, 我们就得到了具备预测能力的新模型: lambda = HMM(A, B, pi), 其中的模型参数已经改变.
  
 （5）之后给定输入序列(x1, x2, ..., xn), 经过模型计算lambda(x1, x2, ..., xn)得到对应隐含序列的条件概率分布.
  
 （6）最后, 使用维特比算法从隐含序列的条件概率分布中找出概率最大的一条序列路径就是我们需要的隐含序列: (y1, y2, ..., yn).
  
 
  
  
 状态转移矩阵通过训练样本学习得到，采用最大似然估计。
  
 初始状态取每种值的概率Π，状态转移概率矩阵A，观测概率矩阵B
  
 隐马尔可夫模型需要解决以下三个问题：
  
 （1）估值问题（观测序列出现的概率）。给定隐马尔可夫模型的参数A和B，计算一个观测序列x出现的概率值p（x）。前向后向算法
  
 （2）解码问题（观测序列最大化的隐含序列）。给定隐马尔可夫模型的参数A和B以及一个观测序列x，计算最有可能产生此观测序列的状态序列z。
  
 已知一个观测序列，寻找最有可能产生它的状态序列。维特比算法
  
 （3）学习问题。给定隐马尔可夫模型的结构，但参数未知，给定一组训练样本，确定隐马尔可夫模型的参数A和B。
  
 保姆韦尔奇算法
  
 隐马尔可夫模型对条件概率p（x|z）建模，因此是一个生成式模型。

6. 从马尔可夫模型到隐马尔可夫模型

 马尔可夫模型个人认为这个概念应该是从 随机过程 里面提出来的，由马尔可夫过程过来的概念。实际上掌握了随机过程里面对马尔可夫过程的特殊情况：离散参数离散状态的马尔可夫链的数学运算的话。就能够很好解决马尔可夫模型上面的计算问题，包括隐马尔科夫模型。讲马尔可夫模型以及过程重点在于其满足的性质-马尔可夫性。
   随机过程：   现实中时常出现，某个事物满足一定的随机分布，但是其随机分布会随着时间的变化而变化。我们假设其在时刻  符合随机分布  并且用随机变量  来表示。假设  。但是在时间  的时候就符合随机分布  并且用随机变量  来表示。假设  。也就是说某个事物的某个特征会随着时间的变化其对应的分布也会发生变化。这样一个总体的过程，称之为 随机过程。
   具体例子：   灯泡寿命问题，灯泡其实在每个时间点上都有一定的可能性会损坏，在这个时间点上损坏的可能性符合一个具体的正态分布（其  是确定的），而随着时间的久远，灯泡损坏的可能性就变大了。所以在之后的某个时间点上灯泡损坏的可能性可能就符合另外一个具体的正态分布（其  就和先前不一样了，会有变坏的趋势）。灯泡损坏在传统的概率论中也是一个经典例子，可能传统的概率论会认为灯泡的寿命长短符合一个随机分布，并且用一个随机变量来表示，我们研究这个分布的特征。这里和传统的概率论中不一样，可以发现的是，引入了随机过程，可以对随机现象更加深入彻底地描述和研究。
   定义随机过程中的一些量。   参数：也就是上述的时间，如果是和时间有关，往往叫做时间序列。但是很多的现象研究不是和时间相关的。
   状态：也就是上述的随着时间变化的随机变量。
   马尔可夫过程：满足马尔科夫性的随机过程。
   以后再解释   马尔可夫性：   马尔可夫链：
   马尔可夫模型和上述的关系。
   具体讲一下 隐马尔可夫模型。
   和普通的马尔可夫不一样，马尔可夫模型是可以确定状态序列的。也就是说序列上的每个项的分布是怎么样的是已知的。而隐马尔可夫模型是连序列上的每个项的是什么分布都不能够知道，都是随机的。
   对于这样的一个随机模型。   经常要解决三个基本问题：   1). 给定  和  ，求解  。 又叫作 计算问题。   2). 给定  和  ，求解一个状态转换序列  ，使得最优可能产生上面的序列。又叫做估计问题。   3). 在模型参数（A或者B）未知或者参数不准确的情况下，由  来调整参数。又叫做训练问题。
   状态一定是按着产生了部分观察序列来的。考虑前缀。  表示处理到了n,观察序列到n为止都是答案的概率。但是不好转移，转移的时候要枚举前后隐藏状态，考虑把隐藏状态也表示出来。  表示处理到了n，并且第n个状态为j的概率。   范围：     结果：     初始化：     转移：  
   知道  和  ，求Q，状态序列，使得产生  的可能性最大。
   定义：        这个函数的含义是：    模型在时刻t处于状态i，观察到  的最佳状态转换序列的概率。    从而有了转移方程：        而  就是     因此  的转移过程构成了一个图，而Q就是上面的最优路径。
   利用  观察数据进行对模型参数  或者  或者  进行预测和修正，训练问题，又可以叫做预测问题。
   并且这个问题其实是带有隐变量的最大似乎估计，也就是EM算法。   直接讲EM,用数学角度来引入 或者 用递归式来求解含有隐变量的参数估计 都是可以的，后者会比较清楚。   但是课上老师给出了另外一种比较好的解释：   考虑第三个问题，实际上应该分两种情况。   1：带指导的参数学习。   给出的数据是这样的：   状态/观察数据。   硬币中的例子就是   H/1 H/1 T/1 T/2 H/3 T/3 T/2 H/1 T/2 H/3 H/3 H/1   其实当拥有了数据 状态/观察数据 是可以直接对参数进行估计的。   假设是齐次的（一般也是齐次的，概率只和状态有关，和时间关系不大，放在词句中就是词语所在的句子的部位关系不是很大，而是上下文内容关系比较大。），
   考虑aij 指的是在状态i和状态j的转移概率。   可以直接对上面2个2个统计进行参数估计。   考虑bi(o_j)也就是状态为i输出为o_j的。   一个一个枚举来即可。   考虑pi_i。也就是初始状态。   一个一个枚举状态即可。
   带有指导的是有缺点的：   数据上不可行，状态这样的数据其实都是人工标注的。   数据量要求比较大。
   但是在NLP中这个方法是很重要的。因为效果比较好。
   2：不带指导的参数学习   数据上只给出了 观察序列，没有状态序列。
   实际上1中就出了答案。没有状态序列，我们就枚举状态序列。   比如上述。如果观察出来了   1 2 2   那么我们就考虑以下   1 2 2   HHH   HHT   HTH   HTT   THH   THT   TTH   TTT   所有情况。   所以就产生了   H/1 H/2 H/2   H/1 H/2 T/2   ....   然后分组进行统计参数估计即可。
   但是这里有两个问题：   1：状态太多了。N^T。   2：给每个状态的权重是一样的。不是很科学。（实际上还行，如果使用熵最大原理。）   那么怎么办？解决2考虑给不同状态加权重，那么要有一个先验的的知识：   咱们先给出先验的 模型参数。   那么就可以计算P(Q|O,人)P（Q,O|人）这样的东西了。   明显可以用P(Q|O,人)作为一个路径序列的权重。   但是这样计算的时候，路径序列很长。并且转移路径还是N^T条。   不可行。
   避开对路径的考虑。考虑参数abt最多只有涉及两个时间点的。   我们如果只关注两个时间点之间的状态。那么就可以变成二维的。   使Q不是一个路径的。而是只是两个时间点之间的状态。   q_t = i q_t+1 = j 。把这个概率计算出来的话。就能直接对aij这样的进行估计了。   （实际上只是换了一种计数方式，就减少了问题规模，因为咱们关注的也只是路径上两个点两个点之间的。）
   由此引出Baum_Welch算法：
   定义以下：
   这样就能对参数们进行评估了。有以下：
   这样只要挑一个满足条件的初始值，然后迭代求解即可。

7. 如何用简单易懂的例子解释隐马尔可夫模型

8. 隐马尔可夫模型的历史

隐马尔可夫模型最初是在20世纪60年代后半期Leonard E. Baum和其它一些作者在一系列的统计学论文中描述的。HMM最初的应用之一是开始于20世纪70年代中期的语音识别。在1980年代后半期，HMM开始应用到生物序列尤其是DNA的分析中。此后，在生物信息学领域HMM逐渐成为一项不可或缺的技术。