Автоматическое программирование в системе XPLAN

Хотя трассировка активизации правил и дает информацию о поведении системы, сама по себе она не может объяснить мотивов этого поведения [Swartout, 1983]. Это объясняется тем, что мотивация поведения является частью знаний, используемых при построении и внедрении программы, и она нигде не представлена явно в виде программного кода. Другими словами, те "знания как", которые заложены в конструкции системы, т.е. принципы логического вывода суждений, как правило, смешаны со "знанием что", т.е. моделью той предметной области, на работу в которой ориентирована конкретная экспертная система. В основу проектирования системы XPLAN, созданной Свотаутом (Swartout), была положена простая, но вместе с тем продуктивная идея увязать процесс разработки экспертной системы с процессом формирования пояснений. Один из методов проектирования экспертных консультирующих систем состоит в том, чтобы выработать спецификацию модели предметной области, включив в нее и принципы функционирования объектов этой области, а затем воспользоваться услугами "автоматического программиста" и сформировать по этой спецификации собственно программу экспертной системы. Предписывающие и описывающие компоненты спецификации объединяются таким образом в единую систему и используются затем для формирования пояснений в процессе функционирования этой системы.

Модель предметной области содержит сведения, касающиеся специфики области приложения экспертной системы, в частности сведения о причинно-следственных связях и систематике объектов в этой области. Эта концепция достаточно близка тому, что Кленси (Clancy) назвал "структурным знанием" (см. об этом в главе 12). Подобные знания лежат в основе системы правил, регламентирующих действия в определенных ситуациях. Но модель предметной области включает и такие методы и эвристики, которые обычно жестко "встраиваются" в интерпретатор экспертной системы или передаются интерпретатору в качестве метаправил. Этот вид знаний в терминологии Кленси получил наименование стратегических. Свотаут отметил, что такое разделение видов знаний положительно сказывается на производительности экспертной системы при выполнении большинства функций, исключая функцию формирования пояснений.



Свотаут собрал информацию о тех вопросах, которые задают студенты-медики при работе с консультирующей системой Digitalis Therapy Advisor. В собранном массиве он выделил три базовые группы.

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

Вопросы, касающиеся причин принятия программой того или иного решения. Например, почему программа рекомендует именно такой, а не иной курс лечения.

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

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

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


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

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

Формирование пояснений

и автоматическое программирование

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

В этом разделе мы остановимся на двух экспертных системах, XPLAN и PEA, при разработке которых создатели попытались решить указанные проблемы, воспользовавшись специальной программой-оболочкой. Работы выполнялись в рамках исследовательского проекта EES — Explainable Expert Systems (экспертные системы, способные давать пояснения).

Формирование пояснений носнове фреймов

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

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

Формирование пояснений носнове знаний

На начальном этапе исследований в области экспертных систем, которые выполнялись в Станфордском университете в 60-70-х годах/поясняющая информация предоставлялась в виде трассировки процесса выполнения программы и использовалась в основном для отладки разрабатываемых систем. Этого было достаточно для разработчиков экспериментальных систем, подобных MYCIN, но не соответствовало тому уровню сервиса пользователя, который необходим для коммерческого программного продукта. Впоследствии вопросу формирования информации, которая давала бы возможность пользователю четко представить себе ход рассуждений программы, стало уделяться значительно больше внимания.

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

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

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

Формирование пояснений в системах, производных от MYCIN

Вряд ли для кого-нибудь является секретом, что по мере увеличения размеров базы знаний в экспертной системе проблемы понимания ее поведения, оперативного наблюдения и корректировки поведения нарастают как, снежный ком (см., например, [Davis, 1980, b]). Например, бывает трудно обеспечить полную совместимость новых правил с включенными ранее в базу знаний или разобрать в потоке управления в тех ситуациях, когда большое число конкурирующих друг с другом правил пытается "обратить на себя внимание" интерпретатора. Исследователям пришлось немало потрудиться над проблемой обнаружения противоречивости и преодоления избыточности множества правил (см. в [Suwa et al, 1980, b]).

Система EMYCIN (Empty MYCIN — пустая MYCIN) представляет собой оболочку, созданную на базе системы MYCIN [van Melle, 1981]. Идея состояла в том, чтобы удалить из системы MYCIN базу знаний и создать таким образом систему, сохраняющую все функциональные возможности MYCIN, которую в дальнейшем можно наполнять знаниями из той или иной предметной области (подробнее об этом см. в главе 10). В процессе разработки в EMYCIN были внесены некоторые усовершенствования по сравнению с прототипом. Для облегчения работы инженеров по знаниям в ходе отладки новой базы знаний в систему включены команды EXPLAIN (объяснение), TEST (проверка) и REVIEW (просмотр). Как и в MYCIN, команда EXPLAIN выводит на печать список тех правил, которые были активизированы в процессе сеанса работы. При этом выводится еще и дополнительная информация:

(1) значение коэффициента уверенности, полученное в результате выполнения правила;

(2) значения условий, специфицированных в активизированном правиле;

(3) последний вопрос, который задавала система пользователю перед тем, как сформировать заключение.

Использование в MYCIN и EMYCIN метаправил, которые позволяют в явной форме управлять выбором активизируемых правил, создает предпосылки для анализа пользователем стратегии поведения экспертной системы в процессе формирования рекомендаций.
Теперь можно было задуматься и над тем, как отразить применение метаправил в формируемых пояснениях, — предоставить пользователю информацию о том, почему в данной ситуации из множества возможных правил система выбрала именно это, а остальные отвергла.

В конце 1970-х годов в Станфорде на основе ранее созданных систем была разработана усовершенствованная программа NEOMYCIN, в которой была предпринята попытка использовать более абстрактный подход к решению медицинских проблем, чем в прототипе, все в той же MYCIN [Clancey and Letsinger, 1984], [Clancey, 1987, с]. В центре внимания разработчиков оказались те знания, которыми пользуются врачи-практики при рутинной процедуре диагностики, и связанный с ними ход рассуждений. Таким образом, было уделено значительное внимание моделированию того метода решения проблемы, который присущ человеку (так называемое когнитивное моделирование). Тот метод логического вывода, который был использован в системе-прототипе MYCIN, вряд ли придет в голову кому-либо из практикующих врачей — совпадают у них только результаты.

Этот новый подход отразился и на средствах формирования пояснений. В NEOMYCIN упор был сделан на пояснении стратегии поведения системы — предоставлении пользователю информации об общем плане решения проблемы и методах, использованных для достижения поставленной цели, а не просто перечислении правил, активизированных в процессе работы [Hasting et al., 1984]. В процессе накопления и интерпретации данных в центре внимания постоянно находилось текущее множество гипотез (дифференциал — термин, производный от дифференциального диагностирования). Для того чтобы разобраться в поведении программы, т.е. в вопросах, которые ставит программа, и в потоке управления, пользователю нужен доступ к стратегии диагностирования, которую использует программа.

Основные принципы организации системы NEOMYCIN следующие.

Стратегические знания отделены от собственно медицинских и представлены в виде метаправил.

Информация о заболеваниях имеет таксономическую организацию, как в системе INTERNIST, и таким образом обеспечено в некотором роде явное представление пространства гипотез.



Знания перечисленных выше типов отделены от правил, которые связывают гипотезы с данными.

Таким образом, основным является все-таки подход на базе эвристической классификации (см. об этом в главах 11 и 12), но смешанная схема представления структур данных и управления использованием правил упрощает реализацию процесса. Кроме того, правила, относящиеся к предметной области, в свою очередь, разделены на четыре класса.

Причинные правила связывают симптомы и гипотезы через сеть симптомов и категорий заболеваний.

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

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

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

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

METARULE397

ЕСЛИ: В дифференциале имеются два элемента, которые отличаются какими-либо характеристиками заболевания, ТО: Задать вопрос, который позволит выяснить отличие этих заболеваний.

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

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


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

В дополнение к правилам, которые запрашивают конкретные данные у пользователя, в NEOMYCIN существуют и правила, управляющие процессом опроса пользователя. Эти правила цитируются при формировании пояснения, почему пользователю был задан конкретный вопрос.

Другой вариант модернизации системы MYCIN был осуществлен в 1970-х годах и вылился в создание системы CENTAUR [Aikins, 1983]. В этой программе (см. главу 13) используется смешанное представление знаний, заимствованных из ранее созданной экспертной системы PUFF, предназначенной для диагностики легочных заболеваний. В архитектуре системы CENTAUR фреймы (см. главу 6) и порождающие правила (см. главу 6) объединены таким образом, что это значительно упрощает формирование пояснений.

Использование мультимедийного интерфейсдля формирования пояснений

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

Один из способов дополнить и расширить возможности формирования пояснений в системах, базирующихся на представлении знаний в виде фреймов, — добавить в них возможность формирования изображений. В системе JETA [Abu-Hakima et al., 1993] привычный текстовый интерфейс, подобный тому, который использовался при формировании пояснений в системе CENTAUR, был дополнен изображениями диаграмм в виде схем и графов. В основу архитектуры системы JETA положена трехуровневая структура фреймов (рис. 16.2). Два уровня фреймов — диагностики и параметров — аналогичны фреймам системы CENTAUR. Третий уровень — уровень фреймов глоссария (glossary frames) — поддерживает функционирование двух первых и содержит маркеры гипертекста. Фреймы этой группы предназначены специально для формирования пояснений и поддержки системы оперативной справки, касающейся функционирования фреймов других уровней. Назначение экспертной системы JETA — определение причин отклонений в работе реактивных двигателей.

Рис. 16.2. Трехуровневая структура фреймов экспертной системы JETA

В исследовательской системе COMET [Feiner and McKeown, 1991] была предпринята попытка реализовать обширную интеграцию средств формирования пояснений со средствами представления знаний и формирования суждений.
В этой системе изображения и текст не просто "законсервированы", а генерируются с помощью трех баз знаний:

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

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

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

Например, для проверки удаленного модуля ввода/вывода приемопередающей станции нужно выполнить следующие операции, оговоренные в инструкции.

(1) Нажать кнопку ВАТТ/CALL на передней панели.

(2) Настроить приемопередатчик, используя для этого переносной пульт.

(3) Проверить, появилась ли на табло надпись CALL.

В системе такая инструкция для пользователя озвучивается и снабжается иллюстрацией в виде анимации. Для этого координированно выполняются две последовательности операций — одна формирует звук (V), а другая — динамическое изображение (А):

V: Нажмите и удерживайте кнопку ВАТТ/CALL.

А: На экране увеличивается изображение клавиатуры и табло и крупным планом выделяется кнопка BAIT/CALL

V: Удерживая кнопку, настройте приемопередатчик.

А: На экране крупным планом выводится переносной пульт.

V: Одновременно следите за надписью на табло.

А: На экране подсвечивается изображение табло.

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

Организация выводпояснений в системе CENTAUR

Первый вариант реализации системы PUFF, который был выполнен на основе оболочки EMYCIN (см., например, [Aikins et al., 1984]), оказался вполне работоспособным в том смысле, что хорошо справлялся с решением проблем в своей области, но схема представления знаний в нем не совсем удовлетворила разработчиков по следующим причинам.

С ее помощью трудно представлять типовые образцы данных или типичные классы пациентов.

Добавление или модификация правил при расширении базы знаний или уточнении ранее введенных знаний требовали слишком больших затрат.

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

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

Эйкинс (Aikins) также обратила внимание на то, что отчетливо выраженная модульность и единообразие порождающих правил имеет и обратную сторону. Большинство наборов правил обладает неявно выраженной группировкой, которая существует либо в виде определенного порядка индексации, скрытой в интерпретаторе (например, в наборе ORGRULES и PATRULES системы MYCIN, которые относятся к микроорганизмам и пациентам соответственно), либо в виде условий и операций, которые манипулируют лексемами целей в рабочей памяти. Такая организация зачастую имеет иерархический характер, предполагающий таксономический характер организации гипотез (в задачах классификации) и декомпозицию целей на подцели (в задачах конструирования). Многие из упомянутых выше проблем можно свести к минимуму, выделив отдельные виды знаний и манипулируя ими по-разному. Как вы помните из главы 13, в системе CENTAUR разработчики объединили методы программирования, основанные на правилах и концепции фреймов, таким образом, чтобы компенсировать слабости каждого из подходов и усилить их достоинства.



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

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

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

В ходе выполнения программы прототип находится в одном из трех возможных состояний:

неактивный, т.е. не рассматриваемый в качестве гипотезы;

потенциальный кандидат, т.е. такой, который имеет смысл рассмотреть исходя из имеющихся значений данных;

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

Прототипы заболеваний представляют гипотезы! Список гипотез — это, по сути, список пар "прототип-коэффициент уверенности", упорядоченных в убывающем порядке значений коэффициентов уверенности.


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

Основные события в сеансе выполнения консультации с помощью системы CENTAUR следующие:

ввод исходных данных;

отбор прототипов с использованием антецедентных правил;

оценка прототипов и выбор единственного, который назначается "текущим";

анализ известных фактов и заполнение на их основе полей данных текущего прототипа;

проверка соответствия фактов и ожидаемых значений;

выявление данных, не учтенных начальным вариантом диагноза;

уточнение диагноза на основе выявленных данных;

суммирование и вывод результатов.

В самом начале сеанса в качестве текущего выбирается прототип CONSULTATION (консультация), а в список активных включаются две задачи текущего прототипа: FILL-IN (заполнение) и CONFIRM (подтверждение), которые извлекаются из управляющих слотов TO-FILL-IN и IF-CONFIRMED прототипа. Структура слотов прототипа CONSULTATION представлена ниже.

CONSULTATION

....................

TO-FILL-IN:

Запросить значение

TRACING-LEVEL для задачи

CONSULTATKDN Запросить значение

AGENTA-PRINTING для задачи

CONSULTATION Запросить значение

STRATEGY для задачи

CONSULTATION

IF-CONFIRMED:

Установить порог подтверждения равным 0

Установить относительное заполнение слотов, необходимое для подтверждения прототипа, равным 0.75

Установить процедуру по умолчанию для заполнения слотов: заполнение в убывающем порядке по степени важности Определить предмет консультации Выбрать лучший из текущих прототипов Заполнить прототип

Применить задачи из слота IF-CONFIRMED прототипа Отметить все факты, принимаемые во внимание прототипом Применить правила уточнения, связанные с подтвержденными прототипами; применить правила подведения итога, связанные с подтвержденными прототипами; выполнить операции, связанные с подтвержденными прототипами

Слот TO-FILL-IN прототипа фактически содержит три подзадачи, каждая из которых устанавливает определенную переменную сеанса консультаций: переменная TRACING-LEVEL задает уровень детализации трассировки, переменная AGENTA-PRINTING указывает, будут ли выводиться на печать наименования задач по мере включения их в список активных или по мере выполнения, а переменная STRATEGY может принимать значения CONFIRMATION (выбор наилучшего варианта и подтверждение его), или ELIMINATION (выбор наихудшего варианта и исключение его), или FIXED-ORDER (использование предопределенного порядка обработки гипотез).



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

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

------ПАЦИЕНТ-7 -------------

1) Идентификационный номер пациента: 7446

2) По поводу какого заболевания: АСТМА

[Прототип ASTHMA, МП 900]

3) ООЛ/ООЛ предсказываемый:

261

4) ОЕЛ (плетизмографическая) наблюдаемая/предсказываемая: 139

5) ФЖЕ/ФЖЕ предсказываемая:

81

[Прототип NORMAL, МП 500]

6) Отношение ОФВ1/ФЖЕ: 40

[Прототип ОАО, МП 900]

7) ПСОУ/ПСОУ предсказываемая: 117

[Прототип NORMAL, МП 7dO]

8) Изменение в ОФВ1 (после приема бронхолитиков): 31

9) УПМС/УПМС предсказываемая:

12

[Прототип ОАО, МП 900]

10) Наклон П5025: 9

[Прототип ОАО, МП 900]

Рассмотрим подробнее один из вопросов в этом протоколе.

6) Отношение ОФВ1/ФЖЕ: 40 [Прототип ОАО, КУ900]

Аббревиатуры в этих строках обозначают найденные прототипы заболеваний, МП означает "мера правдоподобия", ООЛ, ОЕЛ, ФВЖ и т.д.


— результаты лабораторных анализов и измерения легочных функций:

ООЛ — остаточный объем легких, литры;

ОЕЛ — общая емкость легких, литры;

ФУКЕ — форсированная жизненная емкость легких, литры;

ОФВ1 — объем форсированного выдоха за 1 с, литры;

ПСОУ — проникающая способность для окиси углерода.

Введенное пользователем значение 40 отношения объема форсированного выдоха за 1 с (ОФВ1) к форсированной жизненной емкости легких (ФЖЕ) побуждает систему активизировать прототип ОАО (Obstructive Airways Dicease — обтурация воздухоносных путей) с мерой правдоподобности этой гипотезы 900.

Значение меры правдоподобия той или иной гипотезы выбирается в диапазоне от -1000 до 1000 исключительно из соображений упрощения вычислений. Этот параметр отражает степень уверенности системы в обоснованности выдвинутой (активизированной) гипотезы на основе имеющихся данных о конкретной истории болезни. Фактически при определении меры правдоподобия система сравнивает введенные пользователем данные с теми, которые хранятся в слотах прототипа-кандидата. Полученные значения служат основанием для выбора самой правдоподобной из имеющихся гипотез (прототипов). Назначение параметра "мера правдоподобия" в системе CENTAUR такое же, как и коэффициента уверенности в системах MYCIN и EMYCIN, причем для операций с мерами правдоподобия используются те же алгоритмы, что и для операций с коэффициентами уверенности. Обратите внимание — в процессе диалога с пользователем система не объясняет, почему выбрано именно такое, а не иное значение меры правдоподобия. Для пользователя алгоритм вычисления меры правдоподобия является "черным ящиком".

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


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

После завершения диалога система предъявляет пользователю свои "соображения" по поводу введенных данных.

Гипотеза: ASTHMA, МП: 900. Причина: предыдущий диагноз — АСТМА

Гипотеза: NORMAL, МП: 500. Причина: ФЖЕ равно 81

Гипотеза: ОАО, МП: 900. Причина: отношение ОФВ1/ФЖЕ равно 40

Гипотеза: NORMAL, МП: 700. Причина: ПСОУ равно 117

Гипотеза: ОАО, МП: 900. Причина: УПМС равно 12

Гипотеза: ОАО, МП: 900. Причина: наклон П5025 равен 9

Наиболее правдоподобные гипотезы: NORMAL, ОАО [Новые анализируемые прототипы: NORMAL, ОАО]

Из этой распечатки следует, что далее система сосредоточится на двух наиболее правдоподобных гипотезах: NORMAL и OAD. Эти две гипотезы являются непосредственными "наследниками" прототипа PULMONARY-DISEASE. Рассмотрение гипотезы ASTHMA на время откладывается по той причине, что она является подтипом гипотезы OAD. Эта гипотеза будет рассмотрена в процессе уточнения гипотезы OAD, в полном соответствии со стратегией нисходящего уточнения. Иерархическая структура пространства гипотез позволяет дать пользователю полную и ясную информацию о том, как эта стратегия претворяется в жизнь в экспертной системе. В системах, полностью основанных на правилах, пользователь должен представлять себе ту стратегию разрешения конфликтов между конкурирующими правилами, которая используется в системе, и только тогда он сможет понять, почему в определенной ситуации было отдано предпочтение именно той гипотезе, которая зафиксирована в распечатке результата трассировки, а не какой-либо иной.

Обратите внимание — не все данные, введенные пользователем в ходе начального диалога, приводят к выбору гипотез-кандидатов, а в список гипотез-кандидатов попадает несколько прототипов. При заполнении данными отобранных в этом списке двух гипотез — NORMAL и OAD — такой параметр, как ОЕЛ (общая емкость легких), который в ходе диалога не повлиял на начальный список, будет учтен и, вполне возможно, повлияет на значение меры правдоподобия анализируемой гипотезы.


Значение этого параметра (139) заставляет систему подвергнуть сомнению правдоподобность гипотезы NORMAL, как будет показано ниже в примере распечатки значений тех параметров, которые привели систему "в замешательство". Данные, которые "не вписываются" в диапазон, представленный в слотах определенных прототипов, заставляют систему снижать меру правдоподобия соответствующей гипотезы.

!.Неожиданное значение: ООЛ равно 261 в NORMAL, МП: 700

!Неожиданное значение: ОЕЛ равно 139 в NORMAL, МП: 400

!Неожиданное значение: ОФВ1/ФЖЕ равно 40 в NORMAL, МП: -176

!Неожиданное значение: УПМС равно 12 в NORMAL, МП: -499

!Неожиданное значение: П5025 равно 9 в NORMAL, МП: -699

Из представленной распечатки видно, что, хотя по итогам предварительного экспресс-анализа введенных данных гипотеза NORMAL представлялась весьма правдоподобной, более подробное исследование всей совокупности данных, в частности пяти параметров, включенных в распечатку, заставило систему весьма засомневаться в ее обоснованности. Всю эту информацию пользователь может почерпнуть из распечаток, которые система CENTAUR выводит в процессе работы. Затем формируется список гипотез, который упорядочивается в порядке убывания, причем на первом месте оказывается прототип ОАО:

Список гипотез: (ОАО 999) (NORMAL -699)

Проверяется гипотеза ОАО (ОБТУРАЦИЯ ВОЗДУХОНОСНЫХ ПУТЕЙ)

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

[Выполнение уточняющих правил ...]

20) Число "пачко-лет" курения: 17

21) Как давно пациент бросил курить: 0



22) Степень затруднения дыхания: НЕТ

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

[Выполняются действия, заданные в слоте ACTION прототипа ОАО ...]

Заключение: показания, свидетельствующие в пользу диагноза "Обтурация воздухоносных путей", следующие:

Увеличенные объемы легких указывают на гипернаполнение.

Увеличенное значение отношения ООЛ/ОЕЛ согласуется с наличием тяжелой обтура-ции воздухоносных путей. Форсированная жизненная емкость в норме, но отношение ОФВ1/ФЖЕ понижено, что указывает на обтурацию воздухоносных путей в тяжелой форме.

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

После приема бронхолитиков улучшается проходимость воздухоносных путей, что подтверждается изменением значения ОФВ1.

После приема бронхолитиков улучшается проходимость воздухоносных путей, что подтверждается изменением значения УПМС.

Обратимость обтурации воздухоносных путей подтверждается улучшением проходимости после приема бронхолитиков.

Эти правила суммируют информацию, собранную в процессе диалогового "обследования" пациента, и не требуют никакой ответной реакции со стороны пользователя.

Пример окончательного заключения, которое выполняется правилами, хранящимися в слоте ACTION прототипа PULMONARY-DISEASE, представлен ниже.

[Выполняются действия, заданные в слоте ACTION прототипа PULMONARY-DISEASE ...]

-------Заключение--------

— Обтурация воздухоносных путей------

Диагноз "Обтурация воздухоносных путей" сделан на основании следующих фактов:

Отношение ОФВ1/ФЖЕ для ПАЦИЕНТА-7: 40

Отношение УПМС/УПМС-предсказываемая для ПАЦИЕНТА-7: 12



Значение наклона П5025 для ПАЦИЁНТА-7: 9

Кроме того, диагноз " Обтурация воздухоносных путей" согласуется со следующими

данными:

Отношение ОЕЛ/ОЕЛ-предсказываемая для ПАЦИЕНТА-7: 139

Отношение ООЛ/ООЛ-предсказываемая для ПАЦИЕНТА-7: 261

Значение П25 для ПАЦИЕНТА-7: 45

Степень затруднения дыхания для ПАЦИЕНТА-7: НЕТ

Интенсивность кашля для ПАЦИЕНТА-7: НЕТ

При установлении диагноза "Обтурация воздухоносных путей" должны приниматься во внимание следующие показания:

Ранее поставленный диагноз для ПАЦИЕНТА-7

Отношение ОФВ1/ФЖЕ для ПАЦИЕНТА-7

Значение П25 для ПАЦИЕНТА-7

Степень затруднения дыхания для ПАЦИЕНТА-7

Интенсивность кашля для ПАЦИЕНТА-7

Все указанные факты были приняты во внимание при подтверждении прототипа.

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

Диагноз: обтурация воздухоносных путей астматического типа в серьезной форме. Консультация завершена.

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

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



Эйкинс отметила наличие четырех принципиальных недостатков в том виде пояснений, которые формируются в программе EMYCIN.

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

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

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

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

Система CENTAUR задает пользователю вопросы в том случае, когда ей не удается выделить необходимую информацию из правил или когда она нуждается в значениях параметров, помеченных в правилах маркером "ask-first" (сначала спроси). Вопросы, которые пользователь может задавать системе CENTAUR, по своему характеру напоминают вопросы "КАК" и "ПОЧЕМУ", которые возможны и при работе с системой EMYCIN, но они интерпретируются в зависимости от текущей стадии процесса консультации. Так, вопрос "ПОЧЕМУ", заданный в контексте конкретного прототипа в ходе выполнения этапа формирования диагноза, будет интерпретироваться как "Почему рассматривается именно данный прототип?" Такой же вопрос на этапе просмотра исходных данных будет интерпретироваться по-другому: "Почему данный прототип подтверждается?" Система CENTAUR всегда предоставляет пользователю информацию о текущем прототипе, а потому пользователь всегда может ориентироваться, в каком контексте программа задает тот или иной вопрос.

Система CENTAUR включает в протокол формирования заключения не только список подтвержденных прототипов, но и множество дополнительной информации:



данные, которые побудили ее рассматривать каждый прототип;

данные, согласующиеся с каждым прототипом;

данные, противоречащие каждому прототипу;

данные, не принятые во внимание ни одним из прототипов.

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

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

Перспективы дальнейших исследований методов формирования пояснений

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

Проект EES служит хорошим примером одного из направлений в современной методологии инженерии знаний, которое предполагает разделение процесса на этапы спецификации знаний и компиляции системы. Но пока что совершенно неясно, как такая методология может справиться с задачей комбинирования разных стратегий решения проблем в рамках единой системы (как это выполняется, например, в системе CENTAUR). Основная сложность в использовании этой методологии — большой объем предыстории разработки и необходимость использования чрезвычайно мощного генератора программ (см. об этом в [Neches et al, 1985]). Альтернативой такому подходу является усложнение интерпретатора включением в него мощных управляющих примитивов. В результате предыстория разработки сокращается и снижаются требования к функциональным возможностям генератора программ, но информация о принятии решений, касающихся поведения программы, оказывается спрятанной в программном коде интерпретатора. Интересно звучит предложение дополнительно нагрузить генератор программ — заставить его формировать и интерпретатор, и информацию, необходимую для формирования пояснений относительно управляющих функций. Это должно привести к еще большему разделению управляющих знаний и знаний о предметной абласти, но, предположительно, одновременно поставит перед разработчиками множество проблем, связанных с интеграцией компонентов системы.

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

(1) дифференциация знаний;

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

(3) моделирование индивидуального уровня подготовки пользователя, работающего с экспертной системой.

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

Планирование текстов пояснений и модели пользователей в PEA

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

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

Сценарии образуют слишком "жесткую" конструкцию, в которую сложно втиснуть подходящие по смыслу ответы на запросы пользователя.

Вместо сценариев Мур использовал операторы планирования, в которых специфицируются определенные цели диалогового процесса, например передать пользователю информацию о мотивации некоторого действия системы. Каждое правило в операторе планирования имеет список условий, при выполнении которых применение оператора даст желаемый эффект. Ниже представлен перевод на "человеческий язык" оператора планирования, побуждающего пользователя (собеседника программы) выполнить определенное действие, например заменить какую-либо программную конструкцию языка LISP, если речь идет об области применения системы PEA.

Для перехода в состояние, в котором собеседник будет склонен выполнить операцию

ЕСЛИ

Операция представляет собой шаг к достижению некоторой цели (целей), приемлемой для собеседника, и

Цели являются наиболее приемлемыми среди всех возможных путей уточнения

ТО

Мотивировать это действие в терминах целей.

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

Рис. 16.6. Уточнение целей при планировании диалога с пользователем

В составе программы нужно также иметь какое-то средство, которое помогло бы определить, достигнута ли цель, поставленная в плане диалога. Например, согласился ли пользователь с тем, что использование оператора IF делает текст программы более читабельным. Таким образом, необходимо динамически формировать модель поведения пользователя (его предпочтений и доверия к программе) и, сверяясь с этой моделью, проверять, удовлетворяются ли условия использования конкретного оператора планирования. В общих чертах это напоминает тот способ обращения к модели мира, который использовался в STRIPS при выяснении, можно ли протолкнуть ящик из одной комнаты в другую (см. главу 3). Но дополнительную сложность вносит необходимость представлять в модели такие понятия, как доверие и предпочтения пользователя. В системе PEA модель отдельного пользователя формируется на базе стереотипа пользователя, который обладает некоторой усредненной суммой знаний. Например, если речь идет о программировании на языке LISP, т.е. о той области, в которой применяется PEA, то следующий набор выражений представляет те знания, которыми обычно располагают пользователи:

(COMPETENT USER (DO USER REPLACE))

(KNOW-ABOUT USER (CONCEPT PROGRAM))

(KNOW-ABOUT USER (CONCEPT LISP-FUNCTION))

(KNOW-ABOUT USER (CONCEPT S-EXPR))

(KNOW-ABOUT USER (CONCEPT READABILITY))

(KNOW-ABOUT USER (CONCEPT MAINTAINABILITY))

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

Подсистемформирования пояснений в MYCIN

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

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

вывод на экран правил, активизированных на любой стадии консультации;

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

использование индексации правил, которая дает возможность извлечь определенное правило в ответ на вопрос, содержащийся в пользовательском запросе.

Как отмечалось в главе 3, процесс выполнения консультаций в экспертной системе, использующей обратную цепочку логического вывода, включает поиск в дереве целей (рис. 16.1). Следовательно, справки о ходе выполнения консультации можно разделить на два типа:

почему система сочла необходимым задать пользователю определенный вопрос;

как система пришла к определенному заключению.

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

Тот факт, что MYCIN отслеживает прохождение структур цель-подцель в процессе выполнения вычислений, позволяет этой системе отвечать на вопросы вроде приведенного ниже.



" Почему вас интересует, является ли окраска микроорганизма грамотрицательной?"

Рис. 16.1. Формирование ответов на основе дерева целей в системе MYCIN

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

В MYCIN сохраняется список всех решений, принятых в течение сеанса работы, а затем этот список используется для пояснения и уточнения принятых решений в ответ на вопрос пользователя почему, например, такой:

"Почему вы предполагаете, что Организм-1 это протеин?"

В ответ MYCIN процитирует правило, относящееся к этому заключению, и выведет значение степени уверенности в достоверности этого правила. Системе MYCIN можно также задавать вопросы общего характера. Такие вопросы касаются правил безотносительно к текущему состоянию базы данных, т.е. безотносительно к конкретному пациенту. Например:

"Что прописывать при заражении инфекцией pseudonomas?"

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

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

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

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

Проект Explainable Expert Systems

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

Система XPLAN создавалась в рамках проекта Explainable Expert Systems (EES) [Heches et al, 1985], [Moore, 1995]. Идея этого проекта вполне созвучна существующей в настоящее время тенденции группировать и представлять в явном виде знания различного вида. Кроме того, в рамках этого проекта предпринята попытка использовать формальные методы, которые позволили бы зафиксировать в базе знаний системы основные решения, принимаемые в процессе ее разработки. Отсутствие таких формальных методов приводит к тому, что информация об основных решениях, положенных в основу проектирования, теряется на стадии реализации системы.

На рис. 16.3 представлена структурная схема оболочки, созданной в рамках проекта EES. Обратите внимание на прямоугольник в левой части схемы, который представляет базу знаний системы. В эту базу знаний входят не только модель и правила предметной области, но и много дополнительной информации, например описание терминологии предметной области, информация, связанная с правилами предметной области, о доводах в пользу и против выбора определенной стратегии достижения цели, информация о том, каким целям отдается предпочтение в процессе решения проблемы, и т.д. Знания, выделенные в группу "Интеграция", используются для разрешения конфликтов между правилами предметной области в процессе работы "автоматического программиста", а знания, выделенные в группу "Оптимизация", имеют отношение к производительности экспертной системы, генерируемой этим автоматическим программистом.
Эти служебные группы знаний представляют те виды метазнаний, которые не связаны непосредственно с выбором правил объектного уровня в процессе логического вывода на этапе функционирования экспертной системы, а имеют отношение скорее к этапу ее проектирования.

Рис. 16.3. Структура оболочки EES ([Neches et al., 1985])

Семантика базы знаний системы EES представлена в виде семантической сети, получившей наименование NIKL [Moser, 1983]. Сеть появилась в результате развития идей, положенных в основу создания сети KL-ONE [Brachman and Schmolze, 1985]. NIKL, так же, как и KL-ONE, формирует множество концептов, имеющих собственную внутреннюю структуру (набор слотов или ролей), между которыми можно задавать отношения (формировать связи). NIKL также имеет в своем составе классификатор, который, располагая информацией о структуре конкретной сети и новом концепте с определенной структурой, может поместить этот новый концепт на соответствующее ему место в общей таксономии концептов.

Пусть, например, в сети имеются узлы концептов ЖИВОТНОЕ, СОБАКА и БЕШЕНОЕ-ЖИВОТНОЕ, а в классификатор поступает новый концепт БЕШЕНАЯ-СОБАКА. В ответ классификатор формирует новый узел для этого концепта и отводит ему место в иерархии. Новый узел будет связан "узами наследования" с узлами СОБАКА и БЕШЕНОЕ-ЖИВОТНОЕ. Это выполняется после анализа свойств и характеристик нового концепта (рис. 16.4). Трудно переоценить способность системы наращивать таким образом базу знаний, которая, как правило, никогда не создается за "один присест".

Исчез (Neches) описал применение оболочки EES для построения экспертной системы Program Enhancement Advisor (PEA). Эта программа предназначена для оказания помощи программистам в повышении "читабельности" текстов программ. В той предметной области, в которой должна работать новая экспертная система, концептами семантической сети являются преобразования элементов программного кода, например замена оператора COND языка LISP на конструкцию IF-THEN-ELSE.


Концепт является частным случаем другого концепта, KEYWORD CONSTRUCT, который, в свою очередь, является частным случаем концепта Easy-TO-READ CONSTRUCT. Используя организованную таким образом базу знаний, экспертная система может предложить программисту-пользователю заменить оператор

(COND ((АТОМ X) X) (Т (CAR X)))

другим оператором, смысл которого более понятен при анализе текста программы: (IF (АТОМ X) THEN X ELSE (CAR X)).



Рис. 16.4. Включение нового концепта в семантическую сеть знаний

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

Генератор программ работает по принципу нисходящего (сверху вниз) уточнения, выполняя декомпозицию целей на подцели. Так, главная цель программы PEA — усовершенствовать программу — разделяется на подцели, например улучшить читабельность. Разработчики системы назвали такой процесс декомпозиции целей "динамическим уточнением, направляемым пользователем", поскольку характер действий, выполняемых создаваемой системой, определяется инженером по знаниям, формирующим базу знаний. Если выбрана определенная цель, скажем улучшить читабельность, то она автоматически становится субъектом процесса дальнейшей декомпозиции цель/подцель. Например, следующими подцелями будет просмотр текста программы и выявление в нем синтаксических конструкций, которые можно безболезненно заменить другими, более понятными, получение подтверждения от пользователя, одобряющего предлагаемую замену, выполнение замены и т.д. Фрагмент предыстории разработки системы PEA, в котором отображена описанная декомпозиция, представлен на рис. 16.5.





Рис. 16.5. Фрагмент предыстории разработки системы PEA, в котором отображена декомпозиция цели на подцели ([Moore, 1995])

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

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

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

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

Рекомендуемая литература

Читателей, интересующихся историей разработки модели пользователя, мы отсылаем к сборникам [Sleeman and Brown, 1982] и [Poeson and Richardson, 1988]. Довольно обширная подборка статей, касающихся проблематики интерфейса с пользователем; представлена в сборнике [Maybury, 1993]. В работах [Moore and Paris, 1993] и [Moore et al, 1996] суммируется опыт планирования диалога, приобретенный авторами в процессе разработки оболочки EES и экспертной системы PEA.

Читателям, интересующимся дескриптивными языками описания семантических сетей, мы советуем обратить внимание на язык LOOM, представленный в работе [MacGregor, 1991].

Средствформирования пояснений

ГЛАВА 16.

Средства формирования пояснений

16.1. Формирование пояснений на основе знаний

16.2. Формирование пояснений и автоматическое программирование

16.3. Перспективы дальнейших исследований методов формирования пояснений

Рекомендуемая литература

Упражнения

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

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

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

Эту главу мы начнем с краткого обзора ранних работ, касающихся включения в экспертные системы специальных средств, формирующих для пользователя информацию о ходе рассуждений (в дальнейшем для краткости мы будем называть ее поясняющей информацией). Затем более детально будут рассмотрены средства формирования пояснений экспертной системы CENTAUR, о которой уже упоминалось в главе 13. И в заключение мы обсудим одно из последних исследований в этой области, выполненное в рамках проекта Explainable Expert Systems, в котором основное внимание было уделено обеспечению прозрачности экспертной системы с точки зрения инженеров по знаниям, т.е. была предпринята попытка рассмотреть в комплексе вопросы формирования поясняющей информации и извлечения знаний.

в качестве пояснения процесса логического

1. Почему в качестве пояснения процесса логического вывода пользователю недостаточно представить только результаты трассировки активизируемых правил?

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

3. Какую помощь в формировании пояснений может оказать использование фреймов? С какой целью фреймы комбинируются с порождающими правилами?

4. Ниже представлена новая версия программы Assault-weapon (оружие нападения), которая была рассмотрена в главе 11. В этой версии программа задает пользователю вопросы об определенном виде оружия, а затем формирует пояснение, почему данный тип оружия относится (или не относится) к классу "оружие нападения" в соответствии с имеющимися в программе правилами. Программа состоит из двух частей: в первой уточняются характеристики модели оружия, а во второй формируется пояснение.

I) Разработайте правила, которые не представлены в приведенном ниже тексте программы. Указания, какие именно правила требуется разработать, выделены в комментариях в тексте программы.

;; Объявления (deftemplate gun

(field name (type SYMBOL))

(field model (type SYMBOL))

(field class (type SYMBOL) (default NIL))

(field action (type SYMBOL) (default NIL))

(field caliber (type FLOAT) (default 0.0))

(field capacity (type INTEGER) (default 0))

(field features (type SYMBOL) (default NIL))

)

(deftemplate assault-weapon

(field make (type SYMBOL))

(field model (type SYMBOL))

)

;; ПРАВИЛА

;; Общий случай

;; Любая полуавтоматическая

;; винтовка (semi-automatic rifle)

;; или охотничье ружье (shotgun) с емкостью

;; магазина более 5 патронов.

(defrule Parti

(gun (make ?M) (model ?N)

(class ?CSrifle|shotgun) (action semi) (capacity ?X&:(> ?X 5))) =>

(assert (assault-weapon (make ?M) (model ?N)))

)

Разработайте правило make-and-model, которое будет запрашивать у пользователя необходимую информацию о модели оружия и формировать вектор gun в рабочей памяти.

Базовые функции экспертных систем

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

Что такое экспертная система?

1.1. Смысл экспертного анализа

1.2. Характеристики экспертных систем

1.3. Базовые функции экспертных систем

1.4. Резюме и структура книги Рекомендуемая литература Упражнения

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

Call to Undefined Link (Вызов неопределенной связи).

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

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

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

Характеристики экспертных систем

Экспертная система отличается от прочих прикладных программ наличием следующих признаков.

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

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

При решении задач основными являются эвристические и приближенные методы, которые, в отличие от алгоритмических, не всегда гарантируют успех. Эвристика, по существу, является правилом влияния (rule of thumb), которое в машинном виде представляет некоторое знание, приобретенное человеком по мере накопления практического опыта решения аналогичных проблем. Такие методы являются приблизительными в том смысле, что, во-первых, они не требуют исчерпывающей исходной информации, и, во-вторых, существует определенная степень уверенности (или неуверенности) в том, что предлагаемое решение является верным.

Экспертные системы отличаются и от других видов программ из области искусственного интеллекта.

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

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

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

Зачастую термин система, основанная на знаниях (knowledge-based system), используется в качестве синонима термина экспертная система, хотя, строго говоря, экспертная система — это более широкое понятие. Система, основанная на знаниях, — это любая система, процесс работы которой основан на применении правил отношений к символическому представлению знаний, а не на использовании алгоритмических или статистических методов. Таким образом, программа, способная рассуждать о погоде, будет системой, основанной на знаниях, даже в том случае, если она не способна выполнить метеорологическую экспертизу. А вот чтобы иметь право называться метеорологической экспертной системой, программа должна быть способна давать прогноз погоды (другой вопрос — насколько он будет достоверен).



Суммируя все сказанное, отметим — экспертная система содержит знания в определенной предметной области, накопленные в результате практической деятельности человека (или человечества), и использует их для решения проблем, специфичных для этой области. Этим экспертные системы отличаются от прочих, "традиционных" систем, в которых предпочтение отдается более общим и менее связанным с предметной областью теоретическим методам, чаще всего математическим. Процесс создания экспертной системы часто называют инженерией знаний (knowledge engineering) и он рассматривается в качестве "применения методов искусственного интеллекта" (см. [Feigenbaum, 1977]). Далее, в главах 2 и 3, мы более пристально рассмотрим отличие между общепринятым в программировании подходом к решению проблем и тем, который предлагается при проектировании экспертных систем.

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

Представление знаний

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

1.2. Синтаксис и семантика представления семейных отношений

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

"Сэм — отец Билла". "Сэм — Биллов отец". "Биллов отец — Сэм".

"Отцом Билла является Сэм".

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

отец (сэм, билл).

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

Можно также заметить, что предложения

"Сэм — отец Джилла".

"Отцом Билла является Сэм".

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

отец (сэм, билл). отец (сэм, джилл).

О синтаксисе и семантике мы поговорим более подробно в главах 3 и 8.

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

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

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

Символические вычисления означают выполнение нечисловых операций, в которых могут быть сконструированы символы и символьные структуры для представления различных концептов и отношений между ними. Обсуждение проблем символьных вычислений мы отложим до главы 4. Пример символического представления вы найдете во врезке 1.2.

В области искусственного интеллекта ведется интенсивная работа по созданию языков представления (representation languages). Под этим термином понимаются компьютерные языки, ориентированные на организацию описаний объектов и идей, в противовес статическим последовательностям инструкций или хранению простых элементов данных.


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

Логическая адекватность означает, что представление должно обладать способностью распознавать все отличия, которые вы закладываете в исходную сущность. Например, невозможно представить идею, что каждое лекарство имеет какой-либо побочный нежелательный эффект, если только нельзя будет провести отличие между предназначением конкретного лекарственного препарата и его побочным эффектом (например, аспирин усугубляет язвенную болезнь). В более общем виде выражение, передающее этот эффект, звучит так: "каждое лекарство обладает нежелательным побочным эффектом, специфическим для этого препарата".

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

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


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

За прошедшие годы было предложено немало соглашений, пригодных для кодирования знаний на языковом уровне. Среди них отметим порождающие правила (production rules) [Davis and King, 1977], структурированные объекты (structured objects) [Findler, 1979] и логические программы (logic programs) [Kowalski, 1979]. В большинстве экспертных систем используется один или несколько из перечисленных формализмов, а доводы в пользу и против любого из них до сих пор представляют собой тему для оживленных дискуссий среди теоретиков. Несколько формализмов такого рода критически рассмотрены в главах 5-8, а программные средства для их реализации — в главах 17-19.

Большинство фрагментов программного кода, приведенных в этой книге, написано на языке CLIPS, в котором используется комбинация порождающих правил и структурированных объектов. В Приложении вы найдете достаточно пространное описание основных концепций и программных конструкций языка CLIPS, которое сопровождается множеством примеров. Там же читатель сможет найти и нетривиальные программы, в которых продемонстрированы как многие интересные возможности языка, так и реализация его средствами методов искусственного интеллекта, обсуждаемых в главах 1-3.

Приобретение знаний

Бучанан следующим образом сформулировал функцию приобретения знаний [Buchanan et al, 1983]:

"[Приобретение знаний это] передача потенциального опыта решения проблемы от некоторого источника знаний и преобразование его в вид, который позволяет использовать эти знания в программе".

Передача знаний выполняется в процессе достаточно длительных и пространных собеседований между специалистом по проектированию экспертной системы (будем в дальнейшем называть его инженером по знаниям) и экспертом в определенной предметной области, способным достаточно четко сформулировать имеющийся у него опыт. По существующим оценкам, таким методом можно сформировать от двух до пяти "элементов знания" (например, правил влияния) в день. Конечно, это очень низкая скорость, а потому многие исследователи рассматривают функцию приобретения знаний в качестве одного из главных "узких мест" технологии экспертных систем [Feigenbaum, 1977].

Причин такой низкой производительности предостаточно. Ниже перечислены только некоторые из них.

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

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

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

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

1.1. Забытый пароль

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

Сэм: Так вот, если это YP-пароль, я первым делом регистрируюсь как "root" на YP-главном.

Кен: А что такое YP-главный?

Сэм: Это дисковая машина, на которой установлена база данных с информацией обо всей сети.

Кен: А "дисковая машина" означает...

Сэм: Что на ней ОС установлена на локальном диске.

Кен: Ах вот что. (Почесывает в затылке) Итак, ты регистрируешься на...

Сэм: Как "root".


Затем я редактирую файл данных паролей, удаляю зашифрованный элемент и создаю новую карту паролей.

Кен: ...карту паролей. (Насмешливо) А что произойдет, если ты забудешь собственный пароль?

Сэм: На дисковой машине я мог бы перегрузиться и запуститься в однопользовательском режиме или можно было бы загрузить MINI ROOT. Тогда можно редактировать /etc/password. Или можно переустановить всю систему, но этого я скорее всего делать не буду. Корневые пароли обычно не включаются в YP. На бездисковой машине клиента я мог бы воспользоваться командой passwd.

Кен: Уф-ф-ф. (Сожалеет, что взялся за onpoc)

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

Неудовлетворительные результаты подобных собеседований пробудили у некоторых исследователей интерес к автоматизации процесса передачи знаний специалистом машине. Одно из направлений исследований в этой области — автоматизированное извлечение знаний (automated knowledge elicitation) — появилось как побочный продукт в развитии систем человеко-машинного диалога (см. главу 10). Другие исследователи полагают, что "расшить" это узкое место можно, двигаясь по пути машинного обучения (machine learning). Идея состоит в том, чтобы машина училась решать проблемы примерно так, как учится человек (см. главу 20).

Распределение материалкниги по главам

В табл. 1.1 суммированы темы, обсуждавшиеся в разделе 1.3, и указаны главы, в которых'эти темы рассматриваются подробно. Рядовому читателю, скорее всего, будут интересны темы, касающиеся представления знания и управления процессом анализа, поскольку это ключевые проблемы в технологии экспертных систем. Темы восприятия знаний и объяснения принятого решения имеют не меньшее значение при построении экспертных систем, но они носят более прикладной характер.

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

Таблица 1.1. Содержание глав

	Тема		Определение		Главы
	Овладение знаниями		Передача опыта решения проблемы от человека программе		10-15,20
	Представление знаний		Кодирование информации об опыте решения проблем внутри машины		2-9,21-23
	Управление процессом поиска решения		Принятие решения о последовательности использования имеющихся знаний		3, 11, 12, 17-19
	Объяснение принятых решений		Передача информации о ходе решения проблемы пользователю		3,5, 16,23

В главах 3-9 освещаются основные схемы представления проблемно-ориентированных знаний в программах и методы применения этих знаний к решению сложных проблем с помощью компьютера. Мы начнем с краткого обзора работ в области символических вычислений, а затем перейдем к анализу некоторых специализированных языков представления знаний, таких как CLIPS. Будут также рассмотрены и возможности использования для построения экспертных систем объектно-ориентированных языков общего назначения, подобных C++. И в завершение этой части книги будет рассмотрена проблема приблизительных рассуждений и различные качественные и количественные методы оценки неопределенности.



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

В главах 17-19 анализируются инструментарий и структура программного обеспечения экспертных систем. Мы начнем с критического обзора разного рода сред разработки, используемых при проектировании программного обеспечения экспертных систем. Затем будут описаны два типа структурной организации: системы с доской объявлений (blackboard systems) и системы обработки правдоподобия {truth maintenance systems).

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

Разъяснение принятого решения

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

Представление информации о поведении экспертной системы важно по многим причинам.

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

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

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

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

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

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

Отсутствие достаточной прозрачности поведения системы не позволит эксперту повлиять на ее производительность или дать совет, как можно ее повысить. Прослеживание и оценка поведения системы — задача довольно сложная и для ее решения необходимы совместные усилия эксперта и специалиста по информатике (подробно этот вопрос рассматривается в главах 3, 13 и 17).

1.4. Загадка одного портрета

В одной известной загадке человек смотрит на портрет и говорит:

"У меня нет братьев и сестер, но отец этого человека — это сын моего отца".

Спрашивается: 'Кто изображен на портрете?" Во-первых, потратьте пару минут и решите эту загадку. Во-вторых, представьте себе, как вы будете объяснять ход решения кому-нибудь постороннему, но при этом нельзя пользоваться никакими вспомогательными средствами вроде карандаша и бумаги. Для многих эта загадка представляется головоломной, причем немало и таких, которые не могут проследить за ходом уже описанного решения (Smullyan, 1978].

Ответ прост: отец смотрит на портрет сына (человек, который смотрит на портрет, — отец человека, изображенного на портрете). Как мы пришли к такому заключению, станет ясно после того, как мы воспользуемся логическим представлением. Пусть Пит — человек на портрете, а Люк — человек, который смотрит на портрет.

"...это сын моего отца".

сын(отец(люк)), отец(пит).

"У меня нет братьев и сестер..."

for all X,

if сын(отец(люк), X) then Х=люк.

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

отец(пит) = люк. Таким образом, Люк смотрит на портрет своего сына.

Правильное логическое представление зачастую значительно упрощает решение задачи и делает его более понятным. Но сформировать такое представление — это в значительной мере искусство. Объяснение не всегда имеет форму доказательства, как в данном случае, о чем будет подробно рассказано в главе 16.

Рекомендуемая литература

Обзоры ранних исследований в области экспертных систем опубликованы в работах [Barr and Feigenbaum, 1982], [Hayes-Roth et al., 1983], [Buchanan and Shortliffe, 1984] и [Waterman, 1986].

Применение технологии экспертных систем в разных предметных областях описано в работах [Weiss and Kulikowski, 1983], [Klahr and Waterman, 1986], [Gale, 1986] и [Quinlan, 1987].

Читателям, интересующимся применением экспертных систем в промышленности, следует заглянуть в работу [Feigenbaum et al., 1988]. Кроме того, множество обзоров такого рода регулярно публикуется в отраслевых изданиях, в частности в Expert Systems Review for Business and Accounting.

Из работ последних лет следует обратить внимание на книги [Harmon and Sawyer, 1990], [Giarratano andRiley, 1994] и [Stefik, 1995].

Резюме и структуркниги

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

Смысл экспертного анализа

Задумайтесь над таким вопросом: "При выполнении каких условий компьютерную программу можно назвать экспертом?"

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

Знания, которыми обладает программа, должны быть сконцентрированы на определенную предметную область. Случайный набор имен, дат и мест событий, сентенций из классиков и т.п. — это отнюдь не те знания, которые могут послужить основой для программы, претендующей на способность выполнить экспертный анализ. Знания предполагают определенную организацию и интеграцию — то есть отдельные сведения должны соотноситься друг с другом и образовывать нечто вроде цепочки, в которой одно звено "тащит" за собой следующее.

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

Теперь попробуем подытожить эти рассуждения в следующем формальном определении экспертной системы.

Экспертная система — это программа для компьютера, которая оперирует со знаниями в определенной предметной области с целью выработки рекомендаций или решения проблем.

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

Текущее состояние проблемы

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

способен решить проблему;

знает, как решается проблема;

способен объяснить другому, как решается проблема;

располагает временем, чтобы объяснить другому, как решается проблема;

имеет достаточные побудительные мотивы к активному участию в этом предприятии.

Например, предсказание погоды — это не та задача, которую может решить кто-либо, даже умудренный большим опытом эксперт. Распознавание речи — это задача, которую решает практически каждый, но никто из нас (включая и профессиональных лингвистов) не может вразумительно объяснить, как это делается. А потому использовать для решения этой проблемы методы, основанные на анализе знаний, вряд ли удастся. Здесь большего следует ожидать от статистического моделирования. Даже имея на примете гениального эксперта, знающего, как решается задача, нельзя рассчитывать на успех, если этот эксперт не может или не желает подробно и вразумительно объяснить, как он это делает. Эксперт может быть не расположен к общению с посторонними или слишком занят, чтобы терять время на длительные собеседования с инженером, которому поручено проектирование базы знаний. Как правило, эксперт высокого класса не испытывает недостатка в предложениях работы в той области, с которой он хорошо знаком, а потому предпочитает выполнять ее, а не вести пространные беседы о том, как он это делает. Есть еще и психологический фактор — многие эксперты весьма ревниво относятся к своему уникальному опыту и не склонны его разглашать, поскольку считают (и нам нечего возразить им), что, передавая опыт автоматизированным системам, они рубят сук, на котором сидят.

Управление процессом поискрешения

При проектировании экспертной системы серьезное внимание должно быть уделено и тому, как осуществляется доступ к знаниям и как они используются при поиске решения [Davis, 1980, а]. Знание о том, какие знания нужны в той или иной конкретной ситуации, и умение ими распорядиться — важная часть процесса функционирования экспертной системы. Такие знания получили наименование метазнаний — т.е. знаний о знаниях. Решение нетривиальных проблем требует и определенного уровня планирования и управления при выборе, какой вопрос нужно задать, какой тест выполнить, и т.д.

Использование разных стратегий перебора имеющихся знаний, как правило, оказывает довольно существенное влияние на характеристики эффективности программы. Эти стратегии определяют, каким способом программа отыскивает решение проблемы в некотором пространстве альтернатив (см. главы 2 и 3). Как правило, не бывает так, чтобы данные, которыми располагает программа работы с базой знаний, позволяли точно "выйти" на ту область в этом пространстве, где имеет смысл искать ответ.

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

1.3. Обслуживание автомобиля

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

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

"Сначала проверь весь узел, а уже потом приступай к проверке его компонентов".

Это правило можно считать частью режима управления — систематической стратегии применения имеющихся знаний. Другое эвристическое правило можно сформулировать, например, так:

"Сначала меняй более дешевые детали, а уже потом берись за более дорогие".

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

Чем экспертные системы отличаются от

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

2. В чем разница между экспертной системой и системой, основанной на знаниях?

3. Является ли экспертной системой программа предсказания погоды в южной Калифорнии, которая выводит сообщение такого рода: "Завтра погода не будет отличаться от сегодняшней"? Предположим, что она представляет сегодняшнюю погоду в символьном виде, легко модифицируется и способна к расширению, прекрасно работает и может объяснить, почему она пришла к определенному заключению, выведя примерно такое сообщение:

"Суточные изменения климатических условий в это время года маловероятны".

4. Является ли экспертной системой программа, которая формирует прогноз погоды на определенную дату (скажем, 16 июня), усредняя температуру воздуха, количество выпавших осадков и количество солнечных часов 16 июня за все годы, начиная с 1900?

5. Является ли система поиска в сети World Wide Web экспертной? Если нет, то каких свойств ей не хватает для того, чтобы квалифицировать ее как экспертную систему поиска нужной Web-страницы?

6. Почему задача приобретения знаний является узким местом в проектировании экспертных систем? Какие решения предлагаются для устранения такой ситуации?

7. Объясните замечание о логической и эвристической адекватности, которое относится к языку представления знаний.

8. Рассмотрите такой вариант загадки, представленной во врезке 1.4. Человек, который рассматривает портрет, говорит:

''У меня нет братьев и сестер, но сын этого человека — это сын моего отца".

Объясните решение, используя ту же нотацию, что и во врезке.

9. В разделе 1.3.4 отмечалось, что хорошее представление подчас значительно облегчает понимание сути проблемы и упрощает анализ решений. В головоломке "8 ферзей" задача состоит в следующем: нужно так расположить восемь ферзей на шахматной доске, чтобы ни один из них не находился под ударом другого (если кто-нибудь из читателей не знаком с шахматами, то ферзь держит под ударом поля по обеим диагоналям от себя, по горизонтали и по вертикали).

10. Можно представить себе разные способы представления ситуации на шахматной доске. Например, воспользуемся массивом битов размером 8x8, где каждый элемент соответствует одной клетке доски (полю). Если поле находится под ударом, соответствующему элементу массива присвоим значение 1, а иначе — 0. Но существует лучшее представление, в котором используется только один вектор длиной 8 элементов. Использование такого представления существенно уменьшает размерность, а соответственно и сложность задачи. Какое это представление?

Анализ проблемы

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

Предложенные головоломки можно решить, систематически анализируя, что случится, если персонаж, произносящий реплику, является правдолюбцем, а что, если он — лжец. Обозначим через Т(А) факт, что А говорит правду и, следовательно, является правдолюбцем, а через F(A) — факт, что А лжет и, следовательно, является лжецом.

Рассмотрим сначала головоломку Р1. Предположим, что А говорит правду. Тогда из его реплики следует, что либо А лжец, либо В правдолюбец. Формально это можно представить в следующем виде:

Т(А) => F(A) v T(B)

Поскольку А не может быть одновременно и лжецом и правдолюбцем, то отсюда следует

T(A)=> Т(В). Аналогично можно записать и другой вариант. Предположим, что А лжет:

F(A) => -{F(A) v T(B)).

Упростим это выражение:

F(A) => -F(A) ^ -T(B) или F(A) => Т(А) ^ F(B).

Сравнивая оба варианта, нетрудно прийти к выводу, что только последний правильный, поскольку в первом варианте мы пришли к выводу, противоречащему условиям (не могут быть правдолюбцами одновременно А и В).

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

Однако наши головоломки включают и нечто, выходящее за рамки типовых проблем математической логики, поскольку реплики в них может произносить не один персонаж (как в головоломке Р2), а на реплику одного персонажа может последовать ответная реплика другого (как в головоломке РЗ).
В исходной версии программы, которую мы рассмотрим ниже, это усложнение отсутствует, но в окончательной оно должно быть учтено. Мы покажем, что постепенное усложнение программы довольно хорошо согласуется с использованием правил.

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

Р0. А заявляет: "Я лжец". Кто же в действительности А — лжец или правдолюбец?

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

Есть много достоинств в выборе для прототипа программы варианта головоломки Р0.

В головоломке присутствует только один персонаж.

Выражение не содержит логических связок, таких как И или ИЛИ, или кванторов, вроде квантора общности (все) и прочих.

Отсутствует ответная реплика.

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

формировать альтернативные интерпретации высказываниям;

анализировать наличие противоречий.

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

Факты

Сразу после запуска CLIPS-приложения на выполнение на экране появится приглашение, извещающее пользователя, что он работает с интерпретатором.

CLIPS>

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

CLIPS> (assert (today is Sunday))

<Fact-0>

CLIPS> (assert (weather is warm))

<Fact-l>

Для лучшего восприятия текста Приложения мы в дальнейшем будем выделять текст, вводимый пользователем, полужирным шрифтом, а запросы и ответы интерпретатора — обычным моноширинным шрифтом.

Для вывода списка фактов, имеющихся в базе, используется команда facts:

CLIPS> (facts)

f-0 (today is Sunday)

f-1 (weather is warm)

В последних версиях CLIPS, в частности, в той, которая работает в операционной среде Windows, такие команды, как facts, можно вызывать с помощью меню. Для удаления фактов из базы используется команда retract.

CLIPS> (retract 1)

CLIPS> (facts)

f-0 (today is Sunday)

Эти же команды, assert и retract, используются в выполняемой части правила (заключении правила) и с их помощью выполняется программное изменение базы фактов. Часто приходится пользоваться и другой командой интерпретатора, clear, которая очищает базу фактов (как правило, эта команда доступна в одном из выпадающих меню).

CLIPS> (clear) CLIPS> (facts)

В тексте программы факты можно включать в базу не по одиночке, а целым массивом. Для этого в CLIPS имеется команда deffacts.

(deffacts today

(today is Sunday)

(weather is warm) )

Выражение deffacts имеет формат, аналогичный выражениям в языке LISP. Выражение начинается с команды deffacts, затем приводится имя списка фактов, который программист собирается определить (в нашем примере — today), а за ним следуют элементы списка, причем их количество не ограничивается. Этот массив фактов можно затем удалить из базы командой undef facts.

CLIPS> (undeffacts today)

Выражение def facts можно вводить и в командную строку интерпретатора, но лучше записать его в текстовый файл с помощью редактора CLIPS или любого другого текстового редактора.
Загрузить этот файл в дальнейшем можно с помощью команды в меню File либо из командной строки.

CLIPS> (load "my file")

Однако после загрузки файла факты не передаются сразу же в базу фактов CLIPS. Команда deffacts просто указывает интерпретатору, что существует массив today, который содержит множество фактов. Собственно загрузка выполняется командой reset.

CLIPS> (reset)

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

f-0 (initial-fact)

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

Можно проследить, как выполняется команда reset, если перед выполнением приведенных выше команд установить режим слежения среды разработки. Для этого нужно вызвать команду Watch из меню Execution и установить в ней флажок Facts.

Использование шаблонов

Для определения фактов можно использовать не только списочные структуры, но и шаблоны, которые напоминают простые записи. (Шаблоны в CLIPS не имеют ничего общего с шаблонами C++.) Шаблон выглядит примерно так:

(deftemplate student "a student record"

(slot name (type STRING)) (slot age (type NUMBER) (default 18))

Каждое определение шаблона состоит из произвольного имени шаблона, необязательного комментария и некоторого количества определений слотов. Слот включает поле данных, например name, и тип данных, например STRING. Можно указать и значение по умолчанию, как в приведенном выше примере.

Если в программу включено приведенное выше определение шаблона, то выражение

(deffacts students

(student (name fred))

(student (name freda) (age 19)) )

приведет к тому, что в базу фактов после выполнения команды reset будет добавлено

(student (name fred) (age 18)) (student (name freda) (age 19))

Краткая история CLIPS

Название языка CLIPS — аббревиатура от С Language Integrated Production System. Язык был разработан в Центре космических исследований NASA (NASA's Johnson Space Center) в середине 1980-х годов и во многом сходен с языками, созданными на базе LISP, в частности OPS5 и ART. Использование С в качестве языка реализации объясняется тем, что компилятор LISP не поддерживается частью распространенных платформ, а также сложностью интеграции LISP-кода в приложения, которые используют отличный от LISP язык программирования. Хотя в то время на рынке уже появились программные средства для задач искусственного интеллекта, разработанные на языке С, специалисты из NASA решили создать такой продукт самостоятельно. Разработанная ими система в настоящее время доступна во всем мире, и нужно сказать, что по своим возможностям она не уступает множеству гораздо более дорогих коммерческих продуктов.

Первая версия представляла собой, по сути, интерпретатор порождающих правил. Процедурный язык и объектно-ориентированное расширение CLIPS Object-Oriented Language (COOL) были включены в этот программный продукт только в 1990-х годах. Существующая в настоящее время версия может эксплуатироваться на платформах UNIX, DOS, Windows и Macintosh. Она является хорошо документированным общедоступным программным продуктом и доступна по сети FTP с множества университетских сайтов. Исходный код программного пакета CLIPS распространяется совершенно свободно и его можно установить на любой платформе, поддерживающей стандартный компилятор языка С. Однако я бы рекомендовал пользоваться официальной версией для определенной платформы, поскольку такие версии оснащены пользовательским интерфейсом, включающим меню команд и встроенный редактор.

Это Приложение организовано следующим образом. В разделе А.2 рассмотрены основные функции языка описания правил и процедурного языка. В разделе А.З представлены методы работы с объектами и показано, как использовать их в сочетании с правилами и процедурами. В разделе А.4 описан пример, демонстрирующий некоторые приемы программирования правил, а в разделе А.5 резюмируются характеристики этого программного продукта и предлагаются темы для более углубленного изучения.

Наблюдение зпроцессом интерпретации

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

(defrule start

(initial-fact)

(printout t "hello, world" crlf) )

Выполните команду reset. Для этого либо введите эту команду в командной строке интерпретатора

CLIPS> (reset)

либо выберите в меню команду Execution => Reset, либо нажмите <CTRL+U> (последних два варианта возможны в версии, которая работает под Windows).

Затем запустите интерпретатор. Для этого либо введите эту команду run в командную строку интерпретатора

CLIPS> (run)

либо выберите в меню команду ExecutionORun, либо нажмите <CTRL+R> (последних два варианта возможны в версии, которая работает под Windows).

В ответ программа должна вывести сообщение hello, world, знакомое всем программистам мира. Для повторного запуска программы повторите команды reset и run.

Если в меню Execution^Watch ранее был установлен флажок Rules или перед запуском программы на выполнение вы ввели в командную строку команду watch rules, то на экране появится результат трассировки процесса выполнения

CLIPS> (run) FIRE 1 start: f-0 hello, world

В этом сообщении в строке, начинающейся с FIRE, выведена информация об активизированном правиле: start— это имя правила, а f-0— имя факта, который "удовлетворил" условие в этом правиле. Команда watch позволяет организовать несколько разных режимов трассировки, с деталями которых вы можете познакомиться в Руководстве пользователя. Если перед запуском программы вы ввели

CLIPS> (dribble-on "dribble.dp")

TRUE

то выведенный протокол трассировки будет сохранен в файле dribble.dp. Сохранение протокола прекратится после ввода команды

CLIPS> (dribble-off)

TRUE

Это очень удобная опция, особенно на этапе освоения языка.

Объектно-ориентированные средствв CLIPS

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

Первым делом определим класс pistol, в котором будут перечислены свойства, необходимые для моделирования.

(defclass pistol

(is-a USER)

(role concrete)

(pattern-match reactive)

(slot safety (type SYMBOL) (create-accessor read-write))

(slot slide (type SYMBOL) (create-accessor read-write))

(slot hammer (type SYMBOL) (create-accessor read-write))

(slot chamber (type INTEGER) (create-accessor read-write))

(slot magazine (type SYMBOL) (create-accessor read-write))

(slot rounds (type INTEGER) (create-accessor read-write)) )

Первые три слота — системные. Они нужны объектно-ориентированной надстройке CLIPS (COOL — CLIPS object-oriented language). Эти слоты COOL извещают о том, что

pistol — это пользовательский класс;

pistol является конкретным классом, т.е. возможно создание экземпляров этого класса (альтернативный тип — абстрактный класс, который играет ту же роль, что и виртуальный класс в C++);

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

Следующие пять слотов представляют свойства и члены данных класса:

слот safety (предохранитель) может содержать символ on или off;

слот slide (затвор) может содержать значение forward или back, т.е. хранит информацию о положении затвора;

слот hammer (курок) содержит информацию о состоянии курка, back или down;

слот chamber (патронник) содержит значение 1 или 0, в зависимости от того, есть ли патрон в патроннике;

слот magazine (обойма) может содержать значение in или out, в зависимости от того, вставлена ли обойма;



слот rounds (патроны) содержит текущее количество патронов в обойме.

Для того чтобы иметь возможность записывать в слот новое значение или считывать текущее, нужно разрешить формирование соответствующих функций доступа через фацет create-accessor. Теперь сформируем экземпляр класса pistol с помощью следующего выражения:

(definstances pistols (РРК of pistol (safety on)

(slide forward) (hammer down) (chamber 0) (magazine out) (rounds 6)

Этот экземпляр, РРК, правильно уложен — обойма вынута из рукоятки, пистолет установлен на предохранитель, затвор в переднем положении, курок опущен, а патронник пуст. В обойме имеется 6 патронов.

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

есть ли патрон в патроннике;

произведен ли выстрел.

Для этого можно использовать следующий шаблон:

(deftemplate range-test

(field check (type SYMBOL) (default no))

(field fired (type SYMBOL) (default no)) )

Первое правило будет устанавливать в рабочую память программы задачу range-test.

(defrule start

(initial-fact) =>

(assert (range-test)) )

При активизации этого правила в рабочую память будет добавлено (range-test (check no) (fired no))

Следующие три правила будут проверять, правильно ли снаряжен пистолет.

(defrule check

(object (name [PPK]) (safety on) (magazine out)

?T <- (range-test (check no)) =>

(send [PPK] clear)

(modify ?T (check yes) )

Правило check заключается в том, что если пистолет стоит на предохранителе (safety on), обойма вынута (magazine out) и пистолет не был проверен, то нужно очистить патронник и проверить, нет ли в нем патрона. Обработчик сообщения clear для класса pistol будет выглядеть следующим образом:

(defmessage-handler pistol clear ( )

(dynamic-put chamber 0)

(ppinstance) )



В первой строке объявляется, что clear является обработчиком сообщения для класса pistol, причем этот обработчик не требует передачи аргументов. Оператор во второй строке "очищает" патронник. Присвоение выполняется независимо от того, какое текущее значение имеет слот chamber, — 0 или 1 . Оператор в третьей строке требует, чтобы экземпляр распечатал информацию о текущем состоянии своих слотов.

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

(defrule correctl

(object (name [PPK]) (safety off) )

(range-test (check no)) =>

(send [PPK] safety on)

)

(defrule correct2

(object (name [PPK]) (safety on) (magazine in))

(range-test (check no)) =>

(send [PPK] drop) )

Как и при разработке предыдущего правила, нам понадобятся обработчики сообщений safety и drop.

(defmessage-handler pistol safety (?on-off)

(dynamic-put safety ?on-off)

(if (eq ?on-off on)

then (dynamic-put hammer down)

) )

Обработчик сообщения safety принимает единственный аргумент, который может иметь только два символических значения on или off. В противном случае нам пришлось бы разработать два обработчика: один для сообщения saf ety-on, а другой — для сообщения safety-of f . Учтите, что в некоторых моделях, например в Walther PPK, при установке пистолета на предохранитель патронник очищается автоматически.

Обработчик сообщения drop просто извлекает обойму из пистолета.

(defmessage-handler pistol drop ()

(dynamic-put magazine out) )

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

(defrule mag-in

(object (name [PPK]) (safety on) (magazine out))

(range-test (fired no) (check yes)) =>

(send [PPK] seat) )

Обработчик сообщения seat выполняет действия, противоположные тем, которые выполняет обработчик drop.



(defmessage-handler pistol seat ()

(dynamic-put magazine in) )

Можно было бы, конечно, включить в программу и следующее правило mag-in:

(defrule mag-in

?gun <- (object (name [PPK]) (safety on)

(magazine out)) (range-test (fired no) (check yes)) =>

(modify ?gun (magazine in) )

но это противоречит одному из принципов объектно-ориентированного программирования, который гласит, что объект должен самостоятельно обрабатывать содержащиеся в нем данные. Следующее правило обеспечивает снаряжение обоймы патронами:

(defrule load

(object (name [PPK]) (magazine in) (chamber 0)) =>

(send [PPK] rack) )

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

(defmessage-handler pistol rack ()

(if (> (dynamic-get rounds) 0) then (dynamic-put chamber 1)

(dynamic-put rounds (- (dynamic-get rounds) 1))

(dynamic-put slide forward) else (dynamic-put chamber 0)

(dynamic-put slide back)

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

(defrule ready

(object (name [PPK]) (chamber 1)) =>

(send [PPK] safety off) )

Правило fire выполняет стрельбу.

(defrule fire

(object (name [PPK]) (safety off);

?T <- (range-test (fired no)) =>

(if (eq (send [PPK] fire) TRUE)

then (modify ?T (fired yes))) )

Обратите внимание, что в данном правиле используется обработчик сообщения, которое возвращает значение. Анализируя его, можно выяснить, произведен ли выстрел, т.е. выполнена ли в действительности та операция, которая "закреплена" за этим сообщением. Если в патроннике был патрон и пистолет был снят с предохранителя, то обработчик сообщения вернет значение TRUE (после того, как выведет на экран BANG ! ).


В противном случае он вернет FALSE (после того, как выведет на экран click).

(def message-handler pistol fire () (if (and

(eq (dynamic-get chamber) 1) (eq (dynamic-get safety) off)

)

then (printout t crlf "BANG!" t crlf)

TRUE

else (printout t crlf "click" t crlf) FALSE

)

Пусть вас не смущает, что в обработчике сообщения анализируется условие, которое уже было проанализировано правилом, отославшим сообщение (в данном случае речь идет об условии safety off). Дело в том, что одно и то же сообщение может отсылаться разными правилами и нет никакой гарантии, что в каждом из них будет проверяться это условие.

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

(defrule unready

(object (name [PPK]) (safety off))

(range-test (fired yes)) =>

(send [PPK] safety on) )

Следующая операция — вынуть обойму. Обратите внимание, что в нем мы вновь обращается к обработчику сообщения drop.

(defrule drop

(object (name [PPK]) (safety on))

(range-test (fired yes)) =>

(send [PPK] drop) )

Последнее правило выбрасывает патрон из патронника, вызывая обработчик сообщения clear.

(defrule unload

(object (name [PPK]) (safety on) (magazine out))

(range-test (fired yes)) =>

(send [PPK] clear) )

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

Обработкметавысказываний

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

Рассмотрим высказывание:

А: "В утверждает, что он правдолюбец".

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

В более сложных сценариях работы с "мирами" нам потребуется также отслеживать, был ли данный объект world проанализирован полностью. Это упростит механизм выполнения отката.

;;Объект world представляет множество утверждений,

;;сформированных при определенном предположении

;;о правдивости или лживости высказывания,

;;принадлежащего некоторому персонажу.

;;Объект имеет уникальный идентификатор

;;в поле tag, который соответствует

;;тэгу высказывания.

;;Смысл допущения - истинность или лживость -

;;фиксируется в поле scope.

;;Поле TASK содержит одно из перечисленных

;;ниже значений:

;;CHECK - анализ предположений о

;;правдивости или лживости высказывания;

;;CONTRA - анализ обнаруженного противоречия;

;;CLEAN - удаляет все утверждения, созданные

;;в противоречивом "мире" ;

;;BАСК - откат в точку возврата;

;;QUIT - прекращение процесса.

;;Поле prior может содержать идентификатор

;;объекта world, обработанного перед тем,

;;как был создан данный объект, и с которым данный

;;объект может потенциально конфликтовать.

;;Поле upper содержит идентификатор другого объекта

;;world, в который внедрен данный объект, если

;;соответствующее высказывание содержит другое

;;высказывание.

;;Например, А говорит, что В сказал, что А - лжец.

;; В поле context сохраняется текущий контекст

;;анализируемого операнда дизъюнкции.

;;Поле done содержит информацию о том, обработано ли

;;уже высказывание, на основании которого создан этот

;;объект.

(deftemplate world

(field tag (type INTEGER) (default 1))

(field scope (type SYMBOL) (default truth))

(field task (type SYMBOL) (default check))

(field prior (type INTEGER) (default 0))

(field upper (type INTEGER) (default 0))

(field context (type INTEGER) (default 0))

(field done (type INTEGER) (default 0))

;;Объект statement (высказывание) связан с определенным

;;персонажем (поле speaker).

;;Высказывание содержит утверждение (поле claim).

;;Высказывание имеет основание - причину (поле reason).

;;Если данный объект не является производным от другого

;;объекта statement, в поле reason устанавливается

;;значение 0.

;;В поле tag устанавливается уникальный числовой

;;идентификатор объекта - число, большее 0.

;;В поле DONE устанавливается одно из

;;следующих значений:

0 означает, что объект еще не обрабатывался;

;;1 означает, что объект обрабатывался в предположении

;;о правдивости высказывания;

;;2 означает, что объект обрабатывался в предположении

;;о лживости высказывания. (deftemplate statement

(field speaker (type SYMBOL))

(multifield claim (type SYMBOL))

(field scope (type SYMBOL) (default truth))

(multifield reason (type INTEGER) (default 0))

(field tag (type INTEGER) (default 0))

(field done (type INTEGER) (default 0)) )

;;Теперь разработаем правило, которое будет

;;"распаковывать" высказывание о высказывании.

;; ЕСЛИ объект world базируется на предположении о

;; правдивости метавысказывания,

;; ТО предположить, что персонаж говорит правду и что

;; высказывание истинно.

(defrule unwrap-true-state

?W <- (world (tag ?N) (scope truth) (task check)

(done 0)) ?S <- (statement (speaker ?X) (claim SAY ?Z $?Y)



(done 0)) =>

(printout t crlf "Assuming " Т ?X " and " ?Z " says " $?Y

" in world " ?N

;; "Предполагается " Т ?X " и " ?Z " говорит " $?Y

;; "в мире " ?N

t crlf

)

;; Зафиксировать, что высказывание было распаковано

;; в предположении о его правдивости,

(modify ?S (tag ?N) (done 1))

;; Предположим, что персонаж в текущем "мире" является

;; правдолюбцем.

(assert (claim (content T ?X) (reason ?N)

(scope truth)))

;; Зафиксировать в объекте world, что высказывание

;; распаковано, (modify ?W (done 1))

;; Сформировать новый объект world для внедренного

;; высказывания и зафиксировать, что этот объект

;; является внутренним по отношению к объекту ?N.

(assert (world (tag ( + ?N 1)) (scope truth) (upper ?N)))

;; Зафиксировать внедренное высказывание в новом

;; объекте world.

(assert (statement (speaker ?Z) (claim $?Y) (reason ?N)))

)

;; ЕСЛИ объект world базируется на предположении о

;; лживости метавысказывания,

;; ТО предположить, что персонаж лжет.

;; Каких-либо предположений об истинности

;; утверждения не делается.

(defrule unwrap-false-state

?W <- (world (tag ?N) (scope falsity)

(task check)) ?S <- (statement (speaker ?X)

(claim SAY ?Z $?Y)

(tag ?N) (done 1)) =>

(printout t crlf "Assuming " F " "?X " and

NOT " ?Z " says " $?Y

" in. world " ?N

;; "Предполагается " F " "?X " и HE " ?Z "

говорит " $?Y ;; " в мире " ?N t crlf

)

;; Изменить значение в поле scope текущего объекта

;; world.

(modify ?W (scope falsity) (done 2))

;; Зафиксировать, что высказывание было распаковано

;; в предположении о лживости, (modify ?S (scope falsity) (done 2))

;; Предположить, что в текущем "мире" персонаж,

;; произнесший метавысказывание, лжец.

(assert (claim (content F ?X)

(reason ?N) (scope falsity))) )

Чтобы облегчить себе жизнь, будем считать, что в метавысказывании не может быть отрицания, т.е. мы не будем рассматривать метавысказывания вида

А: "В не говорил, что он правдолюбец".

Более того, если А говорит, что В заявил нечто, то по условиям, принятым в головоломках этого класса, для того чтобы доказать, что А лжец, требуется только показать, что не существует непротиворечивого "мира", в котором В мог бы сделать правдивое утверждение. Таким образом, нам не придется обрабатывать отрицания в метавысказыва-ниях и анализировать их непротиворечивость. Указанные условия нашли свое отражение в правиле unwrap-false-state. В этом правиле которое активизируется, когда предположение о правдивости персонажа не срабатывает, просто предполагается, что этот персонаж лжет, а более глубокий анализ не проводится.

Обратное прослеживание и множество контекстов

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

Упражнение 3

Р5. Встречаются два человека, А и В, которые заявляют следующее. А: "Я говорю правду, либо В лжец", В: " А говорит правду, либо я лжец".

К какой категории следует отнести каждый из персонажей? (Решите эту задачу самостоятельно вручную, используя ту же систему обозначений, которая применялась ранее в этом Приложении.)

Задача анализа высказываний нескольких персонажей потребует использования более сложной методики, которая получила наименование "обратное прослеживание на основе анализа зависимостей"(dependency-directed backtracking).

От программы потребуется выполнить обратное прослеживание (откат) в следующих ситуациях:

когда обнаружится конфликт между текущим "миром" и ранее существовавшим, причем в ранее существовавшем "мире" предполагается истинность высказывания, но не была проанализирована его лживость;

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

Чтобы смысл этих формулировок стал более понятным, рассмотрим следующий пример. Р6. Встречаются два человека, А и В, которые заявляют следующее.

А: "Хотя бы один из нас говорит правду". В: "Хотя бы один из нас лжец". К какой категории следует отнести каждый из персонажей?

Высказывания персонажей представим в следующем виде:

А: Т(А) v Т(В) В: F(A) v F(B)

Начнем с заявления персонажа В 71(5) => F(A) v F(B)

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

Получив непротиворечивую интерпретацию высказывания персонажа В, перейдем к анализу высказывания персонажа А:



Т(А) => FALSE,

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

F(A) => -(T(А) v T(B)) => F(A) ^ F(B) => FALSE.

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

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

N(B) => F(A) v F(B)

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

Поэтому придется вернуться назад в ту точку процесса логического анализа, где было сделано предположение об истинности левого операнда в дизъюнкции, и проанализировать вместо него правый операнд F(B). При этом сразу же будет обнаружено противоречие между истинностью F(B) и ранее высказанным предположением о правдивости персонажа В, но, не вернувшись назад и не выполнив этот анализ, мы не смогли бы обнаружить это противоречие. Теперь остается проанализировать следствие из предположения, что В — лжец.

F(B) => -(F(A) v F(B)) => Т(А) ^T(В) => FALSE.

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

Чтобы в системе, использующей правила в качестве основного программного компонента, реализовать откат (обратное прослеживание), нужно в первую очередь иметь возможность восстановить тот контекст, который существовал в момент, когда было сформулировано предположение, приведшее к не удовлетворяющему нас результату. Как было показано в главе 5, одно из достоинств продукционных систем, подобных CLIPS, состоит в том, что они способны выполнить такой откат, не сохраняя прежнего состояния процесса вычислений, что коренным образом отличает их от фундаментально рекурсивных языков программирования, таких как LISP и PROLOG.


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

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

(1) Сохранять информацию о возможных точках возврата.

(2) При обнаружении противоречия принимать решение, выполнять или не выполнять откат, а если выполнять, то в какую именно точку.

(3) Отменить все изменения, внесенные в состояние рабочей памяти после "прохождения" выбранной точки возврата.

(4) Возобновить вычисления начиная с точки возврата. Рассмотрим подробнее каждую из этих операций.

Каждый объект world имеет уникальный числовой идентификатор, который хранится в поле tag. Эта информация практически не используется при решении задач с единственным высказыванием, поскольку мы всегда имеем дело с одним и тем же объектом world, связанным с этим высказыванием. Но при решении задач, оперирующих с несколькими высказываниями, нам придется различать утверждения, которые порождены разными высказываниями в разных "мирах". По мере того, как мы будем переходить от анализа одних высказываний к другим, будут формироваться и новые объекты world. Прежние объекты world нужно оставлять в таком состоянии, чтобы при необходимости к ним можно было еще раз вернуться. Это означает, что вектор world, с которым прекращены операции (возможно, временно), содержал всю информацию, которая потребуется программе для возобновления работы с ним.


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

Поскольку каждый объект world имеет свой уникальный идентификатор и каждое утверждение (объект claim) индексировано определенным объектом world, можно довольно просто выяснить, существует ли противоречие между разными "мирами" (т.е. между утверждениями, связанными с разными объектами world). Остается единственный вопрос — нужно ли возвращаться в ранее покинутый "мир", если в текущем "мире" обнаружено противоречие с ним. Мы будем применять стратегию поиска в глубину, которая состоит в том, что откат нужно выполнять только в том случае, если противоречие сохраняется после полного завершения анализа текущего "мира".

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

Если прежний объект world содержит полную информацию о том, в каком состоянии был покинут "мир", и утверждения в этом "мире" не противоречат этому состоянию, то ничто не мешает нам продолжить вычисления из точки возврата.

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

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


Если текущее высказывание само по себе противоречиво (т.е. является парадоксом), нет смысла выполнять откат в прежний мир и искать в нем разрешения противоречия.

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

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

Объект world представляет контекст, сформированный определенными предположениями о правдивости или лживости высказывания, принадлежащего некоторому персонажу. Объект имеет уникальный идентификатор в поле tag, а смысл допущения - истинность или лживость -фиксируется в поле scope. Поле prior может содержать идентификатор объекта world, обработанного перед тем, как был создан данный объект, и с которым данный объект может потенциально конфликтовать. В поле context сохраняется текущий контекст анализируемого операнда дизъюнкции, (deftemplate world

(field tag (type INTEGER) (default 1))

(field scope (type SYMBOL) (default truth))

(field prior (type INTEGER) (default 0))

(field context (type INTEGER) (default 0)

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

CHECK. Эта операция реализует нормальный режим выполнения вычислений при анализе предположений о правдивости или лживости.

CONTRA. Анализ обнаруженного противоречия. Возникло ли оно между двумя высказываниями в одном и том же "мире"? Возникло ли противоречие между двумя высказываниями в одном и том же "мире", но в разных контекстах, например в разных операндах дизъюнкции? Возникло ли оно между двумя разными "мирами", производными от высказываний разных персонажей?

CLEAN. После того, как выявлен характер возникшего противоречия, и перед тем, как выполнить откат в точку возврата, эта операция удаляет все утверждения, созданные в текущем "мире".



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

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

Еще раз модифицируем определение шаблона объекта world — внесем в него поле TASK, в котором будут представлены перечисленные задачи. Это поле будет использовано правилами, которые нам еще предстоит разработать. Механизм работы с задачами подобен тому, который использовался для манипулирования лексемами управления (control tokens), описанными в главах 5 и 14. Этот механизм активизирует определенные правила. Однако при этом мы не будем использовать стратегию МЕА или специальные векторы. Лексемы управления будут просто сохраняться в определенном поле объекта world. Но результат будет тот же — эта лексема будет использована для активизации определенного правила.

;;Объект world представляет контекст,

;;сформированный определенными предположениями

;;о правдивости или лживости высказывания,

;;принадлежащего некоторому персонажу.

;;Объект имеет уникальный идентификатор

;;в поле tag, который соответствует

;;тэгу высказывания.

;;Смысл допущения - истинность или лживость -

;;фиксируется в поле scope.

;;Поле TASK содержит одно из перечисленных

;;ниже значений:

CHECK - анализ предположений о правдивости или лживости высказывания; CONTRA - анализ обнаруженного противоречия; CLEAN - удаляет все утверждения, созданные в противоречивом мире



;; BACK - откат в точку возврата

;; QUIT - прекращение процесса.

;; Поле prior может содержать идентификатор

;;объекта world, обработанного перед тем,

;;как был создан данный объект, и с которым данный

;;объект может потенциально конфликтовать.

;;В поле context сохраняется текущий контекст

;;анализируемого операнда дизъюнкции,

(deftemplate world

(field tag (type INTEGER) (default 1))

(field scope (type SYMBOL) (default truth))

(field task (type SYMBOL) (default check))

(field prior (type INTEGER) (default 0))

(field context (type INTEGER) (default 0)) )

Теперь разработаем правила, которые будут выполнять перечисленные выше операции. Кроме того, нужно внести некоторые изменения и в правила, разработанные для прежней версии программы.

Выявление противоречий

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

между высказываниями в одном и том же "мире", но, возможно, в разных контекстах дизъюнктивного утверждения;

между высказываниями в разных "мирах".

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

обнаруживается противоречие между предположением и высказыванием, которые существуют в одном и том же контексте (например, если из предположения Т(А) непосредственно следует заключение F(A), как в заявлении персонажа A: F(A));

обнаруживается противоречие между предположением и одним из дизъюнктов составного высказывания, как в заявлении персонажа А: 1\В) v F(A).

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

текущий "мир" рассматривается в предположении, что персонаж говорит правду (в поле scope объекта world содержится значение truth);

текущий "мир" рассматривается в предположении, что персонаж лжет (в поле scope объекта world содержится значение falsity).

Если, предположив правдивость персонажа, программа обнаружит противоречие, она должна проанализировать и следствие из противоположного предположения — что персонаж лжец.


И только при условии, что оба варианта предположения приводят к противоречию, нужно выполнить откат.

Анализ каждого из четырех вариантов ситуации выполняется отдельным правилом, программы которых представлены ниже. Обратите внимание, что все правила имеют довольно высокий приоритет (значение параметра salience). Это обеспечивает их первоочередную активизацию механизмом разрешения конфликтов между правилами. Кроме того, правила, анализирующие противоречие в пределах одного и того же "мира", имеют более высокий приоритет, чем правила, анализирующие противоречие между разными "мирами". Тем самым обеспечивается реализация стратегии по возможности избегать откатов в процессе решения проблемы.

ЕСЛИ обнаруживается противоречие между предположением и производными от него фактами в пределах одного и того же "мира" и в одном и том же контексте, ТО зафиксировать противоречие и удалить противоречивые утверждения (объекты claim) из базы фактов. (defrule contradiction

(declare (salience 100))

?W <- (world (tag ?N) (task check) (context ?S)

(prior 0)) ?P <- (claim

(content ?F ?X) (reason ?N)

(context ?S)) ?Q <- (claim

(content ?GS:(not (eq ?G ?F)) ?X)

(reason ?N) (context ?S)) =>

(printout t crlf

"CONTRADICTION: " ?F ?X " versus " ?G ?X "in world " ?K

;; "ПРОТИВОРЕЧИЕ между: " ?F ?X " и "?G ?X "в мире " ?N

t crlf) (retract ?P) (retract ?Q) (modify ?W (task contra))

)

;; ЕСЛИ обнаруживается противоречие между предположением

;; и производными от него фактами в пределах одного и

;; того же "мира", но в разных контекстах,

;; ТО зафиксировать противоречие.

(defrule transcontext

(declare (salience 90))

?W <- (world (tag ?N) (task check) (context ?T)

(prior 0)) (claim (content ?F ?X) (reason ?N)

(context ?S:(< ?S ?T))) (claim

(content ?GS:(not (eq ?G ?F)) ?x)

(reason ?N) (context ?T)) =>

(printout t crlf

"TRANSCONTEXT CONTRADICTION: " ?F ?X " versus



?G ?X " in world " ?N

"ТРАНСКОНТЕКСТНОЕ ПРОТИВОРЕЧИЕ между: " ?F ?X

;;" и "?G ?X "в мире " ?N

t crlf) (modify ?W (task contra))

)

; ; ЕСЛИ обнаруживается противоречие между

;; текущим "миром" в предположении о правдивости

;; и ранее покинутым "миром" ,

;; ТО зафиксировать противоречие.

(defrule transworld-truth (declare (salience 80))

?W <- (world (tag ?N) (scope truth) (task check)

(prior 0))

(claim (content ?F ?X) (reason ?N))

(claim (content ?G&:(not (eq ?G ?F)) ?X) (reason ?M&:(< ?M ?N))) =>

(printout t crlf

"TRANSWORLD CONTRADICTION: " ?F ?X "

versus ?G ?X " in worlds " ?N "|" ?M

;; "МЕЖМИРОВОЕ ПРОТИВОРЕЧИЕ: " ?F ?X "

противоречит ; ; ?G ?X " в мирах " ?N " | " ?M

t crlf) (modify ?w (task contra))

)

;; ЕСЛИ обнаруживается противоречие между

;; текущим "миром" в предположении о лживости

;; и ранее покинутым "миром",

;; ТО подготовиться к выполнению отката в ранее

;; покинутый "мир" .

(defrule transworld-falsity

(declare (salience 80))

?W <- (world (tag ?N) (scope falsity)

(task check)) (claim (content ?F ?X)

(reason ?N)) (claim (content ?G&:(not (eq ?G ?F)) ?X)

(reason ?MS:(< ?M ?N))) =>

(printout t crlf

"TRANSWORLD CONTRADICTION: " ?F ?X " versus

" ?G ?X " in worlds " ?N " | " ?M

;; "МЕЖМИРОВОЕ ПРОТИВОРЕЧИЕ: " ?F ?X "

противоречит " ;; ?G ?X " в мирах " ?N "|" ?M

t crlf) (modify ?W (task contra) (prior ?M) )

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

Подготовка рабочей памяти к выполнению отката



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

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

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

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

;; ЕСЛИ обнаружено противоречие с одним из

;; дизъюнктивных контекстов "мира",

;; ТО удалить все утверждения (объекты claim)

;; этого контекста.

;; ПРИМЕЧАНИЕ: правило будет активизироваться повторно,

;; пока не будут удалены все ненужные объекты,

(defrule clean-context

(declare (salience SO))

(world (tag ?N) (task contra) (prior 0)

(context ?S&~0))

?F <- (claim (reason ?N) (context ?S)) =>

(retract ?F) )

;; ЕСЛИ противоречие обнаружено в текущем "мире" в

;; предположении о правдивости,

;; ТО повторить анализ, предположив лживость персонажа.

(defrule switch-context

(declare (salience 40))

;; Если больше нет правых дизъюнктов,

?W <- (world (tag ?N) (scope truth) (task contra)

(prior 0) (context ?S&"1)) =>

;; изменить предположение и сформировать новый контекст.

(modify ?W (scope falsity) (task check) (context 0))

)

;; Удалить все утверждения (объекты claim),

;; сформированные на основании предположения о

;; правдивости.

;; ПРИМЕЧАНИЕ: правило будет активизироваться повторно,

;; пока не будут удалены все ненужные объекты,

(defrule sweep-truth

(declare (salience 100))

(world (tag ?N) (scope falsity))

?F <- (claim (reason ?N) (scope truth))-=>



(retract ?F) )

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

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

Выполнение отката

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

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

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

Правило undirected-falsity выполняет необходимые для этого подготовительные операции. Смысл слова undirected (ненаправленный) состоит в том, что это правило реализует откат в "хронологическом" порядке создания "миров". В механизме разрешения конфликтов в CLIPS реализовано "хронологическое предпочтение", которое обеспечивает откат к последнему из ранее сформированных "миров", удовлетворяющих заданным условиям.


Но при этом не предпринимается никакой попытки локализовать в процессе выбор точки, которая стала причиной конфликта, например выбрать именно тот "мир", с которым конфликтует текущий.

;; Хронологический откат к тому "миру", который был

;; покинут без выполнения анализа в предположении

;; о лживости (поле scope содержит значение truth,

;; а поле task - значение check),

(defrule undirected-falsity

(world (tag ?N) (scope falsity) (task contra))

?W <- (world (tag, ?M&:(< ?M ?N)) (scope truth) (task check))

=>

(modify ?W (task back)) )

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

Приведенное ниже правило undirected-disjunct выполняет подготовку к такому откату в хронологическом порядке.

;; Хронологический откат к тому "миру", который был

;; покинут без завершения анализа дизъюнктов,

(defrule undirected-disjunct

world (tag ?N) (scope falsity) (task contra))

V <- (world (tag ?M&:(< ?M ?N))

(task check) (context 1))

claim (content OR ?P ?X ?Q ?Y) (reason ?M)

(scope ?S)) =>

;; Дизъюнкт в ранее покинутом "мире", анализ которого

;; не был выполнен.

assert (claim (content ?Q ?Y) (reason ?M) (scope ?S)

(context 2)))

;; Зафиксировать необходимость отката в этот "мир".

modify ?V (task back)) )

Хронологический откат является не единственной операцией такого рода. Ниже представлены "направленные" (directed) версии соответствующих правил, в которых используется информация о том, в каком именно "мире" имеется утверждение, ставшее причиной конфликта с текущим "миром".


Эта информация содержится в слоте prior текущего объекта world.

Если обнаружено противоречие между объектами world M и N и объект М создан ранее объекта N, причем анализ М в предположении о лживости соответствующего высказывания не был выполнен, ТО вернуться к анализу объекта М.

(defrule directed-falsity

(world (tag ?N) (scope falsity)

(task contra) (prior ?M&"0))

?W <- (world (tag ?M) (scope truth) (task check))

=>

(modify ?W (task back)) )

;; Если обнаружено противоречие между

;; объектами world М и N

;; и объект М создан ранее объекта N, причем

;; не был выполнен анализ всех дизъюнктов в М,

;; ТО вернуться к анализу объекта М.

(defrule directed-disjunct

(world (tag ?N) (scope falsity)

(task contra) (prior ?MS~0))

?V <- (world (tag ?M) (task check) (context 1))

(claim (content OR ?P ?X ?Q ?Y) (reason ?M)

(scope ?S)) =>

;; Дизъюнкт в ранее покинутом "мире", анализ которого

;; не был выполнен.

(assert (claim (content ?Q ?Y) (reason ?M)

(scope ?S) (context 2)))

;; Зафиксировать необходимость отката в этот "мир".

(modify ?V (task back)) )

Если вы думаете, что эти два правила позволяют справиться со всеми возможными ситуациями, в которых может возникнуть необходимость выполнить откат, то вы ошибаетесь. "Миры" W и V могут конфликтовать, хотя в обоих проанализированы все варианты предположений и все дизъюнкты. А источник конфликта при этом находится в некотором третьем "мире", в котором не был завершен анализ предположений или дизъюнктов (см. пример 4).

Упражнение 4

Проанализируйте следующую головоломку, в которой участвуют персонажи А, В и С.

А: "В лжец".

В: "С лжец".

С: "В говорит правду".

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

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



Правила directed- и undirected- можно использовать в комбинации, нр с первого взгляда трудно решить, как именно это сделать. Условные части правил undirected-falsity и directed-falsity одинаковы, а потому нам остается только манипулировать значением параметра salience. Обычно "направленные" варианты правил более эффективны, но в результате их применения может пострадать полнота исследования "миров" в особо хитроумных задачах. "Ненаправленные" варианты работают медленнее, но зато обеспечивают исчерпывающий просмотр всех имеющихся в задаче объектов world. Я предлагаю читателям самостоятельно поэкспериментировать с обоими вариантами при решении разных задач рассматриваемого класса. Мы же в дальнейшем будем использовать только "ненаправленные" варианты этих правил.

Восстановление контекста

При восстановлении контекста придется удалить из рабочей памяти все объекты world, созданные после того объекта, к анализу которого программа возвращается. Удаляются и все утверждения, сформированные на основании высказываний, связанных с удаляемыми объектами. Сами же высказывания (объекты statement) должны быть сохранены и при этом помечены признаком, указывающим, что их нужно в дальнейшем анализировать повторно.

Удаление объектов world. ЕСЛИ выполняется откат к объекту М, ТО удалить все объекты world, имеющие идентификатор, больший М. ПРИМЕЧАНИЕ: правило может активизироваться несколько раз. (defrule undo-world

(declare (salience 40))

(world (tag ?M) (task back))

?W <- (world (tag ?N&:(> ?N ?M)))

?S <- (statement (tag ?N) (done ?X&"0)) =>

(retract ?W)

(modify ?S (done 0))

)

;; Удаление объектов claim.

; ; ЕСЛИ выполняется откат к объекту world M,

; ; ТО удалить все объекты claim,

; ; связанные с удаленными объектами world .

(defrule unclaim

(declare (salience 30))

(world (tag ?M) (task back))

?F <- (claim (reason ?N&:(> ?N ?M))) =>

(retract ?F)

)

Возобновление процесса вычислений начиная с точки возврата.


ЕСЛИ все объекты world, созданные после объекта М, удалены, ТО повторно сформировать объект М, предположив лживость высказывания. (defrule restart

(declare (salience 20) )

?W <- (world (tag ?M) (scope truth)

(task back) (context ?C&~1)) =>

(retract ?W)

(modify ?W (scope falsity)

(task check) (context 0))

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

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

Упражнение 5

Проанализируйте следующую головоломку.

Р7. Встретились два человека, А и В , которые заявляют следующее. А: "В утверждает, что он правдолюбец". В: "А утверждает, что он лжец".

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

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

Включение в постановку задачи высказывания о высказывании (назовем его ме-тавысказыванием) несколько усложняет положение дел. В такой постановке высказывание образует "мир", в котором другое выказывание, а не утверждение, может быть истинным или ложным.Это второе, внутреннее, высказывание должно также формировать собственный "мир".

Рассмотрим высказывание

А: "В утверждает, что он правдолюбец".

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

А что можно сказать о "мире", в котором А лжет? Мы должны показать, что заявление В о том, что он лжец, приведет к противоречию.

Онтологический анализ и представление знаний

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

По-видимому, для решения задач этого класса нам придется иметь дело со следующими объектами.

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

Утверждение, содержащееся в реплике. Это утверждение может быть либо целиком лживым, либо абсолютно правдивым (истинным).

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

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

Существует еще нечто, что мы назовем причинами, или причинными связями (reasons), которые связывают высказывания в том или ином гипотетическом мире. Если А утверждает, что "В — лжец", и мы предполагаем, что А — правдолюбец, то это утверждение является причиной (основанием), по которой мы можем утверждать, что в данном гипотетическом мире В — лжец, а следовательно, все утверждения, которые содержатся в репликах, произносимых В., лживы. Отслеживая такие связи между высказываниями, можно восстановить исходное состояние проблемы, если в результате рассуждений мы придем к противоречию.

Естественно, что эти объекты можно представлять в программе по-разному. Онтологический анализ практически никогда не приводит к единственному способу представления. Для первой версии CLIPS-программы я выбрал следующее представление описанных объектов:

;;Объект statement (высказывание) связан с определенным

;;персонажем (поле speaker).

;;Высказывание содержит утверждение (поле claim).

;;Высказывание имеет основание - причину (поле reason),

;; по которой ему можно доверять,

;;и тэг (tag) - это может быть произвольный

;;идентификатор, (deftemplate statement

(field speaker (type SYMBOL))

(multifield claim (type SYMBOL))

(multifield reason (type INTEGER) (default 0))

(field tag (type INTEGER) (default 1)) )

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

(statement (speaker A) (claim F A))

Этот шаблон можно перевести на "человеческий" язык следующим образом: "Существует высказывание, сделанное персонажем А, в котором утверждается, что А лжец и тэг этого высказывания по умолчанию получает значение 1". Обратите внимание на то, что в поле reason также будет установлено значение по умолчанию (это значение равно 0), т.е. мы можем предположить, что никаких предшествующих высказываний, которые могли бы подтвердить данное, в этой задаче не было.

Обратите внимание, что поля claim и reason имеют квалификатор multifield, поскольку они могут содержать несколько элементов данных (более подробно об этом рассказано в Руководстве пользователя).

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

Утверждение, смысл которого, например, состоит в следующем, ;;Т А ... означает, что А правдолюбец; ;;F А ... означает, что А лжец. ;;Утверждение может иметь под собой ;;основание (reason) - обычно это тэг ;;высказывания (объекта statement) или тэг ;;другого утверждения (объекта claim). ;;Утверждение также характеризуется признаком scope, ;;который может принимать значение "истина" или "ложь", (deftemplate claim



(multifield content (type SYMBOL))

(multifield reason (type INTEGER) (default 0))

(field scope (type SYMBOL)) )

Например, раскрыв содержимое приведенного выше высказывания в предположении, что А говорит правду, получим следующее утверждение (объект claim):

(claim (content F A) (reason 1) (scope truth)).

Таким образом, объект claim наследует содержимое от объекта statement. Последний становится обоснованием (reason) данного утверждения. Поле scope объекта claim принимает значение предположения о правдивости или лживости этого высказывания.

Еще нам потребуется представление в программе того мира (world), в котором мы в настоящее время находимся. Объекты world порождаются в момент, когда мы формируем определенные предположения. Нужно иметь возможность различать разные множества предположений- и идентифицировать их в программе в тот момент, когда процесс размышлений приводит нас к противоречию. Например, противоречие между высказываниями Т(А) и F(A) отсутствует, если они истинны в разных мирах, т.е. при разных предположениях. Если у вас есть на сей счет сомнения, вернитесь вновь к примерам в самом начале раздела А.4.

Миры будем представлять в программе следующим образом:

;;Объект world представляет контекст,

;;сформированный определенными предположениями

;;о правдивости или лживости персонажей.

;;Объект имеет уникальный идентификатор в поле tag,

;;а смысл допущения - истинность или лживость -

;;фиксируется в поле scope,

(deftemplate world

(field tag (type INTEGER) (default 1))

(field scope (type SYMBOL) (default truth)) )

Обратите внимание на то, что при указанных в шаблоне значениях по умолчанию мы можем начинать каждый процесс вычислений с объекта world, имеющего в поле значение 1, причем этот "мир" можно заселить высказываниями персонажей, которых мы предположительно считаем правдолюбцами. Таким образом можно инициализировать базу фактов the-facts для задачи Р0 следующим образом:

;; Утверждение, что А лжец.

(deffacts the-facts

(world)

(statement (speaker A) (claim FA)) )

Если этот оператор deffacts будет включен в тот же файл, что и объявления шаблонов (а также правила, о которых речь пойдет ниже), то после загрузки этого файла в среду CLIPS нам понадобится для запуска программы дать только команду reset.

Определение функций

В языке CLIPS функции конструируются примерно так же, как в языке LISP (см. главу 4). Существенное отличие состоит в том, что переменные должны иметь префикс ?, как это показано в приведенном ниже определении.

(deffunction hypotenuse (?a ?b)

(sqrt (+ ( ?a ?a) ( ?b ?b)) )

Формат определения функции в CLIPS следующий:

(deffunction <имя функции (<аргумент> ... <аргумент>) <выражение>

<выражение> )

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

(deffunction init (?day)

(reset)

(assert (today is ?day)) )

В результате после запуска функции на выполнение командой CLIPS> (init Sunday)

будет выполнена команда reset и, следовательно, очищена база фактов, а затем в нее будет включен новый факт (today is Sunday).

Полный листинг программы

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

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

Программа может обрабатывать конъюнктивные и дизъюнктивные составные утверждения. Программа может решать задачи с множеством высказываний и метавысказываниями.

TEMPLATES

Объект CLAIM имеет следующие поля: CONTENT - содержимое утверждения, например, Т А ... означает, что А является правдолюбцем; F A ... означает, что А является лжецом; OR Т A F В ... означает, что А является правдолюбцем или В является лжецом, и т.д. REASON указывает, на основании какого высказывания сформировано данное утверждение. Значение этого поля равно идентификатору (полю tag) соответствующего объекта statement (высказывание). CONTEXT ::= 0 / 1 / 2; значение 0 означает глобальный контекст, значение 1 означает локальный контекст левого операнда, значение 2 означает локальный контекст правого операнда дизъюнкции,

(deftemplate claim

(multifield content (type SYMBOL))

(field reason (type INTEGER))

(field scope (type SYMBOL))

(field context (type INTEGER) (default 0))

)

;; Объект statement (высказывание) связан с определенным

персонажем (поле speaker).

;;Высказывание содержит утверждение (поле claim).

;;Высказывание имеет основание - причину (поле reason).

;;Если данный объект не является производным от другого

;;объекта statement, в поле reason устанавливается

;;значение 0.

;;В поле tag устанавливается уникальный числовой

;;идентификатор объекта - число, большее 0.

;;В поле DONE устанавливается одно из

;;следующих значений:

;;0 означает, что объект еще не обрабатывался;

;;1 означает, что объект обрабатывался в предположении

;;о правдивости высказывания;

;;2 означает, что объект обрабатывался в предположении

;;о лживости высказывания, (deftemplate statement



(field speaker (type SYMBOL))

(multifield claim (type SYMBOL))

(field scope (type SYMBOL) (default truth))

(multifield reason (type INTEGER) (default 0))

(field tag (type INTEGER) (default 0))

(field done (type INTEGER) (default 0))

)

;;Объект world представляет множество утверждений,

;;сформированных при определенном предположении

;;о правдивости или лживости высказывания,

;;принадлежащего некоторому персонажу.

;;Объект имеет уникальный идентификатор

;;в поле tag, который соответствует

;;тэгу высказывания.

;;Смысл допущения - истинность или лживость -

;;фиксируется в поле scope.

;; Поле TASK содержит одно из перечисленных

;;ниже значений:

CHECK - анализ предположений о

;;правдивости или лживости высказывания;

;;CONTRA - анализ обнаруженного противоречия;

;; CLEAN - удаляет все утверждения, созданные

;;в противоречивом "мире" ;

;;BАСК - откат в точку возврата;

QUIT - прекращение процесса.

;;Поле prior может содержать идентификатор

;;объекта world, обработанного перед тем,

;;как был создан данный объект, и с которым данный

;;объект может потенциально конфликтовать.

;;Поле upper содержит идентификатор другого объекта

;;world, в который внедрен данный объект, если

;;соответствующее высказывание содержит другое

;;высказывание.

;;Например, А говорит, что В сказал, что А - лжец.

;;В поле context сохраняется текущий контекст

;;анализируемого операнда дизъюнкции.

;;Поле done содержит информацию о том, обработано ли

;; уже высказывание, на основании которого создан этот

;; объект.

(deftemplate world

(field tag (type INTEGER) (default 1))

(field scope (type SYMBOL) (default truth))

(field task (type SYMBOL) (default check))

(field prior (type INTEGER) (default 0))

(field upper (type INTEGER) (default 0))

(field context (type INTEGER) (default 0))

(field done (type INTEGER) (default 0))

)

;; ФУНКЦИЙ

;; Изменяет область определения предиката с Т на F

;; и наоборот.

(deffunction flip (?P)



(if (eg ?P Т) then F else T)

)

;; ПРАВИЛА

Распаковка высказываний

;; ЕСЛИ объект world базируется на предположении о

;;правдивости высказывания,

;;ТО предположить, что персонаж говорит правду и что

;;высказывание истинно.

;;Значение поля TAG объекта statement передается в поле

;;reason объектов claim.

;;ПРИМЕЧАНИЕ. Это правило не используется для

;;распаковки метавысказываний. (defrule unwrap-true

?W <- (world (tag ?N) (scope truth) (task check)

(done 0)) ?S <- (statement (speaker ?X)

(claim ?PS:(not (eg ?P SAY)) $?Y) (done 0)) =>

(printout t crlf

"Assuming " T ?X " and " ?P $?Y " in world " ?N

;; "Предполагается " T ?X " and " ?P $?Y " в мире " ?N t crlf

)

;;Зафиксировать, что высказывание было распаковано

;;в предположении о его правдивости,

;;modify ?S (tag ?N) (done 1))

;;Зафиксировать в объекте world, что высказывание

;;распаковано, modify ?W (done 1))

;;Предположим, что персонаж в текущем "мире" является

;;правдолюбцем.

(assert (claim (content Т ?Х) (reason ?N)

(scope truth) ) )

;; Предполагается, что утверждение в высказывании

;; истинно. (assert (claim (content ?P $?Y) (reason ?N)

(scope truth)))

)

;; ЕСЛИ объект world базируется на предположении о

; ; правдивости метавысказывания,

;; ТО предположить , что персонаж говорит правду и что

;; высказывание истинно.

(defrule unwrap-true-state

?W <- (world (tag ?N) (scope truth) (task check)

(done 0)) ?S <- (statement (speaker ?X) (claim SAY ?Z $?Y)

(done 0)) =>

(printout t crlf "Assuming " T ?X " and " ?Z " says " $?Y

" in world " ?N

;; "Предполагается " T ?X " и " ?Z " говорит " $?Y

;; " в мире " ?N t crlf

)

;; Зафиксировать, что высказывание было распаковано

;; в предположении о его правдивости.

(modify ?S (tag ?N) (done 1))

; ; Предположим, что персонаж в текущем мире является



; ; правдолюбцем.

(assert (claim (content T ?X) (reason ?N)

(scope truth) ) )

;; Зафиксировать в объекте world, что высказывание

;; распаковано . (modify ?W (done 1))

; ; Сформировать новый объект world для внедренного

;; высказывания и зафиксировать, что этот объект

;; является внутренним по отношению к объекту

?N. (assert (world (tag (+ ?N 1)) (scope truth)

(upper ?N)))

;; Зафиксировать внедренное высказывание в новом

;; объекте world. (assert (statement (speaker ?Z) (claim $?Y)

(reason ?N)))

)

;; ЕСЛИ объект world базируется на предположении о

;; лживости высказывания,

;; ТО предположить, что персонаж лжет и что

;; высказывание ложно.

;; ПРИМЕЧАНИЕ. Это правило не используется для

;; распаковки метавысказываний. (defrule unwrap-false

?W <- (world (tag ?N) (scope falsity) (task check))

?S <- (statement (speaker ?X)

(claim ?P&:(not (or (eq ?P NOT) (eq ?P SAY))) $?Y)

(tag ?N) (done 1) ) =>

(printout t crlf

"Assuming " F ?X " and NOT " in world " ?N

;; "Предполагается " F ?X " и HE " ?P $?Y " в мире " ?N t crlf

)

;; Зафиксировать, что высказывание анализируется

;; в предположении о его лживости.

(modify ?S (scope falsity) (done 2))

;; Зафиксировать в объекте world, что анализируется

;; лживость высказывания.

(modify ?W (done 2))

;; Предположим, что персонаж лжец.

(assert (claim (content F ?X) (reason ?N)

(scope falsity)))

;; Сформировать отрицание утверждения,

(assert (claim (content NOT ?P $?Y) (reason ?N)

(scope falsity))) )

ЕСЛИ объект world базируется на предположении о лживости метавысказывания, ТО предположить, что персонаж лжет. Каких-либо предположений об истинности утверждения не делается.

ПРИМЕЧАНИЕ. Правило используется только для работы с метавысказываниями, которые не содержат отрицаний. Правило не может обрабатывать метавысказываний вида: А: "В не говорил, что он лжец." или А: "В говорил, что он не лжец." (defrule unwrap-false-state



?W <- (world (tag ?N) (scope falsity)

(task check)) ?S <- (statement (speaker ?X)

(claim SAY ?Z $?Y)

(tag ?N) (done 1)) =>

(printout t crlf "Assuming " F " "?X "

and NOT " ?Z " says " $?Y

" in world " ?N

;; "Предполагается " F " "?X " и HE " ?Z " говорит

;; " $?Y " в мире " ?N t crlf

)

;; Изменить значение в поле scope текущего объекта

;; world.

(modify ?W (scope falsity) (done 2))

;; Зафиксировать, что высказывание было распаковано

;; в предположении о лживости,

(modify ?S (scope falsity) (done 2))

;; Предположить, что в текущем "мире" персонаж,

;; произнесший метавысказывание, лжец,

(assert (claim (content F ?X) (reason ?N)

(scope falsity))) )

;;-------------------------------

;; ЛОГИЧЕСКИЕ ОПЕРАТОРЫ

;; Правила отрицания

;; ЕСЛИ некто не правдолюбец,

;; ТО он лжец. (defrule notl

(declare (salience 5))

?F <- (claim (content NOT Т ?P)) =>

(modify ?F (content F ?P)) )

;; ЕСЛИ некто не лжец,

;; ТО он правдолюбец, (defrule not2

(declare (salience 5))

?F <- (claim (content NOT F ?P)) =>

(modify ?F (content Т ?Р)) )

;;---------------------

;; Распространение отрицания на дизъюнкцию,

(defrule not-or

(declare (salience 5))

?F <- (claim .(content NOT OR ?P ?X ?Q ?Y)) =>

(modify ?F (content AND (flip ?P) ?X (flip ?Q) ?Y))

)

;;-------------------------

;; Распространение отрицания на конъюнкцию,

(defrule not-and

(declare (salience 5))

?F <- (claim (content NOT AND ?P ?X ?Q ?Y)) =>

(modify ?F (content OR (flip ?P) ?X (flip ?Q) ?Y))

)

;;------------------------------

;; Устранение конъюнкции, (defrule conj

(world (tag ?N) (scope ?V) (task check)

(context ?L)) (claim (content AND ?P ?X ?Q ?Y) (reason ?N)

(scope ?V) (context ?L) =>

(assert (claim (content ?P ?X) (reason ?N)

(scope ?V) (context ?L))

(assert (claim (content ?Q ?Y) (reason ?N)



(scope ?V) (context ?L))

;; ОБРАБОТКА ДИЗЪЮНКТИВНЫХ УТВЕРЖДЕНИЙ

)

;; ЕСЛИ мы имеем дело с дизъюнктивным утверждением,

;; т.е. context = 0,

;; ТО сначала проанализировать левый дизъюнкт.

;; ПРИМЕЧАНИЕ. Устанавливается значение 1 как в поле

;; context объекта world, так и в поле context нового

; ; объекта claim.

(defrule left-disjunct

?W <- (world (tag ?N) (task check)

(scope ?V) (context 0))

(claim (content OR ?P ?X ?Q ?Y) (reason ?N)

(scope ?V) (context 0» =>

(assert (claim (content ?P ?X)

(reason ?N) (scope ?V) (context 1)))

(modify ?W (context 1))

)

;; ЕСЛИ при анализе левого дизъюнкта обнаружено

;; противоречие ,

;; ТО проанализировать правый дизъюнкт.

(defrule right-disjunct

(declare (salience 10))

?W <- (world (tag ?N) (task contra) (context 1))

(claim (content OR ?P ?X ?Q ?Y) (reason ?N)

(scope ?V)) =>

(assert (claim (content ?Q ?Y)

(reason ?N) (scope ?V) (context 2)))

(modify ?W (task check) (context 2))

)

;; ЕСЛИ выполнен откат к анализу правого дизъюнкта,

;; ТО установить соответствующий контекст.

(defrule resume-disjunct

?W <- (world (tag ?N) (task back) (context 1))

(claim (content OR ?P ?X ?Q ?Y) (reason ?N) (scope ?V))

=>

(assert (claim (content ?Q ?Y) (reason ?N)

(scope ?V) (context 2))) (modify ?W

(task check) (context 2))

)

;; ЕСЛИ анализ обоих дизъюнктов в предположении о

;; правдивости персонажа привел к противоречию

;; в том же самом "мире" ,

;; ТО выполнить анализ, предполагая, что персонаж лжет.

(defrule false-disjuncts

?W <- (world (tag ?M) (scope truth)

(task contra) (prior 0) (context 2))

(not (claim (reason ?M) (context 2))) =>

(modify ?W (scope falsity) (task check) (context 0))

)

;; ЕСЛИ анализ в предположении о правдивости персонажа

;; привел к противоречию с другим "миром" ,

;; ТО выполнить анализ, предполагая, что персонаж лжет.

(defrule other-world

?W <- (world (tag ?N) (scope truth) (task contra)



(prior ?M&"0) (context 0)) =>

(modify ?W (scope falsity) (task check))

)

;;ОБРАБОТКА ПРОТИВОРЕЧИЙ

;; ЕСЛИ обнаруживается противоречие между предположением

;;и производными от него фактами в пределах одного и

;;того же мира и в одном и том же контексте,

;;ТО зафиксировать противоречие и удалить

;;противоречивые утверждения (объекты claim)

;;из базы фактов, (defrule contradiction

(declare (salience 100))

?W <- (world (tag ?N) (task check) (scope ?V)

(context ?S)) ?P <- (claim

(content ?F ?X) (scope ?V) (reason ?N)

(context ?S)) ?Q <- (claim

(content ?G&:(-not (eq ?G ?F)) ?X)

(scope ?V) (reason ?N) (context ?S)) =>

(printout t crlf

"CONTRADICTION: " ?F ?X " versus " ?G ?X "in world " ?N

;; "ПРОТИВОРЕЧИЕ между: " ?F ?X " и "?G ?X "в мире " ?N

t crlf) (retract ?P) (retract ?Q)

(modify ?W (task contra))

;; ЕСЛИ обнаруживается противоречие между предположением

;; и производными от него фактами в пределах одного и

;; того же мира, но в разных контекстах,

;; ТО зафиксировать противоречие.

(defrule transcontext

(declare (salience 90))

?W <- (world (tag ?N) (task check) (scope ?V)

(context ?T))

(claim (content ?F ?X) (scope ?V) (reason ?N)

(context ?S&:(< ?S ?T)))

(claim (content ?G&:(not (eq ?G ?F)) ?x') (scope ?V)

(reason ?N) (context ?T)) =>

(printout t crlf

"TRANSCONTEXT CONTRADICTION: " ?F ?X " versus "

?G ?X " in world " ?N

;; "ТРАНСКОНТЕКСТНОЕ ПРОТИВОРЕЧИЕ между: "

?F ?X ;; " и "?G ?X "в мире " ?N

t crlf) (modify ?W (task contra))

)

;; ЕСЛИ обнаруживается противоречие между

;; текущим "миром" в предположении о правдивости

;; и ранее покинутым "миром",

;; ТО зафиксировать противоречие.

(defrule transworld-truth (declare (salience 80))

?W <- (world (tag ?N) (scope truth) (task check)

(upper 0))

;; В текущем "мире" имеется утверждение,



;; противоречащее утверждению в другом "мире",

(claim (content ?F ?X) (reason ?N))

;; "Мир", с которым обнаружен конфликт, имеет

;; идентификатор, меньший, чем текущий "мир",

;; т.е. сформирован раньше,

(claim (content ?G&:(not (eq ?G ?F)) ?X)

(reason ?M&:(< ?M ?N))) =>

(printout t crlf

"TRANSWORLD CONTRADICTION: " ?F ?X "

versus ?G ?X " in worlds " ?N "|" ?M

;; "МЕЖМИРОВОЕ ПРОТИВОРЕЧИЕ: " ?F ?X " противоречит

;; ?G ?X " в мирах " ?N "|" ?M

t crlf) (modify ?w (task contra))

;;ЕСЛИ обнаруживается противоречие между

;;текущим "миром" в предположении о лживости

;;и ранее покинутым "миром",

;;ТО подготовиться к выполнению отката в ранее

;;покинутый "мир". (defrule transworld-falsity

(declare (salience 80)) ?W <- (world (tag ?N)

(scope falsity)

(task check) (upper 0)) (claim (content ?F ?X)

(reason ?N)) (claim

(content ?G&:(not (eq ?6 ?F)) ?X) (reason ?M&:(< ?M ?N))) =>

(printout t crlf

"TRANSWORLD CONTRADICTION: " ?F ?X "

versus ?G ?X " in worlds " ?N "|" ?M

;; "МЕЖМИРОВОЕ ПРОТИВОРЕЧИЕ: " ?F ?X " противоречит

;; ?G ?X " в мирах " ?N "|" ?M

t crlf) (modify ?W (task contra) (prior ?M))

ЕСЛИ обнаружено противоречие между внедренным "миром" метавысказывания и ранее покинутым "миром", ТО удалить высказывание, связанное с внедренным "миром"

(defrule upper-world

(declare (salience 80))

?W <- (world (tag ?N)

(task check) (upper ?U&"0))

(claim (content ?F ?X) (reason ?N))

(claim

(content ?G&:(not (eq ?G ?F) ) ?X)

(reason ?M&:(< ?M ?N))) ?S <- (statement (tag ?N) (reason ?U)) =>

(printout t crlf

"TRANSWORLD CONTRADICTION: " ?F ?X "

versus " ?G ?X " in worlds " ?N "|" ?M

;; "МЕЖМИРОВОЕ ПРОТИВОРЕЧИЕ: " ?F ?X "



противоречит " ;; ?G ?X " в мирах " ?N "|" ?M

t crlf) (retract ?S) (modify ?W (task contra) (prior ?U))

;;ОПЕРАЦИИ УДАЛЕНИЯ

;; Удаление дизъюнкта, (defrule clean-context

(declare (salience 50)) (world

(tag ?N)

(task ?T&:(or (eg ?T contra) (eq ?T back))

(context ?S&~0))

?F <- (claim (reason ?N) (context ?S)) =>

(retract ?F)

;; ЕСЛИ текущий мир проанализирован только

;; в предположении о правдивости,

;; ТО проанализировать его, предполагая

;; лживость персонажа.

(defrule switch-scope

(declare (salience 40))

?W <- (world (tag ?N) (scope truth) (task contra)

(context ?C&~1) =>

(modify ?W (scope falsity) (task check))

)

;; Удалить все утверждения, сделанные в предположении

;; о правдивости, перед тем как анализировать

;; предположение о лживости, (defrule sweep-claims

(declare (salience 100))

(world

(tag ?N) (scope truth) (context ?C&~1)

(task ?T&:(or (eq ?T contra) (eq ?T back))))

?F <- (claim (reason ?N) (scope truth) (context ?D&~1)) =>

(retract ?F)

)

;; Удалить все объекты statement, основанные на предположении

;; о правдивости, перед тем как анализировать

;; предположение о лживости, (defrule sweep-statements

(declare (salience 100))

(world

(tag ?N) (task ?T&:(or (eq ?T contra)

(eq ?T back))) (scope truth) (context 0))

?F <- (statement (reason ?N) (scope truth)) =>

(retract ?F)

)

;; Удалить утверждения, связанные с "миром",

;; в котором обнаружены противоречия.

(defrule kill-claims

(declare (salience 100)) (world (tag ?N)

(task clean)) ?F <- (claim (reason ?N))

=>

(retract ?F)

)

;; ЕСЛИ все ненужные объекты claim или statement удалены,

;; ТО удалить объект world, которому назначена задача clean,

(defrule stop-killing

(declare (salience 100))

?W <- (world (tag ?N) (task clean))

(not (claim (reason ?N))) =>

(retract ?W)

)

;;ОПЕРАЦИИ ОТКАТА

Хронологический откат к тому "миру", который был покинут без выполнения анализа в предположении о лживости (поле scope содержит значение truth, а поле task - значение check).



(defrule undirected-falsity (declare (salience 20))

(world (tag ?N) (scope falsity)

(task contra)) ?W <- (world (tag ?M&:(< ?M ?N))

(scope truth) (task check)) =>

(modify ?W (task back))

;;Хронологический откат к тому "миру", который был

;; покинут без завершения анализа дизъюнктов,

(defrule undirected-disjunct (declare (salience 20))

(world (tag ?N) (scope falsity) (task contra))

?V <- (world (tag ?M&:(< ?M ?N)) (task check)

(context 1)) (claim (content OR ?P ?X ?Q ?Y) (reason ?M)

(scope ?S)) =>

;; Дизъюнкт в ранее покинутом "мире", анализ которого

;; не был выполнен.

(assert (claim (content ?Q ?Y) (reason ?M) (scope ?S)

(context 2));

;; Зафиксировать необходимость отката в этот "мир".

(modify ?V (task back))

;; Удаление объектов world .

;; ЕСЛИ выполняется откат к объекту М,

;; ТО удалить все объекты world,

;; имеющие идентификатор, больший М.

(defrule undo-world

(declare (salience 50)) (world (tag ?M)

(task back)) ?W <- (world (tag ?N&:(> ?N ?M))) ==>

(retract ?W)

)

;; Откат к прежним высказываниям.

(defrule restate

(declare (salience 50)) (world (tag ?M)

(task back)) ?S <- (statement (tag ?N&:

(> ?N ?M)] (reason 0) (done ?X&"0))

=>

(modify ?S (done 0))

)

;; Удаление объектов claim.

;; ЕСЛИ выполняется откат к объекту world M,

;; ТО удалить все объекты claim,

;; связанные с удаленными объектами world.

(defrule unclaim

(declare (salience 30))

(world (tag ?H) (task back))

?F <- (claim (reason ?N&:(> ?N ?M))) =>

(retract ?F)

)

;; Удаление объектов statement.

;; ЕСЛИ выполняется откат к объекту world M,

;; ТО удалить все объекты statement,

;; связанные с удаленными объектами world.

(defrule unstate

(declare (salience 30))

(world (tag ?M) (task back))

?F <- (statement (reason ?N&:(> ?N ?M))) =>

(retract ?F)

)

;;Возобновление процесса вычислений,

;;начиная с точки возврата.



;;ЕСЛИ все объекты world, созданные

;;после объекта М, удалены,

;;ТО повторно сформировать объект М,

;;предположив лживость высказывания.

(defrule restart

(declare (salience 20))

?W <- (world (tag ?M) (scope truth)

(task back) (context ?C&~1)) =>

(modify ?W (scope falsity) (task check) (context 0))

)

;;ПЕРЕХОД К АНАЛИЗУ СЛЕДУЮЩЕГО "МИРА" И

;;ВЫВОД ОТЧЕТА О РЕЗУЛЬТАТАХ

;;Переход к анализу следующего "мира",

;; ЕСЛИ никакие другие правила не ожидают активизации,

;;ТО анализ текущего "мира" завершен и

;;можно приступить к формированию нового "мира",

;;если имеются необработанные высказывания.

;;ПРИМЕЧАНИЕ. Это правило имеет приоритет,

;;более низкий, чем все прочие правила,

;;исключая правило вывода результатов,

(defrule move

(declare (salience -50))

;;Существует "мир", сформированный на основе

;;исходного высказывания.

?W <- (world (tag ?N&:(> ?N 0)) (task check))

;;В базе фактов отсутствуют объекты world,

;;созданные позже текущего.

(not (world (tag ?T&:(> ?T ?N))))

В базе фактов имеется высказывание, подготовленное к созданию нового объекта world.

(statement (reason 0) (done 0)) =>

;; Сформировать новый объект world на основе

;; этого объекта statement.

(assert (world (tag (+ ?N 1))))

)

;;ЕСЛИ отсутствуют противоречия в объектах world,

;;ТО распечатать результаты.

;;ПРИМЕЧАНИЕ. Это правило будет активизироваться

;;повторно до тех пор, пока не будет выведена

;;непротиворечивая интерпретация,

(defrule report-results

(declare (salience -40)) (not (world (task contra)))

(not (statement (reason 0) (done 0)))

(statement (tag ?N) (done ?MS~0))

(claim (content ?P ?X) (reason ?N)) =>

(printout t crlf

"RESULT: " ?P ?X " from statement " ?N

;; "РЕЗУЛЬТАТ: " ?P ?X " из высказывания " ?N

t crlf)

;; ЕСЛИ противоречие остается и после анализа всех точек отката

;; и нет больше правил, которые можно было бы активизировать,



;; ТО прекратить процесс вычислений,

(defrule sanity-check

(declare (salience -100))

(world (tag ?N) (task ?T&:(or (eg ?T contra)

(eq ?T back))))

(not (world (tag ?M&:(< ?M ?N))

(scope truth) (task check))) =>

(printout t crlf

"FAIL: Statements inconsistent, detected in world " ?N

;; "РЕШЕНИЕ НЕ НАЙДЕНО: Высказывания противоречивы,

;; обнаружены в мире " ?N

t crlf) (halt)

)

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

методику прямого логического вывода, которая обеспечивает разрешение конфликтов (глава 5);

целенаправленный логический вывод с использованием лексем задач (главы 5 и 14);

анализ множества контекстов при разных исходных предположениях (главы 17 и 19).

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

Правила

В языке CLIPS правила имеют следующий формат:

(defrule <имя правила>

< необязательный комментарий >

< необязательное объявление >

< предпосылка_1 >

< предпосылка_т > =>

< действие_1 >

< предпосылка_п > )

Например:

(defrule chores

"Things to do on Sunday"

(salience 10)

(today is Sunday)

(weather is warm) =>

(assert (wash car))

(assert (chop wood) )

В этом примере Chores — произвольно выбранное имя правила. Предпосылки в условной части правила

(today is Sunday) (weather is warm)

сопоставляются затем интерпретатором с базой фактов, а действия, перечисленные в выполняемой части правила (она начинается после пары символов =>), вставят в базу два факта

(wash car) (chop wood)

в случае, если правило будет активизировано. Приведенный в тексте правила комментарий

"Things to do on Sunday"

"Что сделать в воскресенье"

поможет в дальнейшем вспомнить, чего ради это правило включено в программу. Выражение

(salience 10)

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

(defrule fun

"Better things to do on Sunday"

(salience 100)

(today is Sunday)

(weather is warm) =>

(assert (drink beer))

(assert (play guitar)) )

Поскольку предпосылки обоих правил одинаковы, то при выполнении оговоренных условий они будут "конкурировать" за внимание интерпретатора. Предпочтение будет отдано правилу, у которого параметр salience имеет более высокое значение, в данном случае — правилу fun. Параметру salience может быть присвоено любое целочисленное значение в диапазоне [-10 000, 10 000]. Если параметр salience в определении правила опущен, ему по умолчанию присваивается значение 0.

Обычно в определении правила присутствуют и переменные. Если, например, правило

(defrule pick-a-chore

"Allocating chores to days"

(today is ?day)

(chore is ?job) =>

(assert (do ?job on ?day)) )

Правили функции в CLIPS

CLIPS включает в язык представления порождающих правил и язык описания процедур.

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

Основными компонентами языка описания правил являются база фактов (fact base) и база правил (rule base). На них возлагаются следующие функции:

база фактов представляет исходное состояние проблемы (см. главу 2);

база правил содержит операторы, которые преобразуют состояние проблемы, приводя его к решению (см. главы 2 и 3).

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

(1) сопоставление фактов и правил;

(2) выбор правила, подлежащего активизации;

(3) выполнение действий, предписанных правилом.

Такой трехшаговый циклический процесс иногда называют "циклом распознавание— действие" (см. главу 5).

Программирование нязыке CLIPS

А.1. Краткая история CLIPS

А.2. Правила и функции в CLIPS

А.З. Объектно-ориентированные средства в CLIPS

А.4. Задача "Правдолюбцы и лжецы"

А.5. Стиль программирования на языке CLIPS

Упражнения

Расширение наборправил — работс составными высказываниями

А.4.4. Расширение набора правил — работа с составными высказываниями

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

Р4. Встречаются два персонажа, А и В, каждый из которых либо лжец, либо правдолюбец. Персонаж А говорит: "Мы оба лжецы". К какой категории следует отнести каждого из них?

В этой задаче нам придется иметь дело с конъюнкцией, поскольку утверждение, высказанное персонажем А, моделируется выражением

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

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

Т(А) v Т(B).

Таким образом, в программу нужно включить правило выполнения отрицания составных высказываний и правило, которое "понимало" бы, что дизъюнкты вроде Т(А) в действительности являются предположениями. Составное выражение Т(А) v T(B) будем обрабатывать, предположив Т(А), и проанализируем, нет ли в нем противоречия. Если таковое не обнаружится, то можно предположить, что Т(А) v Т(B) совместимо с утверждением о том, что А лгун, т.е. F(A). Но если предположение Т(А) приведет к несовместимости, то нужно отказаться от него и предположить Т(Е). Если и это предположение приведет к несовместимости, то это означает, что утверждение Т(А) v T(B) несовместимо с предположением F(A). В противном случае Т(В) образует часть совместимой интерпретации исходного высказывания.

В CLIPS составные высказывания проще всего представлять с помощью так называемой "польской" (или префиксной) нотации операций.
Суть этого способа представления операций состоит в том, что символ операции предшествует символам операндов. Каждый оператор имеет фиксированное количество операндов, а потому всегда существует возможность однозначно установить область действия операции даже в случае, если операнды представляют собой вложенные выражения. Таким образом, выражение, представленное скобочной формой —(F(/4) ^ Т(В)), в польской записи будет иметь вид

NOT AND F А Т В.

Легче всего восстановить исходный вид выражения, представленного в польской нотации, просматривая его справа налево. При этом операнды считываются до тех пор, пока не встретится объединяющий их оператор. Полученное выражение оказывается операндом следующего оператора. В представленном выше выражении В является операндом одноместного оператора Т, а пара операндов Т(В) и F(A) объединяется оператором AND.

Задавшись таким способом представления составных высказываний, сформируем правило выполнения отрицания дизъюнктивной и конъюнктивной форм, в котором будет использоваться функция flip, заменяющая "Т" на "F" и наоборот.

(defrule not-or

?F <- (claim (content NOT OR ?P ?X ?Q ?Y)) =>

(modify ?F (content AND (flip ?P) ?X (flip ?Q) ?Y))

(defrule not-and

?F <- (claim (content NOT AND ?P ?X ?Q ?Y)) =>

(modify ?F (content OR (flip ?P) ?X (flip ?Q) ?Y)) )

Использование функции flip упрощает преобразование и позволяет перейти от выражения

NOT AND F А Т В

прямо к

OR Т A F В,

минуя

OR NOT F A NOT Т В.

Функция flip определена следующим образом:

(def function flip (?P)

(if (eq ?P Т) then F else T) )

Для упрощения мы ограничимся утверждениями в виде простых дизъюнкций или конъюнкций вида

Т(А) v Т(В)

или

F(A) ^ T(B),

но не будем использовать более сложные утверждения в форме

F(B) ^ (T(А) v T)B))

или

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

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


Например, нет противоречия между F(A) и Т(А) v F(B). Противоречие, которое обнаружится при обработке первого операнда дизъюнкции ДЛ) в предположении F(A), будет локальным в контексте Т(А). Но если мы вернемся к исходной дизъюнкции и попробуем проанализировать контекст F(B), то никакого противоречия обнаружено не будет, и, следовательно, интерпретация найдена.

Реализовать такой анализ локальных и глобальных противоречий можно, добавив в шаблон объекта claim атрибут context:

(def template claim

(multifield content (type SYMBOL))

(multifield reason (type INTEGER)

(default 0)) (field scope (type SYMBOL))

(field context (type INTEGER) (default 0)) )

Значение 0 в поле context означает, что мы имеем дело с глобальным контекстом, значение 1 — с локальным контекстом левого операнда, а значение 2 — с локальным контекстом правого операнда дизъюнкции. Пусть, например, анализируется дизъюнкция

T(A) v F(B)

причем Т(А) будет истинным в контексте 1, a F(B)— истинным в контексте 2. В этом случае все выражение будет истинным глобально, т.е. в контексте 0.

Структуру объекта world также нужно модифицировать — внести в нее поле context. Это позволит отслеживать ход вычислений. Пусть, например, объект world имеет вид

(world (tag 1) (scope truth) (context 2)).

Это означает, что данный "мир" создан следующей парой предположений:

истинно высказывание, имеющее идентификатор (tag), равный 1, и

правый операнд утверждения, которое содержится в этом высказывании, имеет значение "истина".

Новый вариант шаблона объекта world приведен ниже.

Объект world представляет контекст, сформированный определенными предположениями о правдивости или лживости персонажей.

Объект имеет уникальный идентификатор в поле tag, а смысл допущения - истинность или лживость - фиксируется в поле scope.

В поле context сохраняется текущий контекст анализируемого операнда дизъюнкции.

0 означает глобальный контекст дизъюнкции,

1 означает левый операнд,

2 означает правый операнд, (deftemplate world



(field tag (type INTEGER) (default 1))

(field scope (type SYMBOL) (default truth))

(field context (type INTEGER) (default 0)) )

Следующий шаг— разработка правил, манипулирующих контекстом. Приведенное ниже правило формирует контекст для левого операнда дизъюнкции.

(defrule left-or

?W <- (world (tag ?N) (context 0))

(claim (content OR ?P ?X ?Q ?Y)(reason ?N)

(scope ?V)) =>

(modify ?W (context 1)) (assert (claim

(content ?P ?X) (reason ?N) (scope ?V)

(context 1))) )

Это правило устанавливает значение 1 в поле context объекта world и формирует соответствующий объект claim.

По этому же принципу разработаем правило для формирования контекста правого операнда дизъюнкции.

(defrule right-or

?W <- (world (tag ?N) (context 1))

(claim (content OR ?P ?X ?Q ?Y) (reason ?N)

(scope ?V)) =>

(modify ?W (context 2)) (assert (claim

(content ?Q ?Y) (reason ?N) (scope ?V) (context 2))

)

Упражнение 2

Разработайте самостоятельно правило, которое оперировало бы с объектом claim содержим утверждение в конъюнктивной форме, как показано ниже.

(claim (content AND Т A F В) (reason 1) (scope truth))

Это правило должно разделить такое утверждение на два: суть первого — утверждение, что А — правдолюбец, а второго — утверждение, что В — лжец. Новые объекты claim должны существовать в текущем контексте, определенном в объекте world.

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

;; Выявление противоречия между предположением о

;; правдивости и следующими из него фактами

;; в разных контекстах одного и того же объекта world,

(defrule contra-truth-scope

(declare (salience 10)) (world (tag ?N)

(scope truth) (context ?T)) (claim

(content Т ?Х) (reason ?N) (scope truth)

(context ?S&:(< ?S ?T))) ?Q <- (claim

(content P ?x) (reason ?N)

(scope truth) (context ?T)) =>

(printout t "Disjunct " ?T

" is inconsistent with earlier truth context. "



;; "Дизъюнкт " ?T

;; " противоречит ранее установленному контексту правдивости.

" crlf)

(retract ?Q)

)

;; Выявление противоречия между предположением о

;; лживости и следующими из него фактами

;; в разных контекстах одного и того же объекта world.

(defrule contra-falsity-scope (declare (salience 10))

?W <- (world (tag ?N) (scope falsity)

(context ?T» (claim

(content F ?X) (reason ?N) (scope falsity)

(context ?S&:(< ?S ?T))) ?Q <- (claim (content Т ?Х)

(reason ?N)

(scope falsity) (context ?T)) =>

(printout t "Disjunct " ?T

" is inconsistent with earlier falsity context."

;; "Дизъюнкт " ?T

;; " противоречит ранее установленному контексту лживости . "

crlf)

(retract ?Q) )

Нам потребуется модифицировать и прежний вариант правила centra-truth.

;; Выявление противоречия между предположением о

;; правдивости и следующими из него фактами

;; в одном и том же контексте одного и того же объекта world .

(defrule contra-truth

(declare (salience 10))

?W <- (world (tag ?N) (scope truth))

?P <- (claim (content Т ?Х) (reason ?N)

(context ?S)

(scope truth) ) ?Q <- (claim (content F ?X)

(reason ?N) (context ?S)

(scope truth) ) =>

(printout t

"Statement is inconsistent if "?X " is a knight"

;; "Высказывание противоречиво, если " ? X

;; " правдолюбец . "

crlf)

(retract ?Q) (retract ?P) (modify ?W (scope falsity) (context 0)

;; Выявление противоречия между предположением о

;; лживости и следующими из него фактами

;; в одном и том же контексте одного и того же объекта world.

(defrule contra-falsity (declare (salience 10))

?W <- (world (tag ?N) (scope falsity))

?P <- (claim (content F ?X) (reason ?N)

(context ?S) (scope falsity))

?Q <- (claim (content Т ?Х) (reason ?N)

(context ?S)(scope falsity)) =>

(printout t

"Statement is inconsistent whether " ?X

" is knight or knave."



;; "Высказывание противоречиво, независимо от того,"

;; "является ли " ?Х " правдолюбцем или лжецом."

crlf)

(modify ?W (scope contra) )

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

(defrule consist-truth

(declare (salience -10))

?W <- (world (tag ?N) (scope truth))

(statement (speaker ?Y) (tag ?N)) =>

(printout t

"Statement is consistent:"

;; "Высказывание непротиворечиво:"

crlf)

(modify ?W (scope consist)

)

(defrule consist-falsity

(declare (salience -10)) ?W <- (world (tag ?N)

(scope falsity)) (statement (speaker ?Y) (tag ?N)) =>

(printout t

"Statement is consistent:"

;; "Высказывание непротиворечиво:"

crlf) (modify ?W (scope consist)

)

(defrule true-knight

(world (tag ?N) (scope consist))

?C <- (claim (content T ?X) (reason ?N) =>

(printout t

?X "is a knight" ;; ?X "- правдолюбец"

crlf) (retract ?C)

)

(defrule false-knave

(world (tag ?M) (scope consist))

?C <- (claim (content F ?X) (reason ?N))

(printout t

?X " is a knave" ;; ?X "- лжец"

crlf)

(retract ?C) )

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

(defrule conj

(world (tag ?N (context ?S))

(claim (content AND ?P ?X ?Q ?Y) (reason ?N)

(scope ?V)) =>

(assert (claim

(content ?P ?X) (reason ?N) (scope ?V)

(context ?S))) (assert (claim

(content ?Q ?Y) (reason ?N) (scope ?V)

(context ?S))) )

Прежде чем запустить программу на выполнение, сформируем исходные факты в соответствии с условиями задачи Р4:

(deffacts the-facts

(world)

(statement (speaker A) (claim AND F A F B) (tag 1)) )



После запуска программы в режиме трассировки интерпретатор сформирует распечатку процесса ее выполнения, приведенную в листинге А.2.

Листинг А.2. Трассировка решения задачи Р4

CLIPS> (reset)

==> f-0 (initial-fact)

==> f-1 (world (tag 1) (scope truth) (context 0))

==> f-2 (statement (speaker A)

(claim OR F A T B) (reason 0) (tag 1))

CLIPS> (run)

FIRE 1 unwrap-trues f-1,f-2

Assumption

A is a knight, so (OR F A T B) is true.

==> f-3 (claim (content OR F A T B)

(reason 1) (scope truth) (context 0))

==> f-4 (claim (content T A) (reason 1)

(scope truth) (context 0)) FIRE 2 left-or: f-1,f-3

==> f-5 (claim (content F A) (reason 1)

(scope truth) (context 1))

<== f-1 (world (tag 1) (scope truth) (context 0))

==> f-6 (world (tag 1) (scope truth) (context 1))

FIRE 3 contra-truth-scope: f-6,f-4,f-5

Disjunct 1 is inconsistent with earlier truth context.

<== f-5 (claim (content F A) (reason 1)

(scope truth) (context 1)) FIRE 4 right-or: f-6,f-3 .

==> f-7 (claim (content Т В) (reason 1)

(scope truth) (context 2))

<== f-6 (world (tag 1) (scope truth)

(context 1))

==> f-8 (world (tag 1) (scope truth)

(context 2))

FIRE 5 consist-truth: f-8, f-2

Statement is consistent:

<== f-8 (world (tag 1) (scope truth) (context 2))

==> f-9 (world (tag 1) (scope consist) (context 2))

FIRE 6 true-knight: f-9, f-7

В is a knight

<== f-7 (claim (content Т В) (reason 1)

(scope truth) (context 2))

FIRE 7 true-knight: f-9,f-4

A is a knight

<== f-4 (claim (content Т A) (reason 1)

(scope truth) (context 0))

CLIPS>

Разработкправил

В этом разделе мы рассмотрим набор правил, который помогает справиться с вырожденной формулировкой Р0 задачи о лжецах и правдолюбцах. Первые два правила, unwrap-true и unwrap-false, извлекают содержимое высказывания в предположении, что персонаж, которому принадлежит высказывание, является соответственно правдолюбцем или лжецом, и на этом основании формируют объект claim.

;; Извлечение содержимого высказывания,

(defrule unwrap-true

(world (tag ?N) (scope truth))

(statement (speaker ?X) (claim $?Y) (tag ?N)) =>

(assert (claim (content Т ?Х) (reason ?N)

(scope truth)))

(assert (claim (content $?Y) (reason ?M)

(scope truth)))

)

(defrule unwrap-false

(world (tag ?N) (scope falsity))

(statement (speaker ?X) (claim $?Y) (tag ?N)) =>

(assert (claim (content F ?X) (reason ?N)

(scope falsity)))

(assert (claim (content NOT $?Y) (reason ?N)

(scope falsity)) )

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

Далее нам понадобятся правила, которые введут отрицания в выражения. Поскольку —<Т(А) эквивалентно F(A), a —F(A) эквивалентно Т(А), то правила, выполняющие соответствующие преобразования, написать довольно просто. Анализ результатов применения этих правил значительно упростит выявление противоречий, следующих из определенного предположения.

;; Правила отрицания (defrule notl

?F <- (claim (content NOT Т ?Р)) =>

(modify ?F (content F ?P))

)

(defrule not2

?F <- (claim (content NOT F ?P)) =>

(modify ?F (content Т ?Р))

)

;; Выявление противоречия между предположением о

;; правдивости и следующими из него фактами,

(defrule contra-truth

(declare (salience 10))

?W <- (world (tag ?N) (scope truth))

?S <- (statement (speaker ?Y) (tag ?N))

?P <- (claim (content Т ?Х) (reason ?N) (scope truth))



?Q <- (claim (content F ?X) (reason ?N) (scope truth)) =>

(printout t crlf

"Statement is inconsistent if " ?Y " is a knight."

;; "Высказывание противоречиво, если " ?Y " правдолюбец."

t crlf)

(retract ?Q)

(retract ?P)

(modify ?W (scope falsity)) )

Если предположить, что исходное высказывание было правдивым, то в дальнейшем обнаруживается противоречивая пара утверждений, которые затем удаляются из рабочей памяти, а значение "правдивости" предположения в объекте world изменяется на falsity (лживость). Если же после этого также будет обнаружено противоречие, то мы приходим к выводу о глобальной несовместимости условий задачи, т.е. в данной постановке мы имеем дело с логическим парадоксом.

;; Выявление противоречия между предположением о

;; лживости и следующими из него фактами, (defrule contra-falsity

(declare (salience 10))

?W <- (world (tag ?N) (scope falsity))

?S <- (statement (speaker ?Y) (tag ?N))

?P <- (claim (content F ?X) (reason ?N) (scope falsity))

?Q <- (claim (content T ?X) (reason ?N)

(scope falsity)) => (printout t crlf

"Statement is inconsistent if " ?Y " is a knave. "

;; "Высказывание противоречиво, если " ?Y " лжец." t crlf)

(modify ?W (scope contra))

Правило sweep обеспечивает проверку, все ли следствия из неверного предположения удалены из памяти.

;; Удалить из базы фактов все утверждения,

;; которые следуют из предположения о правдивости.

(defrule sweep

(declare (salience 20))

(world (tag ?N) (scope falsity))

?F <- (claim (reason ?N) (scope truth)) =>

(retract ?F)

Обратите внимание на то, что правила contra-truth, contra-f alsity и sweep имеют более высокий приоритет (значение параметра salience), чем другие правила. Этим обеспечивается как можно более ранее обнаружение противоречия, а следовательно, и удаление из базы фактов утверждений, сделанных на основе предположения, приведшего к противоречию.



Если теперь запустить на выполнение программу, представив ей исходный набор фактов, соответствующих условию задачи РО, то программа обнаружит, что оба контекста противоречивы. Другими словами, независимо от того, предполагаем ли мы, что А говорит правду или лжет, программа обнаружит противоречие в контексте world. Трассировка программы в этом случае представлена в листинге А. 1. Строки, выведенные курсивом, — сообщения основной программы, а прочие — сообщения программы трассировки. Для удобства строки, указывающие на активизацию правил, представлены полужирным шрифтом.

Листинг А.1. Трассировка решения задачи Р0

CLIPS> (reset)

==> f-0 (initial-fact)

==> f-1 (world (tag 1) (scope truth))

==> f-2 (statement (speaker A)

(claim F A) (reason 0) (tag 1))

CLIPS> (run)

FIRE 1 unwrap-true: f-1,f-2

Assumption:

A is a knight, so (T A) is true.

==> f-3 (claim (content F A) (reason 1)

(scope truth))

==> f-4 (claim (content T A) (reason 1)

(scope truth)) FIRE 2 contra-truth:

f-1, f-2, f-4, f-3

Statement is inconsistent if A is a knight.

<== f-3 (claim (content F A) (reason 1)

(scope truth)) <== f-4 (claim (content T A)

(reason 1) (scope truth)) <== f-1 (world (tag 1)

(scope truth)) ==> f-5 (world (tag 1)

(scope falsity)) FIRE 3 unwrap-false:

f-5, f-2 Assumption

A is a knave, so (T A) is false.

==> f-6 (claim (content NOT F A)

(reason 1) (scope falsity))

==> f-7 (claim (content F A) (reason 1) (scope falsity))

FIRE 4 not2: f-6

<== f-6 (claim (content NOT F A) (reason 1) (scope falsity))

==> f-8 (claim (content Т A) (reason 1) (scope falsity))

FIRE 5 contra-falsity: f-5, f-2, f-7, f-8

Statement is inconsistent if A is a knave.

<== f-5 (world (tag 1) (scope falsity))

==> f-9 (world (tag 1) (scope contra))

Упражнение 1

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

Предположим, что персонаж А утверждает: "Я всегда говорю правду".


К какой категории следует отнести этот персонаж?

В такой постановке задача имеет неоднозначное решение. Предположение, что А правдолюбец, не приводит нас к противоречию. Но точно так же не приводит к противоречию и предположение, что А —лжец.

Ваша задача— модифицировать описанную выше программу таким образом, чтобы она давала заключение, что оба контекста непротиворечивы. Один из возможных вариантов модификации — ввести в состав программы правила consist-truth и consist-falsity, разработав их по образцу правил contra-truth и contra-falsity. Эти правила должны дать пользователю знать, что при данном предположении противоречий не обнаружено, причем правила должны активизироваться в случае, когда нет больше правил, претендующих на внимание интерпретатора.

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

Стиль программирования нязыке CLIPS

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

Эта программа является относительно простой и включает всего 35 правил, тогда как в практических экспертных системах их может быть значительно больше. Например, в прототипе системы R1/XCON, который был разработан в 1980 году (см. главу 14), содержалось около 750 правил, причем по мере совершенствования системы их число росло и к 1984 году достигло 3300. В среднем каждое правило в R1 анализирует шесть условий и выполняет три действия.

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

TMPxr

ПРИЛОЖЕНИЕ. Программирование на языке CLIPS

А.1. Краткая история CLIPS А.2. Правила и функции в CLIPS

А.2. Правила и функции в CLIPS

А.2.1. Факты

А.2.2. Правила

А.2.3. Наблюдение за процессом интерпретации

А.2.4. Использование шаблонов

А.2.5. Определение функций

А.3. Объектно-ориентированные средства в CLIPS

А.4. Задача "Правдолюбцы и лжецы"

А.4.1. Анализ проблемы

А.4.2. Онтологический анализ и представление знаний

А.4.3. Разработка правил

А.4.4. Расширение набора правил — работа с составными высказываниями

А.4.5. Обратное прослеживание и множество контекстов

А.4.6. Обработка метавысказываний

А.4.7. Полный листинг программы

А.5. Стиль программирования на языке CLIPS

Упражнения

Разработайте программу моделирования, которая использовала

1. Разработайте программу моделирования, которая использовала бы объекты и правила, аналогичные описанным в разделе А.З, но для какого-нибудь другого устройства.

2. Разработайте программу, которая решала бы детективные головоломки типа той, что представлена ниже (головоломки описаны в книге [Smullyan, 1978]).

Расследуется дело об ограблении, причем подозреваемых трое — А, В и С. По крайней мере один из них виновен и известно, что никто, кроме этих троих, не мог принимать участия в ограблении.

Задача 1. А никогда не работает в одиночку, т.е. имеет хотя бы одного сообщника. У С есть твердое алиби. Виновен или невиновен В?

Задача 2. А никогда не работает с С. С никогда не работает в одиночку. Если А виновен, а В невиновен, то С виновен. Кто из этих троих совершил ограбление?

Задача 3. Если А виновен, то у него есть точно один сообщник. Если точно два виновны, то А — один из них. В и С дают показания, из которых следует, что у другого из них есть алиби. Кто совершил ограбление?

Программа должна решать все три задачи.

3. Критически проанализируйте и модифицируйте любую CLIPS-программу, представленную на страницах данной книги.

Задач"Правдолюбцы и лжецы"

Для того чтобы продемонстрировать вам возможности языка CLIPS, я выбрал головоломку, а не задачу из практики применения экспертных систем. В головоломке решается одна из задач, возникающих на острове, населенном обитателями двух категорий: одни всегда говорят правду (назовем их правдолюбцами), а другие всегда лгут (их, естественно, назовем лжецами). Множество подобных головоломок вы можете встретить на страницах занимательной книги Раймонда Смуляна (Raymond Smullyan) What is the Name of this Book?. Ниже приведены разные задачи из этой серии.

Р1. Встречаются два человека, А и В, один из который правдолюбец, а другой — лжец. А говорит: "Либо я лжец, либо В правдолюбец". Кто из этих двоих правдолюбец, а кто лжец?

Р2. Встречаются три человека, А, В и С. А и говорит: "Все мы лжецы", а В отвечает: "Только один из нас правдолюбец". Кто из этих троих правдолюбец, а кто лжец?

РЗ. Встречаются три человека, А, В и С. Четвертый, проходя мимо, спрашивает А: "Сколько правдолюбцев среди вас?" А отвечает неопределенно, а В отвечает: "А сказал, что среди нас есть один правдолюбец". Тут в разговор вступает С и добавляет: "В врет!" Кем, по-вашему, являются В и С?

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

---

---