隐马尔可夫模型

WindBlow

2024-01-20

统计学

贝叶斯

一、隐马尔可夫模型(HMM)

隐马尔可夫模型由初始状态概率向\pi、状态转移概率矩阵A和观测概率矩阵B决定。因此，隐马尔可夫模型可以写成\lambda=(A, B, \pi)。
隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态的序列，再由各个状态随机生成一个观测而产生观测的序列的过程。
隐马尔可夫模型是一个生成模型，表示状态序列和观测序列的联合分布，但是状态序列是隐藏的，不可观测的。

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

\{q_1,q_2,\cdots,q_N\}, V=\{v_1,v_2,\cdots,v_M\}

其中，N 是可能状态数，M 是可能观测数。
I 是长度为 T 的状态序列， O 是对应的观测序列：

\{i_1,i_2,\cdots,i_T\}, O=\{o_1,o_2,\cdots,o_T\}

A 是状态转移概率矩阵：A=[a_{ij}]_{N*N}
其中, a_{ij} = P(i_{t+1}=q_j | i_t=q_i), i=1,2,\cdots,N;j=1,2,\cdots,N
是在时刻 t 处于状态 q_i 的条件下在时刻 t+1 转移到状态 q_j 的概率。

B 是观测概率矩阵：B=[b_{j}(K)]_{N*M}
其中, b_{j}(K) = P(o_{t}=v_k | i_t=q_j), k=1,2,\cdots,M; j=1,2,\cdots,N
是在时刻 t 处于状态 q_j 的条件下生成观测概率 v_k 的概率。

\pi 是初始状态概率向量：\pi=(\pi_i)
其中, \pi_i = P(i_1=q_i), i=1,2,\cdots,N
是时刻 t=1 处于状态 q_i 的条概率。

1. 隐马尔可夫模型的两个基本假设：

齐次马尔科夫假设，即假设隐藏的马尔可夫链在任意时刻的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻无关。
观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关。

2. 隐马尔可夫模型的三个基本问题：

概率计算问题。给定模型\lambda=(A, B, \pi)和观测序列O＝(o_1，o_2,\cdots,o_T)，计算在模型\lambda下观测序列O出现的概率P(O|\lambda)。前向-后向算法是通过递推地计算前向-后向概率可以高效地进行隐马尔可夫模型的概率计算。
学习问题。已知观测序列O＝(o_1，o_2,\cdots,o_T)，估计模型\lambda=(A, B, \pi)参数，使得在该模型下观测序列概率P(O|\lambda)最大。即用极大似然估计的方法估计参数。Baum-Welch算法，也就是EM算法可以高效地对隐马尔可夫模型进行训练。它是一种非监督学习算法。
预测问题。已知模型\lambda=(A, B, \pi)和观测序列O＝(o_1，o_2,\cdots,o_T)，求对给定观测序列条件概率P(I|O)最大的状态序列I＝(i_1，i_2,\cdots,i_T)。维特比算法应用动态规划高效地求解最优路径，即概率最大的状态序列。

二、概率计算算法

HMM概率计算问题：
给定模型\lambda=(A, B, \pi)和观测序列O＝(o_1，o_2,\cdots,o_T)，计算在模型\lambda下观测序列O出现的概率P(O|\lambda)。前向-后向算法是通过递推地计算前向-后向概率可以高效地进行隐马尔可夫模型的概率计算。
计算观测序列概率P(O|\lambda)的前向(forward)与后向(backward)算法。

2.1 前向概率

给定隐马尔可夫模型\lambda，定义时刻t部分的观测序列为o_1,o_2,...,o_t且状态为q_i的概率为前向概率，记作：

\alpha_t(i)=P(o_1,o_2,\cdots,o_t,i_t=q_i |\lambda)

可递推求得前向概率\alpha_t(i)及观测序列概率P(O|\lambda)。

观测序列概率的前向算法
输入：隐马尔可夫模型\lambda，观测序列 O。
输出：观测序列概率P(O|\lambda)

step 1：
初值：\alpha_1(i)=\pi_ib_i(o_1),i=1,2,\cdots,N
step 2:
递推：对t=1,2,\cdots,T-1,

\alpha_{t+1}=\bigg[\sum_{j=1}^N\alpha_t(j)a_{ji}\bigg]b_i(o_{t+1}),i=1,2,\cdots,N

step 3:
终止：P(O|\lambda)=\sum_{i=1}^N\alpha_T(i)

例1：

给定盒子和球组成的隐马尔可夫模型\lambda=(A,B,\pi)，状态集合Q={1,2,3}，观测集合V={红, 白}，

A=\left[\begin{array}{ccc}0.5&0.2&0.3\\0.3&0.5&0.2\\0.2&0.3&0.5\end{array}\right], \quad B=\left[\begin{array}{cc}0.5&0.5\\0.4&0.6\\0.7&0.3\end{array}\right], \quad \pi=(0.2,0.4,0.4)^T

设T=3, O=(红, 白, 红)，试用前向算法计算P(O|\lambda)。

Q <- c(1,2,3) # 可能状态集合
N <- length(Q) # 状态数

V <- c("R","W") # 可能观测集合
A <- matrix(c(0.5,0.3,0.2,0.2,0.5,0.3,0.3,0.2,0.5),nrow = 3) # 状态转移概率矩阵
B <- matrix(c(0.5,0.4,0.7,0.5,0.6,0.3), 
            nrow = 3,dimnames = list(Q,V))  # 观测概率矩阵
pi <- c(0.2,0.4,0.4) # 初始状态

O <- c("R","W","R") # 对应的观测序列
M <- length(O) # 观测数

# forward
alpha <- list()
for (t in 1:M) {  # 时刻数=观测数
  if (t == 1) {
    alpha[[t]] <- pi*B[,O[t]]
  } else {
    alpha[[t]] <- colSums(alpha[[t-1]] * A) * B[,O[t]]
  }
}
P <- sum(alpha[[M]])
print(alpha)
print(P)

2.2 后向概率

给定隐马尔可夫模型\lambda，定义时刻 t 部分的观测序列为o_1,o_2,...,o_t且状态为 q_i 的概率为前向概率，记作：

\beta_t(i)=P(o_1,o_2,\cdots,o_t|i_t=q_i, \lambda)

可递推求得前向概率 \alpha_t(i) 及观测序列概率 P(O|\lambda)。

观测序列概率的后向算法
输入：隐马尔可夫模型\lambda，观测序列 O。
输出：观测序列概率P(O|\lambda)

step 1：
初值：\beta_T(i)=1,i=1,2,\cdots,N
step 2:
递推：对t=T-1,T-2,\cdots,1

\beta_{t}(i)=\sum_{j=1}^Na_{ij}b_j(o_{t+1})\beta_{t+1}(j),i=1,2,\cdots,N

step 3:
终止：P(O|\lambda)=\sum_{i=1}^N\pi_ib_i(o_1)\beta_1(i)

例2：

同例1，试用后向算法计算P(O|\lambda)。

# backward
beta <- list()
for (t in M:1) {  # 时刻数=观测数
  if (t == M) {
    beta[[t]] <- rep(1,N)
  } else {
    beta[[t]] <- colSums(t(A) * B[,O[t+1]]*beta[[t+1]])
  }
}
P2 <- sum(pi*B[,O[1]]*beta[[1]])
print(beta)
print(P2)

三、一些概率和期望值的计算

利用前向概率和后向概率，可以计算单个状态和两个状态的概率

给定模型 \lambda 和观测 O，在时刻 t 处于状态q_i 的概率，由前向概率\alpha_t(i)和后向概率\beta_t(i)定义，记：

\gamma_t(i)=P(i_t=q_i|O, \lambda) = \frac{P(i_t=q_i,O| \lambda)}{P(\lambda|O)}=\frac{\alpha_t(i)\beta_t(i) }{\sum_{j=1}^N{\alpha_t(j)\beta_t(j)}}

给定模型 \lambda 和观测 O，在时刻 t 处于状态 q_i，且在时刻 t+1处于状态 q_j 的概率,记：

\begin{aligned} \xi_t(i,j)&=P(i_t=q_i,i_{t+1}=q_j|O, \lambda) \\ &= \frac{P(i_t=q_i,i_{t+1}=q_j,O| \lambda)}{P(O|\lambda)}\\ &= \frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum_{i=1}^N\sum_{j=1}^N{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}} \\ \end{aligned}

将\gamma_t(i)和\xi_t(i,j)对各个时刻 t 求和，可以得到一些有用的期望值。
- 在观测O下状态i出现的期望值:
sum_{t=1}^T\gamma_t(i)
- 在观测O下状态i转移的期望值:
sum_{t=1}^{T-1}\gamma_t(i)
- 在观测O下由状态i转移到状态j的期望值:
sum_{t=1}^{T-1}\xi_t(i,j)

例3:
同例1，设T=8,O=(红,白,红,红,白,红,白,白)，试计算P(i_4=q_3|O,\lambda)。

\displaystyle P(i_4=q_3|O,\lambda)=\frac{P(i_4=q_3,O|\lambda)}{P(O|\lambda)}=\frac{\alpha_4(3)\beta_4(3)}{P(O|\lambda)}

Q <- c(1,2,3) # 可能状态集合
N <- length(Q) # 状态数
V <- c("R","W") # 可能观测集合
A <- matrix(c(0.5,0.3,0.2,0.2,0.5,0.3,0.3,0.2,0.5),nrow = 3) # 状态转移概率矩阵
B <- matrix(c(0.5,0.4,0.7,0.5,0.6,0.3),
            nrow = 3,dimnames = list(Q,V))  # 观测概率矩阵

O <- c("R","W","R","R","W","R","W","W") 
M <- length(O) # 观测数

# forward
alpha <- list()
for (t in 1:M) {  # 时刻数=观测数
  if (t == 1) {
    alpha[[t]] <- pi * B[,O[t]]
  } else {
    alpha[[t]] <- colSums(alpha[[t-1]] * A) * B[,O[t]]
  }
}
P <- sum(alpha[[M]])
# backward
beta <- list()
for (t in M:1) {  # 时刻数=观测数
  if (t == M) {
    beta[[t]] <- rep(1,N)
  } else {
    beta[[t]] <- colSums(t(A) * B[,O[t+1]]*beta[[t+1]])
  }
}
P2 <- sum(pi*B[,O[1]]*beta[[1]])
res <- (alpha[[4]][3]*beta[[4]][3])/P)
print(res)
# 0.4340691