隐马尔可夫模型：参数估计问题（BaumWelch算法）

HMM的参数估计问题：给定一个观察序列$O = O_{1} O_{2} \cdots O_{T}$O=O1​O2​⋯OT​，计算使$P(O | \mu)$P(O∣μ)最大时，模型$\mu = (\mathbf{A}, \mathbf{B}, \mathbf{\pi})$μ=(A,B,π)的参数

$\hat{\mu} = \argmax_{\mu} P(O_{\text{training}} | \mu)$μ^​=μargmax​P(Otraining​∣μ)

对于完全情况（complete case），产生观察序列$O$O的状态序列$Q = q_{1} q_{2} \cdots q_{T}$Q=q1​q2​⋯qT​已知（完全数据），可通过最大似然估计HMM参数：

$\bar{\pi}_{i} = \delta(q_{1}, s_{i})$πˉi​=δ(q1​,si​)

$\begin{aligned}\bar{a}_{ij} & = \frac{ Q\text{中从状态}s_{i}\text{转移到}s_{j}\text{的次数} }{ Q\text{中所有从状态}s_{i}\text{转移到另一状态（包括}s_{j}\text{自身）的次数} } \\ & = \frac{ \sum_{t = 1}^{T - 1} \delta(q_{t}, s_{i}) \delta(q_{t + 1}, s_{j}) }{ \sum_{t = 1}^{T - 1} \delta(q_{t}, s_{i}) } \end{aligned}$aˉij​​=Q中所有从状态si​转移到另一状态（包括sj​自身）的次数Q中从状态si​转移到sj​的次数​=∑t=1T−1​δ(qt​,si​)∑t=1T−1​δ(qt​,si​)δ(qt+1​,sj​)​​

$\begin{aligned}\bar{b}_{j}(k) & = \frac{ Q\text{中从状态}s_{j}\text{输出符号}v_{k}\text{的次数} }{ Q\text{到达}s_{j}\text{的次数} } \\ & = \frac{ \sum_{t = 1}^{T} \delta(q_{t}, s_{j}) \delta(O_{t}, v_{k}) }{ \sum_{t = 1}^{T} \delta(q_{t}, s_{j}) } \end{aligned}$bˉj​(k)​=Q到达sj​的次数Q中从状态sj​输出符号vk​的次数​=∑t=1T​δ(qt​,sj​)∑t=1T​δ(qt​,sj​)δ(Ot​,vk​)​​

其中，$v_{k}$vk​为HMM输出符号集中的第$k$k个符号。$\delta(x, y)$δ(x,y)为克罗奈克（Kronecker）函数，

$\delta(x, y) = \begin{cases} 1, & x = y \\ 0, & \text{otherwise} \end{cases}$δ(x,y)={1,0,​x=yotherwise​

非完全情况（incomplete case），HMM中的状态序列$Q$Q是无法观察的（隐变量，非完全数据）。

期望最大化（expectation maximization, EM）算法：对含有隐变量的统计模型的参数最大似然估计，其基本思想为：初始时随机地给模型的参数赋值，该赋值遵循模型对参数的限制（例如，从某–状态出发的所有转移概率的和为1），给定模型参数初值后，得到模型$\mu_{0}$μ0​；然后根据$\mu_{0}$μ0​可以得到模型中隐变量的期望值（例如，从$\mu_{0}$μ0​得到从某一状态转移到另一状态的期望次数），用期望值替代方程（6-23）中的实际次数，可以得到模型参数新的估计值，并得到新模型$\mu_{1}$μ1​。根据$\mu_{1}$μ1​，计算模型中隐变量的期望值，然后重新估计模型参数，迭代直至参数收敛于最大似然估计值。这种迭代爬山算法可以使$P(O; \mu)$P(O;μ)局部最大化。

BaumWelch算法（前向后向算法，forward backward algorithm）：EM算法的一种具体实现。给定HMM的参数$\mu$μ和观察序列$O = O_{1} O_{2} \cdots O_{T}$O=O1​O2​⋯OT​，在$t$t时该位于状态$s_{i}$si​、$t + 1$t+1时刻位于状态$s_{j}$sj​的概率$\xi_{t}(i, j) = P(q_{t} = s_{i}, q_{t + 1} = s_{j} | O; \mu)$ξt​(i,j)=P(qt​=si​,qt+1​=sj​∣O;μ)（$1 \leq t \leq T$1≤t≤T、$1 \leq i, j \leq N$1≤i,j≤N）为：

$\begin{aligned} \xi_{t}(i, j) & = \frac{P(q_{t} = s_{i}, q_{t + 1} = s_{j}, O; \mu)}{P(O; \mu)} \\ & = \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} \tag {6-24}$ξt​(i,j)​=P(O;μ)P(qt​=si​,qt+1​=sj​,O;μ)​=∑i=1N​∑j=1N​αt​(i)aij​bj​(Ot+1​)βt+1​(j)αt​(i)aij​bj​(Ot+1​)βt+1​(j)​​(6-24)

给定HMM$\mu$μ和观察序列$O = O_{1} O_{2} \cdots O_{T}$O=O1​O2​⋯OT​，在$t$t时刻位于状态$s_{i}$si​的概率$\gamma_{t}(i)$γt​(i)为

$\gamma_{t}(i) = \sum_{j = 1}^{N} \xi_{t}(i, j) \tag {6-25}$γt​(i)=j=1∑N​ξt​(i,j)(6-25)

因此，$\mu$μ的参数可重新估计为：

$\bar{\pi}_{i} = P(q_{1} = s_{i} | O; \mu) = \gamma_{1}(i) \tag {6-26}$πˉi​=P(q1​=si​∣O;μ)=γ1​(i)(6-26)

$\begin{aligned}\bar{a}_{ij} & = \frac{ Q\text{中从状态}s_{i}\text{转移到}s_{j}\text{的期望次数} }{ Q\text{中所有从状态}s_{i}\text{转移到另一状态（包括}s_{j}\text{自身）的期望次数} } \\ & = \frac{ \sum_{t = 1}^{T - 1} \xi_{t}(i, j) }{ \sum_{t = 1}^{T - 1} \gamma_{t}(i) } \end{aligned} \tag {6-27}$aˉij​​=Q中所有从状态si​转移到另一状态（包括sj​自身）的期望次数Q中从状态si​转移到sj​的期望次数​=∑t=1T−1​γt​(i)∑t=1T−1​ξt​(i,j)​​(6-27)

$\begin{aligned}\bar{b}_{j}(k) & = \frac{ Q\text{中从状态}s_{j}\text{输出符号}v_{k}\text{的期望次数} }{ Q\text{到达}s_{j}\text{的期望次数} } \\ & = \frac{ \sum_{t = 1}^{T} \gamma_{t}(j) \delta(O_{t}, v_{k}) }{ \sum_{t = 1}^{T} \gamma_{t}(j) } \end{aligned} \tag {6-28}$bˉj​(k)​=Q到达sj​的期望次数Q中从状态sj​输出符号vk​的期望次数​=∑t=1T​γt​(j)∑t=1T​γt​(j)δ(Ot​,vk​)​​(6-28)

算法6-4（前向后向算法，forward-backward algorithm）

1. 初始化，随机给参数$\pi_{i}$πi​、$a_{ij}$aij​、$b_{j}(k)$bj​(k)赋值，使其满足如下约束：

$\sum_{i = 1}^{N} \pi_{i} = 1$i=1∑N​πi​=1

$\sum_{j = 1}^{N} a_{i, j} = 1, 1 \leq i \leq N$j=1∑N​ai,j​=1,1≤i≤N

$\sum_{k = 1}^{M} b_{j}(k) = 1, 1 \leq j \leq N$k=1∑M​bj​(k)=1,1≤j≤N

得到模型$\mu_{0}$μ0​。令$i = 0$i=0，执行EM估计。

2. EM计算

E步骤：由模型$\mu_{i}$μi​，根据方程（6-24）、（6-25）计算期望值$\xi_{t}(i, j)$ξt​(i,j)和$\gamma_{t}(i)$γt​(i)；

M步骤：用E步骤得到的期望值，根据方程（6-26）、（6-27）和（6-28）重新估计参数$\pi_{i}$πi​、$a_{ij}$aij​、$b_{j}(k)$bj​(k)的值，得到模型$\mu_{i + 1}$μi+1​。

3. 迭代计算

令$i = i + 1$i=i+1，重复执行EM计算，直到$\pi_{i}$πi​、$a_{ij}$aij​、$b_{j}(k)$bj​(k)收敛。

实际应用中，多个概率连乘会引起的浮点数下溢问题。在Viterbi算法中，由于只涉及乘法运算和求最大值问题，因此可以对概率相乘取对数运算，将乘法运算转变成加法运算，这样一方面避免能浮点数下溢问题，另一方面能提高运算速度。在前向后向算法中，也经常采用对数运算方法判断参数$\pi_{i}$πi​、$a_{ij}$aij​、$b_{j}(k)$bj​(k)是否收敛：

$| \log P(O; \mu_{i + 1}) - \log P(O; \mu_{i}) | \lt \epsilon$∣logP(O;μi+1​)−logP(O;μi​)∣<ϵ

其中，$\epsilon$ϵ为一个足够小的正实数。在前向后向算法中，EM计算包含加法，因此无法采用对数运算。此时，可以设置一个辅助的比例系数，将概率值乘以该比例系数以放大概率值，避免浮点数下溢。在每次迭代结束重新估计参数值时，再将比例系数取消。