鲍姆-韦尔奇算法

在电气工程、计算机科学、统计计算和生物信息学中，鲍姆-韦尔奇算法是用于寻找隐马尔可夫模型未知参数的最大期望算法，它利用前向-后向算法来计算E-Step的统计信息。

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

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

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

记离散的隐含随机变量为${\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 \; -->})$描述隐马尔科夫链，鲍姆-韦尔奇算法寻找${\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}$，然后求出最大的概率，再归一化之后更新初始状态的概率。

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