前向算法

✍ dations ◷ 2025-04-04 04:50:11 #自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})} 最大化的状态序列。

相关

  • 内湖科技园区内湖科技园区,简称内科,于台湾台北市内湖区西侧,是台湾第一座由民间投资及政府放宽产业进驻而发展出来的科学园区。最北与最西位于在堤顶大道上段(二段)与内湖路一段的交界处,最南
  • 异性恋异性恋亦称为异性向,一般指对异性(包括生理性别及性别认同为当事人的异性)能产生爱慕感、建立浪漫关系,或认为异性拥有性吸引力的一种现象。把异性恋视作性倾向时,其定义则为“一
  • 超级名模超级模特(英文:Supermodel),俗称超级名模,简称超模,顾名思义,指的是模特行业中的超级成功者。超级模特这个名词开始广泛的被使用始于1980年代,要获得此头衔者,最基本必须是业内公认权
  • 安妮特·班宁安妮特·卡洛儿·贝宁(英语:Annette Carol Bening,1958年5月29日-),是一位美国女演员,出生于堪萨斯州的托皮卡。小学时就在学校参与出演话剧。高中毕业前一年便考入旧金山州立大学
  • 华盛顿州立大学华盛顿州立大学(英文:Washington State University、简称WSU)是美国华盛顿州资助办理的一所研究型大学,也是该州的赠地大学。它的主校位于华盛顿州东部的普尔曼,而在斯波坎、三城
  • 汤普金斯广场公园汤普金斯广场公园(Tompkins Square Park)是美国纽约市的一个公园,面积10.5-英亩(4.2-公顷),位于曼哈顿东村字母城。这是一个方形的公园,北到东10街,东到B大道,南面是东7街,西到A大道。
  • 夏威夷野鸟夏威夷在世界动物地理分区上属于大洋区,约有300种鸟类被记录。由于与其他大陆的隔离,因此有许多特有种鸟类。夏威夷约有71种特有种或特有亚种被记录,其中23种已绝种,余下的48种
  • 北黎凡特方言黎凡特阿拉伯语(اللهجة الشامية),也叫东部阿拉伯语,是在黎凡特地区广泛使用的一种阿拉伯语变体。它是五种(一说六种)主要的阿拉伯语变体之一。与其他地方的阿拉伯语
  • 马里纳·斯托达德·埃克尔斯马里纳·斯托达德·埃克尔斯(Marriner Stoddard Eccles,1890年9月9日 - 1977年12月18日),生于犹他州洛根市,美国银行家、经济学家,曾任美国联邦准备理事会主席(1934年-1948年)。而19
  • 2019冠状病毒病卡塔尔疫情2019冠状病毒病卡塔尔疫情,介绍在2019新型冠状病毒疫情中,在卡塔尔发生的情况。2020年2月27日,一批卡塔尔公民搭乘一架私人飞机由伊朗撤回国内。2月29日,卡塔尔确诊首例新冠肺