前向算法

✍ dations ◷ 2025-06-08 09:57:38 #自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})} 最大化的状态序列。

相关

  • 后工业化后工业社会是社会科学名词,指涉开始自1960年代的工业社会转型出现的社会现象,该词最早出自法国社会学家阿兰·图赖讷,后由美国社会学家丹尼尔·贝尔的著作《后工业社会的来临》
  • 有限集合数学中,一个集合被称为有限集合,简单来说就是元素个数有限,严格而言则是指有一个自然数n使该集合与集合 { 1 , 2 ,
  • 雪莉·安·杰克逊雪莉·安·杰克逊(英语:Shirley Ann Jackson,1946年8月5日-),美国物理学家,壬色列理工学院第 18 届院长,曾任总统情报顾问委员会(英语:President's Intelligence Advisory Board)(英语:Pr
  • 检测2019冠状病毒病检测(英语:COVID-19 testing)是通过核酸或抗体等分子检测(英语:Molecular diagnostics)手段及CT断层成像等临床辅助手段,对人体是否感染2019冠状病毒或患有2019冠状
  • 统一资源标志符统一资源标识符(英语:Uniform Resource Identifier,缩写:URI)在电脑术语中是一个用于标识某一互联网资源名称的字符串。该种标识允许用户对网络中(一般指万维网)的资源通过特定的协
  • 美廉社三商家购股份有限公司(简称:美廉社连锁折扣店,英语:Simple Mart)是三商行经营的台湾零售商,成立于2006年。商品陈列采用类似量贩店的大型货架式,但以小店面的经营方式深入各地住宅
  • 亚洲武艺运动会亚洲武艺运动会是亚洲一个以武术为主题构想的新兴综合性运动会,每隔四年举行一届。武术项目于1990年被引入亚洲运动会的示范项目,并于2002年的釜山亚运会成为列为竞赛项目。20
  • 帕萨迪纳市立学院帕萨迪纳市立学院(Pasadena City College,简称PCC)是一所位于美国的社区学院。位于加州洛杉矶东北部的帕萨迪纳。该校创建于1924年,共有学生24,932名。校长为Dr. Paulette J.
  • 总书记总书记或第一书记是政党的党务或政治领导职位,以共产党、劳动党、社会党和其他左翼政党较多使用。一些政党同时有主席和总书记(第一书记)的职位,两者的职权区分在各个政党中各有
  • 迈阿密热火队迈阿密热火(英语:Miami Heat),是一支位于美国佛罗里达州迈阿密的NBA篮球队,分属于东部的东南赛区,主场为美国航空球场。球队成立于1988年,在2006年、2012年和2013年获得NBA总冠军。