精华内容
下载资源
问答
  • 隐马尔科夫模型

    2019-10-17 18:49:06
    文章目录隐马尔科夫模型1 隐马尔科夫模型概述1.1 隐马尔科夫模型的定义1.2 观测序列的生成过程1.3 隐马尔科夫模型的三个基本问题2 概率计算2.1 直接计算法2.2 前向算法2.3 后向算法2.4 一些概率与期望值的计算3 参数...

    隐马尔科夫模型

    1 隐马尔科夫模型概述

    1.1 隐马尔科夫模型的定义

    隐马尔科夫模型是关于时序的概率模型,描述由隐藏的马尔科夫链生成不可观测的状态序列,再由状态序列生成可观测的观测序列的过程。

    设隐马尔科夫模型的状态集合Y\mathcal{Y}{s1,s2,...,sN}\{s_1,s_2,...,s_N\},观测集合X\mathcal{X}{o1,o2,...,oM}\{o_1,o_2,...,o_M\}。一个隐马尔科夫模型的变量可以分为两组,一组是状态变量Y=(y1,y2,...,yT)Y=(y_1,y_2,...,y_T),其中yiy_i表示系统在第ii时刻的状态,状态是不可观测的;一组是观测变量X=(x1,x2,...,xT)X=(x_1,x_2,...,x_T),其中xix_i表示系统在第ii时刻的观测值。

    为确定一个隐马尔科夫模型,需要以下三组参数

    • 状态转移概率:模型在状态间转换的概率,表示为矩阵A=[aij]N×NA=[a_{ij}]_{N\times N},其中
      aij=P(yt+1=sjyt=si) a_{ij}=P(y_{t+1}=s_j\mid y_{t}=s_i)

    • 输出观测概率:模型在当前状态获得各个观测值的概率,表示为矩阵B=[bj(k)]N×MB=[b_{j}(k)]_{N \times M},其中
      bj(k)=P(xt=okyt=sj) b_{j}(k)=P(x_t=o_k\mid y_t=s_j)

    • 初始状态概率:模型在初识时刻各状态出现的概率,通常表示为π=(π1,π2,...,πN)\pi=(\pi_1,\pi_2,...,\pi_N),其中
      πi=P(y1=si) \pi_i=P(y_1=s_i)

    因此,隐马尔科夫模型可用三元组λ=(A,B,π)\lambda=(A,B,\pi)表示。

    1.2 观测序列的生成过程

    给定隐马尔科夫模型λ\lambda,观测序列的生成过程描述如下:

    (1)(1) 按照初始状态概率选择y1y_1,令t=1t=1

    (2)(2) 根据输出观测概率矩阵BByty_t选择观测值xtx_t

    (3)(3) 根据状态转移矩阵BByty_t选择状态yt+1y_{t+1}

    (4)(4) 如果t<Tt<T,设置t=t+1t=t+1,转到第(2)步,否则停止。

    1.3 隐马尔科夫模型的三个基本问题

    隐马尔科夫模型有33个基本问题。

    (1)(1) 概率计算问题。给定模型λ=(A,B,π)\lambda=(A,B,\pi)和观测序列X=(x1,x2,...,xT)X=(x_1,x_2,...,x_T),计算在模型λ\lambda下观测XX出现的概率P(Xλ)P(X\mid\lambda)

    (2)(2) 参数估计问题。给定观测序列X=(x1,x2,...,xT)X=(x_1,x_2,...,x_T),估计模型λ=(A,B,π)\lambda=(A,B,\pi)的参数,使得在该模型下观测概率P(Xλ)P(X\mid\lambda)最大。

    (3)(3) 状态预测问题。给定模型λ=(A,B,π)\lambda=(A,B,\pi)和观测序列X=(x1,x2,...,xT)X=(x_1,x_2,...,x_T),求最有可能的状态序列,即使得P(YX)P(Y\mid X)最大的状态序列Y=(y1,y2,...,yT)Y=(y_1,y_2,...,y_T)

    下面将逐一介绍这三种问题的解法。

    2 概率计算

    2.1 直接计算法

    给定模型λ=(A,B,π)\lambda=(A,B,\pi)和观测序列X=(x1,x2,...,xT)X=(x_1,x_2,...,x_T),计算在模型λ\lambda下观测XX出现的概率P(Xλ)P(X\mid\lambda),最直接的方法就是枚举所有可能的状态序列Y=(y1,y2,...,yT)Y=(y_1,y_2,...,y_T),计算联合概率P(X,Yλ)P(X,Y\mid\lambda),然后对所有可能的状态序列求和,计算P(Xλ)P(X\mid\lambda)

    根据贝叶斯公式
    P(X,Yλ)=P(XY,λ)P(Yλ) P(X,Y\mid\lambda)=P(X\mid Y,\lambda)P(Y\mid\lambda)
    其中
    P(Yλ)=πy1ay1y2ay2y3,...,ayT1yTP(XY,λ)=by1(x1)by2(x2),...,byT(xT) \begin{aligned} P(Y\mid\lambda)&=\pi_{y_1}a_{y_1y_2}a_{y_2y_3},...,a_{y_{T-1}y_T}\\ P(X\mid Y,\lambda)&=b_{y_1}(x_1)b_{y_2}(x_2),...,b_{y_T}(x_T) \end{aligned}
    因此
    P(X,Yλ)=πy1by1(x1)ay1y2by2(x2),...,ayT1yTbyT(xT) P(X,Y\mid\lambda)=\pi_{y_1}b_{y_1}(x_1)a_{y_1y_2}b_{y_2}(x_2),...,a_{y_{T-1}y_T}b_{y_T}(x_T)
    然后,通过对所有可能的状态序列求和,就可以得到观测序列XX的概率P(Xλ)P(X\mid\lambda),即
    P(Xλ)=YP(X,Yλ)=y1,y2,...,yTπy1by1(x1)ay1y2by2(x2),...,ayT1yTbyT(xT) \begin{aligned} P(X\mid\lambda)&=\sum_{Y}P(X,Y\mid\lambda)\\ &=\sum_{y_1,y_2,...,y_T}\pi_{y_1}b_{y_1}(x_1)a_{y_1y_2}b_{y_2}(x_2),...,a_{y_{T-1}y_T}b_{y_T}(x_T) \end{aligned}
    这种方法计算量很大,不可行。下面介绍更有效的算法:前向-后向算法。

    2.2 前向算法

    前向概率:给定隐马尔科夫模型λ\lambda,定义到时刻tt观测序列为x1,x2,...,xtx_1,x_2,...,x_t且状态为sis_i的概率为前向概率,记作
    αt(i)=P(x1,x2,...xt,yt=siλ) \alpha_t(i)=P(x_1,x_2,...x_t,y_t=s_i\mid\lambda)

    观测序列概率的前向算法

    输入:隐马尔科夫模型λ\lambda,观测序列XX

    输出:观测序列概率P(Xλ)P(X\mid\lambda)

    (1)(1) 初值
    α1(i)=πibi(x1)i=1,2,...,N \alpha_1(i)=\pi_ib_{i}(x_1)\quad i=1,2,...,N
    (2)(2) 递推,对t=1,2,...,T1t=1,2,...,T-1
    αt+1(i)=(j=1Nαt(j)aji)bi(xt+1)i=1,2,...,N \alpha_{t+1}(i)=(\sum_{j=1}^N\alpha_{t}(j)a_{ji})b_{i}(x_{t+1})\quad i=1,2,...,N
    (3)(3) 终止
    P(Xλ)=j=1NαT(i) P(X\mid\lambda)=\sum_{j=1}^N\alpha_T(i)

    2.3 后向算法

    后向概率:给定隐马尔科夫模型λ\lambda,定义时刻tt状态为sis_i的条件下,从t+1t+1TT观测序列为xt+1,xt+2,...,xTx_{t+1},x_{t+2},...,x_{T}的概率为后向概率,记作
    βt(i)=P(xt+1,xt+2,...,xTyt=si,λ) \beta_t(i)=P(x_{t+1},x_{t+2},...,x_T\mid y_t=s_i,\lambda)

    观测序列概率的后向算法

    输入:隐马尔科夫模型λ\lambda,观测序列XX

    输出:观测序列概率P(Xλ)P(X\mid\lambda)

    (1)(1) 初值
    βT(i)=1i=1,2,...,N \beta_T(i)=1\quad i=1,2,...,N
    (2)(2) 递推,对t=T1,T2,...,1t=T-1,T-2,...,1
    βt(i)=j=1Naijbj(xt+1)βt+1(j)i=1,2,...,N \beta_{t}(i)=\sum_{j=1}^Na_{ij}b_{j}(x_{t+1})\beta_{t+1}(j)\quad i=1,2,...,N
    (3)(3) 终止
    P(Xλ)=i=1Nπibi(x1)β1(i) P(X\mid\lambda)=\sum_{i=1}^N\pi_ib_{i}(x_1)\beta_1(i)

    2.4 一些概率与期望值的计算

    利用前向概率和后向概率,可以方便的对一些概率进行计算。

    1.1. 给定参数λ\lambda和观测XX,在时刻tt处于状态sis_i的概率,记为
    γt(i)=P(yt=siX,λ) \gamma_t(i)=P(y_t=s_i\mid X,\lambda)
    根据贝叶斯公式
    γt(i)=P(yt=si,Xλ)P(Xλ)=P(yt=si,Xλ)i=1NP(yt=si,Xλ) \gamma_t(i)=\frac{P(y_t=s_i,X\mid\lambda)}{P(X\mid\lambda)}=\frac{P(y_t=s_i,X\mid\lambda)}{\sum_{i=1}^NP(y_t=s_i,X\mid\lambda)}
    根据前向概率与后向概率的定义有
    P(yt=siX,λ)=αt(i)βt(i) P(y_t=s_i\mid X,\lambda)=\alpha_t(i)\beta_t(i)
    因此得到
    γt(i)=αt(i)βt(i)j=1Tαt(j)βt(j) \gamma_t(i)=\frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^T\alpha_t(j)\beta_t(j)}
    2.2. 给定参数λ\lambda和观测XX,在时刻tt处于状态sis_i且在时刻t+1t+1处于状态sjs_j的概率,记为
    ξt(i,j)=P(yt=si,yt+1=sjX,λ) \xi_t(i,j)=P(y_t=s_i,y_{t+1}=s_j\mid X,\lambda)
    根据贝叶斯公式
    ξt(i,j)=P(yt=si,yt+1=sj,Xλ)P(X,λ)=P(yt=si,yt+1=sj,Xλ)i=1Nj=1NP(yt=si,yt+1=sj,Xλ) \xi_t(i,j)=\frac{P(y_t=s_i,y_{t+1}=s_j,X\mid\lambda)}{P(X,\mid\lambda)} =\frac{P(y_t=s_i,y_{t+1}=s_j,X\mid\lambda)}{\sum_{i=1}^N\sum_{j=1}^NP(y_t=s_i,y_{t+1}=s_j,X\mid\lambda)}

    P(yt=si,yt+1=sj,Xλ)=αt(i)aijbj(xt+1)βt+1(j) P(y_t=s_i,y_{t+1}=s_j,X\mid\lambda)=\alpha_t(i)a_{ij}b_{j}(x_{t+1})\beta_{t+1}(j)
    因此得到
    ξt(i,j)=αt(i)aijbj(xt+1)βt+1(j)i=1Nj=1αt(i)aijbj(xt+1)βt+1(j) \xi_t(i,j)=\frac{\alpha_t(i)a_{ij}b_{j}(x_{t+1})\beta_{t+1}(j)}{\sum_{i=1}^N\sum_{j=1}\alpha_t(i)a_{ij}b_{j}(x_{t+1})\beta_{t+1}(j)}
    3.3. 一些有用的期望:

    (1)(1) 在观测XX下状态sis_i出现的期望值
    t=1Tγt(i) \sum_{t=1}^T\gamma_t(i)
    (2)(2) 在观测XX下由状态sis_i转移的期望值
    t=1T1γt(i) \sum_{t=1}^{T-1}\gamma_t(i)
    (3)(3) 在观测XX下由状态sis_i转移到状态sjs_j的期望值
    t=1T1ξ(i,j) \sum_{t=1}^{T-1}\xi(i,j)

    3 参数估计

    通过观测序列或者观测序列和状态序列来估计隐马尔科夫模型参数的算法,称为隐马尔科夫模型的学习算法

    3.1 监督学习

    假设给定的训练数据包含若干个观测序列和对应的状态序列,那么可以利用极大似然估计来估计参数

    1.\mathrm{1.} 转移概率aija_{ij}的计算

    设样本中时刻tt处于状态ii时刻t+1t+1处于状态jj的频数是AijA_{ij},那么aija_{ij}的估计是
    aij=Aijj=1NAij a_{ij}=\frac{A_{ij}}{\sum_{j=1}^NA_{ij}}
    2.\mathrm{2.} 观测概率bj(k)b_{j}(k)的计算

    设样本中状态jj且观测为kk的频数是BjkB_{jk},那么bj(k)b_{j}(k)的估计是
    bj(k)=Bjkk=1MBjk b_{j}(k)=\frac{B_{jk}}{\sum_{k=1}^MB_{jk}}
    3.\mathrm{3.} 初始状态πi\pi_i的估计为所有样本中初始状态为sis_i的概率

    3.2 非监督学习

    对于非监督学习,此时的训练数据将只包含观测序列,状态序列是隐变量,这时应该使用BaumWelch\mathrm{Baum-Welch}算法,也即EM\mathrm{EM}算法。

    1.\mathrm{1.} 确定完全数据的对数似然函数

    所有观测数据为X=(x1,x2,...,xT)X=(x_1,x_2,...,x_T),所有隐数据为Y=(y1,y2,...,yT)Y=(y_1,y_2,...,y_T),完全数据是(X,Y)=(x1,x2,...,xT,y1,y2,...,yT)(X,Y)=(x_1,x_2,...,x_T,y_1,y_2,...,y_T),完全数据的对数似然函数是logP(X,Yλ)\log P(X,Y\mid\lambda)

    2.\mathrm{2.} EM\mathrm{EM}算法的QQ函数
    Q(λ,λˉ)=YP(YX,λˉ)P(X,Yλ)=YP(X,Yλˉ)P(Xλˉ)P(X,Yλ) \begin{aligned} Q(\lambda,\bar{\lambda})&=\sum_{Y}P(Y\mid X,\bar{\lambda})P(X,Y\mid\lambda)\\ &=\sum_{Y}\frac{P(X,Y\mid\bar{\lambda})}{P(X\mid\bar{\lambda})}P(X,Y\mid\lambda) \end{aligned}
    其中λˉ\bar{\lambda}表示当前估计值,由于P(Xλˉ)P(X\mid\bar{\lambda})是常数项,略去后可写成
    Q(λ,λˉ)=YP(X,Yλˉ)P(X,Yλ) Q(\lambda,\bar{\lambda})=\sum_{Y}P(X,Y\mid\bar{\lambda})P(X,Y\mid\lambda)
    由于
    P(X,Y,λ)=πy1by1(x1)ay1y2by2(x2)...ayT1yTbyT(xT) P(X,Y,\mid\lambda)=\pi_{y_1}b_{y_1}(x_1)a_{y_1y_2}b_{y_2}(x_2)...a_{y_{T-1}y_T}b_{y_T}(x_T)

    于是QQ函数可以写成
    Q(λ,λˉ)=Ylogπy1P(X,Yλˉ)+Y(t=1T1logaytyt+1)P(X,I,λˉ)+Y(t=1Tlogbyt(xt))P(X,I,λˉ) \begin{aligned} Q(\lambda,\bar{\lambda})&=\sum_{Y}\log\pi_{y_1}P(X,Y\mid\bar{\lambda})+\sum_{Y}(\sum_{t=1}^{T-1}\log a_{y_ty_{t+1}})P(X,I,\mid\bar{\lambda})\\ &+\sum_{Y}(\sum_{t=1}^T\log b_{y_t}(x_t))P(X,I,\mid\bar{\lambda}) \end{aligned}

    3.\mathrm{3.} 极大化QQ函数

    由于QQ函数中的3\mathrm{3}个参数都是单独出现的,因此可以对每一项分别极大化。

    (1)(1) 初始状态概率的极大化
    Ylogπy1P(X,Yλˉ)=i=1NlogπiP(X,y1=iλˉ) \sum_{Y}\log\pi_{y_1}P(X,Y\mid\bar{\lambda})=\sum_{i=1}^N\log\pi_iP(X,y_1=i\mid\bar{\lambda})
    这里可以理解为合并同类项,由于存在约束条件i=1Nπi=1\sum_{i=1}^N\pi_i=1,利用拉格朗日乘子法,拉格朗日函数为
    L(π,γ)=i=1NlogπiP(X,y1=iλˉ)+γ(i=1Nπi1) L(\pi,\gamma)=\sum_{i=1}^N\log\pi_iP(X,y_1=i\mid\bar{\lambda})+\gamma(\sum_{i=1}^N\pi_i-1)
    πi\pi_i求偏导
    L(π,λ)πi=P(X,y1=iλˉ)πi+γ \frac{\partial L(\pi,\lambda)}{\partial\pi_i}=\frac{P(X,y_1=i\mid\bar{\lambda})}{\pi_i}+\gamma
    令偏导数等于00
    P(X,y1=iλˉ)+γπi=0 P(X,y_1=i\mid\bar{\lambda})+\gamma\pi_i=0
    ii求和得
    γ=P(Xλˉ) \gamma=-P(X\mid\bar\lambda)
    因此
    πi=P(X,y1=iλˉ)P(Xλˉ) \pi_i=\frac{P(X,y_1=i\mid\bar{\lambda})}{P(X\mid\bar\lambda)}

    (2)(2) 状态转移概率的极大化

    Y(t=1T1logaytyt+1)P(X,I,λˉ)=i=1Nj=1Nt=1T1logaijP(X,yt=i,yt+1=jλˉ) \sum_{Y}(\sum_{t=1}^{T-1}\log a_{y_ty_{t+1}})P(X,I,\mid\bar{\lambda})=\sum_{i=1}^N\sum_{j=1}^N\sum_{t=1}^{T-1}\log a_{ij}P(X,y_t=i,y_{t+1}=j\mid\bar\lambda)
    由于存在约束条件j=1Naij=1\sum_{j=1}^Na_{ij}=1,拉格朗日函数为
    L(a,γ)=i=1Nj=1Nt=1T1logaijP(X,yt=i,yt+1=jλˉ)+i=1Nγi(j=1Naij1) L(a,\gamma)=\sum_{i=1}^N\sum_{j=1}^N\sum_{t=1}^{T-1}\log a_{ij}P(X,y_t=i,y_{t+1}=j\mid\bar\lambda)+\sum_{i=1}^N\gamma_i(\sum_{j=1}^Na_{ij}-1)
    aija_{ij}求偏导
    L(a,λ)aij=t=1T1P(X,yt=i,yt+1=jλˉ)aij+γi \frac{\partial L(a,\lambda)}{\partial a_{ij}}=\frac{\sum_{t=1}^{T-1}P(X,y_t=i,y_{t+1}=j\mid\bar\lambda)}{a_{ij}}+\gamma_i
    令偏导数等于00
    t=1T1P(X,yt=i,yt+1=jλˉ)+aijγi=0 \sum_{t=1}^{T-1}P(X,y_t=i,y_{t+1}=j\mid\bar\lambda)+a_{ij}\gamma_i=0
    对所有的jj求和的
    γi=t=1T1P(X,yt=iγˉ) \gamma_i=-\sum_{t=1}^{T-1}P(X,y_t=i\mid\bar\gamma)
    因此
    aij=t=1T1P(X,yt=i,yt+1=jλˉ)t=1T1P(X,yt=iλˉ) a_{ij}=\frac{\sum_{t=1}^{T-1}P(X,y_t=i,y_{t+1}=j\mid\bar\lambda)}{\sum_{t=1}^{T-1}P(X,y_t=i\mid\bar\lambda)}
    (3)(3) 输出观测概率的极大化

    Y(t=1Tlogbyt(xt))P(X,I,λˉ)=j=1Nt=1Tlogbj(xt)P(X,yt=jλˉ) \sum_{Y}(\sum_{t=1}^T\log b_{y_t}(x_t))P(X,I,\mid\bar{\lambda})=\sum_{j=1}^N\sum_{t=1}^{T}\log b_j(x_t)P(X,y_t=j\mid\bar\lambda)
    存在约束条件k=1Mbj(k)=1\sum_{k=1}^Mb_j(k)=1,拉格朗日函数为
    L(b,γ)=j=1Nt=1Tlogbj(xt)P(X,yt=jλˉ)+j=1Nγj(k=1Mbj(k)1) L(b,\gamma)=\sum_{j=1}^N\sum_{t=1}^{T}\log b_j(x_t)P(X,y_t=j\mid\bar\lambda)+\sum_{j=1}^{N}\gamma_j(\sum_{k=1}^Mb_j(k)-1)
    bj(k)b_j(k)求偏导时,只有在xt=okx_t=o_kbj(xt)b_j(x_t)bjkb_{jk}的偏导数才不为00,用I(xt=ok)I(x_t=o_k)表示
    L(b,γ)bj(k)=t=1TI(xt=ok)P(X,yt=jλˉ)bj(k)+γj \frac{\partial L(b,\gamma)}{\partial b_j(k)}=\frac{\sum_{t=1}^{T}I(x_t=o_k)P(X,y_t=j\mid\bar\lambda)}{b_j(k)}+\gamma_j
    令偏导数等于00
    t=1TI(xt=ok)P(X,yt=jλˉ)+bj(k)γj=0 \sum_{t=1}^{T}I(x_t=o_k)P(X,y_t=j\mid\bar\lambda)+b_j(k)\gamma_j=0
    kk求和得
    γj=t=1TP(X,yt=jλˉ) \gamma_j=-\sum_{t=1}^{T}P(X,y_t=j\mid\bar\lambda)
    因此
    bj(k)=t=1TI(xt=ok)P(X,yt=jλˉ)t=1TP(X,yt=jλˉ) b_j(k)=\frac{\sum_{t=1}^{T}I(x_t=o_k)P(X,y_t=j\mid\bar\lambda)}{\sum_{t=1}^{T}P(X,y_t=j\mid\bar\lambda)}

    到此就推导完了EM\mathrm{EM}算法中的迭代更新公式,我们可以使用在2.32.3中定义的概率值来重写更新公式
    πi=γ1(i)aij=t=1T1ξ(i,j)t=1T1γt(i)bj(k)=t=1Tγt(i)I(xt=ok)t=1Tγt(i) \begin{aligned} \pi_i&=\gamma_1(i)\\ a_{ij}&=\frac{\sum_{t=1}^{T-1}\xi(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)}\\ b_j(k)&=\frac{\sum_{t=1}^{T}\gamma_t(i)I(x_t=o_k)}{\sum_{t=1}^{T}\gamma_t(i)} \end{aligned}
    BaumWelch\mathrm{Baum-Welch}算法

    输入:观测数据X=(x1,x2,...,xT)X=(x_1,x_2,...,x_T)

    输出:隐马尔科夫模型参数。

    (1)(1) 初始化,对n=0n=0,选取aij(0),bj(k)(0),πi(0)a_{ij}^{(0)},b_j(k)^{(0)},\pi_i^{(0)},得到模型λ(0)=(A(0),B(0),π(0))\lambda^{(0)}=(A^{(0)},B^{(0)},\pi^{(0)})

    (2)(2) 递推。对n=1,2,...,n=1,2,...,
    aij(n+1)=t=1T1ξ(i,j)t=1T1γt(i)bj(k)(n+1)=t=1Tγt(i)I(xt=ok)t=1Tγt(i)πi(n+1)=γ1(i) \begin{aligned} a_{ij}^{(n+1)}&=\frac{\sum_{t=1}^{T-1}\xi(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)}\\ b_j(k)^{(n+1)}&=\frac{\sum_{t=1}^{T}\gamma_t(i)I(x_t=o_k)}{\sum_{t=1}^{T}\gamma_t(i)}\\ \pi_i^{(n+1)}&=\gamma_1(i) \end{aligned}
    右端各值按观测X=(x1,x2,...,xT)X=(x_1,x_2,...,x_T)和模型λ(n)=(A(n),B(n),π(n))\lambda^{(n)}=(A^{(n)},B^{(n)},\pi^{(n)})计算。

    (3)(3) 终止,得到模型参数λ(n+1)=(A(n+1),B(n+1),π(n+1))\lambda^{(n+1)}=(A^{(n+1)},B^{(n+1)},\pi^{(n+1)})

    4 状态预测

    4.1 近似算法

    近似算法的思想是,在每个时刻tt,选择在该时刻最有可能出现的状态yty_t^*作为该时刻的预测,也即
    yt=argmax1iN[γt(i)] y_t^*=\arg\max\limits_{1\leq i\leq N}[\gamma_t(i)]
    从而得到状态序列Y=(y1,y2,...,yT)Y=(y_1^*,y_2^*,...,y_T^*),近似算法是一种贪婪算法,优点是计算简单,缺点是不能保证得到的状态序列是最优状态序列。

    4.2 维特比算法

    维特比算法利用动态规划法求解隐马尔科夫模型的状态预测问题。维特比算法将一个状态序列当做一条路径,目的是求解概率最大路径。

    根据动态规划原理,最优路径具有最优子结构的性质。即如果最优路径在时刻tt通过节点yty_t^*,那么这一路径中从节点yty_t^*到节点yTy_T^*的部分路径,对于从yty_t^*yTy_T^*的所有可能路径来说,必然是最优的。否则就会得到一条比原来路径更优的路径,这是矛盾的。

    因此,只需从时刻t=1t=1开始,递推的计算在时刻tt状态为ii的各条部分路径的最大概率,直至得到时刻TT状态为ii的各条路径的最大概率。时刻t=Tt=T的最大概率即为最优路径的概率PP^*,最优路径的终结点yTy_T^*也已经得到,之后从yTy_T^*开始,从后向前逐步求得yT1,...,y1y_{T-1}^*,...,y_1^*,得到最优路径Y=(y1,y2,...,yT)Y^*=(y_1^*,y_2^*,...,y_T^*)

    定义在时刻tt状态为ii的所有单个路径(y1,y2,...,yt)(y_1,y_2,...,y_t)中概率最大值为
    δt(i)=maxy1,y2,...,yt1P(yt=i,yt1,...,y1,xt,...,x1λ),i=1,2,...,N \delta_t(i)=\max\limits_{y_1,y_2,...,y_{t-1}}P(y_t=i,y_{t-1},...,y_1,x_t,...,x_1\mid\lambda),\quad i=1,2,...,N
    变量δ\delta的递推公式为
    δt+1(i)=maxy1,y2,...,ytP(yt+1=i,yt,...,y1,xt+1,...,x1λ)=max1jN[δt(j)aji]bi(xt+1),i=1,2,...,N,t=1,2,...,T1 \begin{aligned} \delta_{t+1}(i) &=\max\limits_{y_1,y_2,...,y_t}P(y_{t+1}=i,y_t,...,y_1,x_{t+1},...,x_1\mid\lambda)\\ &=\max\limits_{1\leq j\leq N}[\delta_t(j)a_{ji}]b_i(x_{t+1}),\quad i=1,2,...,N,t=1,2,...,T-1 \end{aligned}
    定义在时刻tt状态为ii的所有单个路径(y1,y2,...,yt)(y_1,y_2,...,y_t)中概率最大的路径的第t1t-1个节点为
    ψt(i)=argmax1jN[δt1(j)aji],i=1,2,...,N \psi_t(i)=\arg\max\limits_{1\leq j\leq N}[\delta_{t-1}(j)a_{ji}],\quad i=1,2,...,N
    有了这两个变量,就可以介绍维特比算法。

    维特比算法

    输入:隐马尔科夫模型λ=(A,B,π)\lambda=(A,B,\pi)和观测X=(x1,x2,...,xT)X=(x_1,x_2,...,x_T)

    输出:最优状态序列Y=(y1,y2,...,yT)Y^*=(y_1^*,y_2^*,...,y_T^*)

    (1)(1) 初始化
    δ1(i)=πibi(x1),i=1,2,...,Nψ1(i)=0,i=1,2,...,N \begin{aligned} \delta_1(i)&=\pi_ib_i(x_1),\quad i=1,2,...,N\\ \psi_1(i)&=0,\quad\quad\quad\quad i=1,2,...,N \end{aligned}
    (2)(2) 递推。对t=2,3,...,Tt=2,3,...,T
    δt(i)=max1jN[δt1(j)aji]bi(xt),i=1,2,...,Nψt(i)=argmax1jN[δt1(j)aji],i=1,2,...,N \begin{aligned} \delta_{t}(i) &=\max\limits_{1\leq j\leq N}[\delta_{t-1}(j)a_{ji}]b_i(x_{t}),\quad i=1,2,...,N\\ \psi_t(i)&=\arg\max\limits_{1\leq j\leq N}[\delta_{t-1}(j)a_{ji}],\quad i=1,2,...,N \end{aligned}
    (3)(3) 终止
    P=max1iN[δT(i)]yT=argmax1iN[δT(i)] \begin{aligned} P^*&=\max\limits_{1\leq i\leq N}[\delta_T(i)]\\ y_T^*&=\arg\max\limits_{1\leq i\leq N}[\delta_T(i)] \end{aligned}
    (4)(4) 回溯。对t=T1,T2,...,1t=T-1,T-2,...,1
    yt=ψt+1(yt+1) y_t^*=\psi_{t+1}(y_{t+1}^*)

    求得最优状态序列Y=(y1,y2,...,yT)Y^*=(y_1^*,y_2^*,...,y_T^*)

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,432
精华内容 972
关键字:

隐马尔科夫模型