隐马尔可夫模型维特比算法尝试

隐马尔可夫模型维特比算法尝试（一）隐马尔可夫模型基本概念隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态序列，称为状态序列（statesequence）;每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列（observationsequence）。序列的每个位置又可以看作是一个时刻。隐马尔可夫模型由初始概率分布、状态转移概率分布以及观测概率分布确定。隐马尔可夫模型的形式定义如下：设Q是所有可能的状态的集合，V是所有可能的观测的集合。12{,,,}NQqqq12{,,,}MVvvvI是长度为T的状态序列，O是对应的观测序列。12{,,,}TIiii12{,,,}TOoooA是状态转移概率矩阵：[]NNAija其中，1()ijtjtiaPiqiq1,2,,iN；1,2,,jN是在时刻t处于状态iq的条件下在时刻1t转移到状态jq的概率。B是观测概率矩阵：[()]NMBjbk其中，()()jtktjbkPoviq1,2,,kM；1,2,,jN是在时刻t处于状态jq的条件下生成观测kv的概率。是初始状态概率向量：()i其中，1()iiPiq1,2,,iN是时刻1t处于状态iq的概率。隐马尔可夫模型的3个基本问题：（1）概率计算问题。给定模型和观测序列，计算在模型下观测序列出现的概率。（2）学习问题。已知观测序列，估计模型参数，使得在该模型下观测序列概率最大。即用极大似然估计的方法估计参数。（3）预测问题，也称为解码（decoding）问题。已知模型和观测序列，求对给定观测序列条件概率最大的状态序列。即给定观测序列，求最有可能的对应的状态序列。（二）Viterbi算法原理维特比算法实际是用动态规划解隐马尔可夫模型预测问题，即用动态规划（dynamicprogramming）求概率最大路径（最优路径）输入：模型(,,)AB和观测11(,,,)TOooo；输出：最优路径****12(,,,)TIiii。（1）初始化11()()iiibo1,2,,iN1()0i1,2,,iN（2）递推对2,3,,tT11()[()]()maxttjiitjNijabo1,2,,iN11()[()]argmaxttjijNija1,2,,iN（3）终止*1()maxTjNPj*1[()]argmaxTTiNii（4）最优路径回溯对1,2,,1tTT**11()tttii求得最优路径****12(,,,)TIiii（三）例子三个盒子均有红白两种球，但每个盒子里面红白球的比例不同，从摸出来的球的颜色来判断盒子的状态序列。模型(,,)AB，0.50.20.30.30.50.20.20.30.5A，0.50.50.40.60.70.3B，(0.2,0.4,0.4)T已知观测序列O=（红，白，红），试求最优状态序列，即最优路径****123(,,)Iiii。解：要在所有可能的路径中选择一条最优路径，按照以下步骤处理：（1）初始化。在1t时，对每一个状态i，1,2,3i，求状态为i观测1o为红的概率，记此概率为1()i，则11()()()iiiiibob红，1,2,3i代入实际数据1(1)0.101(2)0.161(3)0.28记1()0i1,2,3i（2）在2t时，对每一个状态i，1,2,3i，求在1t时状态为j观测为红并在2t时状态为i观测2o为白的路径的最大概率，记此最大概率为2()i，则21213()[()]()maxjiijijabo同时，对每个状态i，1,2,3i，记录概率最大路径的前一个状态j：2113()[()]argmaxjijija1,2,3i计算：2111213(1)[()]()maxjjjabo0.100.5,0.160.3,0.280.2}0.5maxj＝0.0282(1)32(2)0.05042(2)32(3)0.0422(3)3同样，在3t时，32313()[()]()maxjiijijabo3213()[()]argmaxjijija3(1)0.007563(1)23(2)0.010083(2)23(3)0.01473(3)3（3）以*P表示最优路径的概率，则*313()0.0147maxjPj最优路径的终点是*3i：*33[()]3argmaxiii（4）由最优路径的终点*3i，逆向找到*2i，*1i：在2t时，**2333()(3)3ii在1t时，**1222()(3)3ii于是求得最优路径，即最优状态序列****123(,,)(3,3,3)Iiii。（四）程序实现A-matrix(c(0.5,0.2,0.3,0.3,0.5,0.2,0.2,0.3,0.5),nrow=3,ncol=3,byrow=T)B-matrix(c(0.5,0.5,0.4,0.6,0.7,0.3),nrow=3,ncol=2,byrow=T)O-c(0,1,0)#T=3pi-t(t(c(0.2,0.4,0.4)))N=3#NkindstateM=2#MkindofobservationT=3#initialize:Delta-matrix(,nrow=3,ncol=3)for(iin1:N){Delta[1,i]=pi[i]*B[i,1]}#Recursion:psi-matrix(,nrow=3,ncol=3)Psi-matrix(,nrow=3,ncol=3)Psi[1,]-c(0,0,0)t=2for(iin1:N){for(jin1:N){psi[i,j]-Delta[t-1,j]*A[j,i]}Delta[t,i]-max(psi[i,])*B[i,2]Psi[t,i]-which.max(psi[i,])}psi1-matrix(,nrow=3,ncol=3)t1=3for(iin1:N){for(jin1:N){psi1[i,j]-Delta[t,j]*A[j,i]}Delta[t1,i]-max(psi1[i,])*B[i,1]Psi[t1,i]-which.max(psi1[i,])}#以p表示最优路径的概率，则p-max(Delta[3,])i[3]-which.max(Delta[3,])i[2]-Psi[3,i[3]]i[1]-Psi[2,i[2]]print(每种盒子在每一步路径的最大概率矩阵如下：)Deltacat(paste(第一步选盒子,i[1]),\n,paste(第二步选盒子,i[2]),\n,paste(第三步选盒子,i[3]),\n)结果：每种盒子在每一步路径的最大概率矩阵如下：Delta[,1][,2][,3][1,]0.100000.160000.2800[2,]0.028000.050400.0420[3,]0.007560.010080.0147第一步选盒子3；第二步选盒子3；第三步选盒子3。参考：《统计学习方法》