Таблица 22.8. Трассировка выполнения задания, в котором система Sequitur осуществляет индуктивный вывод грамматики для входного текста "abcdbcabcd". Работа начинается с введения правила для S и добавления каждого символа к концу этого правила по очереди. После добавления шестого символа обнаруживается первое вхождение повторяющейся пары: be. Поэтому оба вхождения be заменяются новым нетерминальным символом А и вводится правило. После добавления еще трех символов девятый символ вызывает еще одно повторение be, поэтому такая пара снова заменяется символом А. Это приводит к появлению двух вхождений символов аА, поэтому они заменяются новым нетерминальным символом в. После добавления десятого и последнего терминального символа обнаруживаются два вхождения Bd, поэтому они заменяются новым нетерминальным символом С. Но теперь символ в появляется только один раз, в правой части правила С, поэтому в заменяется его расширением аА

В следующей главе будут описаны другие алгоритмы индуктивного вывода грамматики, которые могут применяться к вероятностным контекстно-свободным грамматикам. А теперь обратимся к проблеме определения с помощью обучения грамматики, которая дополнена семантикой. Поскольку расширенная грамматика представляет собой логическую программу, состоящую из хорновских выражений, то для этого могут применяться методы индуктивного логического программирования. Одной из программ индуктивного логического программирования (Inductive Logic Programming— ILP) является Chill [1640], которая на основании примеров определяет с помощью обучения грамматику и специализированный синтаксический анализатор для этой грамматики. Целевой проблемной областью являются запросы к базе данных на естественном языке. Обучающие примеры состоят из пар, в которые собраны строки из слов и соответствующих запросов, например, как показано ниже.

Задача программы Chill состоит в том, чтобы определить с помощью обучения предикат Parse (words, query), который является совместимым с примерами и, можно надеяться, допускает приемлемое обобщение применительно к другим примерам. Непосредственное использование метода ILP для определения этого предиката с помощью обучения приводит к достижению слишком низкой производительности: полученный с помощью индуктивного вывода синтаксический анализатор имеет точность лишь приблизительно 20%. Но, к счастью, системы обучения с помощью ILP могут совершенствоваться путем введения дополнительных знаний. В данном случае большая часть предиката Parse была определена в виде логической программы и задача системы Chill свелась к тому, что нужно было осуществить логический вывод правил управления, которыми может руководствоваться синтаксический анализатор при выборе одного варианта синтаксического анализа перед другим. После введения этих дополнительных знаний система Chill достигла точности от 70 до 85% при решении различных задач обработки запросов к базе данных.