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

Материал из NLPub
Перейти к: навигация, поиск

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

Применение

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

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

Алгоритм

Здесь представлено описание алгоритма Витерби для скрытых марковских моделей второго порядка. Для простоты понимания используется терминология задачи автоматической разметки частей речи. Используются следующие обозначения: x_1...x_n — предложение, * — символ начала предложения, \textit{STOP} — символ конца предложения, S — множество всех возможных тегов, q(s|u,v) — вероятность перехода в состояние s при предыдущих состояниях (u,v), e(x|s) — вероятность присвоения слову x тега s \in S.

Вход: предложение x_1...x_n, параметры q(s|u,v) и e(x|s).

Инициализация: \pi(0,*,*) \leftarrow 1

Определение: S_{-1} = S_0 = \{*\}, S_k = \mathit{S} для k \in {1...n}

Алгоритм:

   for k = 1...n
       
       for u \in S_{k-1}, v \in S_k
           
           \pi(k,u,v) \leftarrow \max_{w \in S_{k-2}} (\pi(k-1,w,u) \times q(v|w,u) \times e(x_k|v))
           
           bp(k,u,v) \leftarrow \arg\max_{w \in S_{k-2}} (\pi(k-1,w,u) \times q(v|w,u) \times e(x_k|v))
   
   (y_{n-1},y_n) \leftarrow \arg\max_{u,v} (\pi(n,u,v) \times q(\textit{STOP}|u,v))
   
   for k = (n-2)...1
       
       y_k \leftarrow bp(k+2, y_{k+1}, y_{k+2})

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

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

Общее время выполнения алгоритма Витерби составляет O(n|S|^3), поскольку выполняется вычисление q(v|w,u) \times e(x_k|v) для всех возможных k, s, u, v. При этом расходуется n|S|^2 ячеек памяти на заполнение таблицы динамического программирования \pi, и столько же на заполнение таблицы bp.

См. также