赞
踩
维特比算法和鲍姆-韦尔奇算法是隐马尔可夫模型(HMM)中的两个重要算法,各自解决不同的问题。
维特比算法用于解码问题,即在给定观测序列的情况下,找到最可能的隐藏状态序列。
维特比算法是一种动态规划算法,通过递归计算最可能的状态序列的概率来找到最佳路径。
维特比算法是一种动态规划算法,用于在隐马尔可夫模型(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(Q∣O,λ)
维特比算法通过最大化联合概率 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(Q∣O,λ)=P(O∣λ)P(Q,O∣λ)
最大化 P ( Q ∣ O , λ ) P(Q | O, \lambda) P(Q∣O,λ)等价于最大化 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(O∣Q,λ)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(O∣Q,λ)=t=1∏Tbqt(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=2∏Taqt−1,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=2∏Taqt−1,qtbqt(Ot)
维特比算法使用动态规划来高效地找到最可能的状态序列。它定义了两个变量:路径概率 δ t ( i ) \delta_t(i) δt(i)和路径指针 ψ t ( i ) \psi_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,…,qt−1maxP(q1,q2,…,qt−1,St=Si,O1,O2,…,Ot∣λ)
ψ 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)=arg1≤j≤Nmax[δt−1(j)aji]
对于每个状态 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),1≤i≤N
ψ 1 ( i ) = 0 \psi_1(i) = 0 ψ1(i)=0
对于每个时间 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)=1≤i≤Nmax[δt−1(i)aij]bj(Ot),2≤t≤T,1≤j≤N
ψ 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)=arg1≤i≤Nmax[δt−1(i)aij],2≤t≤T,1≤j≤N
找到最后一个时刻最优路径的概率:
P ∗ = max 1 ≤ i ≤ N δ T ( i ) P^* = \max_{1 \leq i \leq N} \delta_T(i) P∗=1≤i≤NmaxδT(i)
找到最后一个时刻最优路径的状态:
q T ∗ = arg max 1 ≤ i ≤ N δ T ( i ) q_T^* = \arg\max_{1 \leq i \leq N} \delta_T(i) qT∗=arg1≤i≤NmaxδT(i)
通过路径指针 ψ 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=T−1,T−2,…,1
维特比算法通过以下步骤找到最可能的隐藏状态序列:
维特比算法是一种高效的动态规划算法,可以在 O ( N 2 T ) O(N^2 T) O(N2T) 时间复杂度内解决最优路径问题,其中 N N N是状态数, T T T 是观测序列长度。
维特比算法广泛应用于需要从观测数据中推断隐藏状态序列的场景,如:
鲍姆-韦尔奇算法用于参数学习,即在观测数据的基础上估计隐马尔可夫模型的参数(初始状态概率、状态转移概率和观测概率)。
鲍姆-韦尔奇算法是一种期望最大化(EM)算法,通过迭代优化模型参数来最大化观测数据的似然函数。
假设我们有一个隐马尔可夫模型(HMM),其参数包括:
其中, S t S_t St 是在时间 t t t 的隐藏状态, O t O_t Ot 是在时间 t t t 的观测值。
Baum-Welch算法通过反复执行以下两步来估计参数:期望步(E步)和最大化步(M步)。
首先,为模型参数设定初始值,可以是随机的,也可以基于一些先验知识进行初始化。
在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∣θ)
递推公式如下:
后向算法用于计算在时间 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,…,OT∣St=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=i∣O,θ)=∑j=1Nαt(j)βt(j)αt(i)βt(i)
ξ 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=j∣O,θ)=∑i=1N∑j=1Nαt(i)aijbj(Ot+1)βt+1(j)αt(i)aijbj(Ot+1)βt+1(j)
在M步中,我们使用E步中的计算结果更新参数估计值。
π i = γ 1 ( i ) \pi_i = \gamma_1(i) πi=γ1(i)
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=1T−1γt(i)∑t=1T−1ξt(i,j)
假设观测值是离散的,更新公式为:
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。
重复E步和M步,直到参数收敛(即参数变化小于某个阈值)或达到最大迭代次数。
鲍姆-韦尔奇算法适用于模型参数未知,需要从数据中学习这些参数的情况,如:
这两个算法在HMM的应用中各自发挥着重要作用,维特比算法主要用于推断状态序列,而鲍姆-韦尔奇算法用于训练模型。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。