前向算法

✍ dations ◷ 2025-06-29 17:54:19 #自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})} 最大化的状态序列。

相关

  • 驯化物种驯化(英语:Domestication)是指一种生物的成长与生殖逐渐受另一种生物利用与掌控的过程,例如人类栽培各种农作物、畜牧,以及切叶蚁驯养真菌。人类驯化动植物的目的主要包括作为食
  • 苗瑶语族苗瑶语是苗、瑶、畲等族群所使用的有共同来源的一些语言的总称。学术界对于苗瑶语的语言系属分类有不同看法:华人和中国学者多认为苗瑶语是属于汉藏语系的语族,即苗瑶语族;欧美
  • 教职员教师(英语:Teachers,中文口语也常称作“老师”,旧称“先生”),又称作教育工作者、教员,是大众对教育从业者的称呼,是培养社会所需人才的专业。于教育机构;因应社会需要,亦有家庭教师的
  • 180110 数学 120 信息科学与系统科学 130 力学 140 物理学 150 化学 160 天文学 170 地球科学 180 生物学210 农学 220 林学 230 畜牧、兽医科学 240 水产学310 
  • 加拿大银行加拿大银行(英语:Bank of Canada)是加拿大的中央银行,其依据1934年的《加拿大银行法案》(英语:Bank of Canada Act)而建立。它自身定位为一家非商业银行,不向公众提供银行服务,而是专
  • ProPublicaProPublica成立于2007年,为一间总部设在纽约市曼哈顿区的非盈利性公司,自称是一个独立的非盈利新闻编辑部,为公众利益进行调查报导。ProPublica的记者与多间新闻机构一同合作进
  • 搞笑诺贝尔搞笑诺贝尔奖(英语:Ig Nobel Prizes),又名幽默诺贝尔奖,是对诺贝尔奖的有趣模仿。获奖成就“低俗、下流;却又是一种社会批评,讽刺地揭露出荒谬的现象;并且是有用的研究和知识。”搞
  • 刘 斌刘斌可以指:
  • 佩尔布洛索姆佩尔布洛索姆(英语:Pearblossom)是位于美国加利福尼亚州洛杉矶县的一个非建制地区。该地的面积和人口皆未知。佩尔布洛索姆的座标为34°30′23″N 117°54′32″W / 34.50639°
  • 分布守恒一个物体产生的影响在物体影响产生的“面”上与该面影响的强度乘积为定值,即∑(定距离影响效应×影响面面积)= 定值同一电荷的不同等势面上的电场强度与面积乘积相等即∑Si*xi