精华内容
下载资源
问答
  • HMM前向后向算法

    千次阅读 2018-06-12 21:52:09
    HMM前向后向算法HMM的三个基本问题中,对于HMM参数的学习是最难的。对于给定的观测序列O,如何估计模型参数使得P(O|λ)最大。目前为止,可能并不存在一种方法使得P(O|λ)最大,但是接下里的前向后向算法是能够使上述...

    HMM前向后向算法

    HMM的三个基本问题中,对于HMM参数的学习是最难的。对于给定的观测序列O,如何估计模型参数使得P(O|λ)最大。目前为止,可能并不存在一种方法使得P(O|λ)最大,但是接下里的前向后向算法是能够使上述问题得到局部最优。

    首先:假设给定模型λ和观测序列,计算观测序列出现的概率P(O|λ)。令隐含状态序列I={i1,i2...iT};观测序列是O={O1,O2,...OT},计算联合概率P(O,I|λ),然后将所有可能的I进行求和,就是P(O|λ)。

    隐含状态序列I的概率是:

    当固定隐含状态I和给定模型参数时,观测序列为O={O1,O2,...OT}的概率是P(O|I,λ)


    O和I同时出现的概率是:


    对所有的I进行求和:


    ---------(1)

    (1)  式计算量太大,于是才有之前的前向算法和后向算法。

     

     

    给定模型λ和观测序列O,在t时刻处于状态qi的概率:

    而且还有:

    回顾一下:前向概率的定义:

    给定HMM的参数λ,定义到t时刻的部分观测序列o1,o2..ot,且状态是qi的概率为前向概率:

    后向概率的定义:


    给定HMM的参数λ,在t时刻状态为qi的条件下,t+1到T的观测序列ot+1,ot+2..oT的概率为后向概率:

    P(it=qi,O|λ)的意思是:在给定HMM的参数λ,观测序列是O(O1,O2,...OT),在t时刻的状态为qi的概率。换句话理解就是:从1~t时刻,t时刻的状态为qi,输出是(O1,O2,...Ot),的概率,然后t时刻之后,在t时刻状态为qi,输出序列是(ot+1,ot+2..oT)的概率。

    1~t时刻的,输出是(O1,O2,...Ot),的概率:这不就是前向概率的定义么?

    t时刻之后,在t时刻状态为qi输出序列是(ot+1,ot+2..oT)的概率,这不就是后向概率么?

    于是就有:

    结合公式(1),(3),(6),可以得到:


    ----------(7)

    1.        

    给定模型参数λ和观测序列O,t时刻是qi,t+1时刻是qj的概率是:

    类似于公式(3):

     

    的意思是在给定HMM的参数下,观测序列是O,t时刻的状态是qi,t+1时刻的状态是qj的概率。

    这个概率=P(1~t时刻的输出序列O1,O2,...Ot,t时刻是qi|λ)*P(qi转移到t+1时刻的qj)*P(t+1时刻之后输出序列是ot+2,ot+3..oT|t+1时刻是qj, λ)*P(t+1时刻输出是Ot+1):

    这里面有好几个乘积,逐一解释:

    P(1~t时刻的输出序列O1,O2,...Ot,t时刻是qi|λ):这不就是t时刻的前向概率αt(i)么?

    P(qi转移到t+1时刻的qj):这不就是转移概率aij么?

    P(t+1时刻之后输出序列是ot+2,ot+3..oT|t+1时刻是qj,λ):这不就是t+1时刻的后向概率βt+1(i)么?

    (注意:t+1时刻的后续输出序列是ot+2,ot+3..oT,即下标是从t+2开始,不是t+1开始,请仔细理解后向概率的定义)

    前面少了Ot+1这个时间点的观测序列,因此要补上P(t+1时刻输出是Ot+1),而这个不就是bj(Ot+1)么?

    因此:

    从而根据(8),(9),(10)可以变换为:


    -----------(11)

    ---------(12)

    (12)式表示观测序列是O时,状态i出现的期望

    ---------(13)

    (13)式表示观测序列是O时,由状态i转移的期望

    ----------(14)

    (14)式表示观测序列是O时,由状态i转移到j的期望.

     

    2.       前向-后向算法(baum-welch)

    这里主要来推导非监督情况下的baum-welch算法。

    在只有观测序列时(只有O是已知的),如何估计HMM的参数λ使得P(O|λ)最大,前面已经讲过了,由于没有办法找到一种方法使得P(O|λ)全局收敛,baum-welch算法只能是局部最优。

    在公式(1)中有:

    观测序列是O (o1,o2,...oT),隐含状态是I{i1,i2.....iT},完全数据是(O,I)={ o1,o2,...oT , i1,i2.....iT}完全数据的对数似然函数是log(O,I|λ)。HMM的参数学习算法可以通过EM算法来实现。

    E-step:

    确定Q函数,即隐含变量的期望:


    ----------(16)

    (不太懂这个公式是如何计算来的)

    由于:

    ----------(17)

    因此有:


    ----------(18)

    M-step:

    极大化来计算参数A,B,π。

    对(18)式的三项分别进行极大化.

    第一项:

    其中:

    于是,写成拉格朗日函数如下:


    ----------(19)

    对(19)式求偏导:

    ----------(20)

    于是可以计算出:

    -----------(21)

    同时求和可以得到:

    ----------(22)

    将等式(22)带入到等式(21)中有:

    ----------(23)

    等式(18)第二项:

    -----------(24)

    约束条件是:

    同样让(24)变成拉格朗日函数式:

    ------------(25)

    做法与第一项最大化一致,最后计算的结果是:

    ----------(26)

    第三项:

    -----------(27)

    约束条件是:

    类似的,构建拉格朗日函数:

    ----------(28)

    对bj进行求偏导,并且令求偏导之后的函数为0,

    ----------(29)

    对于(29),如果t时刻,

    同时对j求和,然后可以计算得到:

    在时,(29)时左边才有意义,否则就是0,用来表示这种情况,于是可以计算bj

    以上(23),(26),(30)就是我们最终要的东西。

    再进一步:

    仔细看一下(23)和(7),这俩不是一回事儿么?(23)分子不就是说在给定λ情况下,观测序列是O,在t时刻是i的概率么?于是有,只不过现在t=1而已:

    ----------(31)

    同理:

    ----------(32)

    ----------(33)

    至此,baum-welch算法就已经推导完成了。

     


    展开全文
  • HMM——前向后向算法

    千次阅读 2015-09-19 20:29:14
    前向后向算法或者Baum-Welch,不太好理解

    1. 前言

    解决HMM的第二个问题:学习问题, 已知观测序列,需要估计模型参数,使得在该模型下观测序列 P(观测序列 | 模型参数)最大,用的是极大似然估计方法估计参数。

    根据已知观测序列和对应的状态序列,或者说只有观测序列,将学习过程分为监督和无监督学习方法

    主要参考《李航统计学习》、《PRML》

    2. 监督学习方法

    给定了s个长度相同的观测序列和对应的状态序列(相当于有s个样本,所有样本长度一样)


    然后我们需要做的就是统计三种频率:

    ① 在样本中,从t 时刻的各状态转移到 t+1时刻的各状态的频率,比如第一个状态转移到第二个状态共有3次,第2个状态转移到第三个状态共有10次,等。。。。。

    据此能够推导出状态转移概率


    ② 在样本中,每对(某个状态j,某个观测k)出现的频率,就是状态为j 观测为k的概率,即混淆矩阵


    ③在样本中,统计s个样本中初始状态为 的频率就是初始状态概率πi

    缺点就是:监督学习需要人工标注训练数据,代价高

    3.前向-后向算法

    3.1 目标

    其它称呼有:Baum-Welch算法

    主要针对只有观测序列没有对应的状态序列的情况

    这一部分在《统计学习方法》中推导的非常好,主要利用的是拉格朗日乘子法求解

    已知:训练数据是S个长度为T的观测序列,没有对应的状态序列

    求解:学习隐马尔科夫的参数,包括:转移矩阵、混淆矩阵、初始概率

    思路:

    因为HMM中引入了隐状态,所以设隐状态序列为I,那么HMM就可以当做一个具有隐变量的概率模型:


    其实这个式子就有点像一种边缘概率:


    只不过将这个概率加了一个条件,是在HMM的模型参数下计算的,就变成了条件概率。

    求解的时候利用E-M算法求解即可(EM中,E代表expectation,是求期望;M代表的是maximization,求极大;合起来EM算法就被称为期望值最大化算法)

    3.2 EM步骤简述

    摘自《统计学习方法》

    输入:观测变量数据Y,隐变量数据Z,联合分布 P(Y, Z | θ),条件分布 P( Z | Y , θ)

    输出:模型参数 θ

    步骤:

    ① 选择参数初值,开始迭代

    ② E步:记为第 i 次迭代参数θ的估计值,在第 i+1 次迭代E步,计算


    第二个等式的第二项是给定观测数据Y和当前的估计参数下隐变量数据Z的条件概率分布

    ③ M步:求使得极大化的θ,确定第 i+1 次迭代的参数的估计值


    ④ 重复第②和③步,直到收敛

    3.3求解HMM模型参数

    (1) 确定完全数据的对数似然函数

    观测数据:

    隐藏数据:

    完全数据:

    完全数据的对数似然函数就是

    ②EM算法之E:求Q函数


    式子中是HMM模型参数的当前估计值,λ 是要极大化的HMM模型参数

    对于前面一半,根据概率有向图的联合概率分布,我们知道



    两式相乘就可以得到:


    根据P(O,I | λ)可以将 Q 函数可以改写为:


    式中的求和是对所有训练数据的序列长度T进行的

    ③ EM算法之M:极大化Q函数求解模型参数π、A、B

    观察E步骤的式子发现三个参数刚好分别在三项中,所以单独对每一项求解就行了

    第一步先求π:

    注意,π只与初始状态有关,第一项可以写成


    意思就是在模型参数已知的条件下,初始时候的各种状态以及对应的初始观测的概率的和

    限制条件就是对于某种观测,初始的所有状态,其概率和为1,例如,第一天观测为晴天时候,海藻的干燥、湿润、潮湿三个状态概率和为1


    那么就可以根据拉格朗日乘法计算了,设


    那么令其偏导数等于零


    对 i 求和得到


    再带回偏导为0的式子中得到


    第二步求转移矩阵A

    将第二项改写为


    找到约束条件为


    意思就是上一个隐状态到当前所有隐状态的转移概率和为1,比如今天是晴天,那么到明天得隐状态转移:晴天->多云,晴天->雨天,晴天->晴天的概率和为1

    依旧根据拉格朗日乘子法得到


    第三步求混淆矩阵

    将第三项改写为


    找到约束条件为


    也就是说一个隐状态对应的所有观测概率和为1,比如天气为晴天的时候,对应的海藻干燥、湿润、潮湿的概率和为1

    但是有一个需要注意的是只有当观测状态为当前所求导的状态时候,的偏导数才不为0,其实也就相当于的时候才是偏导不为0,书中用表示,最终偏导以后求得:


    3.4 Baum-Welch算法

    该求得都求了,那么具体的HMM模型参数估计算法就是:

    输入:观测数据

    输出:HMM的模型参数

    (1) 初始化:

    对n=0,选取得到模型

    (2) 递推,对n=1,2,...

    分别计算上面的三个偏导

    (3) 计算到最后一次迭代就得到最终结果了


    后续分析一下HMM的代码再另行添加

    展开全文
  • 前向后向算法

    千次阅读 多人点赞 2018-08-21 15:58:12
     后向算法依旧是解决概率计算问题,只不过是两种计算方式,计算结果应该是和前向算法相同,可以用例1验证一下,如下:  例2( 后向算法 ),考虑盒子和球模型 ,状态集合 ,观测集合 ,并且有: 设 , ,...

    https://blog.csdn.net/Hearthougan/article/details/77930786

     本文是自己学习隐马尔科夫模型的一个总结,为了自己以后方便查阅,也算作是李航老师的《统计学习方法》的一个总结,若有疑问,欢迎讨论。

    推荐阅读知乎上Yang Eninala写的《如何用简单易懂的例子解释隐马尔可夫模型?》,写的非常好。我会联系两者,来作为自己的一篇学习笔记。

        隐马尔可夫模型: 隐马尔可夫模型是关于时序的概率模型,描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列,再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列,称为状态序列(state sequence),每个状态生成一个观测,而由此产生的观测的随机序列,称为观测序列(observation sequenoe )。序列的每一个位置又可以看作是一个时刻。

    隐马尔科夫模型的3个基本问题:

         (1)概率计算问题。给定模型和观测序列,计算在模型下的观测序列出现的概率

        (2)学习问题。已知观测序列,估计模型参数,使得在该模型下观测序列概率最大。

        (3)预测问题,也称为解码(decoding)问题。已知模型参数和观测序列,求对给定观测序列前提下,条件概率最大的状态序列。即给定观测序列,求最有可能的对应的状态序列。

    概率计算问题:
    1、 直接计算方法
        这种方法说白了就是暴力搜索,枚举每一种状态序列,然后在根据状态序列求出观测序列的概率。
        思想很简单,可以这么想:假如我们现在已知状态序列为,那么根据状态序列S,求观测序列的概率,不就是相应的输出概率的连乘么!满足假设的状态序列总共有种,然后对所有假设的状态得出的概率相加,即为。细化如下:

        状态序列的概率是

     


        对已经假设的状态序列,观测序列,的概率是

     

        观测序列O和状态序列S同时出现的概率是:

        最后,对所有的状态序列S求和,即可得到观测序列O的概率

        对于实现上式,很简单,个for循环即可枚举所有的状态,然后计算每种状态对应的观测概率,时间复杂度是O(T),因此要直接计算的话,总的时间复杂度为,当数据量稍微大一点,具体实施就不太可能,因此要实现HMM的第一个问题,就要换一种方法。

    2、前向算法:

        给定隐马尔可夫模型,定义到时刻t部分观测序列且状态为的概率为前向概率,记作

        可以递推地求得前向概率及观测序列概率

        这个可以这么理解,已知选每种骰子的概率,每种骰子的输出概率,那么前t次掷骰子,掷出的点数为,并且第t用的骰子是,的概率是就是

    (1)初值:

    【第一次掷的是骰子是,掷出的点数为的概率,其中表示开始的时候选用骰子的概率】

     

    (2)递推:

    【第t+1次用骰子,掷出的概率】

        上式方括号中,表示第t次使用骰子掷出点数的的概率,,表示前t次掷出点数为的概率×第t+1次使用骰子的概率。

        由于第t次骰子的种类有N种,因此,第t+1次使用,而前一次,也就是第t次,使用的骰子有N种可能,即如下图:

    (3)终止:

        根据(2)的递推式子可以求出,表示第T次使用可以产生序列,i仍有N中可能所以相加即为最终的结果。

        例子1(前向算法):考虑盒子和球模型,状态集合,观测集合,并且有:

    ,试用前向算法计算

    根据上面我们描述的算法,一步一步地计算,

    (1)计算初值:

    (2)递推:

         当时:

        当时:

    3、后向算法

        给定隐马尔可夫模型,定义在时刻t部状态为的条件下,从的部分观测序列为的概率为后向概率,记作:

    可以递推地求得后向概率及观测序列概率

       可以这么理解,已知第t次掷骰子所用的骰子是,那么它表示的就是从次到第次的看到的点数为:的概率。

    (1)初值

    【解释:已知最后一次所用的骰子为,那么第次之后,为任意值的概率,故而为1】

    (2)递推

    (3)终止

        后向算法依旧是解决概率计算问题,只不过是两种计算方式,计算结果应该是和前向算法相同,可以用例1验证一下,如下:

        例2(后向算法),考虑盒子和球模型,状态集合,观测集合,并且有:

    ,试用后向算法计算。
        我们仍然根据上面的算法描述,一步一步地计算,

    (1)计算初值

        当

    (2)递推

        当时:

        当

    (3)终止

     

    可以根绝前向算法和后向算法的定义,将两种计算方式结合起来,如下:

     

    https://blog.csdn.net/u012771351/article/details/53113377

    那么前向算法和后向算法之间联系

    我们来推导一下:

    从结论我们不难看出,在t时刻如果知道了状态为qi,那么可以将这个t之前和之后阻断,最后变换成前向概率和后向概率。

    那么我们就可以求单个状态的概率了:

    这样的话我么你从t=1一直计算到t=T,我们就可以得到每个时刻最有可能的那个状态,但是这样子做对么?

    我认为是不对的,原因是每一个时刻最有可能最终组成的状态序列是不一定存在的,打个比方说,全市高考,我选出每个学科的最高分,那么我就说这是第一名的各科成绩,显然是不一定的,那么正确的做法是什么呢?我们将在后边的Viterbi算法中介绍。

     

    进一步思考:如果要求了t时刻状态为i,t+1时刻状态为j的联合概率呢?

    最终结果是:

    这里把联合概率这块拿出来只是让大家更直观的感觉这个前后向概率而已,跟我们整体的HMM模型框架无关。

    展开全文
  • 前向-后向算法(Forward-backward algorithm)

    万次阅读 2015-11-30 11:31:03
     与HMM模型相关的“有用”的问题是评估(前向算法)和解码(维特比算法)——它们一个被用来测量一个模型的相对适用性,另一个被用来推测模型隐藏的部分在做什么(“到底发生了”什么)。可以看出它们都依赖于隐...

    根据观察序列生成隐马尔科夫模型(Generating a HMM from a sequence of obersvations)

     

      与HMM模型相关的“有用”的问题是评估(前向算法)和解码(维特比算法)——它们一个被用来测量一个模型的相对适用性,另一个被用来推测模型隐藏的部分在做什么(“到底发生了”什么)。可以看出它们都依赖于隐马尔科夫模型(HMM)参数这一先验知识——状态转移矩阵,混淆(观察)矩阵,以及pi向量(初始化概率向量)。
      然而,在许多实际问题的情况下这些参数都不能直接计算的,而要需要进行估计——这就是隐马尔科夫模型中的学习问题。前向-后向算法就可以以一个观察序列为基础来进行这样的估计,而这个观察序列来自于一个给定的集合,它所代表的是一个隐马尔科夫模型中的一个已知的隐藏集合。
      一个例子可能是一个庞大的语音处理数据库,其底层的语音可能由一个马尔可夫过程基于已知的音素建模的,而其可以观察的部分可能由可识别的状态(可能通过一些矢量数据表示)建模的,但是没有(直接)的方式来获取隐马尔科夫模型(HMM)参数。
      前向-后向算法并非特别难以理解,但自然地比前向算法和维特比算法更复杂。由于这个原因,这里就不详细讲解前向-后向算法了(任何有关HMM模型的参考文献都会提供这方面的资料的)。
      总之,前向-后向算法首先对于隐马尔科夫模型的参数进行一个初始的估计(这很可能是完全错误的),然后通过对于给定的数据评估这些参数的的价值并减少它们所引起的错误来重新修订这些HMM参数。从这个意义上讲,它是以一种梯度下降的形式寻找一种错误测度的最小值。
      之所以称其为前向-后向算法,主要是因为对于网格中的每一个状态,它既计算到达此状态的“前向”概率(给定当前模型的近似估计),又计算生成此模型最终状态的“后向”概率(给定当前模型的近似估计)。 这些都可以通过利用递归进行有利地计算,就像我们已经看到的。可以通过利用近似的HMM模型参数来提高这些中间概率进行调整,而这些调整又形成了前向-后向算法迭代的基础。

    要理解前向-后向算法,首先需要了解两个算法:后向算法和EM算法。后向算法是必须的,因为前向-后向算法就是利用了前向算法与后向算法中的变量因子,其得名也因于此;而EM算法不是必须的,不过由于前向-后向算法是EM算法的一个特例,因此了解一下EM算法也是有好处的,说实话,对于EM算法,我也是云里雾里的。好了,废话少说,我们先谈谈后向算法。

    1、后向算法(Backward algorithm)
      其实如果理解了前向算法,后向算法也是比较好理解的,这里首先重新定义一下前向算法中的局部概率at(i),称其为前向变量,这也是为前向-后向算法做点准备:
       ati
      相似地,我们也可以定义一个后向变量Bt(i)(同样可以理解为一个局部概率):
       bti
      后向变量(局部概率)表示的是已知隐马尔科夫模型lamda及t时刻位于隐藏状态Si这一事实,从t+1时刻到终止时刻的局部观察序列的概率。同样与前向算法相似,我们可以从后向前(故称之为后向算法)递归地计算后向变量:
      1)初始化,令t=T时刻所有状态的后向变量为1:
         b1
      2)归纳,递归计算每个时间点,t=T-1,T-2,…,1时的后向变量:
      bi
      这样就可以计算每个时间点上所有的隐藏状态所对应的后向变量,如果需要利用后向算法计算观察序列的概率,只需将t=1时刻的后向变量(局部概率)相加即可。下图显示的是t+1时刻与t时刻的后向变量之间的关系:
       backward
      上述主要参考自HMM经典论文《A tutorial on Hidden Markov Models and selected applications in speech recognition》。下面我们给出利用后向算法计算观察序列概率的程序示例,这个程序仍然来自于UMDHMM

    后向算法程序示例如下(在backward.c中):

    void Backward(HMM *phmm, int T, int *O, double **beta, double *pprob)
    {
      int i, j;
      int t;
      double sum;

      
      for (i = 1; i <= phmm->N; i++)
        beta[T][i] = 1.0;

      
      for (t = T - 1; t >= 1; t--)
      {
        for (i = 1; i <= phmm->N; i++)
        {
          sum = 0.0;
          for (j = 1; j <= phmm->N; j++)
            sum += phmm->A[i][j] *
                  (phmm->B[j][O[t+1]])*beta[t+1][j];
          beta[t][i] = sum;
        }
      }

      
      *pprob = 0.0;
      for (i = 1; i <= phmm->N; i++)
        *pprob += beta[1][i];
    }
    隐马尔科夫模型(HMM)的三个基本问题中,第三个HMM参数学习的问题是最难的,因为对于给定的观察序列O,没有任何一种方法可以精确地找到一组最优的隐马尔科夫模型参数(A、B、pi)使P(O|lamda)最大。因而,学者们退而求其次,不能使P(O|lamda)全局最优,就寻求使其局部最优(最大化)的解决方法,而前向-后向算法(又称之为Baum-Welch算法)就成了隐马尔科夫模型学习问题的一种替代(近似)解决方法。
      我们首先定义两个变量。给定观察序列O及隐马尔科夫模型lamda,定义t时刻位于隐藏状态Si的概率变量为:
            fb1
      回顾一下第二节中关于前向变量at(i)及后向变量Bt(i)的定义,我们可以很容易地将上式用前向、后向变量表示为:
       fb2
      其中分母的作用是确保:fb3
      给定观察序列O及隐马尔科夫模型lamda,定义t时刻位于隐藏状态Si及t+1时刻位于隐藏状态Sj的概率变量为:
        fb4
      该变量在网格中所代表的关系如下图所示:
     fb5
      同样,该变量也可以由前向、后向变量表示:
       fb6
      而上述定义的两个变量间也存在着如下关系:
                fb7
      如果对于时间轴t上的所有fb10相加,我们可以得到一个总和,它可以被解释为从其他隐藏状态访问Si的期望值(网格中的所有时间的期望),或者,如果我们求和时不包括时间轴上的t=T时刻,那么它可以被解释为从隐藏状态Si出发的状态转移期望值。相似地,如果对fb11在时间轴t上求和(从t=1到t=T-1),那么该和可以被解释为从状态Si到状态Sj的状态转移期望值。即:
       fb8
       fb9

    上一节我们定义了两个变量及相应的期望值,本节我们利用这两个变量及其期望值来重新估计隐马尔科夫模型(HMM)的参数pi,A及B:

    fb12

      如果我们定义当前的HMM模型为fb13,那么可以利用该模型计算上面三个式子的右端;我们再定义重新估计的HMM模型为fb14,那么上面三个式子的左端就是重估的HMM模型参数。Baum及他的同事在70年代证明了fb15因此如果我们迭代地的计算上面三个式子,由此不断地重新估计HMM的参数,那么在多次迭代后可以得到的HMM模型的一个最大似然估计。不过需要注意的是,前向-后向算法所得的这个结果(最大似然估计)是一个局部最优解。
      关于前向-后向算法和EM算法的具体关系的解释,大家可以参考HMM经典论文《A tutorial on Hidden Markov Models and selected applications in speech recognition》,这里就不详述了。下面我们给出UMDHMM中的前向-后向算法示例,这个算法比较复杂,这里只取主函数,其中所引用的函数大家如果感兴趣的话可以自行参考UMDHMM。

    前向-后向算法程序示例如下(在baum.c中):

    void BaumWelch(HMM *phmm, int T, int *O, double **alpha, double **beta, double **gamma, int *pniter, double *plogprobinit, double *plogprobfinal)
    {
      int i, j, k;
      int t, l = 0;

      
      前向-后向算法就到此为止了。

      double logprobf, logprobb, threshold;
      double numeratorA, denominatorA;
      double numeratorB, denominatorB;

      double ***xi, *scale;
      double delta, deltaprev, logprobprev;

      deltaprev = 10e-70;

      xi = AllocXi(T, phmm->N);
      scale = dvector(1, T);

      ForwardWithScale(phmm, T, O, alpha, scale, &logprobf);
      *plogprobinit = logprobf;
      BackwardWithScale(phmm, T, O, beta, scale, &logprobb);
      ComputeGamma(phmm, T, alpha, beta, gamma);
      ComputeXi(phmm, T, O, alpha, beta, xi);
      logprobprev = logprobf;

      do
      {

        
        for (i = 1; i <= phmm->N; i++)
          phmm->pi[i] = .001 + .999*gamma[1][i];

        
        for (i = 1; i <= phmm->N; i++)
        {
          denominatorA = 0.0;
          for (t = 1; t <= T - 1; t++)
            denominatorA += gamma[t][i];

          for (j = 1; j <= phmm->N; j++)
          {
            numeratorA = 0.0;
            for (t = 1; t <= T - 1; t++)
              numeratorA += xi[t][i][j];
            phmm->A[i][j] = .001 +
                     .999*numeratorA/denominatorA;
          }

          denominatorB = denominatorA + gamma[T][i];
          for (k = 1; k <= phmm->M; k++)
          {
            numeratorB = 0.0;
            for (t = 1; t <= T; t++)
            {
              if (O[t] == k)
                numeratorB += gamma[t][i];
            }

            phmm->B[i][k] = .001 +
                     .999*numeratorB/denominatorB;
          }
        }

        ForwardWithScale(phmm, T, O, alpha, scale, &logprobf);
        BackwardWithScale(phmm, T, O, beta, scale, &logprobb);
        ComputeGamma(phmm, T, alpha, beta, gamma);
        ComputeXi(phmm, T, O, alpha, beta, xi);

        
        delta = logprobf - logprobprev;
        logprobprev = logprobf;
        l++;

      }
      while (delta > DELTA);

      *pniter = l;
      *plogprobfinal = logprobf;
      FreeXi(xi, T, phmm->N);
      free_dvector(scale, 1, T);
    }

    总结(Summary)

      通常,模式并不是单独的出现,而是作为时间序列中的一个部分——这个过程有时候可以被辅助用来对它们进行识别。在基于时间的进程中,通常都会使用一些假设——一个最常用的假设是进程的状态只依赖于前面N个状态——这样我们就有了一个N阶马尔科夫模型。最简单的例子是N = 1。
      存在很多例子,在这些例子中进程的状态(模式)是不能够被直接观察的,但是可以非直接地,或者概率地被观察为模式的另外一种集合——这样我们就可以定义一类隐马尔科夫模型——这些模型已被证明在当前许多研究领域,尤其是语音识别领域具有非常大的价值。
      在实际的过程中这些模型提出了三个问题都可以得到立即有效的解决,分别是:
      * 评估:对于一个给定的隐马尔科夫模型其生成一个给定的观察序列的概率是多少。前向算法可以有效的解决此问题。
      * 解码:什么样的隐藏(底层)状态序列最有可能生成一个给定的观察序列。维特比算法可以有效的解决此问题。
      * 学习:对于一个给定的观察序列样本,什么样的模型最可能生成该序列——也就是说,该模型的参数是什么。这个问题可以通过使用前向-后向算法解决。
      隐马尔科夫模型(HMM)在分析实际系统中已被证明有很大的价值;它们通常的缺点是过于简化的假设,这与马尔可夫假设相关——即一个状态只依赖于前一个状态,并且这种依赖关系是独立于时间之外的(与时间无关)。
      关于隐马尔科夫模型的完整论述,可参阅:
      L R Rabiner and B H Juang, `An introduction to HMMs’, iEEE ASSP Magazine, 3, 4-16.

    展开全文
  • 维特比算法(Viterbi Algorithm)   找到可能性最大的隐藏序列 通常我们都有一个特定的HMM,然后根据一个可观察序列去找到最可能生成这个可观察序列的隐藏序列。   1.穷举搜索 我们可以在下图中看到每个状态和...
  • 算法

    万次阅读 2018-02-08 00:13:09
    1.算法定义 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出...
  • 大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...
  • Dijkstra算法(迪杰斯特拉算法

    万次阅读 多人点赞 2019-06-24 18:06:30
    对比算法好坏需要考虑的因素 执行算法所耗费的时间 ...迪杰斯特拉算法的主要特点是以起始点为中心外层层扩展,直到扩展到终点为止。 迪杰斯特拉算法的成功率是最高的,因为它每次必能搜索到最优路径。但迪杰...
  • 后向传播(BackPropagation)算法理解

    千次阅读 2016-12-21 18:40:19
    后向传播算法是深度学习中一种训练与学习方法,用来调整深度网络中各个节点之间的权重,使得网络输出的样本标签与实际标签相一致。本文将对后向传播算法的实现细节进行总结。 后向传播算法是将输出层的误差向后进行...
  • 前剪枝算法剪枝算法区别

    万次阅读 2017-11-26 11:10:19
    (一)剪枝算法的简介:剪枝一般是为了避免树的过于复杂,过于拟合而进行的一个动作,剪枝操作是一个全局的操作。(二)预剪枝:预剪枝就是在树的构建过程(只用到训练集),设置一个阈值,使得当在当前分裂节点中分裂...
  • Dijkstra算法原理

    万次阅读 多人点赞 2017-02-19 22:46:13
    Dijkstra算法 1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性...
  • 最优化算法之粒子群算法(PSO)

    万次阅读 多人点赞 2018-08-03 10:26:45
    一、粒子群算法的概念   粒子群优化算法(PSO:Particle swarm optimization) 是一种进化计算技术(evolutionary computation)。源于对鸟群捕食的行为研究。粒子群优化算法的基本思想:是通过群体中个体之间的...
  • 后向最大匹配算法2.1 后向最大匹配算法的原理3. 双向最大匹配算法3.1 双向最大匹配算法的原理 1. 前向最大匹配算法 1.1 前向最大匹配算法的原理 首先,我们分词的目的是将一段中文分成若干个词语,前向最大匹配就是...
  • 智能优化算法:麻雀搜索算法-附代码

    万次阅读 多人点赞 2020-09-27 16:34:00
    2020智能优化算法:麻雀搜索算法-附代码 文章目录2020智能优化算法:麻雀搜索算法-附代码1.算法原理2.算法结果3.参考文献4.Matlab代码 摘要:麻雀搜索算法(Sparrow Search Algorithm, SSA)是于2020年提出的。SSA ...
  • 算法 BF算法

    千次阅读 2018-04-18 17:29:35
    BF算法是字符匹配的一种算法,也称暴力匹配算法算法思想:从主串s1的pos位置出发,与子串s2第一位进行匹配若相等,接着匹配一位字符若不相等,则返回到s1前一次匹配位置的后一位,接着与s2的起始位进行匹配直到与...
  • 由于我之前一直强调数据结构以及算法学习的重要性,所以就有一些读者经常问我,数据结构与算法应该要学习到哪个程度呢?,说实话,这个问题我不知道要怎么回答你,主要取决于你想学习到哪些程度,不过针对这个问题,...
  • 光学算法——经典枝切法(解包裹算法

    万次阅读 多人点赞 2021-04-25 07:58:40
    基于算法实现原理可将解包裹技术大致分为两类:路径跟踪类算法和路径无关类算法。本文介绍了其中一种最经典和应用广泛的相位解包裹算法——枝切法,包括一维相位解包裹原理、二维行列法解包裹原理、枝切法原理和算法...
  • 页面置换算法-CLOCK置换算法及其改进版算法

    万次阅读 多人点赞 2018-12-29 13:31:51
    页面置换算法中的LRU算法最接近理想情况下的OPT算法,但是实现起来比较困难且开销较大,所以很多设计者试图用开销比较小的算法接近LRU算法,CLOCK算法就是其中一种。 1.简单的CLOCK算法是通过给每一个访问的页面...
  • 如神经网络算法,蚁群算法,遗传算法,隐马尔科夫模型的Veterbi算法,前向后向算法等,这几天粗略地看了一下这些算法.大体上了解了这些算法的基本思路.从这些算法中,不得不感慨人类的智慧和大自然的巧妙.包括神经网络算法...
  • 算法算法评价

    万次阅读 多人点赞 2019-07-05 20:42:11
    一、算法的基本概念 算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。具有以下性质: 1.有穷性:一个算法必须总是在执行有穷步之后结束,且每一步都可在有穷时间内...
  • 数据挖掘算法——常用分类算法总结

    万次阅读 多人点赞 2019-06-17 10:55:22
    常用分类算法总结分类算法总结NBC算法LR算法SVM算法ID3算法C4.5 算法C5.0算法KNN 算法ANN 算法 分类算法总结 分类是在一群已经知道类别标号的样本中,训练一种分类器,让其能够对某种未知的样本进行分类。分类算法...
  • Dijkstra算法

    万次阅读 2021-02-17 12:18:58
    迪科斯彻算法使用了广度优先搜索解决非负权有图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。 该算法的输入包含了一个有权重的有图 G,以及G中的一个...
  • Mysql算法内部算法 - 嵌套循环连接算法1.循环连接算法// 循环连接算法分为两种 1.嵌套循环连接算法 2.块嵌套循环连接算法2.嵌套循环连接算法一个简单的嵌套循环连接(NLJ)算法从一个循环中的第一个表中读取一行中的...
  • 夜深人静写算法(三)- 初等数论入门

    万次阅读 多人点赞 2017-12-28 15:33:22
    初等数论:扩展欧几里得算法,中国剩余定理,欧拉函数,容斥原理,大数判素
  • 快速排序算法

    万次阅读 多人点赞 2019-01-11 21:09:08
    但是这种算法时间复杂度高,当需要排序的元素较多时,程序运行时间很长,因此产生了快速排序算法。该算法的实现可分为以下几步: 1. 在数组中选一个基准数(通常为数组第一个); 2. 将数组中小于基准数的数据移到...
  • 趣写算法系列之--匈牙利算法

    万次阅读 多人点赞 2013-07-18 13:39:59
    【书本上的算法往往讲得非常复杂,我和我的朋友计划用一些简单通俗的例子来描述算法的流程,这只是刚开始的样稿,其实我们也才刚开始】 匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是...
  • 刷了 3333 题 算法的一点点经验总结 —— 题不是这么刷的!
  • 遗传算法 ...对于一个最优化问题,一定数量的候选解(称为个体)的抽象表示(称为染色体)的种群更好的解进化。传统上,解用二进制表示(即0和1的串),但也可以用其他表示方法。进化从完全随机个

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,794,622
精华内容 1,917,848
关键字:

后向算法