Модель отступления Каца

Откат Каца — это генеративная n- грамм модель языка , которая оценивает условную вероятность слова с учетом его истории в n -грамме. Эта оценка достигается за счет отступления от все более коротких моделей истории при определенных условиях. При этом модель с наиболее достоверной информацией о данной истории используется для получения лучших результатов.

Модель была представлена ​​в 1987 году Славой М. Кацем. До этого модели языка n-грамм строились путем обучения отдельных моделей различным порядкам n-грамм с использованием оценки максимального правдоподобия и последующей их совместной интерполяции.

Метод

Уравнение модели отсрочки Каца:

${\begin{aligned}&P_{bo}(w_{i}\mid w_{i-n+1}\cdots w_{i-1})\\[4pt]={}&{\begin{cases}d_{w_{i-n+1}\cdots w_{i}}{\dfrac {C(w_{i-n+1}\cdots w_{i-1}w_{i})}{C(w_{i-n+1}\cdots w_{i-1})}}&{\text{if }}C(w_{i-n+1}\cdots w_{i})>k\\[10pt]\alpha _{w_{i-n+1}\cdots w_{i-1}}P_{bo}(w_{i}\mid w_{i-n+2}\cdots w_{i-1})&{\text{otherwise}}\end{cases}}\end{aligned}}$

где

C ( x ) = количество раз x появляется в обучении

w _i = i- е слово в данном контексте

По сути, это означает, что если n -грамма была просмотрена более k раз при обучении, условная вероятность слова с учетом его истории пропорциональна оценке максимального правдоподобия этой n -граммы. В противном случае условная вероятность равна условной вероятности отката ( n − 1)-граммы.

Более сложная часть — определение значений k , d и α .

$k$ является наименее важным из параметров. Обычно его выбирают равным 0. Однако эмпирическое тестирование может найти лучшие значения для k.

$d$ обычно это сумма дисконтирования, найденная с помощью оценки Гуда – Тьюринга . Другими словами, если оценки Гуда – Тьюринга $C$ как $C^{*}$, затем $d={\frac {C^{*}}{C}}$

Чтобы вычислить $\alpha$, полезно сначала определить величину β, которая представляет собой оставшуюся вероятностную массу для ( n − 1)-граммы:

$\beta _{w_{i-n+1}\cdots w_{i-1}}=1-\sum _{\{w_{i}:C(w_{i-n+1}\cdots w_{i})>k\}}d_{w_{i-n+1}\cdots w_{i}}{\frac {C(w_{i-n+1}\cdots w_{i-1}w_{i})}{C(w_{i-n+1}\cdots w_{i-1})}}$

Тогда вес отсрочки α рассчитывается следующим образом:

$\alpha _{w_{i-n+1}\cdots w_{i-1}}={\frac {\beta _{w_{i-n+1}\cdots w_{i-1}}}{\sum _{\{w_{i}:C(w_{i-n+1}\cdots w_{i})\leq k\}}P_{bo}(w_{i}\mid w_{i-n+2}\cdots w_{i-1})}}$

Приведенная выше формула применима только в том случае, если имеются данные для «( n − 1)-граммы». В противном случае алгоритм полностью пропускает n-1 и использует оценку Каца для n-2. (и так далее, пока не будет найдена n-грамма с данными)

Обсуждение

Эта модель обычно хорошо работает на практике, но в некоторых случаях дает сбой. Например, предположим, что биграмма «a b» и униграмма «c» очень распространены, но триграмма «ab c» никогда не встречается. Поскольку «a b» и «c» очень распространены, может быть важно (то есть не случайно), что «ab c» никогда не встречается. Возможно, это запрещено правилами грамматики. Вместо того, чтобы присвоить более подходящее значение 0, метод вернется к биграмме и оценит P ( c | b ), который может быть слишком большим.