Алгоритм Вітербі алгоритм пошуку найбільш відповідного списку станів званого шляхом Вітербі який в контексті ланцюгів Ма

Алгоритм Вітербі — алгоритм пошуку найбільш відповідного списку станів (званого шляхом Вітербі), який в контексті ланцюгів Маркова отримує найбільш ймовірну послідовність подій, що відбулися. Алгоритм був запропонований Ендрю Вітербі в 1967 році як алгоритм декодування згорткового коду, переданого по мережах за наявністю шуму.

Є алгоритмом динамічного програмування. Алгоритм використовується в CDMA і GSM цифрового зв'язку, в модемах і космічних комунікаціях. Також він широко використовується в розпізнаванні мови, синтезі мови, комп'ютерній лінгвістиці та біоінформатиці. Приміром, при розпізнаванні мови звуковий сигнал сприймається як послідовність подій і рядок тексту є «прихований сенс» акустичного сигналу. Алгоритм Вітербі знаходить найбільш ймовірний рядок тексту по даних сигналу.

Алгоритм робить кілька припущень:

спостережувані і приховані події повинні бути послідовністю. Послідовність найчастіше впорядкована за часом;
дві послідовності повинні бути вирівняні: кожна спостережувана подія має відповідати рівно одній прихованій події;
обчислення найбільш імовірної прихованої послідовності до моменту t повинно залежати тільки від спостережуваної події в момент часу t, і найбільш імовірної послідовності до моменту t — 1.

Примітки

Алгоритм Витерби [ 4 жовтня 2015 у Wayback Machine.] (рос.)

Див. також

G. David Forney, Jr. The Viterbi Algorithm: A Personal History /MIT [ 6 січня 2017 у Wayback Machine.]

Це незавершена стаття зі статистики.
Ви можете проєкту, виправивши або дописавши її.

[1] Алгоритм Витерби [ 4 жовтня 2015 у Wayback Machine.] (рос.)