注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

眼睛想旅行

技术就是我的生命与信仰!

 
 
 

日志

 
 
关于我

精通C,C++,python,Erlang。并熟悉各种其他编程语言,用cocos2dx游戏引擎作过几个项目。会MySQL增删改查,了解OpenGL渲染原理。懂单片机,能设计数字电路系统,会画电路图和设计电路板。喜欢了解最新前沿技术,并持续关注和学习新技术。

网易考拉推荐

马尔可夫模型(HMM)与隐马尔克夫模型(转)  

2010-07-18 13:33:51|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

马尔可夫模型

        马尔可夫模型:是用来预测具有等时间隔(如一年)的时刻点上各类人员的分布状况。

  马尔可夫模型,它是根据历史数据,预测等时间间隔点上的各类人员分布状况。此方法的基本思想上根据过去人员变动的规律,推测未来人员变动的趋势。步骤如下:

  ①根据历史数据推算各类人员的转移率,迁出转移率的转移矩阵; 

  ②统计作为初始时刻点的各类人员分布状况;

  ③建立马尔科夫模型,预测未来各类人员供给状况。

隐马尔可夫模型

         马尔可夫模型(Hidden Markov Model,HMM)作为一种统计分析模型,创立于20世纪70年代。80

年代得到了传播和发展,成为信号处理的一个重要方向,现已成功地用于语音识别,行为识别,文字识别以及故障诊断等领域。

 

马尔可夫模型(HMM)与隐马尔克夫模型(转) - ♂苹果 - 眼睛想旅行

         隐马尔可夫模型是马尔可夫链的一种,它的状态不能直接观察到,但能通过观测向量序列观察到,每个观测向量都是通过某些概率密度分布表现为各种状态,每一个观测向量是由一个具有响应概率密度分布的状态序列产生。所以,隐马尔可夫模型是一个双重随机过程----具有一定状态数的隐马尔可夫链和显示随机函数集。自20世纪80年代以来,HMM被应用于语音识别,取得重大成功。到了90年代,HMM还被引入计算机文字识别和移动通信核心技术“多用户的检测”。近年来,HMM在生物信息科学、故障诊断等领域也开始得到应用。

          模型的表达:

        隐马尔可夫模型(HMM)可以用五个元素来描述,包括2个状态集合和3个概率矩阵:
  1. 隐含状态 S
  这些状态之间满足马尔可夫性质,是马尔可夫模型中实际所隐含的状态。这些状态通常无法通过直接观测而得到。(例如S1、S2、S3等等)
  2. 可观测状态 O
  在模型中与隐含状态相关联,可通过直接观测而得到。(例如O1、O2、O3等等,可观测状态的数目不一定要和隐含状态的数目一致。)
  3. 初始状态概率矩阵 π 
  表示隐含状态在初始时刻t=1的概率矩阵,(例如t=1时,P(S1)=p1、P(S2)=P3、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,π)三元组来简洁的表示一个隐马尔可夫模型。隐马尔可夫模型实际上是标准马尔可夫模型的扩展,添加了可观测状态集合和这些状态与隐含状态之间的概率关系。

 

        应用HMM通常解决的3类基本问题

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

针对以上三个问题,人们提出了相应的算法
  *1 评估问题: 向前向后算法
  *2 解码问题: Viterbi算法
  *3 学习问题: Baum-Welch算法

隐马尔可夫模型学习

介绍

崔晓源 翻译

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

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

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

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

Generating Patterns

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

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

马尔可夫模型(HMM)与隐马尔克夫模型(转) - ♂苹果 - 眼睛想旅行 

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

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

马尔可夫模型(HMM)与隐马尔克夫模型(转) - ♂苹果 - 眼睛想旅行 

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

马尔可夫模型(HMM)与隐马尔克夫模型(转) - ♂苹果 - 眼睛想旅行 

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

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

马尔可夫模型(HMM)与隐马尔克夫模型(转) - ♂苹果 - 眼睛想旅行 

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

状态:晴、多云、雨

状态转移概率

初始概率

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

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

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

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

HMM

下图是天气例子中两类状态的转移图,我们假设隐状态是由一阶马尔科夫过程描述,因此他们相互连接。马尔可夫模型(HMM)与隐马尔克夫模型(转) - ♂苹果 - 眼睛想旅行


隐状态和观察状态之间的连线表示:在给定的马尔科夫过程中,一个特定的隐状态对应的观察状态的概率。我们同样可以得到一个矩阵:
马尔可夫模型(HMM)与隐马尔克夫模型(转) - ♂苹果 - 眼睛想旅行
注意每一行(隐状态对应的所有观察状态)之和为1。
到此,我们可以得到HMM的所有要素:两类状态和三组概率
 
两类状态:观察状态和隐状态;
三组概率:初始概率、状态转移概率和两态对应概率(confusion matrix)

HMM 定义

崔晓源 翻译

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

P : the vector of the initial state probabilities;

 A : the state transition matrix;

 B : the confusion matrix;

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

HMM的应用

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

(1) 评估

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

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

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

(2) 解码

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

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

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

(3) 学习

从观察序列中得出HMM

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

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

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


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

 


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

 


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

http://blogcui.spaces.live.com/blog/cns!46BDB23E24219CE9!148.entry?_c=BlogPart


 

找到观察序列的概率

崔晓源 翻译

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的观察状态序列表示为:
Y{k{1}}, Y{k{2}}, .... , Y{k{T}}
 
2a. Partial probabilities, (a's)

在计算trellis中某一中间状态的概率时,用所有可能到达该状态的路径之和表示。
比如在t=2时间,状态为cloudy的概率可以用下面的路径计算:

at ( j ) 表示在时间t时 状态j的部分概率。计算方法如下:
at ( j )= Pr( observation | hidden state is j ) * Pr(all paths to state j at time t)
最后的观察状态的部分概率表示,这些状态所经过的所有可能路径的概率。比如:

这表示最后的部分概率的和即为trellis中所有可能路径的和,也就是当前HMM下观察序列的概率。
Section 3  会给出一个动态效果介绍如何计算概率。
 
2b.计算初始状态的部分概率
我们计算部分概率的公式为:
a t ( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t)
但是在初始状态,没有路径到达这些状态。那么我们就用probability乘以associated observation probability计算:
formula
这样初始时刻的状态的部分概率就只与其自身的概率和该时刻观察状态的概率有关。

Forward Algorithm

崔晓源 翻译

书接上文,前一话我们讲到了Forward Algorithm中初始状态的部分概率的计算方法。这次我们继续介绍。

2c.如何计算t>1时刻的部分概率

回忆一下我们如何计算部分概率:

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

我们可知(通过递归)乘积中第一项是可用的。那么如何得到Pr(all paths to state j at time t) 呢?

为了计算到达一个状态的所有路径的概率,就等于每一个到达这个状态的路径之和:


随着序列数的增长,所要计算的路径数呈指数增长。但是在t时刻我们已经计算出所有到达某一状态的部分概率,因此在计算t+1时刻的某一状态的部分概率时只和t时刻有关。
[Formula]
这个式子的含义就是恰当的观察概率(状态j下,时刻t+1所真正看到的观察状态的概率)乘以此时所有到达该状态的概率和(前一时刻所有状态的概率与相应的转移概率的积)。因此,我们说在计算t+1时刻的概率时,只用到了t时刻的概率。这样我们就可以计算出整个观察序列的概率。
 
2d.复杂度比较
对于观察序列长度T,穷举法的复杂度为T的指数级;而Forward Algorithm的复杂度为T的线性。
=======================================================
最后我们给出Forward Algorithm的完整定义
We use the forward algorithm to calculate the probability of a T long observation sequence;

[Formula]

where each of the y is one of the observable set. Intermediate probabilities (a's) are calculated recursively by first calculating a for all states at t=1.

[Formula]

Then for each time step, t = 2, ..., T, the partial probability a is calculated for each state;   [Formula]

that is, the product of the appropriate observation probability and the sum over all possible routes to that state, exploiting recursion by knowing these values already for the previous time step. Finally the sum of all partial probabilities gives the probability of the observation, given the HMM, l.   [Formula] =======================================================


我们还用天气的例子来说明如何计算t=2时刻,状态CLOUDY的部分概率

怎么样?看到这里豁然开朗了吧。要是还不明白,我就.....................还有办法,看个动画效果:
http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/s3_pg3.html
参数定义:
http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/s3_pg4.html
http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/s3_pg5.html
最后记住我们使用这个算法的目的(没有应用任何算法都是垃圾),从若干个HMM模型中选出一个最能够体现给定的观察状态序列的模型(概率最大的那个)。
 
Forward Algorithm (Done)
 
http://blogcui.spaces.live.com/blog/cns!46BDB23E24219CE9!152.entry?_c=BlogPart

Viterbi Algorithm

本来想明天再把后面的部分写好,可是睡觉今天是节日呢?一时情不自禁就有打开电脑..........

找到可能性最大的隐含状态序列

 

多数情况下,我们都希望能够根据一个给定的HMM模型,根据观察状态序列找到产生这一序列的潜在的隐含状态序列。

1、穷举搜索方法

马尔可夫模型(HMM)与隐马尔克夫模型(转) - ♂苹果 - 眼睛想旅行 

我们可以通过穷举的方式列出所有可能隐含状态序列,并算出每一种隐状态序列组合对应的观察状态序列的概率。概率最大的那个组合对应的就是最可能的隐状态序列组合。

Pr(observed sequence | hidden state combination).

比如说上图中的trellis中,最有可能的隐状态序列是使得概率:

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)

得到最大值的序列。

同样这种穷举法的计算量太大了。为了解决这个问题,我们可以利用和Forward algorithm一样的原理--概率的时间不变性来减少计算量。

2.用递归方式减少复杂度

在给定的观察序列和HMM模型下,我们用一种递归的方式找到最有可能的隐状态序列。同样我们滴定部分概率,即在trellis中到达某一中间状态的概率。然后介绍如何在初始时刻t=1和t>1的时刻分别求解这个部分概率。但要注意,这里的部分概率是到达某一中间状态的概率最大的路径而不是所有概率之和。

2.1部分概率和部分最优路径

看如下trellis

[Picture of trellis] 

对于trellis中的每个中间状态和结束状态,都存在一条到达它的最优路径。他可能是下图这样:

[Picture] 

我们这些路径为部分最优路径,每一条 部分最优路径都对应一个关联概率--部分概率d。与Forward algorithm不同d是最有可能到达该状态的一条路径的概率。

 d (i,t)是所有序列中在t时刻以状态i终止的最大概率。当然它所对应那条路径就是部分最优路径。  d (i,t)对于每个i,t都是存在的。这样我们就可以在时间T(序列的最后一个状态)找到整个序列的最优路径。

2b. 计算 d 's 在t = 1的初始值

由于在t=1不存在任何部分最优路径,因此可以用初始状态P 向量协助计算。

[Formula]

这一点与Forward Algorithm相同

2c. 计算 d 's 在t > 1 的部分概率

同样我们只用t-1时刻的信息来得到t时刻的部分概率。

[Picture]

由此图可以看出到达X的最优路径是下面中的一条:

(sequence of states), . . ., A, X                                (sequence of states), . . ., B, X or (sequence of states), . . ., C, X

我们希望找到一条概率最大的。回想马尔科夫一阶模型的假设,一个状态之和它前一时刻的状态有关。

Pr (most probable path to A) . Pr (X | A) . Pr (observation | X)

因此到达X的最大概率就是:

[Formula] 

其中第一部分由t-1时刻的部分概率得到,第二部分是状态转移概率,第三部分是混淆矩阵中对应的概率。


      尾声

HMM 的第三个应用就是learning,这个算法就不再这里详述了,并不是因为他难于理解,而是它比前两个算法要复杂很多。这个方向在语音处理数据库上有重要的地位。因为它可以帮助我们在状态空间很大,观察序列很长的环境下找到合适HMM模型参数:初始状态、转移概率、混淆矩阵等。

好了,我们终于可以对HMM做一个阶段性的总结了。通过这个系列的自学过程,我相信各位已经和我一样对HMM的概念和应用有了一个初步的了解。这里我们考虑的都是一阶马尔科夫过程。HMM在语音识别和NLP方面都有很深入的应用。

简单说说我学习HMM的初衷,在科研过程中遇到了reranking的问题,候选一直都是别人为我生成的,处于好奇,终于决定自己也研究一下,大家都知道, reranking是需要产生N-best的候选,既然是N-best,那么viterbi算法就只能生成一条最好的路径,其他的该怎么办呢?原来在实际应用过程中,通常是把viterbi decoding与另一种称为stack decoding的算法联合使用(当然A*算法也可以)产生多个候选。前面我们已经对A*算法作了介绍,在今后的日子里,如果我有时间也会把stack decoding向大家介绍。(希望不要等太长时间)


 

  评论这张
 
阅读(3685)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017