Baum-Welch算法

在电气工程、计算机科学、统计计算和生物信息学中，Baum-Welch算法是用于寻找隐马尔可夫模型(HMM)未知参数的一种EM算法，它利用前向-后向算法来计算E-Step的统计信息。

Baum-Welch算法是以其发明者Leonard E. Baum和Lloyd R. Welch的名字命名的。Baum-Welch算法和隐马尔可夫模型在20世纪60年代末和70年代初由Baum和他的同事在国防分析研究所的一系列文章中首次描述。HMMs最初主要应用于语音处理领域。20世纪80年代，HMMs开始成为分析生物系统和信息，特别是遗传信息的有用工具。此后，它们成为基因组序列概率建模的重要工具。

隐马尔可夫模型描述了一组“隐含”变量和可观测到的离散随机变量的联合概率。它依赖于假设：第${\displaystyle i}$个隐藏变量只与第${\displaystyle i-<!--\; -\; -->1}$个隐含变量相关，而与其他先前的隐藏变量无关，而当前观测到的状态仅依赖于当前的隐藏状态。

Baum-Welch算法利用EM算法，在给定一组观测特征向量的情况下，求出隐马尔可夫模型参数的最大似然估计。

记离散的隐含随机变量为${\displaystyle X_t}$，它总共有$N$种状态(${\displaystyle X_t}$有${\displaystyle N}$个不同的值)。设${\displaystyle P(X_t|X_{t-<!--\; -\; -->1})}$与时间无关，得到与时间无关的随机变量转移矩阵：

${\displaystyle A=\{a_{ij}\}=P(X_t=j|X_{t-<!--\; -\; -->1}=i)}$
初始的状态(即${\displaystyle t=1}$)分布由下式给出：

${\displaystyle {\mathrm{\pi <!--\; \pi \; -->}}_i=P(X_1=i)}$

记观测到的变量为${\displaystyle Y_t}$，总共有${\displaystyle K}$种取值。同样假设由隐含变量得到的可观测变量与时间无关。在时间${\displaystyle t}$，由隐含变量${\displaystyle X_t=j}$得到的可观察变量${\displaystyle Y_t=y_i}$的概率是:

${\displaystyle b_j(y_i)=P(Y_t=y_i|X_t=j)}$

由所有可能得${\displaystyle X_t}$和${\displaystyle Y_t}$的取值，我们可以得到${\displaystyle N\times <!--\; \times \; -->K}$的矩阵${\displaystyle B=\{b_j(y_i)\}}$，其中${\displaystyle b_j}$属于所有可能得隐含状态，${\displaystyle y_i}$属于所有的可观测状态。

给出可观测序列：${\displaystyle Y=(Y_1=y_1,Y_2=y_2,\cdots <!--\; \cdots \; -->,Y_T=y_T)}$。

我们可以用$\mathrm{\theta <!--\; \theta \; -->}(A,B,\mathrm{\pi <!--\; \pi \; -->})$描述隐马尔科夫链，Baum-Welch算法寻找${\displaystyle {\mathrm{\theta <!--\; \theta \; -->}}^{\ast <!--\; \ast \; -->}=\arg <!--\; \; -->\underset{\mathrm{\theta <!--\; \theta \; -->}}{max}P(Y|\mathrm{\theta <!--\; \theta \; -->})}$的局部极大值，也就是能够使得观测到的序列出现的概率最大的HMM的参数${\displaystyle \mathrm{\theta <!--\; \theta \; -->}}$。

初始化参数${\displaystyle \mathrm{\theta <!--\; \theta \; -->}(A,B,\mathrm{\pi <!--\; \pi \; -->})}$，可以随机初始化，或者根据先验知识初始化。

记${\displaystyle {\mathrm{\alpha <!--\; \alpha \; -->}}_i(t)=P(Y_1=y_1,Y_2=y_2,\cdots <!--\; \cdots \; -->,Y_t=y_t,X_t=i|\mathrm{\theta <!--\; \theta \; -->})}$是参数${\displaystyle \mathrm{\theta <!--\; \theta \; -->}}$的条件下，观测的序列是${\displaystyle y_1,y_2,\cdots <!--\; \cdots \; -->,y_t}$，时刻${\displaystyle t}$的状态是${\displaystyle i}$的概率。可以通过递归计算：

记${\displaystyle {\mathrm{\beta <!--\; \beta \; -->}}_i(t)=P(Y_{t+1}=y_{t+1},\cdots <!--\; \cdots \; -->,Y_T=y_T|X_t=i,\mathrm{\theta <!--\; \theta \; -->})}$是参数是${\displaystyle \mathrm{\theta <!--\; \theta \; -->}}$，在时刻${\displaystyle t}$的状态是${\displaystyle i}$的条件下，余下部分的观测序列是${\displaystyle y_{t+1},\cdots <!--\; \cdots \; -->,y_T}$的概率。

假设我们有一只会下蛋的鸡，每天中午我们都会去拾取鸡蛋。而鸡是否下蛋依赖于一些未知的隐含状态，这里我们简单的假设只有两种隐含状态会决定它是否下蛋。我们不知道这些隐含状态的初始值，不知道他们之间的转换概率，也不知道在每种状态下鸡会下蛋的概率。我们随机初始化他们来开始猜测。

假设我们得到的观测序列是(E=eggs, N=no eggs): N, N, N, N, N, E, E, N, N, N。

这样我们同时也得到了观测状态的转移：NN, NN, NN, NN, NE, EE, EN, NN, NN。

通过上面的信息来重新估计状态转移矩阵。

重新估计${\displaystyle S_1}$到${\displaystyle S_2}$的转移概率为${\displaystyle \frac{0.22}{2.4234}=0.0908}$(下表中的"Pseudo probabilities")，重新计算所有的转移概率，得到下面的转移矩阵：

接下来重新估计Emission Matrix:

重新估计从隐含状态${\displaystyle S_1}$得到观察结果E的概率是${\displaystyle \frac{0.2394}{0.2730}=0.8769}$，得到新的Emission Matrix

为了估计初始状态的概率，我们分别假设序列的开始状态是${\displaystyle S_1}$和${\displaystyle S_2}$，然后求出最大的概率，再归一化之后更新初始状态的概率。

一直重复上面的步骤，直到收敛。