软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 互联网 -> HMM(隐马尔科夫链)介绍 -> 正文阅读
互联网 最新文章
C++11并发API总结
16.收款(AcceptingMoney)
数据链路层综述
IP协议及IP数据报解析
《浅谈HTTP协议》
计算机网络基础
LoadRunner和RPT之间关于手动关联和参数化的
HTTPS中的对称密钥加密,公开密钥加密,数字
上班需要打卡吗?(开通微信公众号--乘着风
ofbizjmsactivemq

[互联网]HMM(隐马尔科夫链)介绍

  2016-04-01 16:56:05

HMM 隐马尔科夫链介绍
标签(空格分隔): HMM 马尔科夫


最近时间需要了解HMM算法,在此做了一些了解。本文主要基于我爱自然语言处理总结而成。

介绍


我们通常希望寻找一个事物的规律,比如计算机的指令序列,句子中的词语序列等等。
举个例子来说,有人试图通过一片海藻推断天气——民间传说告诉我们‘湿透的’海藻意味着潮湿阴雨,而‘干燥的’海藻则意味着阳光灿烂。如果它处于一个中间状态(‘有湿气’),我们就无法确定天气如何。
然而,天气的状态并没有受限于海藻的状态,所以我们可以在观察的基础上预测天气是雨天或晴天。另一个有用的线索是前一天的天气状态(或者,至少是它的可能状态)——通过综合昨天的天气及相应观察到的海藻状态,我们有可能更好的预测今天的天气。
这是本教程中我们将考虑的一个典型的系统类型。
首先,我们将介绍产生概率模式的系统,如晴天及雨天间的天气波动。
然后,我们将会看到这样一个系统,我们希望预测的状态并不是观察到的——其底层系统是隐藏的。在上面的例子中,观察到的序列将是海藻而隐藏的系统将是实际的天气。
最后,我们会利用已经建立的模型解决一些实际的问题。对于上述例子,我们想知道:
1. 给出一个星期每天的海藻观察状态,之后的天气将会是什么?
2. 给定一个海藻的观察状态序列,预测一下此时是冬季还是夏季?直观地,如果一段时间内海藻都是干燥的,那么这段时间很可能是夏季,反之,如果一段时间内海藻都是潮湿的,那么这段时间可能是冬季。

生成模式(Generating Patterns)

确定性系统


这种系统比较常见,例如红绿灯系统:当前是红色或者绿色,下一个一定是黄色,也就是说,该系统是确定性的。

非确定性系统


前面的天气状态中,我们提到有两种状态:雨天或者晴天,在这里我们加入第三种状态:多云。跟信号灯的例子不同,天气状态不是确定性的,他可以随机的切换到下一个状态中去。但是,我们仍然希望能够找到一个模式或者规律。
一种做法就是,我们假设当前的状态仅仅依赖前面的一个状态,这就是马尔科夫假设。通常情况下,这是不符合现实的。因为天气的下一个状态不仅仅依赖上一个状态,还要依赖风力、气压等状况。但是通过这种简化的手段,我们可以更好的去理解系统。
一个马尔科夫过程是状态间的转移仅依赖于前n个状态的过程。这个过程被称之为n阶马尔科夫模型,其中n是影响下一个状态选择的(前)n个状态。最简单的马尔科夫过程是一阶模型,它的状态选择仅与前一个状态有关。这里要注意它与确定性系统并不相同,因为下一个状态的选择由相应的概率决定,并不是确定性的
下图是天气例子中状态间所有可能的一阶状态转移情况:

对于有M个状态的一阶马尔科夫模型,共有M^2个状态转移,因为任何一个状态都有可能是所有状态的下一个转移状态。也就是说,可以从任意M个状态开始,转移到任意M个状态,因此有M^2种可能。
每一个状态转移都有一个概率值,称为状态转移概率——这是从一个状态转移到另一个状态的概率。所有的M^2个概率可以用一个状态转移矩阵表示。注意这些概率并不随时间变化而不同——这是一个非常重要(但常常不符合实际)的假设。
下面的状态转移矩阵显示的是天气例子中可能的状态转移概率:

-也就是说,如果昨天是晴天,那么今天是晴天的概率为0.5,是多云的概率为0.375。注意,每一行的概率之和为1。
要初始化这样一个系统,我们需要确定起始日天气的(或可能的)情况,定义其为一个初始概率向量,称为pi向量。

-也就是说,第一天为晴天的概率为1。
现在我们定义一个一阶马尔科夫过程如下:
状态:
三个状态——晴天,多云,雨天。
pi向量:定义系统初始化时每一个状态的概率。
状态转移矩阵:给定前一天天气情况下的当前天气概率。
任何一个可以用这种方式描述的系统都是一个马尔科夫过程。

隐藏模式

马尔科夫过程的局限性


在某些情况下,我们希望找到的模式用马尔科夫过程描述还显得不充分。回顾一下天气那个例子,一个隐士也许不能够直接获取到天气的观察情况,但是他有一些水藻。民间传说告诉我们水藻的状态与天气状态有一定的概率关系——天气和水藻的状态是紧密相关的。
在这个例子中,我们有两组状态,观察的状态(水藻的状态)和隐藏的状态(天气的状态)。我们希望为隐士设计一种算法,在不能够直接观察天气的情况下,通过水藻和马尔科夫假设来预测天气。
需要着重指出的是,隐藏状态的数目与观察状态的数目可以是不同的。一个包含三个状态的天气系统(晴天、多云、雨天)中,可以观察到4个等级的海藻湿润情况(干、稍干、潮湿、湿润)。
在这种情况下,观察到的状态序列与隐藏过程有一定的概率关系。我们使用隐马尔科夫模型对这样的过程建模,这个模型包含了一个底层隐藏的随时间改变的马尔科夫过程,以及一个与隐藏状态某种程度相关的可观察到的状态集合。

隐马尔科夫模型(Hidden Markov Models)


  下图显示的是天气例子中的隐藏状态和观察状态。假设隐藏状态(实际的天气)由一个简单的一阶马尔科夫过程描述,那么它们之间都相互连接。

在这个例子中,上面的状态时观察状态,下面的状态是隐藏状态。他们之间的连线,实际上应该从底下指向上面的观察状态:也就是说,这种连接表示,在给定的马尔科夫过程中,一个特定的隐藏状态生成特定的观察状态的概率。因此,在该连接中,我们可以看到:从某个隐藏状态,例如sun,到其他所有观察状态的概率之和应该为1,也就是说:
Sum_{Obs=Dry,Dryish,Damp,Soggy}(Obs|Sun) = 1;
Sum_{Obs=Dry,Dryish,Damp,Soggy}(Obs|Cloud) = 1;
Sum_{Obs=Dry,Dryish,Damp,Soggy}(Obs|Rain) = 1;
obs即观察状态。
因此,从上面的连接关系,我们除了定义了马尔科夫过程的概率关系,我们还可以定义另一个矩阵,定义为混淆矩阵(confusion matrix),它包含了给定一个隐藏状态后得到的观察状态的概率。对于天气例子,混淆矩阵是:

注意矩阵的每一行之和是1。

总结(Summary)


1、我们已经看到在一些过程中一个观察序列与一个底层马尔科夫过程是概率相关的。在这些例子中,观察状态的数目可以和隐藏状态的数码不同。
2、我们使用一个隐马尔科夫模型(HMM)对这些例子建模。这个模型包含两组状态集合和三组概率集合:
  * 隐藏状态:一个系统的(真实)状态,可以由一个马尔科夫过程进行描述(例如,天气)。
  * 观察状态:在这个过程中‘可视’的状态(例如,海藻的湿度)。
  * pi向量:包含了(隐)模型在时间t=1时一个特殊的隐藏状态的概率(初始概率)。
  * 状态转移矩阵:包含了一个隐藏状态到另一个隐藏状态的概率
  * 混淆矩阵:包含了给定隐马尔科夫模型的某一个特殊的隐藏状态,观察到的某个观察状态的概率。
  因此一个隐马尔科夫模型是在一个标准的马尔科夫过程中引入一组观察状态,以及其与隐藏状态间的一些概率关系。

隐马尔可夫模型

定义


一个隐马尔科夫模型,是一个三元组:
Π=(πi) :初始化概率向量
A=(aij) : 状态转移转移矩阵;
B=(bij) : 混淆矩阵
在状态转移矩阵及混淆矩阵中的每一个概率都是时间无关的——也就是说,当系统演化时这些矩阵并不随时间改变。实际上,这是马尔科夫模型关于真实世界最不现实的一个假设。

应用(Uses associated with HMMs)


一旦一个系统可以作为HMM被描述,就可以用来解决三个基本问题。
其中前两个是模式识别的问题:
1、给定HMM求一个观察序列的概率(评估),例如:我们有了HMM的三个要素之后,给你一个序列,序列值是观察状态组成的,那么你来求解这个状态出现的概率是多少;
考虑这样的问题,我们有一些描述不同系统的多个隐马尔科夫模型(也就是一些( pi,A,B)三元组的集合)及一个观察序列。我们想知道哪一个HMM最有可能产生了这个给定的观察序列。例如,对于海藻来说,我们也许会有一个“夏季”模型和一个“冬季”模型,因为不同季节之间的情况是不同的——我们也许想根据海藻湿度的观察序列来确定当前的季节。
因此,我们可以用这几个HMM分别计算其生成该序列的概率,然后选择概率最大的那个即可。
我们使用前向算法(forward algorithm)来计算给定隐马尔科夫模型(HMM)后的一个观察序列的概率,并因此选择最合适的隐马尔科夫模型(HMM)。
  
2、搜索最有可能生成一个观察序列的隐藏状态序列(解码)。例如:有了HMM的三个要素之后,给了一个观察的序列,你要来求最有可能的那个隐藏序列是什么样的。
也就是说,就是搜索生成输出序列的隐藏状态序列。在许多情况下我们对于模型中的隐藏状态更感兴趣,因为它们代表了一些更有价值的东西,而这些东西通常不能直接观察到。
考虑海藻和天气这个例子,一个盲人隐士只能感觉到海藻的状态,但是他更想知道天气的情况,天气状态在这里就是隐藏状态。在看到海藻状态之后,他开始思考:这两天的天气,究竟是什么样子的呢?或者说,最有可能是什么样子呢?
我们使用Viterbi 算法(Viterbi algorithm)确定(搜索)已知观察序列及HMM下最可能的隐藏状态序列。
  Viterbi算法(Viterbi algorithm)的另一广泛应用是自然语言处理中的词性标注。在词性标注中,句子中的单词是观察状态,词性(语法类别)是隐藏状态(注意对于许多单词,如wind,fish拥有不止一个词性)。对于每句话中的单词,通过搜索其最可能的隐藏状态,我们就可以在给定的上下文中找到每个单词最可能的词性标注。
3、给定观察序列生成一个HMM(学习)
  根据观察序列生成隐马尔科夫模型。
  第三个问题,也是与HMM相关的问题中最难的,根据一个观察序列(来自于已知的集合),以及与其有关的一个隐藏状态集,估计一个最合适的隐马尔科夫模型(HMM),也就是确定对已知序列描述的最合适的(pi,A,B)三元组。
  当矩阵A和B不能够直接被(估计)测量时,前向-后向算法(forward-backward algorithm)被用来进行学习(参数估计),这也是实际应用中常见的情况。

总结(Summary)


  由一个向量和两个矩阵(pi,A,B)描述的隐马尔科夫模型对于实际系统有着巨大的价值,虽然经常只是一种近似,但它们却是经得起分析的。隐马尔科夫模型通常解决的问题包括:
  1. 对于一个观察序列匹配最可能的系统——评估,使用前向算法(forward algorithm)解决;
  2. 对于已生成的一个观察序列,确定最可能的隐藏状态序列——解码,使用Viterbi 算法(Viterbi algorithm)解决;
  3. 对于已生成的观察序列,决定最可能的模型参数——学习,使用前向-后向算法(forward-backward algorithm)解决。

前向算法


给定一个HMM,和一个观察序列,计算该观察序列的概率。

穷举搜索


想想一下,加入我们有一个观察序列:(干燥、潮湿、湿、干燥),那么直接计算的话,其概率是多少呢?很简单,我们每个观察序列值都可以是隐藏状态(阴天、晴天,多云)中的一个,总共有3^4中可能,也就是P(干燥、潮湿
湿、干燥|,,,),*是三个状态中的任意一个。
可以知道,这种概率观察算法代价非常大。

使用递归降低问题复杂度


给定一个隐马尔科夫模型(HMM),我们将考虑递归地计算一个观察序列的概率。我们首先定义局部概率(partial probability),它是到达网格中的某个中间状态时的概率。然后,我们将介绍如何在t=1和t=n(>1)时计算这些局部概率。
  假设一个T-长观察序列是:

每个Y值都是观测值中的一种。
  

局部概率(α)


  考虑下面这个网格,它显示的是天气状态及对于观察序列干燥,湿润及湿透的一阶状态转移情况:
  

  下面的dry,damp,soggy是观测到的序列。
  我们可以将计算到达网格中某个中间状态的概率作为所有到达这个状态的可能路径的概率求和问题。
  例如,t=2时位于“多云”状态的局部概率通过如下路径计算得出:
  

  我们定义t时刻位于状态j的局部概率为at(j)——这个局部概率计算如下:
  α(j)=Pr(|j)?Pr(tj
**对于t时刻状态j(假定为damp)来说,通过cloudy得到damp的概率,就等于t-1时刻,所有状态到clouy的概率之和作为cloudy的概率,然后乘以cloudy状态下damp的概率,即为这条线下,damp的概率。
同理,sunny,rainy状态下也会得到各自的damp的概率。
这样,就得到了t时刻,sunny,cloudy,rainy三条线下各自对damp的概率。这样就可以继续计算t+1时刻soggy的状态了。**
  对于最后的观察状态,其局部概率包括了通过所有可能的路径到达这些状态的概率——例如,对于上述网格,最终的局部概率通过如下路径计算得出:

  由此可见,对于这些最终局部概率求和等价于对于网格中所有可能的路径概率求和,也就求出了给定隐马尔科夫模型(HMM)后的观察序列概率。
  

计算t=1时的局部概率α


  我们按如下公式计算局部概率:
  α(j)=Pr(|j)?Pr(tj
  特别当t=1时,没有任何指向当前状态的路径。故t=1时位于当前状态的概率是初始概率,即Pr(state|t=1)=P(state),因此,t=1时的局部概率等于当前状态的初始概率乘以相关的观察概率:

所以初始时刻状态j的局部概率,依赖于此状态的初始概率及相应时刻我们所见的观察概率。
解释下各个字段的含义:
α自然就是我们的局部概率,这个局部概率指的是观察状态的概率,在本例中,也就是dry或者wet的概率;
右下角的‘1’指的是时刻,也就是序列的第1个值;
j指的是隐藏状态的某个值,也就是rainy或者cloudy中的状态中的一种;
K1则是观察状态中的一种了,也就是在观察序列中,在当前时刻的值。
π在本例中,就是初始状态的值了。
因此,本式代表的含义为:
隐藏状态j,从它的初始状态,利用混淆状态bjk1转移到j所对应的观察状态k1的概率。

计算t>1时的局部概率α


  我们再次回顾局部概率的计算公式如下:
  α(j)=Pr(|j)?Pr(tj
  我们可以假设(递归地),乘号左边项“Pr( 观察状态 | 隐藏状态j )”已经有了,现在考虑其右边项“Pr(t时刻所有指向j状态的路径)”。
  为了计算到达某个状态的所有路径的概率,我们可以计算到达此状态的每条路径的概率并对它们求和,例如:
      

  计算α所需要的路径数目随着观察序列的增加而指数级递增,但是t-1时刻α给出了所有到达此状态的前一路径概率,因此,我们可以通过t-1时刻的局部概率定义t时刻的α,即:
     

  
  分开来看:
  αt(i)aij 就是指上个时刻,即t时刻中,从隐藏状态i转换到的观测状态(已知的,上个观测序列值)概率值αt(i),通过转移矩阵值aij,成为在t+1时刻,隐藏状态j的概率。用例子来说,就是在上个状态中(假定上个状态是干燥),晴天导致的干燥的可能值,乘以晴天转为多云的概率,就是t+1时刻,从晴天而来的多云的概率。
但是,转为多云有多种状态:晴天,多云,下雨都有可能,因此:
ni=0αt(i)aij 即为各个状态到多云的概率。
多云的状态*混沌矩阵中,多云转为当前观察状态的概率,即得αt+1(j)
同理,我们可以得到rainy,sunny的状态。
注意我们已经有了一个仅利用t时刻局部概率计算t+1时刻局部概率的表达式。
  现在我们就可以递归地计算给定隐马尔科夫模型(HMM)后一个观察序列的概率了——即通过t=1时刻的局部概率α计算t=2时刻的α,通过t=2时刻的α计算t=3时刻的α等等直到t=T。给定隐马尔科夫模型(HMM)的观察序列的概率就等于t=T时刻的局部概率之和。

降低计算复杂度


  我们可以比较通过穷举搜索(评估)和通过递归前向算法计算观察序列概率的时间复杂度。
  我们有一个长度为T的观察序列O以及一个含有n个隐藏状态的隐马尔科夫模型l=(pi,A,B)。
  穷举搜索将包括计算所有可能的序列:
   

  公式
    

  对我们所观察到的概率求和——注意其复杂度与T成指数级关系。相反的,使用前向算法我们可以利用上一步计算的信息,相应地,其时间复杂度与T成线性关系。
注:穷举搜索的时间复杂度是2TN^T,前向算法的时间复杂度是N^2T,其中T指的是观察序列长度,N指的是隐藏状态数目。

总结


  我们的目标是计算给定隐马尔科夫模型HMM下的观察序列的概率——Pr(observations |lamda)。
  我们首先通过计算局部概率(α)降低计算整个概率的复杂度,局部概率表示的是t时刻到达某个状态s的概率。
  t=1时,可以利用初始概率(来自于P向量)和观察概率Pr(observation|state)(来自于混淆矩阵)计算局部概率;而t>1时的局部概率可以利用t-时的局部概率计算。
  因此,这个问题是递归定义的,观察序列的概率就是通过依次计算t=1,2,…,T时的局部概率,并且对于t=T时所有局部概率α相加得到的。
  注意,用这种方式计算观察序列概率的时间复杂度远远小于计算所有序列的概率并对其相加(穷举搜索)的时间复杂度。

前向算法描述


  我们使用前向算法计算T长观察序列的概率:
     

  其中y的每一个是观察集合之一。局部(中间)概率(α)是递归计算的,首先通过计算t=1时刻所有状态的局部概率alpha:
     

  然后在每个时间点,t=2,… ,T时,对于每个状态的局部概率,由下式计算局部概率alpha:
     

  也就是当前状态相应的观察概率与所有到达该状态的路径概率之积,其递归地利用了上一个时间点已经计算好的一些值。
  最后,给定HMM,lamda,观察序列的概率等于T时刻所有局部概率之和:
     

  再重复说明一下,每一个局部概率(t > 2 时)都由前一时刻的结果计算得出。
  对于“天气”那个例子,下面的图表显示了t = 2为状态为多云时局部概率alpha的计算过程。这是相应的观察概率b与前一时刻的局部概率与状态转移概率a相乘后的总和再求积的结果:
   

(注:本图及维特比算法4中的相似图存在问题,具体请见文后评论,非常感谢读者YaseenTA的指正)
总结(Summary)
  我们使用前向算法来计算给定隐马尔科夫模型(HMM)后的一个观察序列的概率。它在计算中利用递归避免对网格所有路径进行穷举计算。
  给定这种算法,可以直接用来确定对于已知的一个观察序列,在一些隐马尔科夫模型(HMMs)中哪一个HMM最好的描述了它——先用前向算法评估每一个(HMM),再选取其中概率最高的一个。

前向算法代码实现

#encoding:utf-8


import numpy as np

class HMM():
    def __init__(self, observe_list):
        self.pai = [0.63, 0.17, 0.20]
        self.A = np.array([[0.500, 0.375, 0.125],
                           [0.250, 0.125, 0.625],
                           [0.250, 0.375, 0.375]])
        self.B = np.array([
            [0.60, 0.20, 0.15, 0.05],
            [0.25, 0.25, 0.25, 0.25],
            [0.05, 0.10, 0.35, 0.50]
        ])
        self.observe_list = observe_list

    def forward(self):
        theata = self.pai * self.B[:, self.observe_list[0]]  #进行初始化
        print theata
        lenth = len(self.observe_list)
        print lenth
        for i in range(lenth-1):
            theata = (theata.dot(self.A)) # 矩阵相乘的所得值,就是上一个观察状态序列值,到各个隐藏状态的概率值。注意,这里是矩阵相乘。
            #print theata
            #print sum(theata)
            theata = theata * ((self.B[:, self.observe_list[i+1]]))  ##初始theata的值,与各个混沌矩阵中对应转移概率的值相乘,在x轴上求和,即新的在该状态的局部概率。#注意,这里是单纯的乘法 * ,因为这个值求的是当前状态转移到当前观测值的概率,求和在下一个循环。                                                                       
        print sum(theata)  #该值即为序列概率值
if __name__ == "__main__":
    observe_list = [0,2,3]
    a = HMM(observe_list)
    a.forward()

上一篇文章      下一篇文章      查看所有文章
2016-04-01 16:55:16  
360图书馆 论文大全 母婴/育儿 软件开发资料 网页快照 文字转语音 购物精选 软件 美食菜谱 新闻中心 电影下载 小游戏 Chinese Culture
生肖星座解梦 三沣玩客 拍拍 视频 开发 Android开发 站长 古典小说 网文精选 搜图网 天下美图 中国文化英文 多播视频 装修知识库
2017-1-21 4:07:49
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --