Алгоритм внутри-вне

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

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

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

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

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

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

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

Базовый случай:

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

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

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

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

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

$\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)$

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

Базовый случай:

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

Здесь стартовый символ $N_{1}$ .

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

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

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

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

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

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

$\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)$

Ссылки

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

Дж. Бейкер (1979): Обучаемые грамматики для распознавания речи . В книге Дж. Дж. Вольфа и Д. Х. Клатта, редакторов, «Документы по речевой коммуникации, представленные на 97-м собрании Акустического общества Америки» , страницы 547–550, Кембридж, Массачусетс, июнь 1979 г. Массачусетский технологический институт.
Карим Лари , Стив Дж. Янг (1990): Оценка стохастических контекстно-свободных грамматик с использованием алгоритма внутри-вне . Компьютерная речь и язык , 4:35–56.
Карим Лари , Стив Дж. Янг (1991): Приложения стохастических контекстно-свободных грамматик с использованием алгоритма Inside-Outside . Компьютерная речь и язык , 5:237–257.
Фернандо Перейра, Ив Шабес (1992): Переоценка внутри и снаружи из частично заключенных в скобки корпусов . Материалы 30-го ежегодного собрания Ассоциации компьютерной лингвистики, Ассоциация компьютерной лингвистики , 128–135.

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

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

[1]