【机器学习】隐马尔科夫模型之维特比算法(Viterbi Algorithm)和鲍姆-韦尔奇算法(Baum-Welch Algorithm)

维特比算法和鲍姆-韦尔奇算法是隐马尔可夫模型(HMM)中的两个重要算法,各自解决不同的问题。

1.维特比算法

目的

维特比算法用于解码问题,即在给定观测序列的情况下,找到最可能的隐藏状态序列。

方法

维特比算法是一种动态规划算法,通过递归计算最可能的状态序列的概率来找到最佳路径。

算法步骤

维特比算法是一种动态规划算法,用于在隐马尔可夫模型(HMM)中找到给定观测序列的最可能隐藏状态序列。它通过最大化后验概率来实现这一目标。以下是维特比算法的详细解释,包括数学推导和算法步骤。

问题描述

给定一个HMM模型 λ = ( Π , A , B ) \lambda = (\Pi, A, B) λ=(Π,A,B)和一个观测序列 O = { O 1 , O 2 , … , O T } O = \{O_1, O_2, \ldots, O_T\} O={O1,O2,,OT},维特比算法的目标是找到最可能的隐藏状态序列 Q = { q 1 , q 2 , … , q T } Q = \{q_1, q_2, \ldots, q_T\} Q={q1,q2,,qT},即:

Q ∗ = arg ⁡ max ⁡ Q P ( Q ∣ O , λ ) Q^* = \arg\max_Q P(Q | O, \lambda) Q=argQmaxP(QO,λ)

数学推导

维特比算法通过最大化联合概率 P ( Q , O ∣ λ ) P(Q, O | \lambda) P(Q,Oλ) 来找到最可能的状态序列,因为:

P ( Q ∣ O , λ ) = P ( Q , O ∣ λ ) P ( O ∣ λ ) P(Q | O, \lambda) = \frac{P(Q, O | \lambda)}{P(O | \lambda)} P(QO,λ)=P(Oλ)P(Q,Oλ)

最大化 P ( Q ∣ O , λ ) P(Q | O, \lambda) P(QO,λ)等价于最大化 P ( Q , O ∣ λ ) P(Q, O | \lambda) P(Q,Oλ),因为 P ( O ∣ λ ) P(O | \lambda) P(Oλ) 是常数。

联合概率 P ( Q , O ∣ λ ) P(Q, O | \lambda) P(Q,Oλ) 可以表示为:

P ( Q , O ∣ λ ) = P ( O ∣ Q , λ ) P ( Q ∣ λ ) P(Q, O | \lambda) = P(O | Q, \lambda) P(Q | \lambda) P(Q,Oλ)=P(OQ,λ)P(Qλ)

其中:

P ( O ∣ Q , λ ) = ∏ t = 1 T b q t ( O t ) P(O | Q, \lambda) = \prod_{t=1}^T b_{q_t}(O_t) P(OQ,λ)=t=1Tbqt(Ot)

P ( Q ∣ λ ) = π q 1 ∏ t = 2 T a q t − 1 , q t P(Q | \lambda) = \pi_{q_1} \prod_{t=2}^T a_{q_{t-1}, q_t} P(Qλ)=πq1t=2Taqt1,qt

因此:

P ( Q , O ∣ λ ) = π q 1 b q 1 ( O 1 ) ∏ t = 2 T a q t − 1 , q t b q t ( O t ) P(Q, O | \lambda) = \pi_{q_1} b_{q_1}(O_1) \prod_{t=2}^T a_{q_{t-1}, q_t} b_{q_t}(O_t) P(Q,Oλ)=πq1bq1(O1)t=2Taqt1,qtbqt(Ot)

动态规划

维特比算法使用动态规划来高效地找到最可能的状态序列。它定义了两个变量:路径概率 δ t ( i ) \delta_t(i) δt(i)和路径指针 ψ t ( i ) \psi_t(i) ψt(i)

路径概率 δ t ( i ) \delta_t(i) δt(i)

δ t ( i ) \delta_t(i) δt(i) 表示在时间 t t t状态为 S i S_i Si 的最优路径的概率:

δ t ( i ) = max ⁡ q 1 , q 2 , … , q t − 1 P ( q 1 , q 2 , … , q t − 1 , S t = S i , O 1 , O 2 , … , O t ∣ λ ) \delta_t(i) = \max_{q_1, q_2, \ldots, q_{t-1}} P(q_1, q_2, \ldots, q_{t-1}, S_t = S_i, O_1, O_2, \ldots, O_t | \lambda) δt(i)=q1,q2,,qt1maxP(q1,q2,,qt1,St=Si,O1,O2,,Otλ)

路径指针 ψ t ( i ) \psi_t(i) ψt(i)

ψ t ( i ) \psi_t(i) ψt(i) 记录了状态 S i S_i Si 在时间 t t t的最优路径的前一个状态:

ψ t ( i ) = arg ⁡ max ⁡ 1 ≤ j ≤ N [ δ t − 1 ( j ) a j i ] \psi_t(i) = \arg\max_{1 \leq j \leq N} [\delta_{t-1}(j) a_{ji}] ψt(i)=arg1jNmax[δt1(j)aji]

维特比算法步骤

1. 初始化

对于每个状态 i i i

δ 1 ( i ) = π i b i ( O 1 ) , 1 ≤ i ≤ N \delta_1(i) = \pi_i b_i(O_1), \quad 1 \leq i \leq N δ1(i)=πibi(O1),1iN

ψ 1 ( i ) = 0 \psi_1(i) = 0 ψ1(i)=0

2. 递推

对于每个时间 t t t 2 2 2到T,以及每个状态 j j j

δ t ( j ) = max ⁡ 1 ≤ i ≤ N [ δ t − 1 ( i ) a i j ] b j ( O t ) , 2 ≤ t ≤ T ,   1 ≤ j ≤ N \delta_t(j) = \max_{1 \leq i \leq N} [\delta_{t-1}(i) a_{ij}] b_j(O_t), \quad 2 \leq t \leq T, \, 1 \leq j \leq N δt(j)=1iNmax[δt1(i)aij]bj(Ot),2tT,1jN

ψ t ( j ) = arg ⁡ max ⁡ 1 ≤ i ≤ N [ δ t − 1 ( i ) a i j ] , 2 ≤ t ≤ T ,   1 ≤ j ≤ N \psi_t(j) = \arg\max_{1 \leq i \leq N} [\delta_{t-1}(i) a_{ij}], \quad 2 \leq t \leq T, \, 1 \leq j \leq N ψt(j)=arg1iNmax[δt1(i)aij],2tT,1jN

3. 终止

找到最后一个时刻最优路径的概率:

P ∗ = max ⁡ 1 ≤ i ≤ N δ T ( i ) P^* = \max_{1 \leq i \leq N} \delta_T(i) P=1iNmaxδT(i)

找到最后一个时刻最优路径的状态:

q T ∗ = arg ⁡ max ⁡ 1 ≤ i ≤ N δ T ( i ) q_T^* = \arg\max_{1 \leq i \leq N} \delta_T(i) qT=arg1iNmaxδT(i)

4. 路径回溯

通过路径指针 ψ t ( i ) \psi_t(i) ψt(i) 回溯得到最优路径:

q t ∗ = ψ t + 1 ( q t + 1 ∗ ) , t = T − 1 , T − 2 , … , 1 q_{t}^* = \psi_{t+1}(q_{t+1}^*), \quad t = T-1, T-2, \ldots, 1 qt=ψt+1(qt+1),t=T1,T2,,1

总结

维特比算法通过以下步骤找到最可能的隐藏状态序列:

  1. 初始化:计算初始时刻的路径概率。
  2. 递推:利用动态规划递推计算每个时刻的路径概率和路径指针。
  3. 终止:找到最优路径的终止状态。
  4. 回溯:通过路径指针回溯得到最优路径。

维特比算法是一种高效的动态规划算法,可以在 O ( N 2 T ) O(N^2 T) O(N2T) 时间复杂度内解决最优路径问题,其中 N N N是状态数, T T T 是观测序列长度。

应用场景

维特比算法广泛应用于需要从观测数据中推断隐藏状态序列的场景,如:

  • 自然语言处理中的词性标注
  • 生物信息学中的基因序列分析
  • 语音识别中的语音信号解码

2.鲍姆-韦尔奇算法

目的

鲍姆-韦尔奇算法用于参数学习,即在观测数据的基础上估计隐马尔可夫模型的参数(初始状态概率、状态转移概率和观测概率)。

方法

鲍姆-韦尔奇算法是一种期望最大化(EM)算法,通过迭代优化模型参数来最大化观测数据的似然函数。

1. 背景和定义

假设我们有一个隐马尔可夫模型(HMM),其参数包括:

  • 初始状态概率分布 Π = { π i } \Pi = \{\pi_i\} Π={πi} π i = P ( S 1 = i ) \pi_i = P(S_1 = i) πi=P(S1=i)
  • 状态转移概率矩阵 A = { a i j } A = \{a_{ij}\} A={aij} a i j = P ( S t + 1 = j ∣ S t = i ) a_{ij} = P(S_{t+1} = j | S_t = i) aij=P(St+1=jSt=i)
  • 观测概率矩阵 B = { b j ( k ) } B = \{b_j(k)\} B={bj(k)} b j ( k ) = P ( O t = k ∣ S t = j ) b_j(k) = P(O_t = k | S_t = j) bj(k)=P(Ot=kSt=j)

其中, S t S_t St 是在时间 t t t 的隐藏状态, O t O_t Ot 是在时间 t t t 的观测值。

2. 算法步骤

Baum-Welch算法通过反复执行以下两步来估计参数:期望步(E步)和最大化步(M步)。

2.1 初始化

首先,为模型参数设定初始值,可以是随机的,也可以基于一些先验知识进行初始化。

2.2 E步(期望步)

在E步中,我们计算给定当前参数估计下的后验概率。具体来说,我们需要计算前向概率、后向概率、 γ t ( i ) \gamma_t(i) γt(i) ξ t ( i , j ) \xi_t(i, j) ξt(i,j)

前向算法

前向算法用于计算在时间 t t t 观测到部分序列 O 1 , O 2 , … , O t O_1, O_2, \ldots, O_t O1,O2,,Ot 且系统处于状态 i i i 的概率。定义前向变量 α t ( i ) \alpha_t(i) αt(i)

α t ( i ) = P ( O 1 , O 2 , … , O t , S t = i ∣ θ ) \alpha_t(i) = P(O_1, O_2, \ldots, O_t, S_t = i | \theta) αt(i)=P(O1,O2,,Ot,St=iθ)

递推公式如下:

  1. 初始化: α 1 ( i ) = π i b i ( O 1 ) \alpha_1(i) = \pi_i b_i(O_1) α1(i)=πibi(O1)
  2. 递推: α t + 1 ( j ) = ( ∑ i = 1 N α t ( i ) a i j ) b j ( O t + 1 ) \alpha_{t+1}(j) = \left( \sum_{i=1}^N \alpha_t(i) a_{ij} \right) b_j(O_{t+1}) αt+1(j)=(i=1Nαt(i)aij)bj(Ot+1)
后向算法

后向算法用于计算在时间 t t t 系统处于状态 i i i 且从时间 t + 1 t+1 t+1 T T T 的观测序列 O t + 1 , O t + 2 , … , O T O_{t+1}, O_{t+2}, \ldots, O_T Ot+1,Ot+2,,OT 的概率。定义后向变量 β t ( i ) \beta_t(i) βt(i)

β t ( i ) = P ( O t + 1 , O t + 2 , … , O T ∣ S t = i , θ ) \beta_t(i) = P(O_{t+1}, O_{t+2}, \ldots, O_T | S_t = i, \theta) βt(i)=P(Ot+1,Ot+2,,OTSt=i,θ)

递推公式如下:

  1. 初始化: β T ( i ) = 1 \beta_T(i) = 1 βT(i)=1
  2. 递推: β t ( i ) = ∑ j = 1 N a i j b j ( O t + 1 ) β t + 1 ( j ) \beta_t(i) = \sum_{j=1}^N a_{ij} b_j(O_{t+1}) \beta_{t+1}(j) βt(i)=j=1Naijbj(Ot+1)βt+1(j)
计算 γ t ( i ) \gamma_t(i) γt(i) ξ t ( i , j ) \xi_t(i, j) ξt(i,j)
  • (\gamma_t(i)):表示在时间 (t) 系统处于状态 (i) 的概率。

γ t ( i ) = P ( S t = i ∣ O , θ ) = α t ( i ) β t ( i ) ∑ j = 1 N α t ( j ) β t ( j ) \gamma_t(i) = P(S_t = i | O, \theta) = \frac{\alpha_t(i) \beta_t(i)}{\sum_{j=1}^N \alpha_t(j) \beta_t(j)} γt(i)=P(St=iO,θ)=j=1Nαt(j)βt(j)αt(i)βt(i)

  • ξ t ( i , j ) \xi_t(i, j) ξt(i,j):表示在时间 t t t 系统处于状态 i i i 并且在时间 t + 1 t+1 t+1 转移到状态 (j) 的概率。

ξ t ( i , j ) = P ( S t = i , S t + 1 = j ∣ O , θ ) = α t ( i ) a i j b j ( O t + 1 ) β t + 1 ( j ) ∑ i = 1 N ∑ j = 1 N α t ( i ) a i j b j ( O t + 1 ) β t + 1 ( j ) \xi_t(i, j) = P(S_t = i, S_{t+1} = j | O, \theta) = \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)} ξt(i,j)=P(St=i,St+1=jO,θ)=i=1Nj=1Nαt(i)aijbj(Ot+1)βt+1(j)αt(i)aijbj(Ot+1)βt+1(j)

2.3 M步(最大化步)

在M步中,我们使用E步中的计算结果更新参数估计值。

  • 更新初始状态概率分布 Π \Pi Π

π i = γ 1 ( i ) \pi_i = \gamma_1(i) πi=γ1(i)

  • 更新状态转移概率矩阵 A A A

a i j = ∑ t = 1 T − 1 ξ t ( i , j ) ∑ t = 1 T − 1 γ t ( i ) a_{ij} = \frac{\sum_{t=1}^{T-1} \xi_t(i, j)}{\sum_{t=1}^{T-1} \gamma_t(i)} aij=t=1T1γt(i)t=1T1ξt(i,j)

  • 更新观测概率矩阵 B B B

假设观测值是离散的,更新公式为:

b j ( k ) = ∑ t = 1 T γ t ( j ) ⋅ I ( O t = k ) ∑ t = 1 T γ t ( j ) b_j(k) = \frac{\sum_{t=1}^T \gamma_t(j) \cdot \mathbb{I}(O_t = k)}{\sum_{t=1}^T \gamma_t(j)} bj(k)=t=1Tγt(j)t=1Tγt(j)I(Ot=k)

其中 I ( O t = k ) \mathbb{I}(O_t = k) I(Ot=k)是指示函数,当 O t = k O_t = k Ot=k 时取值为1,否则取值为0。

3. 迭代

重复E步和M步,直到参数收敛(即参数变化小于某个阈值)或达到最大迭代次数。

应用场景

鲍姆-韦尔奇算法适用于模型参数未知,需要从数据中学习这些参数的情况,如:

  • 生物信息学中的序列比对和基因识别
  • 语音识别中的声学模型训练
  • 机器翻译中的语言模型训练

3.总结

  • 维特比算法:用于在给定观测序列的情况下找到最可能的隐藏状态序列,适用于解码问题。
  • 鲍姆-韦尔奇算法:用于估计隐马尔可夫模型的参数,适用于模型参数学习。

这两个算法在HMM的应用中各自发挥着重要作用,维特比算法主要用于推断状态序列,而鲍姆-韦尔奇算法用于训练模型。

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-20 14:18:03       142 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-20 14:18:03       156 阅读
  3. 在Django里面运行非项目文件

    2024-07-20 14:18:03       131 阅读
  4. Python语言-面向对象

    2024-07-20 14:18:03       141 阅读

热门阅读

  1. 规范:需求管理规范

    2024-07-20 14:18:03       27 阅读
  2. tmp - configmap动态更新配置?

    2024-07-20 14:18:03       27 阅读
  3. ENSP常见命令及协议命令

    2024-07-20 14:18:03       30 阅读
  4. LeetCode 221. 最大正方形

    2024-07-20 14:18:03       34 阅读
  5. Vue中Key的作用

    2024-07-20 14:18:03       25 阅读
  6. VMware 虚拟机 ping 不通原因排查

    2024-07-20 14:18:03       31 阅读
  7. 数据响应式(Object.defineProperty和Proxy)

    2024-07-20 14:18:03       27 阅读
  8. 云计算的三种服务模式

    2024-07-20 14:18:03       30 阅读
  9. wps的xls文件,如何过滤掉空白没有数据的行

    2024-07-20 14:18:03       28 阅读