2

我以为我已经弄清楚了……但我仍然无法理解它。我正在玩 OpenFst 并试图弄清楚如何在“对数”半环中计算“最短距离”。对于下面的小自动机，

http://i.imgur.com/FThh6.png

“shortestdistance”命令的结果是，

$ fstshortestdistance log.fst
0   0
1   -0.510825634
2   -2.60798359
3   -0.9162907

并且日志中最短距离的描述为，

使用对数半环，计算到 q 的路径权重的 (log) 和。

我觉得自己很愚蠢，但我无法弄清楚最终 -2.6 到底发生了什么。我已经尝试了我能想到的对数和普通和的所有变体，即使是那些看起来不应该适用的变体，但没有任何结果产生-2.6。现在开始让我发疯了。

在这种情况下，我的直觉是两个不同字符串（bc，bd）中每一个的总路径概率应该相加，然后应该返回最佳概率。(bc) 有两条路径，它们的概率总和为 2/3（非对数）。(bd) 路径的概率为 1/3。但是，这绝对不是正在发生的事情，那么发生了什么？

4

1 回答 1

1

对数半环中两个值“x”和“y”的对数和定义为，

-log(exp(-x) + exp(-y))

并且对数半环中的最短距离应该计算与您定义的自动机相关的总可能性。路径输出字符串不相关，但存在三个具有以下关联路径权重的不同路径：

x = (0,1,2):-.51083

y = (0,3,2):-1.2729 = -.91629 + -.35667

z = (0,3,2):-2.1202 = -.91629 + -1.204

如果我们根据得到的 logsum 对 x、y 和 z 求和，

-log( exp(-x) + exp(-y) + exp(-z) ) = -2.607

这就是 OpenFst 将产生的结果。我的猜测是你忘记了讨厌的负面迹象。

于 2012-01-31T15:29:53.663 回答