Стохастическая контекстно-свободная грамматика

Стохастическая контекстно-свободная грамматика (СКС, также вероятностная контекстно-свободная грамматика, ВКС) — контекстно-свободная грамматика, в которой каждому правилу вывода соответствует вероятность. Вероятность вывода определяется как произведение вероятностей используемых в нём правил вывода, таким образом, некоторые выводы лучше соответствуют стохастической грамматике, чем другие. СКС-грамматики расширяют КС-грамматики так же, как скрытые марковские модели расширяют регулярные грамматики. СКС-грамматики широко применяются в науке: от обработки естественных языков до изучения молекул РНК. СКС-грамматики являются особой формой взвешенных контекстно-свободных грамматик.

Вариант алгоритма Кока — Янгера — Касами находит разбор Витерби для заданной строки и СКС-грамматики. Разбор Витерби — это наиболее вероятный вывод из строки по данной СКС-грамматике.

Внутренне-внешние алгоритмы, являющиеся аналогами алгоритмов вперёд-назад, могут быть использованы для вычисления общей вероятности всех выводов, соответствующих данной строке, по данной СКС-грамматике. Это эквивалентно вероятности порождения СКС-грамматикой данной строки, и интуитивно является мерой соответствия данной строки данной грамматике.

Внутренне-внешние алгоритмы могут быть также использованы для вычисления вероятностей того, что данное правило вывода будет использовано в произвольном выводе для данной строки. Это используется для применения EM-алгоритма для получения вероятностей максимального правдоподобия для СКС-грамматики на основе обучающих последовательностей, которые СКС-грамматика должна моделировать. Алгоритм аналогичен тому, который применяется для скрытых марковских моделей.

Контекстно-свободные грамматики изначально создавались при попытке моделирования естественных языков. Некоторые исследователи расширили эту идею, применением СКС-грамматики.

Вот пример СКС-грамматики из двух правил. Перед каждым правилом стоит вероятность, отражающая относительную частоту его применения.

0.7 VP → V NP

0.3 VP → V NP NP

По данной грамматике можно вычислить ожидаемое количество NP, порождаемое из VP: 0.7 x 1 + 0.3 x 2 = 1.3.

В частности, некоторые системы распознавания речи используют СКС-грамматики для улучшения приближения вероятности и, следовательно, качества распознавания.

Недавно вероятностные КС-грамматики сыграли роль в объяснении иерархии доступности, пытающейся показать, почему некоторые структуры сложнее понять, чем другие.

Выяснилось, что если есть вероятностные сведения о более вероятных конструкциях, то можно вычислить информационную энтропию этих конструкций. Если механизм восприятия синтаксиса основан на понятиях теории информации, то он вполне может применять нечто похожее на ВКС-грамматики.^[1]

КС-грамматики применяются для моделирования вторичной структуры РНК^[2][3]. Вторичная структура включает комплементарные нуклеотиды внутри одинарной молекулы РНК. Эта парность биологически важна для правильного функционирования молекулы РНК. Большая часть таких парностей может быть представлена КС-грамматикой (за исключением псевдоузлов).

Рассмотрим, например, следующую грамматику, в которой a, c, g и u представляют нуклеотиды, а S — стартовый символ:

S → aSu | cSg | gSc | uSa

Эта простая КС-грамматика представляет молекулу РНК, состоящую исключительно из двух целиком комплементарных областей, в которых разрешены только канонические комплементарные пары (например, A-U и C-G).

Добавляя вероятности к более сложным КС-грамматикам, возможно моделировать основания или основные пары, которые более или менее соответствуют ожидаемому виду молекулы РНК. СКС-грамматики используются для моделирования последовательностей в семействах РНК-генов в базе данных Rfam, и поиска последовательностей генома для вероятных членов этих семейств. СКС-грамматики также использовались для поиска РНК-генов, используя сравнительную геномику. В этой работе гомологи потенциальных РНК-генов двух родственных организмов исследовались с применением подходов СКС-грамматик, для определения, сохраняется ли вторичная структура. Если да, то последовательность, вероятно, является РНК-геном, а вторичная структура сохраняется для функциональных потребностей РНК-гена. Было также показано, что СКС-грамматики могут предсказывать вторичную структуру молекулу РНК подобно существующим подходам: такие СКС-грамматики используются, например, программой Stemloc.

С публикацией в 1967 году теоремы Гольда было заявлено, что грамматики естественных языков управляются детерминированными правилами, которые не могут быть изучены лишь только на положительных примерах. Это было частью довода о бедности стимула, представленного в 1980 году, и подразумеваемого со времён ранних работ Хомского 1950-х годов. Среди других аргументов, это привело к нативистскому представлению о том, что формы грамматики (включая в некоторых версиях полный концептуальный лексикон) заложены с рождения. Это представление значительно ограничивается теориями GB и MP.

Однако следует заметить, что результат Гольда об обучаемости может быть легко обойдён, если предположить, что изучающий либо узнает практически совершенное приближение верного языка, либо изучает типичные входные данные, а не произвольно распределённые. В самом деле, было доказано, что просто получая входные данные от говорящего, которые выдаёт положительные примеры произвольно, а не по заранее заданному плану, приводит к идентифицируемости с пределом вероятности 1.^[4][5].

Проблема любого формального синтаксиса в том, что часто более одного правила вывода может быть применено к структуре, что приводит к конфликту. Чем больше покрытие, тем сильнее конфликт, и все грамматисты (начиная с Панини) потратили значительные усилия на создание системы приоритетов для правил, которые обычно оказывались опровержимыми. Другая трудность состоит с перегенерацией, при которой генерируются также недопущенные структуры. Вероятностные грамматики обходят эти проблемы, используя частоты различных правил вывода для их упорядочения, в результате получая «наиболее вероятную» интерпретацию, которая по определению опровержима, при поступлении дополнительных данных. Так как шаблоны использования изменяются диахронически, эти вероятностные правила могут быть заново обучены, таким образом обновляя грамматику.

Можно сконструировать вероятностную грамматику из традиционного формального синтаксиса, назначая каждому нетерминалу вероятность, взятую из некоторого распределения, для последующего приближения по реальным данным. На большинстве примеров широкого диапазона языков, вероятностные грамматики, которое подстраивают эти вероятности, основываясь на данных, работают лучше, чем созданные вручную (хотя некоторые грамматики, основанные на правилах, в данный момент по точности приближаются к ВКС-грамматикам).

Недавно вероятностные грамматики получили некоторое субъективное подтверждение. Хорошо известно, что разные синтаксические структуры воспринимаются с разной сложностью (например, иерархия доступности для относительных оборотов). Вероятностные версии минималистических грамматик использовались для вычисления информационной энтропии, которая, как выяснилось, хорошо коррелирует с психолингвистическими данными о лёгкости понимания и воспроизведения.^[1]

• База данных Rfam