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

Материал из NLPub

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

Применение

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

Алгоритм

Вход: униграммы , биграммы , триграммы , значения частот , количество всех униграмм .

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

Определение: при отсутствии в корпусе n-граммы .

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

   for  при 
       
       
       
       
       
       
       
       if  and 
           
           
       
       if  and 
           
           
       
       if  and 
           
           
   
   Нормализовать .

Выход: .

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

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

См. также

Примечания

  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. На этапе вычисления при нулевом значении знаменателя принять нулевое значение всей дроби.