Как работает алгоритм Viterbi

Что проверяют

Умеете ли вы увидеть в алгоритме Витерби динамическое программирование и написать его без ошибок в индексах. Следом обычно просят оценить сложность и объяснить, чем он отличается от прямого алгоритма (forward).

Как отвечать

Постановка: есть скрытая марковская модель с N состояниями, начальными вероятностями pi, матрицей переходов A, вероятностями эмиссий B и последовательность из T наблюдений. Нужна самая вероятная цепочка скрытых состояний. Перебор стоит N в степени T, Витерби решает задачу за O(T·N²) по времени и O(T·N) по памяти.

Каркас:

• инициализация: delta(0, j) = log pi(j) + log B(j, o0);
• рекурсия: для шага t и состояния j берём максимум по предыдущим i от delta(t-1, i) + log A(i, j), прибавляем log B(j, ot) и запоминаем в psi(t, j) тот i, на котором максимум достигнут;
• завершение: последнее состояние это argmax по delta(T-1, j);
• обратный проход: идём по psi от конца к началу и восстанавливаем путь.

Считать нужно в логарифмах: произведение сотни вероятностей порядка 0,1 уже даёт 1e-100, а на длинных последовательностях float64 уходит в ноль. Заодно сложение дешевле умножения. В NumPy рекурсия векторизуется: столбец delta плюс матрица log A дают таблицу N×N, по которой берут max и argmax вдоль оси.

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

Где спотыкаются

Перемножают вероятности напрямую. На игрушечном примере всё работает, на реальной последовательности все пути получают нулевую вероятность.

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

Хранят для каждого состояния полный путь и копируют списки на каждом шаге. Это O(T²·N) памяти и лишние аллокации, хватает таблицы обратных указателей. Ещё частая ошибка: перепутать A(i, j) и A(j, i).