隐马尔可夫模型

贝叶斯
2

一、隐马尔可夫模型(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. 隐马尔可夫模型的两个基本假设：

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

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

  1. 概率计算问题。给定模型​\lambda=(A, B, \pi)和观测序列​O＝(o_1，o_2,\cdots,o_T)，计算在模型​\lambda下观测序列​O出现的概率​P(O|\lambda)。前向-后向算法是通过递推地计算前向-后向概率可以高效地进行隐马尔可夫模型的概率计算。
  2. 学习问题。已知观测序列​O＝(o_1，o_2,\cdots,o_T)，估计模型​\lambda=(A, B, \pi)参数，使得在该模型下观测序列概率​P(O|\lambda)最大。即用极大似然估计的方法估计参数。Baum-Welch算法，也就是EM算法可以高效地对隐马尔可夫模型进行训练。它是一种非监督学习算法。
  3. 预测问题。已知模型​\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)

178a71aa93ebd21ca3c355bc0c20f505.png

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)

9af11fecf72cd3fe461d84ec7235dae8.png

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

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

  1. 给定模型 ​\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)}}
  1. 给定模型 ​\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}

  1. 将​\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