7.1.2. Объединение бейесовских процедур с перечислением

Лингвистическое перечисление приводит к выбору наилучшей пробной грамматики для заданной выборки. Статистический подход к грамматическому выводу приписывал бы каждому кандидату в грамматику вероятность быть „правильной" грамматикой. Эти два подхода были объединены Хорнингом (1969); упоминались они и в работах Ханта (1965) и Ватанабе (1960).

Понятие грамматики надо модифицировать так, чтобы учесть „вероятность появления предложения". Пусть — порождающая

грамматика, тогда каждая ее продукция будет иметь вид , где и — цепочки из словаря грамматики . Будем обозначать продукций с в качестве левой части через Стохастическая грамматика получается из если каждой продукции приписать вероятностную меру Эта мера определяет вероятность того, что к цепочке (если она есть) будет применена продукция . Нияк (1972) предлагает следующий пример:

Цепочка вводится так:

Перемножая вероятности из правого столбца в (19), находим вероятность порождения цепочки а именно Эта величина может показаться слишком малой, но это и надо было ожидать. Для нашего интуитивного представления о языке любое конкретное предложение языка должно иметь небольшую вероятность.

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

Стохастическая согласованность

Две грамматики называются стохастически согласованными, если они согласованы и для всех

Вспомним выдумку об экспериментаторе, выбирающем грамматику и использующем ее для порождения предложений выборки, которая должна определять Предположим, что существует вероятность выбора любой конкретной грамматики для использования ее в качестве Предположим далее, что обучающийся (или машина вывода) может вычислить Вероятность будет называться априорной вероятностью выбора Если обучающийся применяет для вывода по бейесовскую процедуру, то апостериорные вероятности будут приписываться в соответствии с правилом

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

функцию сложности вывода можно выбрать так, чтобы она отражала вероятность появления выборки:

Бейесовское решающее устройство, которому на каждом этапе процесса вывода приходится выбирать единственную грамматику, должно выбрать такую, чтобы величина

была максимальной. Это эквивалентно минимизации функции несовместности

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

Бейесовский алгоритм перечисления для стохастического текстуального представления

1. Пусть — октмовское перечисление бесконечного множества использующее функцию внутренней сложности вида (22).

2. При заданной выборке найти такое наименьшее целое что Подсчитать значение

3. Найти такое наименьшее целое что (Ясно, что

Так как (26) справедливо для любого то целое число максимизирующее на должно лежать в интервале от до включительно.)

4. Выбрать из множества пользуясь обычной бейесовской процедурой вывода. Этим определяется

бейесовский оптимальный выбор грамматики из объясняющей Добавить образовав и повторить процесс с шага 2.

Таким образом, бейесовскую индукцию можно применять для выбора наилучшей грамматики, объясняющей фиксированную выборку. Естественно, что мы также заинтересованы в ограничениях в ходе процесса выбора. Уверены ли мы в том, что правильная грамматика всегда будет рассмотрена (т. е. в конце концов станет элементом множества ), и каковы шансы, что она, будучи там, окажется выбранной в качестве оптимальной?

Независимо от положения грамматики в перечне на некотором этапе ее должны включить в если она еще не там. Пусть — первая в перечне грамматика, для которой При стохастическом текстуальном представлении на некотором этапе все предыдущие грамматики в перечне будут исключены из-за их неспособности допускать некоторые предложения из На этом этапе станет первой грамматикой в Если то безусловно, будет в Грамматика также могла оказаться в на этапе если

В любом случае Если неравенство (27) не выполняется на этапе то оно будет выполнено на некотором последующем этапе . В самом деле, если стохастически не согласуется с то

Как только грамматика будет в бейесовская индукция при неограниченном росте приведет к выбору ее в качестве наиболее вероятной грамматики для объяснения Чтобы в этом убедиться, рассмотрим множество X различных предложений в безотносительно к числу их появлений. — частота появления предложения — ожидаемое число появлений х в предположении, что для порождения исследуемой выборки используется грамматика Можно показать (Хант, 1965), что если для выбора гипотетической „наилучшей" грамматики из фиксированного множества грамматик применяется бейесовский вывод, что выбранная

грамматика минимизирует величину

При неограниченном росте эта функция достигает своего абсолютного минимума (нуля) только на грамматике, для которой

при всех Это переформулировка условия стохастического согласования. Таким образом, в пределе алгоритм бейесовского перечисления выберет в полученном перечне первую грамматику, стохастически согласованную с Этот результат отличается от соответствующего результата для формального лингвистического вывода. С учетом информации о частотах бейесовская процедура может достичь стохастического согласования только при текстуальном представлении, тогда как процедуры формального лингвистического перечисления, основанные на минимизации функции несовместности, не могут при текстуальном представлении даже приблизиться к

Тот факт, что в бейесовском выводе используется (и на самом деле требуется) текстуальное представление, а в лингвистическом эффект больше при работе с информаторным представлением, ставит интересный вопрос. Можно ли объединить стохастическое текстуальное представление с эффективным информаторным представлением, опираясь на то, что бейесовская индукция указывает грамматику, которая лучше всех объясняет а также другие грамматики, дающие разумные альтернативные объяснения? Предположим, например, что бейесовская процедура перечисления показывает, что максимизирует апостериорную вероятность выбора, а величина апостериорной вероятности для почти такая же. Не будет ли разумным в случае информаторного представления выбирать в качестве цепочки, допускаемой только одной из этих двух грамматик? Как нужно было бы изменить соответствующие алгоритмы вывода и перечисления? Непосредственно этот вопрос не изучался. Интересующийся читатель может посмотреть работы Ханта (1965) и Ватанабе (1960, 1969), имеющие некоторое отношение к рассматриваемому вопросу.

Довод в пользу осуществления бейесовского вывода с помощью перечисления опирается на нашу способность проводить необходимое оккамовское перечисление в Разумно предположить, что можно построить машину, порождающую все более сложные грамматики из некоторого класса. Но можно ли построить машину, порождающую все менее и менее вероятные грамматики? Ответ на этот вопрос, по-видимому, лежит в области философии, поскольку он зависит от того, как определить „менее вероятные". Может создаться

впечатление, что неформальный довод в пользу перечисления, основанного на вероятности, слабее довода в пользу перечисления, основанного на сложности.

Можно поставить также вопрос о том, насколько широко применимо понятие стохастической грамматики. В некоторых случаях оно оказывается полезным. Свейн и Фу (1972) использовали для анализа простых рисунков очень похожее понятие — стохастические программированные грамматики. Однако пока не ясно, какую пользу может принести это понятие. Были высказаны серьезные сомнения относительно соответствия стохастического описания естественному языку. Приведем два основных возражения. Одно заключается в том, что понятие вероятностного упорядочения символов принципиально неверно, поскольку при этом не учитывается смысл сказанного. Это собственно философский довод. Другое возражение более прагматическое. Предположим, что мы допускаем, что статистическое описание порождения языка стохастической грамматикой в принципе возможно. Однако практически естественные языки выглядят настолько сложными, что оценить соответствующие параметры не удается, и надо найти какой-нибудь другой вид лингвистических описаний (Миллер и Хомский, 1963). Этот аргумент нисколько не умаляется демонстрацией пригодности перечисления, так как основная идея Миллера и Хомского заключается в том, что сама процедура перечисления слишком громоздка.