隐马尔可夫模型的计算

标签：模式分类

@author lancelot-vim

约定一些新的术语，并且将重新整理记号系统。通常把隐马尔可夫模型图称为有限状态机(finite state machine, FSM)，如果网络内部得转移都和概率相关，那么这样得网络叫做马尔可夫网络。这种网络是严格符合因果关系的，因为下一时刻状态的概率，之和上一时刻状态有关，如果只要选择好相应得合适得初始状态，每个特定得状态发生得概率都非0,那么这个马尔可夫模型就被成为”各态历经”的。最终状态或者吸收状态(final state or absorbing state)只系统一旦进入这个状态，就无法里还的情况(比如 a00=1 ,则系统永远处于初始状态)

前文提到，用 aij 来表示隐状态之间得转移概率，用 bjk 表示发出可见状态得概率：

aij=P(wj(t+1)|wi(t))

bjk=P(vk(t)|wj(t))

我们要求在每一时刻都必须准备好转移到下一时刻，同时要发出一个可见的符号，这样有归一化条件:

$\sum j a i j = 1 \sum k b j k = 1$

定义了这些术语后，使得我们可以关注下列3个隐马尔可夫模型得核心问题：

估值问题：假设我们有一个HMM,其转移概率 aij 和 bjk 已知，计算这个模型某一特定观测序列 VT 得概率

解码问题：假设我们已有一个HMM，和一个观测序列，决定最有可能产生这个观测序列得隐形状态序列 wT

学习问题：假设我们知道一个HMM的大致结构（隐形状态参数数量、可见参数数量）如何从观测中得到 aij和bjk

估值问题

一个模型产生可见序列 VT 得概率为： P(VT)=∑r=1rmaxP(VT|wTr)P(wTr)
其中的r是每个特定长T的隐状态序列得下标: wTr={w(1),w(2), ... ,w(T)} , 在c个不同隐状态下的情况下，为了计算这个特定可见状态序列 VT 得概率，我们必须考虑每一种可能得隐状态序列，计算它们各自产生可见状态序列 VT 的概率，然后进行相加，所以序列概率就是对应得转移概率 aij 和产生可见符号概率 bjk 的乘积。

由于这里处理的是一阶马尔可夫过程，所以公式可以写为: P(wTr)=∏t=1TP(w(t)|w(t−1)) ,也就是序列中的转移概率依次相乘，在上式中， w(T)=w0 为最终的吸收概率，其产生的唯一得独特可见符号为 v0 ，在语音识别中， w0 往往代表一个空状态，或者没有发声音的状态，符号 v0 就表示静音

由于已经假设可见符号的概率只依赖于这个时刻所处得隐状态，因此， P(VT|wTr)=∏t=1TP((v(t)|w(t)) ,也就是把 bjk 依次相乘，最终，我们可以得到:

$P (V T) = \sum r = 1 r m a x \prod t = 1 T P (v (t) | w (t)) P (w (t) | w (t - 1))$

按照这个算法，时间复杂度为 O(cTT) ，假如c = 10, T = 20，可见，几乎是无法实现的，实际上有个可行得代替方案，递归计算 P(VT) ,由于每一项 P(v(t)|w(t))P(w(t)|w(t−1)) 只涉及到 v(t),w(t)和w(t−1) ，我们定义：

$α i (t) = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ 01 \sum i α i (t - 1) a i j b j k v (t) t = 0 且 j \neq 初始状态 t = 0 且 j = 初始状态其他$

其中 bjkv(t) 表示t时刻的可见状态 v(t) 确定的转移概率 bjk , 因此，只需要对具有可见状态 v(t) 得索引k得项求和即可， α(t) 表示我们的HMM在t时刻，位于隐状态 wj ，并且已经产生了可见序列 VT 的前t个符号的概率。

HMM向前算法

initialize t <- 0, aij,bjk,VT,αj(0)=1

repeat t <- t+1

aj(t) <- bjkv(t)∑t=1cαi(t−1)aij

until t = T

return P(VT) <- 最终状态得 a0(T)

end

算法示意图：

隐马尔可夫模型的计算

这个算法的时间复杂度为 O(c2T) ，在实际应用中使用特别广泛

一个小例子
隐马尔可夫模型的计算

如图所示的HMM，他具有一个明确得吸收状态和唯一的独特空可见符号 v0 ，转移矩阵如下：

a = ⎛ ⎝ ⎜ ⎜ ⎜ 1 0.2 0.2 0.8 0 0.3 0.5 0.1 0 0.1 0.2 0.0 0 0.4 0.1 0.1 ⎞ ⎠ ⎟ ⎟ ⎟

b = ⎛ ⎝ ⎜ ⎜ ⎜ 1000 0 0.3 0.1 0.5 0 0.4 0.1 0.2 0 0.1 0.7 0.1 0 0.2 0.1 0.2 ⎞ ⎠ ⎟ ⎟ ⎟

计算观测序列为: V4={v1,v2,v2,v0} 的概率

如下图所示，假设在t=0时刻，系统的隐状态为 w1 ，每一步的可见符号为第一行， αi(t) 的数值在圆圈中已经表示出， aijbjk 按照步骤t=1到t=2已经标出
隐马尔可夫模型的计算

解码问题

所谓解码问题，就是已知观测序列 VT ，求解最可能得隐状态序列得过程，算法如下：

HMM解码算法

begin initialize Path <- {}, t = 0

repeat t <- t + 1

j <- 1

repeat j <- j + 1

αj(t) <- bjkv(t)∑i=1cαi(t−1)aij

until j == c

j’ <- argmax αj(t)

将 wj 添加到Path

until t = T

return Path

end

解码算法是一个贪心的策略，每次选择当前概率最大的 αj 为最优策略，这个可能导致无法达到全局最优解，甚至可能会出现一些无法存在得错解。

学习问题

学习问题是根据观察值(或者说训练样本)确定转移概率 ajk和bjk ，到目前为止，还没有能够根据训练样本确定最优参数集合的方法，但是，通过一种非常直接的方法，我们几乎总能得到一个足够令人满意的解答

向前-向后算法

我们定义 βi(t) 为在t时刻位于状态 wi(T) ，并且将产生t时刻之后的目标序列的概率(时间范围为t+1->T):

$β i (t) = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ 01 \sum j β j (t + 1) a i j b j k v (t + 1) w i (t) \neq w 0 且 t = T w i (t) = w 0 i 且 t = T 其他$

定义从状态 wi(t−1) 转移到 wi(t) 的条件概率为 γij(t)

$γ i j (t) = α i ( t - 1 ) a i j b j k β j ( t ) P ( V T | θ )$

分子代表：产生 VT 中前t-1个状态和后t个状态时，从t-1状态由 wi(t−1) 转换到 wj(t) 的概率
分母代表： P(VT|θ) 是模型产生可见序列 VT 的概率
γij 代表：在模型产生 VT 序列时，状态 wi(t−1) 转移到w(t)的概率

由此可得：
1. 在任意时刻，状态 wi 到状态 wj 的转换预计值为: ∑t=1Tγij(t)
2. 在任意时刻，状态 wi 发生转换概率预计值为: ∑t=1T∑kγik(t)
3. 在任意时刻，状态 wi 到状态 wj 的转换后，观测值为 vk 的预计值为: ∑i=1T∑l,v(t)=vkγjl(t)
4. 在任意时刻，状态 wi 到状态 wj 的转换后,得到所有观测预计值为 ∑i=1T∑lγjl(t)

所以，得到 a^ij，b^jk 为:

$a^i j = \sum t = 1 T γ i j ( t ) \sum t = 1 T \sum k γ i k ( t ) (1) b^j k = \sum i = 1 T \sum l , v ( t ) = v k γ j l ( t ) \sum i = 1 T \sum l γ j l ( t ) (2)$

有了这两个估计值，我们可以通过大量样本，是用以上公式对模型逐步更新，直到收敛为止，这就是著名的Baum-Welch算法：

Baum-Welch算法(向前向后算法)

begin initialize aij,bjk ,训练样本 VT ,收敛判据 θ , z <- 0

do z <- z + 1

通过a(z-1),b(z-1)，由(1)计算 a^(z)

通过a(z-1),b(z-1)，由(2)计算 b^(z)

aij(z) <- a^ij(z−1)

bij(z) <- b^ij(z−1)

until max[ aij(z)−aij(z−1),bjk(z)−bjk(z−1) ]

return aij <- aij(z) , bjk <- bjk(z)

end

秒客网

隐马尔可夫模型的计算

隐马尔可夫模型的计算

估值问题

HMM向前算法

算法示意图：

解码问题

HMM解码算法

学习问题

向前-向后算法

Baum-Welch算法(向前向后算法)

相关文章