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

Материал из NLPub

Алгоритм Витерби (англ. Viterbi algorithm) — алгоритм динамического программирования, выполняющий поиск наиболее подходящего списка состояний и получающий наиболее вероятную последовательность произошедших событий. Алгоритм получил своё название в честь создателя — американского инженера итальянского происхождения Эндрю Витерби.

Применение

Данный алгоритм часто применяется в задачах обработки естественного языка, подразумевающих использование скрытых марковских моделей. Примеры таких задач:

  • разметка частей речи (англ. POS-tagging);
  • извлечение именованных сущностей (англ. named entity recognition).

Алгоритм

Здесь представлено описание алгоритма Витерби для скрытых марковских моделей второго порядка. Для простоты понимания используется терминология задачи автоматической разметки частей речи. Используются следующие обозначения: — предложение, — символ начала предложения, — символ конца предложения, — множество всех возможных тегов, — вероятность перехода в состояние при предыдущих состояниях , — вероятность присвоения слову тега .

Вход: предложение , параметры и .

Инициализация:

Определение: для

Алгоритм:

   for 
       
       for 
           
           
           
           
   
   
   
   for 
       
       

Выход: последовательность тегов .

Сложность и время работы

Общее время выполнения алгоритма Витерби составляет , поскольку выполняется вычисление для всех возможных , , , . При этом расходуется ячеек памяти на заполнение таблицы динамического программирования , и столько же на заполнение таблицы .

См. также