3. Представление

Вид материала

Обзор

Содержание Ante (block x) (assert (on x table))) Conse (mortal x) (goal (man x))). Conse (on x y) Man socrates) Admjre(y, x)).

Подобный материал:

• Вопросы к экзамену по курсу " ЭВМ и периферийные устройства" для групп К2-121, -122,, 75.03kb.
• И представление налоговой отчетности, 357.06kb.
• И представление налоговой отчетности, 394.07kb.
• Дать детям представление о речевом этикете, как о правилах поведения в различных ситуациях;, 241.98kb.
• Дать общее представление о витаминах, познакомить учащихся с их классификацией, представителями, 180.08kb.
• Урок Окружающий мир 2 класс умк «Перспективная начальная школа», 44.76kb.
• Задачи:; развивать обобщенное представление о казахстанцах; сформировать представление, 49.53kb.
• Урок 57 Источники права Цель, 56.46kb.
• Вопросы для подготовки к экзамену по архитектуре ЭВМ, 79.1kb.
• Отчет об оказании юридических услуг за 20 г. Представляют, 89.3kb.

8.4. Процедурная дедукция в системе PLANNER

Система PLANNER явилась одной из первых попыток разработки языка программирования задач искусственного интеллекта, базирующегося на идеях автоматического доказательства теорем. Хотя разработчикам и не удалось в полной мере реализовать задуманное, созданное подмножество языка, получившего название Micro-PLANNER, нашло применение в системах планирования, в частности в программе SHRDLU, представленной в главе 2. Ниже мы обсудим те аспекты системы PLANNER, которые имеют отношение к представлению знаний.

Система PLANNER моделировала состояние некоторой области рассуждений в терминах ассоциативной базы данных, которая содержала как утверждения, так и теоремы, функционирующие как процедуры. Утверждения представляли собой списки типа "предикат-аргумент", подобные тем, что используются в LISP. Например:

(BLOCK B1) (ON Bl TABLE)

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

^ (ANTE (BLOCK X) (ASSERT (ON X TABLE)))

в действительности является процедурой, которая говорит: "Если утверждается, что X это блок, то также утверждается, что X находится на столе". Таким образом, если существует утверждение (BLOCK B1), то можно также считать утверждением и выражение (ON Bl TABLE). Функция ASSERT добавляет собственный конкретизированный аргумент (т.е. аргумент, которому присвоено определенное значение) в базу данных.

Выше был приведен пример антецедентной теоремы. Это название акцентирует внимание на том, что нас интересует только логическая связь между антецедентом и консек-вентом (по аналогии с правилом modus ponens), а не связь между отрицанием консеквен-та и отрицанием антецедента (по аналогии с правилом modus fallens). Мы говорим, что в действительности эта теорема является процедурой, поскольку в ней содержится управляющая информация. Ее функционирование во многом напоминает демонов в системе фреймов, описанных в главе 6.

Система PLANNER поддерживает и другой вид процедур, которые получили наименование консеквентной теоремы. Пример процедуры такого типа приведен ниже:

^ (CONSE (MORTAL X) (GOAL (MAN X))).

Эта процедура может быть прочитана так: "Для того чтобы показать, что X смертен, покажите, что X — человек". Если выражение, которое нужно доказать (цель), сформулировано в виде (MORTAL SOCRATES) (Сократ смертен), то в качестве подцели будет выступать выражение (MAN SOCRATES) (Сократ человек). Функция GOAL организует поиск в базе данных собственного конкретизированного аргумента. Однако не удастся использовать эту теорему для перехода от утверждения (MAN SOCRATES) (Сократ человек) к утверждению (MORTAL SOCRATES) (Сократ смертен).

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

^ (CONSE (ON X Y)

(GOAL (CLEAR X)) (GOAL (CLEAR Y))

(ERASE (ON X Z)) (ASSERT (ON X Y)))

Задавшись целью (ON Bl B2), если на Bl и на В2 ничего не стоит, PLANNER выполнит необходимые операции с базой данных. Таким образом, консеквентная теорема поддерживает в системах автоматизации планирования работу механизма реализации операторов, подобных тем, которые мы видели в программе STRIPS (см. главу 3).

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

С концепцией процедурной дедукции связана проблема полноты. Система доказательства является полной, если все тавтологии, т.е. тривиально истинные выражения вроде (р v —pi), могут быть выведены в ней как теоремы. В системе PLANNER это свойство отсутствует. Мы уже обращали внимание на то, что нельзя сформировать выражение (MORTAL SOCRATES) из базы данных, в которой содержатся

^ (MAN SOCRATES)

(CONSE (MORTAL X)

(GOAL (MAN X))).

Это те издержки, с которыми нужно смириться, если мы хотим объединить управляющую информацию с пропозициональным представлением. К сожалению, система PLANNER оказалась не более эффективной, чем системы, основанные на теоремах резолюций. Это произошло потому, что использованная в ней управляющая информация страдает "близорукостью", отсутствует общая стратегия, а имеющийся набор теорем позволяет формулировать локальные решения, которые могут давать, а могут и не давать желаемый эффект. Отсутствует в PLANNER и возможность каким-то образом формировать суждения о механизме управления, что-то вроде метаправил, о которых шла речь в главе 5.

В следующем разделе мы кратко остановимся на системах, в которых была предпринята попытка устранить эти недостатки

8.5. PROLOG и MBASE

Ранее мы уже видели, что фразу, содержащую предположение, можно представить с помощью исчисления предикатов первого порядка. Фраза

"Если философ выиграет у кого-нибудь в забеге, то этот человек будет им восхищен" в формализме предикатов приобретет вид формулы

(любой A) (любой Y)(PHILOSOPHER(X)^BEATS(X, Y)^ ADMJRE(Y, X)).

Эту формулу можно представить в конъюнктивной нормальной форме следующим образом:

{ADMIRE(Y, X), -ВЕАТS(Х, Y), ->PHILOSOPHER(X)}.

Также было показано, что если записать это выражение таким образом, чтобы слева от оператора ":-" стоял единственный позитивный литерал, а справа — негативные литералы, то получится выражение, представляющее фразу Хорна в синтаксисе языка логического программирования PROLOG:

admire (Y, X) :- philosopher ( X) , beats (X,Y).

Ниже мы рассмотрим, как организовать управление применением таких правил.

8.5.1. Правила поиска в языке PROLOG

Существует аналогия между выражениями вида

admire(Y, X) :- philosopher (X) , beats (X,Y)

в языке PROLOG и консеквентной теоремой в системе PLANNER. При запросе "who admires whom?" ("кто кем восхищается?"), который может быть представлен в виде фразы

:- admire(V, W). ,

приведенное выше выражение интерпретируется следующим образом: "Для того чтобы показать, что Y восхищается X, покажите, что X является философом, а затем покажите, что X обогнал Y".

Цель, которая унифицируется с выражением admire(Y, X), может быть истолкована как вызов процедуры, а процесс унификации может рассматриваться как механизм передачи действительных параметров другим литералам, образующим тело процедуры. В данном случае не имеет значения, являются ли эти "параметры" переменными, как в представленном примере. Подцели в теле процедуры упорядочены. В языке PROLOG такое упорядочение называется правилом поиска слева направо.

В PLANNER и ранних системах, основанных на методе резолюций, цель легко достигается, если в базе данных содержатся утверждения

philosopher (zeno) . beats (zeno, achilles).

Тогда получим ответ

admire (achilles, zeno).

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

philosopher ( socrates ) .

В этом случае, если эта формула отыщется прежде, чем формула

philosopher(zeno).,

обработка следующей подцели приведет к неудаче, а следовательно, нужно будет поискать другого философа. Объем работы, который придется выполнить системе в процессе достижения цели admire(V, W), зависит от количества альтернативных вариантов утверждений, касающихся философов, которые имеются в базе данных.

Предположим, что в базе данных содержатся факты еще о ста философах, т.е. в ней имеются сто других выражений в формате philosopher(X), в которых X отличается от zeno. Тогда в худшем случае программе потребуется 100 раз выполнить обратный просмотр, прежде чем будет найдено именно то утверждение, которое согласуется с целью.

База данных может содержать и другие правила, которые взаимодействуют с интересующим нас выражением admire (V, W). Например, можно положить, что утверждение "X обогнал Y" представляет транзитивное отношение. В этом случае в нашем распоряжении будет правило

beats(X, Y) :- beats(X, Z), beatsf Z, Y).

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

philosopher(X) :- beats(Y, X), tortoise(Y).

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

В следующем разделе описано одно из расширений языка PROLOG— система MBASE, на базе которой реализована программа МЕСНО для решения задач вузовского курса теоретической механики

8.5.2. Управление поиском в системе MBASE

Один из распространенных способов управления поиском в применении к доказательству какого-либо утверждения — тщательное упорядочение базы данных. При поиске нужных фактов или правил исполнительная система языка PROLOG просматривает базу данных от начала до конца. Используя это обстоятельство, можно несколько сократить время доказательства.

Определенные факты (основные атомы — ground atoms) нужно разместить в базе данных раньше, чем правила, которые в качестве цели имеют соответствующие предикаты. Таким образом будут минимизированы издержки обращения к правилам. Например, утверждение

beats(achilles, zeno).

должно стоять раньше правила

beats(X, Y) :- beats(X, Z), beats( Z, Y).

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

flies(X) :- penguin(X), !, fail .

должно стоять раньше общего правила, гласящего, что птицы летают,

flies(X) :- bird(X).

Литерал fail представляет собой один из способов выражения отрицания в языке PROLOG. Кроме того, в языке PROLOG имеется литерал !, который называется "отсечением". Этот литерал говорит исполнительной системе PROLOG, что не нужно осуществлять возврат из этой точки. Комбинация литералов представляет эффективный механизм управления обратным просмотром, предотвращая выполнение ненужных операций.

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

pacifist(X) :- quaker(X).

должна появиться после всех фраз вида

pacifist(nixon) :- !, fail.

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

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

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

Обращение к базе данных (DBC — database call). Этот режим ограничивает зону поиска только основными литералами в базе данных и таким образом исключает применение правил. Для настройки этого режима нужно включить основной литерал в предикат ВВС. Например, факт, что b1 является блоком, будет представлен фразой

DBC(block(b1)).

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

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

at(Block, Placel) :-

DEC(at(Block, Place2)), different(Placel, Place2), !, fail.

Обратите внимание на то, что если бы в теле процедуры отсутствовал предикат ВВС, то программа очень быстро зациклилась.

Вызов правил влияния (DBINF — inference call) — это обычный режим работы исполнительной системы PROLOG с использованием всех имеющихся правил. При этом соблюдаются соглашения о порядке поиска в базе сверху вниз, а в правиле слева направо.

Порождающий вызов (СС — creative call). В этом режиме формируются место-держатели для неизвестных и выполняются вычисления в тех случаях, когда обычный режим может привести к неудаче. Режим используется для математических вычислений, когда отсутствуют значения всех переменных в уравнении.

С помощью литералов 1 и fail обычно определяется отрицание определенной процедуры, например, так:

not(P) :- call(P) !, fail. not(P) .

В языке PROLOG специальный предикат call обрабатывает цель, переданную ему в качестве параметра. Идея состоит в том, что если такая обработка приведет к успеху, то отрицание цели приведет к неудаче, а литерал отсечения предотвратит обратный просмотр. В противном случае мы перейдем ко второй фразе, и отрицание цели очевидно приведет к успеху.

Некоторые из проблем полноты, отмеченные в системе PLANNER, существуют и в языке PROLOG. В частности, использование литералов отсечения и неудачи может серьезно сказаться на полноте и согласованности фактов и правил. Существует множество способов внедрения отрицаний в логику фразы Хорна, но условия, при которых это можно сделать, весьма ограничены (см., например, [Shepherdson, 1984], [Shepherdson, 1985]).

Тем не менее исследователи пришли к выводу, что описанный выше механизм управления далеко не всегда может привести процесс вычислений к искомому заключению, поскольку не обладает достаточной "глобальностью". Проблема состоит в том, что все описанные методы базируются все-таки на довольно ограниченных, локальных знаниях о текущем состоянии процесса вычислений. В MBASE была предпринята попытка дополнить локальное управление двумя механизмами— схематизацией (schemata) и мета-предикатами. О них-то и пойдет речь ниже.

Под схематизацией подразумеваются ассоциативные механизмы, которые используются в основном для представления в компьютере знаний общего характера. Например, ниже приведено представление знаний о системе подъема грузов на основе ворота (pulley system):

sysinfo(pullsys,

[Pull, Str, P1, P2],

[pulley, string, solid, solid]

[ supports(Pull, Str),

attached(Str, Pi),

attached(Str, P2) ]).

Предикат sysinfo принимает четыре аргумента, каждый из которых аналогичен слоту в системе фреймов (см. об этом в главе 6):

первый аргумент, pullsys, свидетельствует о том, что эта схема представляет типовую систему подъема грузов с воротом и, таким образом, аналогичен слоту наименования;

второй аргумент, [Pull, Str, P1, P2], является перечнем деталей в этом механизме — ворот, трос и два груза;

третий аргумент, [pulley, string, solid, solid], содержит информацию о типе этих компонентов;

четвертый аргумент содержит список отношений (связей) между компонентами.

Обратите внимание на то, что в этом представлении нет никакой пропозиционально-сти, например сведений о том, каким способом можно неявно сопоставить два списка. По существу, это представление очень похоже на описание фрейма (но вряд ли с ним можно работать так же эффективно).

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

kind(al, accel, relaccel(...)).

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

relates(accel, [resolve, constaccel, relaccel)).

означает, что формулы resolve, constaccel и relaccel содержат переменные типа accel и, следовательно, могут быть использованы для вычисления ускорения. Приведенные выражения можно рассматривать как один из видов дополнительного индексирования в ассоциативной сети. В данном случае индексирование представлено в форме логики, причем используются структуры, обычно редко встречающиеся в исчислении предикатов первого порядка.

Роль метапредикатов состоит в отборе правил, наиболее подходящих для вывода конкретной цели. Рассмотрим следующий пример:

solve(U, Exprl, Ans) :-

occur)U, Exprl, 2), collect(U, Exprl, Expr2), isolate(U, Expr2, Ans).

Эта процедура означает, что Ans является уравнением, которое решается относительно неизвестного U в выражении Exprl, если

в выражение Exprl неизвестная U входит дважды:

выражение Ехрг2 представляет собой Exprl, в котором выполнено приведение неизвестной U;

Ans является выражением Ехрг2, в котором неизвестная U вынесена в левую часть.

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

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

В главе 23 мы увидим, что, несмотря на существование определенных проблем при использовании концепций логического программирования и основанного на них языка PROLOG, эта концепция имеет приложение в двух других областях исследований, которые представляют интерес с точки зрения экспертных систем, а именно: обобщение на базе объяснения (explanation-based generalization) и логический вывод на метауровне (meta-level inference). Обобщение на базе объяснения используется для машинного обучения, а логический вывод на метауровне позволяет программе строить суждения о собственном поведении.