Введение
Находит наиболее вероятную последовательность скрытых состояний.
Алгоритм Витерби — это алгоритм динамического программирования, предназначенный для получения оценки максимальной апостериорной вероятности наиболее вероятной последовательности скрытых состояний, называемой путем Витерби, которая является причиной последовательности наблюдаемых событий. Это особенно актуально в контексте марковских источников информации и скрытых марковских моделей (HMM). Алгоритм получил широкое применение при декодировании сверточных кодов, используемых в цифровых сотовых сетях CDMA и GSM, в модемах, спутниковой и дальней космической связи, а также в беспроводных локальных сетях 802.11. В настоящее время он также широко используется в распознавании речи, синтезе речи, сегментации речи, обнаружении ключевых слов, вычислительной лингвистике и биоинформатике. Например, при преобразовании речи в текст (распознавании речи) акустический сигнал рассматривается как наблюдаемая последовательность событий, а текстовая строка считается «скрытой причиной» этого акустического сигнала. Алгоритм Витерби определяет наиболее вероятную текстовую строку, соответствующую данному акустическому сигналу.
История
Алгоритм Витерби назван в честь Эндрю Витерби, который предложил его в 1967 году как алгоритм декодирования для свёрточных кодов в шумных цифровых каналах связи. Однако у него есть история многократных независимых изобретений, с как минимум семью самостоятельными открытиями, включая открытия, сделанные Витерби, Нидлманом и Вуншем, а также Вагнером и Фишером. В обработку естественного языка он был внедрён как метод определения частей речи ещё в 1987 году. Термины «путь Витерби» и «алгоритм Витерби» стали стандартными для обозначения применения алгоритмов динамического программирования к задачам максимизации, связанным с вероятностями. Другая область применения – отслеживание объектов, где вычисляется траектория, максимизирующая правдоподобие последовательности наблюдений.
Расширения
Обобщение алгоритма Витерби, называемое алгоритмом максимальной суммы (или алгоритмом максимального произведения), может быть использовано для поиска наиболее вероятного назначения всех или некоторых подмножеств скрытых переменных в большом числе графических моделей, например, байесовских сетей, марковских случайных полей и условных случайных полей. Скрытые переменные должны, как правило, быть связаны между собой подобно скрытой марковской модели (HMM), с ограниченным числом связей между переменными и некоторой линейной структурой. Общий алгоритм включает передачу сообщений и во многом схож с алгоритмом распространения убеждений (являющимся обобщением алгоритма прямого и обратного прохода). Алгоритм, называемый итеративным декодированием Витерби, позволяет найти подпоследовательность наблюдения, которая в среднем наилучшим образом соответствует заданной скрытой марковской модели. Этот алгоритм предложен Ци Ван и др. для работы с турбокодами. Итеративное декодирование Витерби работает путем итеративного вызова модифицированного алгоритма Витерби, переоценивая оценку для заполнения до достижения сходимости. Предложен также альтернативный алгоритм – алгоритм «ленивого» Витерби. Для многих практически важных приложений, при разумных условиях зашумленности, «ленивый» декодер (использующий алгоритм «ленивого» Витерби) значительно быстрее, чем оригинальный декодер Витерби (использующий алгоритм Витерби). В то время как оригинальный алгоритм Витерби вычисляет каждый узел в решетке возможных исходов, алгоритм «ленивого» Витерби поддерживает приоритетный список узлов для последовательной оценки, и количество необходимых вычислений обычно меньше (и никогда не больше), чем у обычного алгоритма Витерби для получения того же результата. Однако его сложнее параллелизировать на аппаратном уровне.
Алгоритм Витерби для мягкого вывода
Алгоритм мягкого вывода Витерби (SOVA) является вариантом классического алгоритма Витерби. SOVA отличается от классического алгоритма Витерби тем, что использует модифицированную метрику пути, учитывающую априорные вероятности входных символов, и выдает мягкий выход, указывающий на достоверность принимаемого решения. Первый шаг в SOVA – выбор оптимального пути, проходящего через единственный узел в каждый момент времени t. Поскольку к каждому узлу сходятся две ветви (одна из которых выбирается для формирования оптимального пути, а другая отбрасывается), разница в метриках (или стоимости) между выбранной и отброшенной ветвями показывает степень неопределенности при выборе. Эта стоимость накапливается на протяжении всего скользящего окна (обычно составляющего не менее пяти разрядов ограничения), чтобы определить меру достоверности жесткого битового решения алгоритма Витерби.
Общие ссылки
(Примечание: алгоритм декодирования Витерби описан в разделе IV.) Требуется подписка. Требуется подписка. (Описывает прямой алгоритм и алгоритм Витерби для скрытых марковских моделей). Shinghal, R. и Godfried T. Toussaint, "Эксперименты по распознаванию текста с использованием модифицированного алгоритма Витерби", IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI l, апрель 1979, стр. 184–193. Shinghal, R. и Godfried T. Toussaint, "Чувствительность модифицированного алгоритма Витерби к статистике источника", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI 2, март 1980, стр. 181–185.