Внутренний – внешний алгоритм - Inside–outside algorithm
![]() | эта статья предоставляет недостаточный контекст для тех, кто не знаком с предметом.Июнь 2012 г.) (Узнайте, как и когда удалить этот шаблон сообщения) ( |
В Информатика, то внутренний – внешний алгоритм это способ переоценки вероятности добычи в вероятностная контекстно-свободная грамматика. Он был представлен Джеймс К. Бейкер в 1979 г. как обобщение вперед-назад алгоритм для оценки параметров на скрытые марковские модели к стохастические контекстно-свободные грамматики. Он используется для вычисления ожиданий, например, как часть алгоритм ожидания – максимизации (алгоритм обучения без учителя).
Внутренние и внешние вероятности
Внутренняя вероятность это полная вероятность образования слов , учитывая корневой нетерминальный и грамматика :[1]
Внешняя вероятность это полная вероятность начать с начального символа и генерируя нетерминальный и все слова снаружи , учитывая грамматику :[1]
Вычисление внутренних вероятностей
Базовый вариант:
Общий случай:
Предположим, есть правило в грамматике, то вероятность порождения начиная с поддерева с корнем является:
Внутренняя вероятность это просто сумма всех возможных правил:
Вычисление внешних вероятностей
Базовый вариант:
Здесь начальный символ .
Общий случай:
Предположим, есть правило в грамматике, которая порождает . Тогда осталось вклад этого правила во внешнюю вероятность является:
Теперь предположим, что есть правило в грамматике. Тогда правильновклад этого правила во внешнюю вероятность является:
Внешняя вероятность представляет собой сумму левого и правого вкладов по всем таким правилам:
использованная литература
- ^ а б Мэннинг, Кристофер Д.; Хинрих Шютце (1999). Основы статистической обработки естественного языка. Кембридж, Массачусетс, США: MIT Press. стр.388 –402. ISBN 0-262-13360-1.
- Дж. Бейкер (1979): Обучаемые грамматики для распознавания речи. В Дж. Дж. Вольф и Д. Х. Клатт, редакторы, Документы по речевой коммуникации, представленные на 97-м собрании Акустического общества Америки, страницы 547–550, Кембридж, Массачусетс, июнь 1979 г. MIT.
- Карим Лари, Стив Дж. Янг (1990): Оценка стохастических контекстно-свободных грамматик с использованием алгоритма внутри – снаружи. Компьютерная речь и язык, 4:35–56.
- Карим Лари, Стив Дж. Янг (1991): Применение стохастических контекстно-свободных грамматик с использованием алгоритма Inside – Outside. Компьютерная речь и язык, 5:237–257.
- Фернандо Перейра, Ив Шабес (1992): Внутренняя и внешняя переоценка частично заключенных в скобки корпусов. Материалы 30-го ежегодного собрания Ассоциации компьютерной лингвистики, Ассоциации компьютерной лингвистики, 128–135.