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

Идея обобщения на основе объяснения впервые была реализована в области ма­шинного обучения, целью которого является обобщение заданных примеров в виде общих описаний рассматриваемых понятий. Одним из способов формирования таких описаний является обобщение на основе объяснения (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 I Moves], 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))