7.1. Задача грамматического вывода

7.1.0. Обозначения и основные идеи

Мы начнем с формальных определений задачи грамматического вывода и ее решения. Большинство обсуждаемых здесь идей основано на работах Фельдмана (Фельдман, 1972; Бирман и Фельдман,

1972), который опирается на работы (Фельдман, Джипе, Хорнинг и Редер, 1969) и (Голд, 1967). Формальные доказательства особенно ясно изложены Фельдманом (1972). Мы будем в основном останавливаться на неформальных иллюстрациях, а не на формальных доказательствах.

Выборкой называется последовательность цепочек символов, выбранных из Т. Предполагается, что некоторые из этих цепочек порождены неизвестной грамматикой Обозначим через множество тех цепочек из которые допускаются грамматикой а через тех цепочек, которые отвергаются ею. Ясно, что

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

Точно так же можно говорить о машине М, которая рассматривает последовательно множества и формирует после каждого просмотра грамматику Задача грамматического вывода разрешима, если можно построить машину, которая в конце концов сформирует грамматику порождающую тот же язык, что и т. е.

В этом случае говорят, что грамматика согласуется с Это самое сильное из разумных определений решения. Мы не можем требовать, чтобы была построена машина, которая в конце концов воспроизведет именно поскольку может быть бесконечно много грамматик, согласованных с Информации, содержащейся в выборке, недостаточно, чтобы различить грамматики в таких парах.

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

удовлетворять, чтобы считалось, что она подходит выборке. Во-первых, она должна правильно классифицировать все цепочки из Во-вторых, она должна давать „естественное" описание множества Это тесно связано со статистической идеей правдоподобия: естественным ли образом следуют из грамматики положительные предложения? Например, выводит ли грамматика положительные предложения короче, чем любая другая грамматика из В-третьих, пробная грамматика должна удовлетворять некоторому критерию простоты ее объяснения. Это понятие аналогично статистической идее „степеней свободы". Грамматику следует предпочесть грамматике если она содержит меньше правил, являющихся просто переформулировками характерной ситуации в рассматриваемой выборке. Для конкретности предположим, что выборка состоит из положительных предложений:

Грамматика с правилами

очевидно, допускает Однако это слишком частное объяснение, подходящее только для этого примера. С другой стороны, все выводы короткие! Можно сравнить с грамматикой

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

порождающую множество всевозможных цепочек, которые можно построить из Интуитивно мы предпочли бы в смысле объяснения поскольку грамматика слишком специальная, слишком общая. Наша цель — воспользоваться этими интуитивными понятиями при вычислении.

Голд (1967) показал, что способ построения выборки может ограничить разнообразие выводов, которые можно осуществить на ее основе, и эффективность процесса вывода. Наиболее существенно различие между выборками, содержащими только положительные предложения, и выборками, содержащими как положительные, так и отрицательные предложения. В первом случае представление называется текстуальным, поскольку оно аналогично задаче для

человека, пытающегося разобрать язык, исследуя тексты, содержащие только правильные конструкции. Во втором случае представление информаторное, поскольку здесь аналогия со случаем, когда человек пытается понять язык, задавая вопросы другому человеку, для которого этот язык родной. Преимущество информаторного представления состоит в том, что обучающийся может выяснить, что не допускается правильной грамматикой Эта информация может оказаться очень важной. К сожалению, многие задачи, которыми занимались в грамматическом выводе, имеют текстуальное представление. Хорошим примером служит задача, с которой сталкивается археолог, когда пытается понять „мертвый" язык, изучая восстановленные манускрипты. У него нет способа выяснить, какая цепочка символов была бы неподходящей, например для шумерского или фригийского.

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

Если процесс вывода может привести к грамматике, согласованной с то в некоторый момент будет содержать те грамматики для которых Однако может быть и бесконечным множеством, содержащим грамматики, не согласованные с . В этом случае процесс вывода не приводит к грамматике, согласованной с Так же будет и в случае, когда в не входит ни одна из согласованных с грамматик.

Наконец, нам потребуется представление о функциях адекватности. Определим здесь функцию адекватности как меру того, насколько грамматика подходит для описания выборки Значения меняются от 0 до причем интерпретируется как „совершенное описание" , а указывает на то, что не годится

для (или потому, что не содержит всех положительных предложений рассматриваемой выборки, или потому, что содержит одно из отрицательных предложений). Нас интересует поведение при неограниченном росте