Обобщение на основе объяснения

Идея обобщения на основе объяснения впервые была реализована в области ма­шинного обучения, целью которого является обобщение заданных примеров в виде общих описаний рассматриваемых понятий. Одним из способов формирования таких описаний является обобщение на основе объяснения (Explanation-Based Generalization - EBG), при котором обычно используется только один пример. Малое количество примеров компенсируется за счет применения в системе фоновых знаний, которые, как правило, именуются теорией проблемной области.

Способ EBG основан на использовании при формировании обобщенных описаний следующей идеи: если дан некоторый экземпляр целевого понятия, то можно вос­пользоваться теорией проблемной области для объяснения того, как этот экземпляр фактически удовлетворяет данному понятию. Затем анализируется это объяснение и предпринимается попытка обобщить его таким образом, чтобы оно подходило не только для заданного экземпляра, но и для множества "аналогичных" экземпляров. Затем такое обобщенное объяснение становится частью описания рассматриваемого понятия и может в дальнейшем использоваться при распознавании экземпляров это­го понятия. Кроме того, требуется, чтобы формируемое описание понятия было опе­рационным; это означает, что оно должно быть сформулировано в терминах понятий, объявленных пользователем как операционные. Интуитивно можно себе представить, что описание понятия является операционным (определяющим некоторую опера­цию), если его можно (относительно) легко использовать на практике. Задача опре­деления того, что подразумевается под словом "операционный", полностью возлагает­ся на пользователя.

В реализации метода EBG эти абстрактные идеи должны были стать более конкрет­ными. Один из способов их реализации в логике языка Prolog состоит в следующем.

• Понятие реализуется в качестве предиката,

• Описание понятия представляет собой определение предиката.

Часть II. Применение языка Prolog в области искусственного интеллекта

• Объяснением является дерево доказательства, которое демонстрирует, как за­данный экземпляр удовлетворяет целевому понятию.

• Теория проблемной области представлена в виде множества доступных преди­катов, определенных как программа Prolog.

Б таком случае задача обобщения на основе объяснения может быть сформулиро­вана, как описано ниже.

Дано

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

• Критерии оиерационкости. Эти критерии определяют предикаты, которые мо­гут использоваться в определении целевого предиката.

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

Найти

Я Обобщение учебного экземпляра и операционное определение целевого поня­тия; это определение состоит из достаточного условия (в терминах операцион­ных предикатов) для данного обобщенного экземпляра, при котором удовле­творяется целевое понятие.

Метод обобщения на основе объяснения в такой постановке может рассматривать­ся как своего рода компиляция программы с преобразованием из одной формы в дру­гую. Первоначальная программа определяет целевое понятие в терминах предикатов теории проблемной области. Откомпилированная программа определяет то же целе­вое понятие (или подпонятие) в терминах "целевого языка", т.е. только с помощью операционных предикатов. Механизм компиляции, предусмотренный в методе EEG, является довольно необычным. Он предусматривает выполнение первоначальной программы на заданном примере, что приводит к получению дерева доказательства. Затем это дерево доказательства обобщается таким образом, что сохраняется его структура, но постоянные заменяются переменными при любой возможности. В по­лученном таким образом обобщенном дереве доказательства некоторые узлы указы­вают на операционные предикаты. Затем дерево сокращается так, что остаются только эти "операционные узлы" и корень. Полученный результат представляет со­бой операционное определение целевого понятия.

Это описание проще всего проиллюстрировать на примере практического приме­нения метода EBG. В листинге 23.3 приведены два определения теорий проблемной области для EBG. Первая теория проблемной области касается вручения подарка, а вторая описывает движения лифта. Рассмотрим первую проблемную область. Допус­тим, что учебный экземпляр состоит в следующем: % Дж он аручает сам себе шоколад (разрешает себе егс съесть) gives( John, John, chocolate)

Листинг 23.3. Два определения задач для обобщения на основе объяснения

% Для совместимости с некоторыми реализациями Prolog следующие предикаты % определены как динамические:

:- dynamic gives/3, would_please/2, would_comfort/2, feels_sorry_for/2, go/3, move/2, move_list/2.

$ теория проблемной области, которая относится к теме вручения подарков

Глава 23. Металрограммирование

gives( Personl, ?erson2, Gift) :-likes( Personl,Person2), would_please( Gift, Person21.

gives( Personl, Persan2, Gift,- :-feels_sorry_for( Personl, Person2), would_coinfort [ Gift, Person2) .

wauld_please( Gift, Person) : -

neecis ( Person, Gift) .

1 would_comfort( Gift, Person) :-

likes[ Person, Gift) .

feels_sorry_for{ Personl, Person2) : -likes ( Personl, Perso:i2) , sad{ Person2).

feels_sorry_for( Person, Person) :-sad( Person;.

i Операционные предикаты

operational{ likes( _, _)) . operational! needs( _, _)) . operati.cr.al ( sad [ _) ) .

Щ Пример проблемной ситуация

likes( John, annie) . likes( annie, John). likes! John, chocolate;, needs( annie, tennis_racket).

sad{ John) .

% Еще одна теория проблемной области, применяемая для описания движений .тифта

i go( Level, GoalLevel, Moves) если

список движений Moves перезолит лифт с этажа Level на этаж GoalLevel

go! Level, GoalLevel, Moves) :-

ncve_list( Moves, Distance!, % Список движений и пройденное расстояние

Distance -:- GoalLevel - Level.

move_list( [] , 0) .

move_list( [Mbvel IMoves], Distance + Distance 1) : -move_list( Moves, Distance), move( Movel, Distancel).

move[ up, 1) . move( down, -1) .

operational! A =:= B) .

В результате выработки доказательства рассматриваемый метаинтерпретатор на­ходит следующее доказательство обоснованности выполненного действия: gives ( John., John, chocolate) <= ( feels_sorry_for{ John, John) <= = sad( John), % Джону стало жалко самого себя,

% поскольку ему грустно, would_comfort{ chocolate, John) <== likes( John, chocolate) % и Джону будет

$ приятно, поскольку он любит шоколад 3

Часть II. Применение языка Prolog в области искусственного интеллекта

Это доказательство может быть обобщено путем замены постоянных John и chocolate переменными следующим образом:

gives( Person, Person, Thing! <== % Человек вручает себе какую-то вещь, если ( feels soi:ry for( Person, Person) <-- sad( Person), I человеку жалко сеОя,

% потому что ему грустно, would^comfort( Thing, Person! <== likes[ Person, Thing) % и человеку Судет

% приятно, поскольку ему нравится эта вешь ) В листинге 23.3 предикаты sad (грустит) и likes (любит) определены как опера­ционные. Теперь может быть получено операционное определение предиката gives путем удаления из дерева доказательства всех узлов, кроме узлов, указанных как "операционные", и корневого узла. Это приводит к получению такого результата:

gives( Person, Person, Thing) <-- % Человек вручает себе какую-то вещь,

( sad[ Person), % если ему грустно

likes [ Person, Thing ) $ и ему нравится эта вещь

)

Таким образом, достаточное условие Condition для предиката gives ( Person, Person, Thing) состоит в следующем: Condition « ( sad( Person), likes( Person, Thing))

Теперь это новое определение можно ввести в первоначальную программу, как показано ниже. asserta ( ( gives( Person, Person, Thing) :- Condition))

В результате получено следующее новое предложение, касающееся предиката gives, для которого требуется оценка только операционных предикатов:

gives( Person, Person, Thing) :-sad( Person) , likes( Person, Thing).

Благодаря обобщению заданного экземпляра gives { John, John, chocolate) было сформировано определение (в операционных терминах) как один из общих слу­чаев применения предиката gives для описания одного из способов самоутешения! Еще одним случаем применения такого понятия может служить результат, получен­ный на основании следующего примера: gives; John, armie, tennis_racket). % Джон вручает Энки теннисную ракетку

В данном случае метод обобщения на основе объяснения приводит к получению такого предложения:

gives[ Personl, Person2, Thing) :- 4 Один человек вручает другому вещь,

likest Personl, Person2), % если он любит э?ого человека,

needs( Person2, Thing]. i а последнему требуется эта вещь

Проблемная область с описанием движений лифта, приведенная в листинге 23.3, является немного более сложной, поэтому проведем с ней эксперименты после реали­зации метода EBG на языке Prolog.

Метод EBG можно запрограммировать как двухэтапный процесс: на первом этапе вырабатывается дерево доказательства для данного примера, а на втором это дерево доказательства обобщается и из него извлекаются "операционные узлы". Для этой цели можно применить описанный выше метаинтерпретатор, который формирует де­ревья доказательства. Но фактически эти два этапа не требуются. Более удобный способ состоит в том, чтобы откорректировать простой метаинтерпретатор, приведен­ный в листинге 23.1, таким образом, чтобы операции обобщения чередовались с опе­рациями доказательства заданного экземпляра. Модифицированный подобным обра­зом метаинтерпретатор, который реализует рассматриваемый метод EBG, будет име­новаться ebg и теперь будет иметь три параметра: ebg( Goal, GenGoal, Condition)

где Goal - заданный пример, который должен быть доказан, GenGoal - обобщен­ная цель. Condition — полученное путем логического вывода достаточное условие

Глава 23. Метапрограммирование

для GenGoal, сформулированное в терминах операционных предикатов. Такой обоб­щающий метаинтерпретатор приведен в листинге 23.4. Для проблемной области с описанием процесса получения подарков {см. листинг 23.3) метаинтерпретатор ebg может быть вызван следующим образом:

?- ebg( gives! John, John, chocolate), gives! X, Y, Z) , Condition]. x = Y Condition - ( sacl( X), likes ( X, Z) )