加权自动机的对数半环中的最短距离
我以为我已经弄清楚了......但我仍然无法理解它。 我正在玩 OpenFst 并试图弄清楚如何在“对数”半环中计算“最短距离”。 对于以下小自动机，
https://i.sstatic.net/9j2Yf.png
结果‘shortestdistance’命令的值为，
$ fstshortestdistance log.fst
0 0
1 -0.510825634
2 -2.60798359
3 -0.9162907
并且日志中最短距离的描述为，
使用对数半环，计算 q 的路径权重的（对数）总和。
我觉得很愚蠢，但我无法弄清楚到底发生了什么才能达到最终的 -2.6。我已经尝试了我能想到的对数和普通和的每一种变体，即使是那些看起来不应该适用的变体，但没有任何结果是-2.6。现在它开始让我发疯了。
在这种情况下，我的直觉是应该将两个不同字符串（bc，bd）中每一个的总路径概率相加，然后返回最佳概率。 (bc) 有两条路径，它们的概率总和为 2/3（非对数）。 (bd) 路径的概率为 1/3。然而，这绝对不是正在发生的事情，那么到底发生了什么呢？
I thought I'd figured this out... but I still cannot wrap my head around it.
I'm playing with OpenFst and trying to figure out how 'shortestdistance' is calculated in the 'log' semiring.
For the following little automaton,
https://i.sstatic.net/9j2Yf.png
The result of the 'shortestdistance' command is,
$ fstshortestdistance log.fst
0 0
1 -0.510825634
2 -2.60798359
3 -0.9162907
and the description for shortestdistance in log is given as,
With the log semiring, the (log) sum of path weights to q is computed.
I feel pretty dumb but I cannot figure out what is actually happening to arrive at the final -2.6. I've tried every variation of the logsum and ordinary sum that I can think of, even ones that seem like they shouldn't apply, but nothing yields -2.6. It's starting to drive me crazy now.
My intuition in this case is that the total path probabilities for each of the two distinct strings (bc, bd) should be summed, and then the best probability should be returned. There are two paths for (bc) and their probabilities sum to 2/3 (non-log). The (bd) path has probability 1/3. However, this is definitely not what is happening, so what is happening?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
对数半环中两个值“x”和“y”的对数和定义为：
和对数半环中的最短距离应该计算与您定义的自动机相关的总似然。路径输出字符串不相关，但存在三个不同的路径，具有以下关联的路径权重：
如果我们根据得到的对数和对 x、y 和 z 求和，
这是 OpenFst 将产生的结果。我猜你忘记了那些讨厌的负面信号。
The logsum of two values, 'x' and 'y' in the log semiring is defined as,
and the shortest-distance in the log semiring should compute the total likelihood associated with the automaton you've defined. The path output strings aren't relevant, but there are three distinct paths with the following associated path weights:
If we sum x, y and z according to the logsum we get,
Which is what OpenFst will produce. My guess is that you forgot the pesky negative signs.