Попытка понять алгоритм VITERBI немного лучше

Question

В настоящее время я пытаюсь реализовать алгоритм viterbi в python, а точнее версию, представленную в онлайн-курсе.

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

Мы предполагаем, что тег K-1 = тег K-2 = '*', то при к идущей от 0 до K, мы устанавливаем тег для маркера следующим образом: тегов (WORD_k) = Argmax (р (k-1, tag_k-2, tag_k-1) * e (word_k, tag_k) * q (tag_k, tag_k-1, tag_k-1))

Из моего понимания это прямолинейно, поскольку параметры p уже рассчитывается на каждом шаге (мы переходим от 1 вперед, и мы уже знаем p0), а max для параметров e и q можно вычислить с помощью одной итерации через теги (поскольку мы не можем придумать 2 разных тега, мы в принципе должны найти тег T, для которого произведение q * e является максимальным, и вернем это). Это экономит много времени, так как мы почти в линейном времени с точки зрения большой нотации O, а не экспоненциальной сложности, которую мы получим, если бы мы повторили все возможные комбинации слов/тегов.

Я получаю ядро ​​алгоритма правильно или я что-то пропустил?

Заранее спасибо

Answer 1

, так как мы не можем придумать с 2 различными метками, мы в основном должны найти метку T, для которого д * е продукт максимален, и вернуть что

Да, звучит правильно. q - вероятность триграммы (перехода) и e называется вероятностью эмиссии. Как вы сказали, не меняется между разными путями на каждом этапе, поэтому max зависит только от двух других.

Каждая последовательность меток должна начинаться с двух звездочек в позициях -2 и -1. Таким образом, первое предположение верно:

Если предположить быть максимальной вероятностью того, что последние две меток в положении k являются u и v, основываясь на том, что мы только что сказали о начале звездочек, то базовый корпус будет

.

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