2路径的(轨道)最大概率估计- Viterbi算法 这是基于动态规划的思想的一种整体性考虑的方法(所谓动态规划实质上就是一种从后向 前逐步取优的优化方法).令在时刻n取到状态i的各个路径的最大概率为 8n()=max4P(Xn=i,Xn1=in1,…,X1=i,Yn=yn,…1=y14),(10.16 那么我们有 8n+1(i)=biy,, max, (8n()aji) (10.17) 用来计算它的实际程式是如下的 Viterbo i算法:假定最佳路径为(X1,…,XN).今设置 个从Xm1得到Xn的对应vn+1:Xn=Vn(Xn+1).计算6n(1)与vn的递推算法的具体设计如 设置初值81(1)=H1b1 用递推公式n+1()=bmax,(nO)an) 再定义vn+1(1)=j,其中广只要满足 n-(1)=b,5n()a (10.18) 最终采取如下的向后递推算法(相当于动态规划,动态规划的核心思想是:在一切最佳 路径上的任意节点出发,其后也应该是最佳路径,因此就能从后向前地逐步求得最佳路 得到如下的“最佳”轨道估计(X1,…,XN): 计算终值XN=1∈:8(=max,8xO)}, (10.19) 反向归纳地取xn=vn(xn+1) (10.20) 4学习问题-由观测Y=y估计模型参数λ 4.1状态链样本已知时的参数的频率估计 设隐 Markov模型的状态链有充分长的样本.把其中从状态i到下一个时刻为状态j转移的 频数记为A·那么,粗略地可取a=”为an的估计,同样设此观测链样本充分长记 ∑A 其中从状态到同一时刻的观测1转移的频数为B,则可取b=B-为b1的估计,不幸的 ∑Bn 是状态链是经过估计得到的,所以不修正地使用频率估计会增加误差.再则,这种估计也过于 敏感 4.2模型参数估计的EM算法的思想 我们取λ的最大似然估计λ,即它满足 P(=ylA)=max P(r=y|2) (10.21) 274274 2 路径的(轨道)最大概率估计 -- Viterbi 算法 这是基于动态规划的思想的一种整体性考虑的方法（所谓动态规划实质上就是一种从后向 前逐步取优的优化方法）. 令在时刻 n 取到状态 i 的各个路径的最大概率为 ( ) max ( , , , , , , | ) d n i i1 , ,i 1 P X n i X n 1 i n 1 X1 i 1 Yn y n Y1 y1 l n = = - = - = = = L - L L , (10. 16) 那么我们有 ( ) max ( ( ) ) 1 1 n iy j n ji i b j a n d d + + = . (10. 17) 用来计算它的实际程式是如下的 Viterbi 算法: 假定最佳路径为( , , ) ^ 1 ^ X L X N . 今设置一 个从 1 ^ X n+ 得到 X n ^ 的对应 : ( 1 ) ^ 1 ^ 1 + + = + n n n yn X y X . 计算 (i) n d 与y n 的递推算法的具体设计如 下: 设置初值 1 ( ) 1 i iy d i = m b ; 用递推公式 ( ) max ( ( ) ) 1 1 n iy j n ji i b j a n d d + + = ; 再定义 * 1 (i) j y n + = ，其中 * j 只要满足 n j i n i biy j a n * 1 ( ) ( ) * d 1 d + + = . (10. 18) 最终采取如下的向后递推算法 (相当于动态规划， 动态规划的核心思想是：在一切最佳 路径上的任意节点出发，其后也应该是最佳路径， 因此就能从后向前地逐步求得最佳路径) 得到如下的“最佳”轨道估计( , , ) ^ 1 ^ X L X N ： 计算终值 { : ( ) max ( )} * ^ X i i i j N N j N = Î d = d , (10. 19) 反向归纳地取 ( ) ^ 1 1 ^ Xn =yn+ X n+ . (10.20) ４ 学习问题 – 由观测Y = y 估计模型参数 l ４.1 状态链样本已知时的参数的频率估计 设隐 Markov 模型的状态链有充分长的样本．把其中从状态i 到下一个时刻为状态 j 转移的 频数记为 Aij ．那么，粗略地可取 å= = N j ij ij ij A A a 1 ^ 为 ij a 的估计. 同样设此观测链样本充分长, 记 其中从状态 i 到同一时刻的观测l 转移的频数为Bij , 则可取 å= = M l il il il B B b 1 ^ 为 il b 的估计． 不幸的 是状态链是经过估计得到的， 所以不修正地使用频率估计会增加误差. 再则, 这种估计也过于 敏感. ４. 2 模型参数估计的 EM 算法的思想 我们取 l 的最大似然估计 ^ l ，即它满足 ( | ) max ( | ) ^ l l l P Y = y = P Y = y (10.21)