Алгоритм Вітербі

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

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

Примітки[ред.ред. код]

Див. також[ред.ред. код]