Кратчайшее расстояние в логарифмическом полукольце для взвешенного автомата

Я думал, что понял это... но я до сих пор не могу понять это. Я играю с OpenFst и пытаюсь понять, как вычисляется «кратчайшее расстояние» в полукольце «журнал». Для следующего маленького автомата

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

Результат команды «кратчайшее расстояние»:

$ 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. Однако это определенно не то, что происходит, так что происходит?


shortest-path automata
person Community    schedule 31.01.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Логарифмическая сумма двух значений «x» и «y» в логарифмическом полукольце определяется как

-log( ехр(-х) + ехр(-у))

и кратчайшее расстояние в логарифмическом полукольце должно вычислять общую вероятность, связанную с определенным вами автоматом. Выходные строки пути не имеют значения, но есть три различных пути со следующими связанными весами пути:

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

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

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

Если мы суммируем x, y и z в соответствии с полученной логарифмической суммой,

-log( exp(-x) + exp(-y) + exp(-z)) = -2,607

Что и будет производить OpenFst. Я предполагаю, что вы забыли надоедливые отрицательные знаки.

person si28719e    schedule 31.01.2012