Удалённая интерполяция

Материал из NLPub
(перенаправлено с «Deleted interpolation»)
Перейти к: навигация, поиск

Удалённая интерполяция (англ. deleted interpolation) — алгоритм подсчёта весовых коэффициентов для строк в корпусе текстов[1]. При расчёте используются частотные характеристики n-грамм, полученные путём предварительной обработки заданного корпуса текстов.

Применение

Данный алгоритм имеет применение в различных задачах построения модели языка. Например, в задаче разметки частей речи (англ. POS-tagging).

Алгоритм

Вход: униграммы (t_3), биграммы (t_2, t_3), триграммы (t_1, t_2, t_3) \in T, значения частот f(t_1, t_2, ..., t_n), количество всех униграмм N.

Инициализация: \lambda_1 \leftarrow 0, \lambda_2 \leftarrow 0, \lambda_3 \leftarrow 0.

Определение: f(t_1, t_2, ..., t_n) = 0 при отсутствии в корпусе n-граммы f(t_1, t_2, ..., t_n).

Алгоритм:[2]

   for (t_1, t_2, ..., t_n) \in T при f(t_1, t_2, ..., t_n) > 0
       
       k_1 \leftarrow \frac{f(t_1, t_2, t_3) - 1}{f(t_1, t_2) - 1}
       
       k_2 \leftarrow \frac{f(t_2, t_3) - 1}{f(t_2) - 1}
       
       k_3 \leftarrow \frac{f(t_3) - 1}{N - 1}
       
       if k_1 > k_2 and k_1 > k_3
           
           \lambda_3 \leftarrow \lambda_3 + f(t_1, t_2, t_3)
       
       if k_2 > k_1 and k_2 > k_3
           
           \lambda_2 \leftarrow \lambda_2 + f(t_1, t_2, t_3)
       
       if k_3 > k_1 and k_3 > k_2
           
           \lambda_1 \leftarrow \lambda_1 + f(t_1, t_2, t_3)
   
   Нормализовать \lambda_1, \lambda_2, \lambda_3.

Выход: \lambda_1, \lambda_2, \lambda_3.

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

Время работы алгоритма линейно зависит от количества триграмм с ненулевой частотой в корпусе.

См. также

Примечания

  1. Brants, Thorsten. "TnT: a statistical part-of-speech tagger." Proceedings of the sixth conference on Applied natural language processing. Association for Computational Linguistics, 2000.
  2. На этапе вычисления k при нулевом значении знаменателя принять нулевое значение всей дроби.