我想知道在隐马尔可夫模型(HMM)中进行推理的前向后向算法和维特比算法之间的区别是什么。
前后向算法和维特比算法有什么区别?
机器算法验证
算法
隐马尔可夫模型
维特双算法
向前向后
2022-01-18 08:02:38
4个回答
先来一点背景知识,也许可以让事情变得更清楚。
在谈论 HMM(隐马尔可夫模型)时,通常需要考虑 3 个问题:
评价问题
- 评估问题回答了这个问题:特定模型产生特定符号序列的概率是多少?
- 对于评估,我们使用两种算法:前向算法或后向算法(不要将它们与前向-后向算法混淆)。
解码问题
- 解码问题回答了这个问题:给定一个符号序列(你的观察)和一个模型,产生该序列的最可能的状态序列是什么。
- 对于解码,我们使用Viterbi 算法。
训练问题
- 训练问题回答了这个问题:给定一个模型结构和一组序列,找到最适合数据的模型。
- 对于这个问题,我们可以使用以下 3 种算法:
- MLE(最大似然估计)
- 维特比训练(不要与维特比解码混淆)
- Baum Welch = 前后向算法
总而言之,当你在一组序列上训练你的模型时,你使用 Viterbi 算法来解决解码问题和 Baum Welch/Forward-backward。
Baum Welch的工作方式如下。
对于序列训练集中的每个序列。
- 使用前向算法计算前向概率
- 使用后向算法计算后向概率
- 计算当前序列对模型转换的贡献,计算当前序列对模型发射概率的贡献。
- 计算新的模型参数(开始概率、转移概率、排放概率)
- 计算模型的新对数似然
- 当对数似然的变化小于给定阈值或通过最大迭代次数时停止。
如果您需要对 Viterbi 解码方程和训练算法的完整描述,请告诉我,我可以为您指明正确的方向。
Forward-Backward 给出每个单独状态的边际概率,Viterbi 给出最可能的状态序列的概率。例如,如果您的 HMM 任务是预测每天的晴天和雨天,Forward Backward 会告诉您每天“晴天”的概率,Viterbi 会给出晴天/雨天的最可能序列,而这个序列的概率。
我发现 {2} 中的这两张幻灯片非常适合将前后和 Viterbi 算法置于 HMM 使用的所有其他典型算法中:
笔记:
- 是观察到的发射,是 HMM 的参数。
- 路径 = 发射序列
- 解码 = 推理
- 学习 = 训练 = 参数估计
- 一些论文(例如,{1})声称 Baum-Welch 与前向-后向算法相同,但我同意 Masterfool 和 Wikipedia 的观点:Baum-Welch 是一种使用前向-后向算法的期望最大化算法。这两个插图也将 Baum-Welch 与前向后向算法区分开来。
参考:
- {1} Lember、Jüri 和 Alexey Koloydenko。“隐藏马尔可夫模型的调整维特比训练。” 伯努利 14,没有。1 (2008): 180-206。
- {2} 6.047/6.878 计算生物学:基因组、网络、进化(2012 年秋季)第 7 讲 - HMMs II(2012-09-29)http://stellar.mit.edu/S/course/6/fa12/6.047/ courseMaterial/topics/topic2/lectureNotes/Lecture07_HMMsIIb_6up/Lecture07_HMMsIIb_6up.pdf(Manolis Kellis):
Morat 的回答有一点是错误的:Baum-Welch 是一种期望最大化算法,用于训练 HMM 的参数。它在每次迭代期间使用前向后向算法。前向-后向算法实际上只是前向和后向算法的组合:一次向前传递,一次向后传递。就其本身而言,前向后向算法不用于训练 HMM 的参数,而仅用于平滑:计算状态序列的边际似然。
https://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm
其它你可能感兴趣的问题