前后向算法和维特比算法有什么区别?

机器算法验证 算法 隐马尔可夫模型 维特双算法 向前向后
2022-01-18 08:02:38

我想知道在隐马尔可夫模型(HMM)中进行推理的前向后向算法维特比算法之间的区别是什么。

4个回答

先来一点背景知识,也许可以让事情变得更清楚。

在谈论 HMM(隐马尔可夫模型)时,通常需要考虑 3 个问题:

  1. 评价问题

    • 评估问题回答了这个问题:特定模型产生特定符号序列的概率是多少?
    • 对于评估,我们使用两种算法:前向算法后向算法(不要将它们与前向-后向算法混淆)。
  2. 解码问题

    • 解码问题回答了这个问题:给定一个符号序列(你的观察)和一个模型,产生该序列的最可能的状态序列是什么。
    • 对于解码,我们使用Viterbi 算法
  3. 训练问题

    • 训练问题回答了这个问题:给定一个模型结构和一组序列,找到最适合数据的模型。
    • 对于这个问题,我们可以使用以下 3 种算法:
      1. MLE(最大似然估计)
      2. 维特比训练(不要与维特比解码混淆)
      3. Baum Welch = 前后向算法

总而言之,当你在一组序列上训练你的模型时,你使用 Viterbi 算法来解决解码问题和 Baum Welch/Forward-backward。


Baum Welch的工作方式如下。

对于序列训练集中的每个序列。

  1. 使用前向算法计算前向概率
  2. 使用后向算法计算后向概率
  3. 计算当前序列对模型转换的贡献,计算当前序列对模型发射概率的贡献。
  4. 计算新的模型参数(开始概率、转移概率、排放概率)
  5. 计算模型的新对数似然
  6. 当对数似然的变化小于给定阈值或通过最大迭代次数时停止。

如果您需要对 Viterbi 解码方程和训练算法的完整描述,请告诉我,我可以为您指明正确的方向。

Forward-Backward 给出每个单独状态的边际概率,Viterbi 给出最可能的状态序列的概率。例如,如果您的 HMM 任务是预测每天的晴天和雨天,Forward Backward 会告诉您每天“晴天”的概率,Viterbi 会给出晴天/雨天的最可能序列,而这个序列的概率。

我发现 {2} 中的这两张幻灯片非常适合将前后和 Viterbi 算法置于 HMM 使用的所有其他典型算法中:

在此处输入图像描述

在此处输入图像描述

笔记:

  • X是观察到的发射,π是 HMM 的参数。
  • 路径 = 发射序列
  • 解码 = 推理
  • 学习 = 训练 = 参数估计
  • 一些论文(例如,{1})声称 Baum-Welch 与前向-后向算法相同,但我同意 Masterfool 和 Wikipedia 的观点:Baum-Welch 是一种使用前向-后向算法的期望最大化算法。这两个插图也将 Baum-Welch 与前向后向算法区分开来。

参考:

Morat 的回答有一点是错误的:Baum-Welch 是一种期望最大化算法,用于训练 HMM 的参数。在每次迭代期间使用前向后向算法。前向-后向算法实际上只是前向和后向算法的组合:一次向前传递,一次向后传递。就其本身而言,前向后向算法不用于训练 HMM 的参数,而仅用于平滑:计算状态序列的边际似然。

https://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm

https://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm