Baum-Welch算法

✍ dations ◷ 2025-07-26 16:05:21 #估计理论,算法

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

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

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

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

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

A = { a i j } = P ( X t = j | X t 1 = i ) {\displaystyle A=\{a_{ij}\}=P(X_{t}=j|X_{t-1}=i)}
初始的状态(即 t = 1 {\displaystyle t=1} )分布由下式给出:

π i = P ( X 1 = i ) {\displaystyle \pi _{i}=P(X_{1}=i)}

记观测到的变量为 Y t {\displaystyle Y_{t}} ,总共有 K {\displaystyle K} 种取值。同样假设由隐含变量得到的可观测变量与时间无关。在时间 t {\displaystyle t} ,由隐含变量 X t = j {\displaystyle X_{t}=j} 得到的可观察变量 Y t = y i {\displaystyle Y_{t}=y_{i}} 的概率是:

b j ( y i ) = P ( Y t = y i | X t = j ) {\displaystyle b_{j}(y_{i})=P(Y_{t}=y_{i}|X_{t}=j)}

由所有可能得 X t {\displaystyle X_{t}} Y t {\displaystyle Y_{t}} 的取值,我们可以得到 N × K {\displaystyle N\times K} 的矩阵 B = { b j ( y i ) } {\displaystyle B=\{b_{j}(y_{i})\}} ,其中 b j {\displaystyle b_{j}} 属于所有可能得隐含状态, y i {\displaystyle y_{i}} 属于所有的可观测状态。

给出可观测序列: Y = ( Y 1 = y 1 , Y 2 = y 2 , , Y T = y T ) {\displaystyle Y=(Y_{1}=y_{1},Y_{2}=y_{2},\cdots ,Y_{T}=y_{T})}

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

初始化参数 θ ( A , B , π ) {\displaystyle \theta (A,B,\pi )} ,可以随机初始化,或者根据先验知识初始化。

α i ( t ) = P ( Y 1 = y 1 , Y 2 = y 2 , , Y t = y t , X t = i | θ ) {\displaystyle \alpha _{i}(t)=P(Y_{1}=y_{1},Y_{2}=y_{2},\cdots ,Y_{t}=y_{t},X_{t}=i|\theta )} 是参数 θ {\displaystyle \theta } 的条件下,观测的序列是 y 1 , y 2 , , y t {\displaystyle y_{1},y_{2},\cdots ,y_{t}} ,时刻 t {\displaystyle t} 的状态是 i {\displaystyle i} 的概率。可以通过递归计算:

β i ( t ) = P ( Y t + 1 = y t + 1 , , Y T = y T | X t = i , θ ) {\displaystyle \beta _{i}(t)=P(Y_{t+1}=y_{t+1},\cdots ,Y_{T}=y_{T}|X_{t}=i,\theta )} 是参数是 θ {\displaystyle \theta } ,在时刻 t {\displaystyle t} 的状态是 i {\displaystyle i} 的条件下,余下部分的观测序列是 y t + 1 , , y T {\displaystyle y_{t+1},\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。

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

重新估计 S 1 {\displaystyle S_{1}} S 2 {\displaystyle S_{2}} 的转移概率为 0.22 2.4234 = 0.0908 {\displaystyle {\frac {0.22}{2.4234}}=0.0908} (下表中的"Pseudo probabilities"),重新计算所有的转移概率,得到下面的转移矩阵:

接下来重新估计Emission Matrix:

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

为了估计初始状态的概率,我们分别假设序列的开始状态是 S 1 {\displaystyle S_{1}} S 2 {\displaystyle S_{2}} ,然后求出最大的概率,再归一化之后更新初始状态的概率。

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

相关

  • 酗酒酗酒(英语:alcoholism),又称酒精使用疾患(alcohol use disorder, AUD)或酒精依赖症候群(alcohol dependence syndrome),其为饮用酒精所致相关问题的广义用语,过去将之分成酒精滥用(英语
  • 通用规范汉字表陶文 ‧ 甲骨文 ‧ 金文 ‧ 古文 ‧ 石鼓文籀文 ‧ 鸟虫书 ‧ 篆书(大篆 ‧  小篆)隶书 ‧ 楷书 ‧ 行书 ‧ 草书漆书 ‧  书法 ‧ 飞白书笔画 ‧ 
  • 性腺动脉性腺动脉(gonadal artery)是二组动脉的通称,这两组都是由腹动脉(英语:Abdominal aorta)分支到生殖腺的动脉。具体来说,性腺动脉可以是以下这些动脉:
  • 长崎长崎(日语:ながさき)可能是指:
  • 黎明鸟黎明鸟属(属名:Orienantius,意为“黎明的反鸟类”)是生存于白垩纪早期的小型反鸟类,体长10至13公分,同时具有一对长达15公分的球拍状装饰尾羽。化石发现于中国河北省北部的四岔口
  • 熟悉的陌生人《熟悉的陌生人》(英语:),是一首由澳大利亚/比利时双重国籍歌手高堤耶演唱的歌曲,由高堤耶本人创作并录制,而新西兰歌手/吉他手金贝拉参与了歌曲伴唱。歌曲于2011年7月5日由Eleven
  • 鲁本·丰塞卡何塞·鲁本·丰塞卡(葡萄牙语:José Rubem Fonseca,1925年5月11日-2020年4月15日),巴西作家。1925年丰塞卡出生在巴西米纳斯吉拉斯州茹伊斯迪福拉,但其一生大部分时间都在里约热内
  • 萌学园角色列表《萌学园》系列角色,包括《萌学园之萌骑士传奇》、《萌学园2圣战再起》、《萌学园3魔法号令》、《萌学园4时空战役》、《萌学园5异界对决》、《萌学园6复活之战》等故事角色
  • 绝热不变量绝热不变量,又称浸渐不变量或缓渐不变量,是指一个物理系统中,经过一个缓慢的变化而几乎保持不变的物理量,比如理想气体在绝热过程中的熵。这可以理解为,物理系统从一个状态向另一
  • 比奇特尔公司比奇特尔公司(英语:Bechtel Corporation,又译比奇特尔集团、贝克特尔公司)是美国最大的建筑和工程公司,在美国私营公司中排名第五。总部在旧金山金融区。截至2012年,比奇特尔公司