在马尔可夫模型中找到两个顶点之间具有最大似然的路径

Question

给定一个马尔可夫模型，它有一个名为 的开始状态S和一个名为的退出状态F，这个模型可以表示为一个有向图，有一些约束：

1. 每条边都有一些权重落在 (0,1] 范围内作为转移概率。

2. 从每个节点出来的边的权重总和为 1。

问题是如何对开始状态和退出状态之间的路径进行排序？或者，更准确地说，如何找出概率最高的路径？

一方面，权重是概率，所以路径越长，乘积越小，所以一种启发式策略是选择较短的路径和较大的权重候选者；但是这个问题可以转化为最短路径问题还是使用一些定制的维特比算法或一些DP算法来解决？

Answer 1

将您的概率转换为对数空间（对数基数无关紧要）。现在路径的概率变成对数空间权重的总和（因为log(ab) = log(a) + log(b)。由于权重/概率<1，对数空间中的权重都将为负，并且路径具有最高权重。

为了将它更多地带入常规问题，您可以否定所有对数空间权重，以便它们都是正数，并且您正在寻找最低的总和。此时，您可以运行标准算法（Dijkstra 会很简单且非常快）来找到您要查找的路径。如果您有总和，则将其取反并计算指数以获得概率。

TL;DR：用 -log(w) 替换所有权重 w 并使用新权重运行 Dijkstra。