Алгоритм «изнутри-снаружи»

Метод оценки параметров для вероятностных контекстно-свободных грамматик

Для алгоритмов синтаксического анализа в информатике алгоритм «изнутри-снаружи» является способом переоценки вероятностей производства в вероятностной контекстно-свободной грамматике . Он был введен Джеймсом К. Бейкером в 1979 году как обобщение алгоритма «вперед-назад» для оценки параметров скрытых марковских моделей на стохастические контекстно-свободные грамматики . Он используется для вычисления ожиданий, например, как часть алгоритма максимизации ожидания (алгоритма обучения без учителя).

Внутренние и внешние вероятности

Внутренняя вероятность — это полная вероятность генерации слов , учитывая корневой нетерминал и грамматику : ^[1] ${\displaystyle \beta _{j}(p,q)}$ ${\displaystyle w_{p}\cdots w_{q}}$ ${\displaystyle N^{j}}$ ${\displaystyle G}$

${\displaystyle \beta _{j}(p,q)=P(w_{pq}|N_{pq}^{j},G)}$

Вероятность снаружи — это полная вероятность начала со стартового символа и генерации нетерминала и всех слов снаружи , учитывая грамматику : ^[1] ${\displaystyle \alpha _{j}(p,q)}$ ${\displaystyle N^{1}}$ ${\displaystyle N_{pq}^{j}}$ ${\displaystyle w_{p}\cdots w_{q}}$ ${\displaystyle G}$

${\displaystyle \alpha _{j}(p,q)=P(w_{1(p-1)},N_{pq}^{j},w_{(q+1)m}|G)}$

Вычисление внутренних вероятностей

Базовый вариант:

${\displaystyle \beta _{j}(p,p)=P(w_{p}|N^{j},G)}$

Общий случай:

Предположим, что в грамматике есть правило , тогда вероятность генерации поддерева, начинающегося с корня, равна: ${\displaystyle N_{j}\rightarrow N_{r}N_{s}}$ ${\displaystyle w_{p}\cdots w_{q}}$ ${\displaystyle N_{j}}$

${\displaystyle \sum _{k=p}^{k=q-1}P(N_{j}\rightarrow N_{r}N_{s})\beta _{r}(p,k)\beta _{s}(k+1,q)}$

Внутренняя вероятность — это просто сумма по всем таким возможным правилам: ${\displaystyle \beta _{j}(p,q)}$

${\displaystyle \beta _{j}(p,q)=\sum _{N_{r},N_{s}}\sum _{k=p}^{k=q-1}P(N_{j}\rightarrow N_{r}N_{s})\beta _{r}(p,k)\beta _{s}(k+1,q)}$

Вычисление внешних вероятностей

Базовый вариант:

${\displaystyle \alpha _{j}(1,n)={\begin{cases}1&{\mbox{if }}j=1\\0&{\mbox{otherwise}}\end{cases}}}$

Здесь начальный символ — . ${\displaystyle N_{1}}$

Общий случай:

Предположим, что в грамматике есть правило , которое генерирует . Тогда левый вклад этого правила во внешнюю вероятность равен: ${\displaystyle N_{r}\rightarrow N_{j}N_{s}}$ ${\displaystyle N_{j}}$ ${\displaystyle \alpha _{j}(p,q)}$

${\displaystyle \sum _{k=q+1}^{k=n}P(N_{r}\rightarrow N_{j}N_{s})\alpha _{r}(p,k)\beta _{s}(q+1,k)}$

Теперь предположим, что в грамматике есть правило . Тогда правильный вклад этого правила во внешнюю вероятность : ${\displaystyle N_{r}\rightarrow N_{s}N_{j}}$ ${\displaystyle \alpha _{j}(p,q)}$

${\displaystyle \sum _{k=1}^{k=p-1}P(N_{r}\rightarrow N_{s}N_{j})\alpha _{r}(k,q)\beta _{s}(k,p-1)}$

Внешняя вероятность представляет собой сумму левых и правых вкладов по всем таким правилам: ${\displaystyle \alpha _{j}(p,q)}$

${\displaystyle \alpha _{j}(p,q)=\sum _{N_{r},N_{s}}\sum _{k=q+1}^{k=n}P(N_{r}\rightarrow N_{j}N_{s})\alpha _{r}(p,k)\beta _{s}(q+1,k)+\sum _{N_{r},N_{s}}\sum _{k=1}^{k=p-1}P(N_{r}\rightarrow N_{s}N_{j})\alpha _{r}(k,q)\beta _{s}(k,p-1)}$

Ссылки

1. Мэннинг, Кристофер Д.; Хинрих Шютце (1999). Основы статистической обработки естественного языка . Кембридж, Массачусетс, США: MIT Press. стр. 388–402. ISBN 0-262-13360-1.

• J. Baker (1979): Обучаемые грамматики для распознавания речи. В JJ Wolf и DH Klatt, редакторы, Speech communication papers, представленные на 97-м заседании Акустического общества Америки , страницы 547–550, Кембридж, Массачусетс, июнь 1979. MIT.
• Карим Лари, Стив Дж. Янг (1990): Оценка стохастических контекстно-свободных грамматик с использованием алгоритма «внутри-снаружи». Компьютерная речь и язык , 4:35–56.
• Карим Лари, Стив Дж. Янг (1991): Применение стохастических контекстно-свободных грамматик с использованием алгоритма «изнутри-снаружи». Компьютерная речь и язык , 5:237–257.
• Фернандо Перейра, Ив Шабес (1992): Внутренне-внешняя переоценка на основе частично заключенных в скобки корпусов. Труды 30-го ежегодного заседания Ассоциации компьютерной лингвистики, Ассоциация компьютерной лингвистики , 128–135.

Внешние ссылки

• Алгоритм «изнутри-снаружи» — Фэй Ся
• Алгоритм «изнутри-снаружи» - Майкл Коллинз