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

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

（一）隐马尔可夫模型基本概念

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。

隐藏的马尔可夫链随机生成的状态序列，称为状态序列（state sequence）;

每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列（observation sequence）。

序列的每个位置又可以看作是一个时刻。

隐马尔可夫模型由初始概率分布、状态转移概率分布以及观测概率分布确定。

隐马尔可夫模型的形式定义如下：

设Q是所有可能的状态的集合，V是所有可能的观测的集合。

Q?{q1,q2,?,qN}V?{v1,v2,?,vM}

I是长度为T的状态序列，O是对应的观测序列。

I?{i1,i2,?,iT}O?{o1,o2,?,oT}

A是状态转移概率矩阵：

A?[aij]N?N

其中，

aij?P(it?1?qjit?qi)i?1,2,?,N；j?1,2,?,N

是在时刻t处于状态qi的条件下在时刻t?1转移到状态qj的概率。

B是观测概率矩阵：

B?[bj(k)]N?M

其中，

bj(k)?P(ot?vkit?qj)k?1,2,?,M；j?1,2,?,N

是在时刻t处于状态qj的条件下生成观测vk的概率。

?是初始状态概率向量：

??(?i)

其中，

?i?P(i1?qi)i?1,2,?,N

是时刻t?1处于状态qi的概率。 隐马尔可夫模型的3个基本问题：

（1） 概率计算问题。给定模型和观测序列，计算在模型下观测序列

出现的概率。

（2） 学习问题。已知观测序列，估计模型参数，使得在该模型下观

测序列概率最大。即用极大似然估计的方法估计参数。 （3） 预测问题，也称为解码（decoding）问题。已知模型和观测序

列，求对给定观测序列条件概率最大的状态序列。即给定观测序列，求最有可能的对应的状态序列。

（二）Viterbi算法原理

维特比算法实际是用动态规划解隐马尔可夫模型预测问题，即用

动态规划（dynamic programming）求概率最大路径（最优路径）

输入：模型??(A,B,?)和观测O?(o1,o1,?,oT)；

**输出：最优路径I*?(i1*,i2,?,iT)。

（1）初始化

?1(i)??ibi(o1)i?1,2,?,N ?1(i)?0i?1,2,?,N

（2）递推对t?2,3,?,T

?t(i)?max[?t?1(j)aji]bi(ot)i?1,2,?,N

1?j?N?t(i)?argmax[?t?1(j)aji]i?1,2,?,N

1?j?N（3）终止

P*?max?T(j)

1?j?N*iT?argmax[?T(i)]

1?i?N（4）最优路径回溯对t?T?1,T?2,?,1

it*??t?1(it*?1)

**求得最优路径I*?(i1*,i2,?,iT)

（三）例子

三个盒子均有红白两种球，但每个盒子里面红白球的比例不同，从摸出来的球的颜色来判断盒子的状态序列。

模型??(A,B,?)，

?0.50.20.3??0.50.5?????A??0.30.50.2?，B??0.40.6?，??(0.2,0.4,0.4)T ?0.20.30.5??0.70.3?????已知观测序列O=（红，白，红），试求最优状态序列，即最优路

**径I*?(i1*,i2,i3)。

解：要在所有可能的路径中选择一条最优路径，按照以下步骤处理：

（1）初始化。在t?1时，对每一个状态i，i?1,2,3，求状态为i观测o1为红的概率，记此概率为?1(i)，则

?1(i)??ibi(o1)??ibi(红)，i?1,2,3

代入实际数据

?1(1)?0.10?1(2)?0.16?1(3)?0.28

记?1(i)?0i?1,2,3

（2）在t?2时，对每一个状态i，i?1,2,3，求在t?1时状态为j观测为红并在t?2时状态为i观测o2为白的路径的最大概率，记此最大概率为

?2(i)，则

?2(i)?max[?1(j)aji]bi(o2)

1?j?3同时，对每个状态i，i?1,2,3，记录概率最大路径的前一个状态j：

?2(i)?argmax[?1(j)aji]i?1,2,3

1?j?3计算：

?2(1)?max[?1(j)aj1]b1(o2)1?j?3

?max?0.10?0.5,0.16?0.3,0.28?0.2}?0.5

j＝0.028

?2(1)?3

?2(2)?0.0504?2(2)?3 ?2(3)?0.042?2(3)?3

同样，在t?3时，

?3(i)?max[?2(j)aji]bi(o3)

1?j?3?3(i)?argmax[?2(j)aji]

1?j?3?3(1)?0.00756?3(1)?2

?3(2)?0.01008?3(2)?2 ?3(3)?0.0147?3(3)?3

（3）以P*表示最优路径的概率，则

P*?max?3(j)?0.0147

1?j?3最优路径的终点是i3*：

*i3?argmax[?3(i)]?3

i（4）由最优路径的终点i3*，逆向找到i2*，i1*：

**在t?2时，i2??3(i3)??3(3)?3 *在t?1时，i1*??2(i2)??2(3)?3

**于是求得最优路径，即最优状态序列I*?(i1*,i2,i3)?(3,3,3)。

（四）程序实现

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=3 pi <- t(t(c(0.2,0.4,0.4)))

N=3#N kind state

M=2#M kind of observation T=3

#initialize:

Delta <- matrix(,nrow=3,ncol=3) for (i in 1: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=2

for (i in 1:N){ for (j in 1: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=3

for (i in 1:N){

for (j in 1: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(\每种盒子在每一步路径的最大概率矩阵如下：\ Delta

cat(paste(\第一步选盒子\ paste(\第二步选盒子\ paste(\第三步选盒子\

结果：

每种盒子在每一步路径的最大概率矩阵如下：

Delta

[,1] [,2] [,3] [1,] 0.10000 0.16000 0.2800 [2,] 0.02800 0.05040 0.0420 [3,] 0.00756 0.01008 0.0147

第一步选盒子 3 ；第二步选盒子 3 ；第三步选盒子

参考：《统计学习方法》

3 。

本文来源：https://www.bwwdw.com/article/63og.html