前向算法

✍ dations ◷ 2025-04-03 17:13:00 #自March 2015需要进一步厘清的条目,马尔可夫模型

前向算法(Forward algorithm),在隐马尔可夫模型(HMM)中,是用于计算“置信状态”的。置信状态指根据既往证据推算出的当前状态的概率分布。这个过程也被叫做“滤波”。前向算法和维特比算法紧密相关但又互不相同。

前向算法是用来解决解码问题的算法之一。自从语音识别技术和模式识别技术发展以来,它也越来越普遍地被用在像计算生物学这样的使用HMM的领域内。

整个算法的目标是计算联合概率分布 p ( x t , y 1 : t ) {\displaystyle p(x_{t},y_{1:t})} 。为了方便,我们把 x ( t ) {\displaystyle x(t)} 简写做 x t {\displaystyle x_{t}} ,将 ( y ( 1 ) , y ( 2 ) , . . . , y ( t ) ) {\displaystyle (y(1),y(2),...,y(t))} 简写做 y 1 : t {\displaystyle y_{1:t}} 。直接计算 p ( x t , y 1 : t ) {\displaystyle p(x_{t},y_{1:t})} 则需要计算所有状态序列 { x 1 : t 1 } {\displaystyle \{x_{1:t-1}\}} 的边缘分布,而它的数量和 t {\displaystyle t} 成指数相关。使用这一算法,我们可以利用HMM的条件独立性质,递归地进行计算。

我们令

利用链式法则来展开 p ( x t , x t 1 , y 1 : t ) {\displaystyle p(x_{t},x_{t-1},y_{1:t})} ,我们可以得到

由于 y t {\displaystyle y_{t}} 和除了 x t {\displaystyle x_{t}} 之外的一切都条件独立,而 x t {\displaystyle x_{t}} 又和 x t 1 {\displaystyle x_{t-1}} 之外的一切都条件独立,因此

这样,由于 p ( y t | x t ) {\displaystyle p(y_{t}|x_{t})} p ( x t | x t 1 ) {\displaystyle p(x_{t}|x_{t-1})} 由HMM的输出概率和状态转移概率我们可以很快计算用 α t 1 ( x t 1 ) {\displaystyle \alpha _{t-1}(x_{t-1})} 计算出 α t ( x t ) {\displaystyle \alpha _{t}(x_{t})} ,并且可以避免递归计算。

前向算法可以很容易地被修改来适应其他的HMM变种,比如马尔可夫跳跃线性系统。

为了能够使用“未来的历史”(比如我们在试图预测过去的某个时点的状态),我们可以运行后向算法,它是前向算法的一个补充。这一操作被称为平滑。 前向-后向算法对 1 < k < t {\displaystyle 1<k<t} 计算 P ( x k | y 1 : t ) {\displaystyle P(x_{k}|y_{1:t})} ,因此使用了过去和未来的全部信息。

为了解码最可能的序列,需要使用维特比算法。它会从过去的观测中试图推测最可能的状态序列,也即使 P ( x 0 : t | y 0 : t ) {\displaystyle P(x_{0:t}|y_{0:t})} 最大化的状态序列。

相关

  • 排尿疼痛排尿疼痛、尿痛(英语:dysuria)是指在排尿过程中出现的疼痛现象,是与膀胱有关的症状(有时也作“下泌尿道症状”)。患者通常会形容排尿疼痛为“刺痛、灼烧、瘙痒”的感觉。该症状通
  • X-三体综合征 (47,XXX)三染色体X综合征是一种人类女性的性染色体疾病;一般女性的性染色体是XX,而患者为XXX。患有该综合征的患者又因其基因行为XXX,被称做超雌性。与XYY三体患者不同的是,三染色体X综
  • Chemical Physics Letters《化学物理通讯》(Chemical Physics Letters)是一个同行评议的学术期刊,主要内容是化学物理。该期刊创建于1967年,出版商为爱思唯尔。现任主编是David Clary(英语:David Clary)、M.
  • 灭菌剂杀菌(Sterilization),又称作灭菌,与消毒(disinfection)近似,但更追求移除或消灭物体表面、液体、药物、培养介质上的任何形式微生物及传播性病原体(如真菌、细菌、病毒、芽孢等)。适
  • 古城古城区是中华人民共和国云南省丽江市下属的市辖区。下辖: 西安街道、大研街道、祥和街道、束河街道、金山街道、开南街道、文化街道、金安镇、七河镇、大东乡和金江白族乡。
  • 约翰·亨利·坡印廷约翰·亨利·坡印亭(英语:John Henry Poynting,FRS,1852年9月9日-1914年3月30日),英国物理学家。1880年至1900年担任梅森科学学院物理学教授,之后担任伯明翰大学教授直至去世。坡印
  • 晶晶书库晶晶书库是1999年1月1日创立于台湾台北市的LGBT主题书店,采合伙事业型态经营。是华人地区第一家同性恋主题书店。长期参与台湾同志游行,争取台湾同志权益,是台湾同志运动的重要
  • 撒娇撒娇又叫嗲、卖萌,粤语叫诈娇,是一种可爱的情感表示,具有吸引眼球的效应,包括但不限于通过可爱的声音/娃娃音、面部表情和手势表达。“撒娇”字面上指一种娇媚的表现,亚洲年轻男
  • ICAO代码国际民航组织机场代码(International Civil Aviation Organization Airport Code,缩写:ICAO code),是国际民航组织为世界上所有机场所订定的识别代码,由4个英文字母组成。ICAO机场
  • 计算机逻辑计算机逻辑描述应用于计算机科学和人工智能的逻辑。它包括:基本数理逻辑比如命题逻辑和谓词逻辑(通常联合上集合论)的研究被认为是对任何大学计算机科学课程都非常重要的理论基