Эвристический поиск

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

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

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

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

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

(2) Если одно из новых состояний является решением проблемы, прекратить процесс. В противном случае перейти в то состояние, которое характеризуется наивысшим значением оценочной функции. Вернуться к шагу (1).

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

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

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

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

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

2.2. Алгоритм А

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

f(n) = g(п) + h(n).

Здесь g(п) соответствует расстоянию на графе от узла п до начального состояния, a h(n) —оценка расстояния от п до узла, представляющего конечное (целевое) состояние. Чем меньше значение оценочной функции f(n), тем "лучше", т.е. узел п лежит на более коротком пути от исходного состояния к целевому. Идея алгоритма состоит в том, чтобы с помощью f(n) отыскать кратчайший путь на графе от исходного состояния к целевому.

Отсюда следует, что если h(n) — нижняя оценка действительного расстояния до целевого состояния, т.е. если h(n) никогда не дает завышенной оценки расстояния, то алгоритм А всегда отыщет оптимальный путь до цели при помощи оценочной функции f(n). Алгоритм, обладающий таким свойством, называется разрешимым (более подробное обсуждение этого вопроса читатель найдет в специальной литературе, в частности в работах Нмпьсона [Nilsson, 1980, Chapter 2] и Перла [Pearl, 1984, Chapter 2]).

Обозначения:

s — узел начального состояния;

g— узел целевого состояния;

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

CLOSED — список, который содержит обработанные узлы.

Алгоритм

(1) OPEN:={s}.

(2) Если ОРЕМ:={}, то прекратить выполнение. Пути к целевому состоянию на графе не существует.

(3) Удалить из списка OPEN узел п, для которого f(n)<f(m) для любого узла т, уже присутствующего в списке OPEN, и перенести его в список CLOSED.

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

(5) Если в сформированном списке очередных узлов присутствует д, то завершить выполнение. Сформировать результат — путь, порожденный прослеживанием указателей от узла д до узла s.

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

Вычислить f(n').

Если n не присутствует ни в списке OPEN, ни в списке CLOSED, добавить его в список, присоединить к нему оценку f(n') и установить обратный указатель на узел п.

Если n' уже присутствует в списке OPEN или в списке CLOSED, сравнить новое значение f(n)=new с прежним f(n')=old.

Если old<new, прекратить обработку нового узла.

Если new<old, заменить новым узлом прежний в списке, причем, если прежний узел

был в списке CLOSED, перенести его в список OPEN.

Конец алгоритма

Применение этого алгоритма рассмотрено в упр. 8.

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

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

Достаточно подробно результаты первых исследований в области программирования игр и машинного доказательства теорем описаны в сборнике статей под редакцией Фей-генбаума и Фельдмана [Feigenbaum and Feldman, 1963]. Я склонен к тому, чтобы считать "классическим" в истории искусственного интеллекта период, который начался с публикации в 1950 году статьи Шеннона об игре в шахматы [Shannon, 1950] и закончился выходом сборника Фейгенбаума и Фельдмана. Наиболее существенные результаты, полученные в этот период, можно сформулировать следующим образом:

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

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

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

Обзор исследований в области искусственного интеллекта

2.1. Классический период: игры и доказательство теорем

2.2. Романтический период: компьютер начинает понимать

2.3. Период модернизма: технологии и приложения

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

Упражнения

Что такое искусственный интеллект? Барр и Файгенбаум предложили следующее определение, которое никем не оспаривается почти два десятка лет [Barr and Feigenbaum, 1981].

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

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

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

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

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

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

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

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

Период модернизма: технологии и приложения

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

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

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

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

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

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

Поиск в пространстве состояний

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

исходное состояние проблемы, например исходное состояние головоломки;

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

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

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

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

Рис. 2.1. Дерево пространства состояний головоломки Scrabble с буквами Т, С и А

Это пространство состояний обладает двумя интересными свойствами, которые присущи далеко не всем пространствам состояний:

оно конечно, поскольку существует только п! способов расставить я букв;

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

Метод формирования анаграмм последовательным перечислением является примером применения алгоритма, получившего наименование generate-and-test (порождение и проверка).

(1) Генерировать новое состояние, модифицируя существующее; например, изменить последовательность букв, добавив новую в существующую последовательность.

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

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

Алгоритм имеет два основных варианта: поиск в глубину (depth-first search) и поиск в ширину (breadth-first search). Отличаются варианты порядком формирования состояний на шаге (1). Действительные алгоритмы приведены в упр. 5, а здесь мы дадим только их неформальное описание.

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

Рис. 2.2. Граф пространства состояний при использовании алгоритма поиска в ширину

Рис. 2.3. Граф пространства состояний при использовании алгоритма поиска в глубину

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

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

Отметим, что свойства этих алгоритмов существенно отличаются.

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

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

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

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

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

Другая задача, которая занимала умы исследователей в области искусственного интеллекта в середине 50-х годов, — доказательство теорем. Смысл задачи доказательства состоит в том, чтобы показать, как некоторое утверждение, которое требуется доказать (теорема), логически следует из декларированного множества других утверждений или аксиом (которые полагаются истинными или являются такими априори).

2.1. Комбинаторный взрыв

Исследованием вычислительной обозримости (или необозримости) проблем занимается теория сложности. Для начала нам потребуется только знать, что существуют классы проблем, решение которых требует ресурсов, экспоненциально возрастающих при линейном увеличении размерности задачи. Например, время, необходимое для отыскания пути в лабиринте, экспоненциально увеличивается при увеличении количества разветвлений в лабиринте. Аналогично, время, необходимое для поиска доказательства теоремы исчислением утверждений, растет экспоненциально по отношению к количеству переменных. Такие проблемы являются в общем случае необозримыми и называются NP-hard. Читателей, которые ими заинтересуются, мы отсылаем к специальной литературе, в частности книге Хопкрофта и Ульмана [Hopcroft and Ullman, 1979].

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

Прекрасное изложение теории вычислительной сложности, рассчитанное на читателя, несклонного к излишнему теоретизированию, можно найти в работе Паунд-стоуна [Poundstone, 1988, Chapter 9].

Рассмотрим такой пример. Пусть имеются две аксиомы, представленные на некотором формальном языке:

"Если компьютер может ошибаться, он ошибется" и

"Мой компьютер может ошибаться".

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

"Мой компьютер ошибется".

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

(любой Х)(F(X))

G(X))

F(a) / [G(a){X/a}]

которое читается следующим образом:

"Все элементы F являются элементами G, а входит в F, следовательно, F есть G".

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

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

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

Романтический период

2.2. Романтический период: компьютер начинает понимать

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

Схемы представления знаний

Независимо от того, насколько это вторжение в науку о познании было продуктивным для психологии, оно способствовало весьма существенному прогрессу в информатике. Ньюэлл (Newell) и Саймон (Simon) предложили схему, известную как набор порождающих правил (production rules). (Подобно мы поговорим о ней в главе 5.) Со временем порождающие правила стали основным инструментом при проектировании экспертных системы. Ньюэллу и Саймону также принадлежит приоритет в разработке методики, получившей наименование анализ протокола (protocol analysis). Эта методика заключается в том, что человеку предлагается "думать вслух" в процессе решения проблемы, а затем зафиксированный протокол анализируют и пытаются отыскать в нем концепции и процедуры, которые были использованы человеком. Этот подход можно считать предшественником используемой сегодня методики извлечения знаний. Уже первые исследования на стыке психологии и информатики показали, насколько сложной является проблема представления знаний, но они также и продемонстрировали, что ее решения следует искать скорее на пути эмпирических исследований, чем философских дебатов.

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

правил в форме, "если имеет место это условие, то примени этот оператор";

разного рода сетей, в которых узлы соответствуют концепциям, а дуги — отношениям между ними;

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

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

Весьма репрезентативная подборка статей, написанных в первой половине этого периода, опубликована Минским [Minsky, I968J. Любая из них представляет интерес, но далеко не все убедительны с точки зрения достижений сегодняшнего дня. Тем не менее множество схем представления знаний, которым мы отдаем предпочтение в современных разработках, основаны именно на результатах, полученных в тот романтический период. Например, в работе Квилиана (Quillian) предложены ассоциативные и семантические сети в качестве графического формализма для описания фактов и определений (подробнее об этом— в главе 6). Без результатов, полученных в это время, вряд ли разработчики современных экспертных систем располагали бы таким разнообразием функций и структур.

Наиболее интересные работы, опубликованные во второй половине этого периода, собраны Уинстоном [Winston, 1976,b]. Среди них я настоятельно рекомендую ознакомиться с фундаментальной работой Минского о формализме представления знаний, получившем наименование фреймов. Работы, выполненные в этом направлении в 70-е годы в Массачусетсском технологическом институте, собраны в двухтомнике Уинстона и Брауна [Winston and Brown, 1979]. Здесь вы найдете множество статей и о тех областях искусственного интеллекта, которые выходят за рамки этой книги, в частности о машинном восприятии естественного человеческого языка, искусственном зрении, робототехнике.

2.4. Летучие мыши и проблема с пингвинами

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

Этот факт никак не отражается на простом графе.

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

Рис. 2.4. Простой таксономический граф, не учитывающий исключений

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

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

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

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

Такие способности редко демонстрируются в современных экспертных системах, хотя в последние годы и наметился определенный прогресс в области машинного обучения (подробнее об этом читайте в главе 20).

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

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

СистемSHRDLU

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

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

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

Другое направление исследований было связано с попытками воспроизвести механизм понимания в менее искусственном и более близком к реальному контексте, например в ситуаиии визита к врачу или посещения ресторана. Шанк и Колби [Schank and Colby, 1973] воспользовались структурой, названной ими сценарием, для объединения разнообразных элементов, представляющих в совокупности реальную ситуацию. Сценарий можно рассматривать как объединение разнообразных целей, решений и обычаев, связанных с определенными событиями. Так, "сценарий посещения ресторана" приводится в действие при возникновении цели "чего бы съесть", удовлетворяется событием "прием пищи" и объединяет промежуточные знания о том, как заказать столик, выбрать блюда в меню, расплатиться, дать на чай и т.п.
Такое объединение целей и средств, характерных для определенной ситуации, объясняет, почему определенные действия считаются нормой в одной ситуации и рассматриваются как неадекватные в другой. Например, раздевание в присутствии постороннего является нормой при визите к врачу и рассматривается как неадекватное при посещении ресторана. Такой же подход позволяет включить и некоторые знания, которые мы считаем само собой разумеющимися, — любой под визитом к врачу понимает посещение клиники, а не квартиры врача. В сценарии "визит к врачу" это учитывается включением в качестве места посещения по умолчанию именно клиники.

2.3. Сценарий посещения ресторана

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

Цель: поесть без самостоятельного приготовления пищи. Предварительные условия: голоден, есть деньги, ресторан работает. Состояние после завершения: сыт, денег стало меньше.

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

Действие второе: просмотреть меню, сделать заказ,и поесть. Не забыть, что в ресторане могут быть фирменные блюда.

Действие третье: получить чек. Заплатить официанту/официантке или кассиру. Покинуть заведение.

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

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

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

Другие исследователи (например, [Newell and Simon, 1972] и [Anderson, 1976]) попробовали на несложных задачах (простенькие головоломки, игры в слова и тесты, оценивающие способность к запоминанию) смоделировать присущий человеку подход к решению проблем. Они стремились сделать так, чтобы знания и стратегия поведения программы как можно больше походили на знания и стратегию поведения человека в аналогичной ситуации. Оценка успешности моделирования производилась путем сравнения поведения человека и программы при решении одной и той же задачи.

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

Почему пакет программ статистического анализа

1. Почему пакет программ статистического анализа нельзя считать программой искусственного интеллекта?

2. Могут ли психологи подсказать нам, как сконструировать думающую машину?

3. Как вы понимаете термин "пространство поиска"? Что представляет собой пространство поиска в игре в шахматы?

4. Как вы понимаете термин "пространство решений"? Что представляет собой пространство решений в игре в шахматы?

5. Ниже приведен алгоритм поиска в глубину. Он записан с помощью функциональной нотации, которая подчеркивает его рекурсивную структуру. Таким образом, dfs представляет собой функцию трех аргументов: goal, current и pending:

goal — это объект поиска,

current — текущий узел на графе состояний (в самом начале — узел исходного состояния),

pending — список узлов, претендующих на обработку (в самом начале — пустой).

В дальнейшем используются следующие обозначения:

символ := означает присваивание;

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

(а b с) + (d e f ) = (а b с d e f);

() означает пустой список;

first и rest — функции, которые возвращают начало и конец списка:

first(a b с) = a

rest(a b c) = (b c).

I) Выразите следующий алгоритм на каком-либо из известных вам языков программирования.

dfsfgoal, current, pending)

{

if current = goal, then success;
else

{

pending := expand (current}+ pending;
if pending = () then fail;
else dfs(goal, first(pending), .rest( pending));

} }

II) Разработайте аналогичный алгоритм для поиска в ширину и реализуйте его на том же языке. Необходимо будет изменить только одно выражение в функции dfs.

6. Рассмотрите головоломку "миссионеры и каннибалы", схематически представленную на рис. 2.6.

Рис. 2.6. Головоломка "миссионеры и каннибалы "

Условия головоломки следующие.

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

К-> одного каннибала с левого берега на правый

КК-> двух каннибалов с левого берега на правый

МК-> одного миссионера и одного каннибала с левого берега на правый

ММ-> двух миссионеров с левого берега на правый

М-> одного миссионера с левого берега на правый

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

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

Рис. 2.7. Построение пространства поиска в головоломке "миссионеры и каннибалы"

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

Рис. 2.8. Законченное пространство поиска в головоломке "миссионеры и каннибалы ", сформированное алгоритмом поиска в глубину

В процессе поиска было развернуто 22 узла, а путь, приводящий к успеху, содержит 11 узлов. Таким образом, оценка проницательности поиска равна 11/22=0.5. Грубо говоря, проницательность поиска говорит нам о том, насколько данный алгоритм позволил избежать выполнения ненужной работы в процессе Поиска решения. Чем выше значение проницательности поиска для того или иного алгоритма, тем лучше.

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

С разными способами формализации этой

задачи можно познакомиться в работе Амарела [Amarel, 1968]. Обратите внимание на то, что существуют способы представления состояний, которые позволяют более экономно использовать вычислительные ресурсы при решении задачи.

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

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

7. Другая классическая головоломка, знакомая в несколько ином виде многим еще со школьной скамьи, — "Восьмерка". В головоломке принимает участие восемь пронумерованных фишек, которые могут перемещаться по игровому полю 3x3. Цель состоит в том, чтобы из некоторого случайного расположения фишек перейти к упорядоченному (рис. 2.9).

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

Рис. 2.9. Головоломка "Восьмерка"

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

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

II) Какая из предложенных выше оценочных функций является более чувствительной? Можете ли вы предложить лучший способ управления поиском?

III) Как будет работать ваша программа, если увеличить количество фишек до 15, а размер игрового поля до 4x4? В этом случае придется исследовать 16! состояний.

Эту головоломку с точки зрения методов искусственного интеллекта рассматривал Нильсон (см. [Nilsson, 1980, Chapter 1].

8. Просмотрите описание алгоритма А во врезке 2.2 и выполните следующее.

I) Реализуйте алгоритм А на любом известном вам языке программирования.

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

III) Попробуйте с помощью этого алгоритма решить криптоарифметическую головоломку, описанную ниже:


BEST	SEND	DONALD	CROSS
+MADE	+MORE	+GERALD	+ROADS
MASTER	MONEY	ROBERT	DANGER

Термин "криптоарифметическая" означает использование цифр, зашифрованных буквами, и соответственно чисел, зашифрованных словами. Задача состоит в том, чтобы найти, какие цифры нужно подставить вместо букв, чтобы представленные арифметические операции над расшифрованными числами давали верный результат. Такая задача рассматривается во многих классических работах по искусственному интеллекту (см., например, [Raphael, 1976, Chapter 3].

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

В знании сила

В период модернизма возросла уверенность, что эвристические возможности "решателя" проблем определяются представлением в явной форме соответствующих зданий, доступных программе, а не применением какого-то изощренного механизма определения взаимовлияния или сложных оценочных функций. Значительные усилия были направлены на разработку методов разбиения знаний, присущих человеку, на модули, которые можно было бы активизировать по заданной схеме (см. врезку 2.5). Уже при первых попытках сымитировать процесс разрешения проблем, характерный для человеческого разума (например, в работе [Newell and Simon, 1972]), исследователи столкнулись с ограниченными возможностями представления знаний и необходимостью упростить механизм их взаимовлияний, хотя более поздние исследования и помогли в определенной степени преодолеть эти трудности (об этом мы поговорим в главах 11-18).

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

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

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

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

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

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

2.5. Процедуральное или декларативное знание

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

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

char fly(char s)

{

char answer = 'д'; if (strcmpfs, "пингвин")==0)

{ answer = 'н';} return answer;

}

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

char с;

с = fly("пингвин");

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

(defrule

(птица (тип ?Х)) =>

(assert (да))

)

(defrule

(птица (тип пингвин)) =>

(assert (нет)) )

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

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

В этот период появился ряд систем, которые довольно эффективно справлялись с нетривиальными задачами. Примером может служить система R1/XCON, предназначенная для структурного синтеза вычислительных систем (подробно о ней — в главе 14). В этой системе реализован ряд концепций, существенно отличающих ее как от обычных программных приложений, так и от исследовательских программ искусственного интеллекта (см. [Davis, 1982]). Те, которые я считаю наиболее важными, перечислены ниже.

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

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

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

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

2.6. Машина логического вывода и база знаний

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

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

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

(deftemplate птица (field (тип SYMBOL)))

в дополнение к имеющимся правилам:

(defrule (птица (тип ?Х))

=>

(assert (да))

)

(defrule

(птица (тип пингвин))

=>

(assert (нет)) )

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

Рис. 2.5. Структура экспертной системы

Физическая символическая система

Ньюэлл [Newell, 1981] описывает физическую символическую систему как помещенную в некоторую среду машину, состоящую из следующих компонентов:

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

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

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

средств ввода из окружающей среды посредством рецепторов и вывода в окружающую среду посредством эффекторов.

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

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

4.1. Главная гипотеза

Ньюэлл и Саймон следующим образом сформулировали гипотезу физической символической системы (Physical Symbol System Hypothesis) [Newell and Simon, 1976]:

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

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

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

Языки представления знаний

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

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

Если рассматривать в этом свете проблематику представления знаний, то ее можно сформулировать следующим образом: "Существует ли способ, пользуясь которым можно закодировать знания о предметной области таким образом, чтобы поддерживать приложение этих знаний к решению различных проблем в разных проектах?" Ответом на этот вопрос является проектирование независящих от приложения "банков знаний", о котором речь пойдет в главе 10. Вы в дальнейшем встретитесь и с такими примерами, когда доступные программе знания по-разному используются в пределах одного и того же приложения (главы 13 и 16).

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

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

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

этот язык относительно дешев;

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

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

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

язык допускает вызов внешних функций, написанных на других языках программирования;

язык включает средства (правда, ограниченные), позволяющие комбинировать правила и объекты.

В главе 6 будет проанализировано использование структурированных объектов, таких как семантические сети и фреймы, а в главе 7 мы перейдем к более тщательному анализу объектно-ориентированного подхода. Описание методики логического программирования, в частности с использованием языка PROLOG, завершит в главе 8 тему изучения языков представления знаний.В главе 17 вы найдете обзор множества доступных на сегодняшний день программных пакетов, предназначенных для построения экспертных систем, а в главах 18 и 19 анализируются более специализированные инструментальные средства.

LISP и разработкпрограмм

Многие программисты склонны к тому, чтобы создавать программный код, напоминающий спагетти, и их буквально приводит в состояние шока знакомство с широкими возможностями, которые сулит в создании такого кода язык LISP. Но при всем этом сообщество приверженцев LISP на удивление мало привнесло в методологию программирования (см. [Abelson et al, 1996]).

4.5. Гипотеза Смита

Смит выдвинул гипотезу представления знаний (Knowledge Representation Hypothesis), которая гласит [Smith, 1982]:

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

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

Многие идеи, касающиеся представления знаний, зародились в процессе развития методики объектно-ориентированного анализа и проектирования. Объектно-ориентированные языки программирования, такие как C++, SmallTalk и Eiffel, стали в последнее время привлекать все большее внимание конструкторов экспертных систем. Появилось довольно много библиотек классов, которые можно использовать при построении такого рода приложений. В этом же направлении стал развиваться и LISP. В частности, на его основе разработан язык CLOS — Common Lisp Object System, в котором механизм множественного наследования работает значительно эффективнее, чем в C++ (подробнее об этом — в главе 7). Но даже самые верные приверженцы LISP находят маловероятным, что его новейшие диалекты скоро найдут широкое применение в создании коммерческих программных продуктов.

Обработксписков

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

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

4.4. Примитивы в LISP

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

Пусть s — множество символических выражений. Можно, например, записать:

Е(Х , Y): S x S -> {Т, NIL}

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

(1)Е(Х , Y): S x S -> {Т, NIL} проверяет, равны ли два атома.

(2)А(Х): S -> {Т, NIL} проверяет, является ли символическое выражение атомом.

(З)Н(Х): S -> S извлекает голову символического выражения, которое не является атомом; если х — атом, то результат функции не определен.

(4) Т(Х): S —> S извлекает хвост символического выражения, которое не является атомом; если х — атом, то результат функции не определен.

(5)С(Х , Y): S х S —> S формирует символическое выражение; если А и в являются символическими выражениями , то можно сформировать новое символическое выражение (А . В).

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

Фактически система, состоящая из трех компонентов

(1) единственного атома NIL;

(2) условного выражения, проверяющего равенство, в форме

if E(X, NIL) then ... else ... 3) функций Н(Х), Т(Х), С(ХД)

к которым добавлена операция композиции функций, вполне позволяет реализовать машину Тьюринга (см. [Minsky, 1972, Chapter 10]).

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

((Alabama Montgomery) (Alaska Juneau) (Arizona Phoenix) ... )

позволяет представить столицы пятидесяти штатов. Представленная ниже LISP-программа сможет затем извлечь название столицы заданного штата из этого ассоциативного списка.

(defun assoc (key alist)

(cond ((null alist) NIL)

((eq (first (first a list)) key) (first alist))

(T (assoc key (rest alist)))) )

Если обратиться к этой функции с помощью, например, выражения (assoc 'Alaska '((Alabama Montgomery) (Alaska Juneau) (Arizona Phoenix) ... ), то функция возвратит список

(Alaska Juneau) .

NULL — это предикат, который проверяет, не пуст ли список, EQ — предикат, который проверяет равенство двух атомов, FIRST — функция, которая возвращает головной элемент списка, a REST — функция, которая возвращает хвост списка (см.

врезку 4.4).

Основным условным выражением в LISP является COND. В приведенном выше фрагменте программного LISP-кода это условное выражение может быть расшифровано следующим образом:

если alist это null, то вернуть NIL, иначе

{

если головной элемент головного элемента alist равен key, то вернуть головной элемент alist,

иначе вернуть результат применения функции assoc к хвосту alist. }

Условное выражение COND можно представить в терминах примитива if-then-else, описанного во врезке 4.4. Выражение COND может включать сколько угодно вложенных конструкций if-then-else.

Конечно, ассоциативные списки — это не самое лучшее средство хранения данных, но наш пример с таким списком помог вам представить, как в LISP организуется рекурсивная обработка списков.

Почему LISP не является языком представления знаний

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

функции и лямбда-исчисление

Для того чтобы разобраться в связи между лямбда-исчислением и языком LISP, нужно постоянно держать в уме сформулированное Черчем отличие между денотацией (означиванием) и абстракцией. Так, выражение (X X) означивает конкретное число, которое зависит от значения X. Но то же число можно получить и при помощи функции square(X), которая является абстракцией, поскольку ее можно приложить к разным значениям X. Для того чтобы отличить означивание от абстракции, первое представляется в лямбда-исчислении в таком виде:

(лх)(X х)

Говорят, что лямбда-оператор, X, связан с переменной X, как квантор связывает отдельные переменные в исчислении предикатов. Тогда (ЛХ)(X X) может служить определением функции возведения в квадрат:

square(X) = (лX)(X X)

Теперь для применения функции возведения в квадрат к конкретному числу, скажем 3, мы должны каким-то образом подставить 3 вместо переменной X и оценить (X ,Х), в результате чего получим 9. Когда определение функции применяется к аргументу 3, используется правило влияния, получившее наименование лямбда-преобразования. Доложим, что (лХ)М определяет любую лямбда-абстракцию, и пусть S(a, X, М) — результат подстановки X в М.

Лямбда-преобразование. Заменим любую часть (lХ)М в формуле на s(a, x, М), причем ограниченные переменные в м отличны как от х, так и от свободных переменных а.

Если мы полагаем, что ((ЛХ)М) а обозначает применение определения функции (ЛХ)М к аргументу а, то

((ЛХ)(Х Х))(3) = (3 3) = 9 .

Какое же все это имеет отношение к языку LISP? А вот какое. Определение функции возведения в квадрат в LISP выглядит примерно так:

(defun SQUARE (X) (LAMBDA (X) ( X X))) .

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

(defun SQUARE (X) ( X X)) .

В любом случае имя функции, в данном случае SQUARE, ассоциируется в определении с лямбда-выражением. Выражение (LAMBDA (X) ( X X)) — это просто синтаксический вариант ((ЛХ) (X X)).
Фактически, если определено SQUARE, в любом диалекте LISP имеем

(SQUARE 3) = ((LAMBDA (X)

( X X)) 3) = ((АХ)(Х Х))(3) = 9 .

Обратите внимание на то, что LAMBDA не является функцией. Это специальный оператор в лямбда-исчислении.

Синтаксическая форма вызова функции в языке LISP имеет вид

(<функция> <аргумент> ... <аргумент>).

Это не самая сложная синтаксическая форма, а вместе с QUOTE, LAMBDA и условными выражениями этим фактически исчерпывается все, что необходимо знать о синтаксисе языка LISP. Тем, кто по каким-то иррациональным причинам испытывает тягу к запятым, двоеточиям, точкам с запятой, палиндромам вроде (if... ft, case ... esac) и тому подобному, будет поначалу трудно свыкнуться с мыслью, что в LISP единственным ограничителем являются круглые скобки. Программа на языке LISP — это просто структура данных, и другая LISP-программа ее может читать, записывать и обрабатывать точно так же, как любой другой набор данных.

Реализация символических структур нязыке LISP

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

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

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

Символические вычисления

4.1. Символическое представление

4.2. Физическая символическая система

4.3. Реализация символических структур на языке LISP

4.4. Почему LISP не является языком представления знаний

4.5. Языки представления знаний

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

Упражнения

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

В этой главе читатель найдет:

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

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

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

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

Специализированные языки, объектно-ориентированный подход и программные инструментальные средства, предназначенные для построения экспертных систем, мы подробно рассмотрим в главах 5, 7 и 17. В этой же главе мы в первую очередь сосредоточим внимание на концепциях программирования и структурах, существенно влияющих на конструирование экспертных систем. Детали реализации и специфические приемы будут рассмотрены в соответствующих разделах других глав в контексте конкретных систем (главы 11-16).

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

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

Символический уровень и уровень знаний

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

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

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

Символическое представление

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

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

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

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

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

Сопоставление с образцом

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

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

at(robot, room). На языке LISP этот факт будет представлен символическим выражением

(at robot room). Положим, что ? — символ универсальной подстановки и что выражение

(at robot ?) представляет собой образец, которому соответствует и выражение

(at robot room), и другое выражение в форме

(at robot blah),

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

(defun match (sample pattern)

(cond ((and (null sample)

(null pattern)) T) ((or

(null sample) (null pattern)) NIL)

((eq (first pattern '?))

(match (rest sample) (rest pattern)))

((eq (first sample) (first pattern))

(match (rest sample) (rest pattern)))

(T NIL)) )

Обращение к этой функции в выражении

(match '(at robot room) '(at robot ?))

даст результат Т, а обращение

(match '(at box room) '(at robot ?))

даст результат NIL.

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

(at ?X ?Y)

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

(at robot room),

который образуется при подстановке {?X/robot, ?Y/room}, как об этом говорилось в главе 3. Можно также потребовать, чтобы присвоение значений переменным было совместимым, т.е. чтобы пример

(at robot room)

не соответствовал образцу

(at ?Х ? X).

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

if (at ?X room) then (paint ?X)

Нужно проверить, соответствует ли условию if (at ?X room) этого правила модель мира, представленная списком

(at box room).

Полученную подстановку {?X/box} применим затем к констатирующей части правила и получим в результате

(paint box).

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

СтруктурLISP-программы

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

(+ X Y) представляет математическое выражение в форме

(<функция> <1-й аргумент> <2-й аргумент>),

которое обозначает сложение двух чисел. Такой метод обозначений (нотация) отличается от привычного нам обозначения функции п переменных в виде f(x1, ... xn). Но возникает вопрос, как компилятор или интерпретатор отличает данные от программы, если и то и другое представлено списками.

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

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

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

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

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

((1 2 3)(4 5 6)(7 8 9))

и пытаться отыскать определение функции (1 2 3).

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

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

4.3. Функции, их вычисление и проблема цитирования в CLIPS

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

Например, в CLIPS можно следующим образом определить функцию:

(deffunction between(?lb ?value ?ub)

(or (> lib ?value) (> ?value ?ub))))

Эта функция определяет, попало ли заданное целочисленное значение в диапазон между указанными нижним и верхним пределами. Знак вопроса, предшествующий именам, говорит интерпретатору CLIPS, что выражения ?lb, ?value и ?ub являются переменными и их не нужно оценивать.

Общепринятым методом реализации функциональных языков типа LISP является использование четырехстековой машины, за которой закрепилось наименование SECD-машины. В четырех стеках машины отслеживаются промежуточные результаты, значения переменных, текущее выражение и копии текущего состояния процесса вычислений сложного выражения, которые нужны, чтобы восстановить состояние после завершения вычисления вложенного выражения (подвыражения). Не вдаваясь в подробности, отметим, что процесс оценивания символического выражения в такой машине — это не что иное, как реализация базовой операции приложения функции, как это определено в лямбда-исчислении (см., например, [Henderson, 1980], [Glaser et al., 1984]).

Структуры данных в языке LISP

Одним из первых языков обработки списков был LISP2 [McCarthy, 1960]. За четыре десятилетия, которые прошли после появления его первой версии, язык неоднократно, модифицировался и расширялся, но в основе своей изменился мало. Разработчики языка утверждали, что LISP отличается от прочих языков программирования следующими свойствами [McCarthy et al, I960]:

основной структурой данных в нем является список;

программы на этом языке также имеют списочную структуру;

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

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

Базовым блоком в структуре данных языка LISP является символическое выражение. Простое символическое выражение использует атомарные символы, или атомы — строки буквенно-цифровых символов, которые начинаются с буквы, например WOMBAT. (Допустимая длина строки варьируется в зависимости от версии исполняющей системы.) Во внутренней структуре данных атом представлен ячейкой памяти. Отдельным атомом является символ Т, которым представляется константа "True" — истина. Другой специальный атом, NIL, представляет, с одной стороны, константу "False"—ложь, а с другой — пустой список.

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

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

("а" (9) () N (? (WOMBAT)) (A . В) NIL 0.9)

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

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

4.2. Списки и точечные пары

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

Любой атом является символическим выражением.

Если А1 и А2 суть символические выражения, то (А1 A2)— это также символические выражения.

Если S = (А,. (А2 . (.... (Ап-1. AJ ....))) — суть символическое выражение для некоторого п>0, то S — список тогда и только тогда, когда Аn =NIL.

В соответствии с этим определением, если п=0, то S представляет собой пустой список, NIL. Такое определение допускает существование списка списков, а также списка атомов. Если S1 S2, ..., Sn— символические выражения, то мы будем представлять список

S1.(S2.(.... (Sn. NIL)....)))

в виде

(S1 S2.... Sn)

Таким образом, (А . (В . NIL)) является списком. Он представляет список (А В), но (А . (В. С)) списком не является, поскольку (С=NIL)).

Символическое выражение, которое не является ни атомом, ни списком, называется точечной парой. Если (А . В) — точечная пара, то А — это голова пары, а B — ее хвост.Точечные пары могут иметь произвольную сложность. Так, ((А . В). С) — тоже точечная пара, так же, как и ((А . В) . (С. D)). Благодаря наличию соответствия между точечными парами и списками, понятия головы и хвоста определены и для списков. Поскольку список (А В) — это (А . (В . NIL)), то очевидно, что А — голова в списке (А В), а хвост — это (В), но не В. Хвостом списка (В) является NIL

к проблематике искусственного интеллекта? Являются

1. Что означает понятие "символ" применительно к проблематике искусственного интеллекта? Являются ли символами изображение и слово?

2. Что представляет собой гипотеза физической символической системы! Является ли она, по вашему мнению, правдоподобной?

3. Пусть L — список

(а (b) с ((d) е (f) g).

Какое значение вернет следующее выражение, состоящее из вложенных функций: first(first(rest(rest(rest(L))))).

Запишите приведенное выше выражение в синтаксисе примитивов LISP.

4. Пусть функция f определяется следующим образом:

f(X Y) = (ЛX)(if Y = 0 then 1, else X f(X, Y - 1)).

Какое значение будет иметь такое применение этой функции:

f(2 3) ?

Запишите приведенное выше выражение в синтаксисе примитивов LISP.

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

(lisp (a functional language)
(invented by (John mccarthy)))

соответствует образцу

(lisp (a ? language) (invented by (? mccarthy))),

но не соответствует образцу

(lisp (a ? language) (invented by (тагу ?))).

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

(? Variable-name),

и тогда образцу

(at (? X) (? Y))

будет соответствовать пример

(at robot room),

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

( (X robot) (Y room))

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

7. Скомбинируйте программы, разработанные в упр. 5 и 6, таким образом, чтобы результирующая программа могла обрабатывать вложенные списки и формировать подстановку. Эта программа должна быть способна, например, показать, что список (lisp (a functional language) (invented by (John mccarthy))) соответствует образцу

(lisp (a (? type) language)
(invented by ((? name) mccarthy))) ,

и вернуть подстановку

((type functional) (name John)) .

Анализ методпредставления и управления в STRIPS

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

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

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

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

at(X, комнатаА), at(Y, комнатаА), at(Z, комнатаА).

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

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

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

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

Язык представления, подобный тому, что используется в STRIPS, с точки зрения программной реализации является интерпретируемым языком, т.е. трансляция с этого языка выполняется интерпретатором, программой, которая способна распознавать в операторах языка формулы, подобные рush(ящик1, комнатаБ, комнатаА), и выразить заложенный в формулах смысл в терминах выполняемых процедур. Так, смысл приведенной выше формулы интерпретируется как необходимость достичь предварительных условий

at(робот, комнатаБ), at(ящик1, комнатаБ),

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

at(po6oт, комнатаА), at(ящик1, комнатаА)

и исключить из модели мира состояние

at(робот, комнатаБ), at(ящик1, комнатаБ).

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

Баззнаний системы MYCIN

База знаний системы MYCIN организована в виде множества правил в форме если условие1 и... и условиет удовлетворяются то прийти к заключению1 и... и к заключению n

Эти правила преобразованы в операторы языка LISP (подробнее о программировании базы знаний рассказано в главе 4).

Вот как выглядит перевод на обычный язык типичного правила MYCIN:

ЕСЛИ 1) организм обладает грамотрицательной окраской, и

2) организм имеет форму палочки, и

3) организм аэробный,

ТО есть основания предполагать (0,8), что этот микроорганизм относится к классу enterobacteriaceae.

Такого рода правила названы оргправилами (ORGRULES) и в них сконцентрированы знания о таких организмах, как strepococcus , pseudonomas и enterobacteriaceae.

Это правило говорит о том, что если организм имеет форму палочки, пятнистую окраску и активно развивается в среде, насыщенной кислородом, то с большой вероятностью его можно отнести в классу enterobacteriaceae. Число 0.8 называется уровнем соответствия (tally) правила, т.е. мерой правдоподобия заключения, сделанного на основании сформулированных условий. Методика использования уровня соответствия правила будет рассмотрена ниже. Каждое правило такого вида можно рассматривать как представление в машинной форме некоторого элемента знаний эксперта. Возможность применить правило определяется тем, удовлетворяются ли в конкретной ситуации условия, сформулированные в первой его части. Сформулированные условия также носят нечеткий характер и могут удовлетворяться с разной степенью истинности. Поэтому в результате импортирования правил из базы знаний применительно к конкретной ситуации формируется более общее правило, включающее и оценки уровня истинности соблюдения условий:

если условие1 удовлетворяется с истинностью х1 и ... и условиеm удовлетворяется с истинностью хм,

то прийти к заключению1 со степенью уверенности у1 и ... и к заключениюn со степенью уверенности уn.

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

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

ложь с определенной степенью достоверности. Примером может служить условие в приведенном выше правиле:

"Организм имеет форму палочки".

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

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

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

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

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

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

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

Информация о пациенте хранится в структуре, названной контекстным деревом (context tree). На рис. 3.3 показано контекстное дерево пациента ПАЦИЕНТ 1. В это дерево включены три культуры организмов (например, полученные из анализа крови пациента) и текущие назначения, которые нужно учитывать при анализе, поскольку они сопряжены с приемом определенных лекарственных средств. С культурами связаны микроорганизмы, присутствие которых предполагается на основании данных, полученных в лаборатории, а с микроорганизмами — лекарственные средства, оказывающие воздействие на них.

Предположим, что в записи, связанной с узлом ОРГАНИЗМ-1 в этой структуре, хранятся данные

ГРАН = (ГРАМ-ОТР 1.0)

МОРФ = (ПАЛОЧКА .8) (КОКОН .2)

ВОЗДУХ = (АЭРОБ .6),

которые имеют следующий смысл:

совершенно определенно организм имеет грамотрицательную окраску;

со степенью уверенности 0.8 организм имеет форму палочки, а со степенью уверенности 0.2 — форму колбочки;

со степенью уверенности 0.6 ОРГАНИЗМ-1 является аэробным (т.е. воздушная среда способствует его росту).

Рис. 3.3. Типичное контекстное дерево в системе MYCIN ([Buchanan and Shortliffe, 1984])

Теперь предположим, что применяется сформулированное выше правило. Нам требуется определить степень уверенности в выполнении всех трех перечисленных в нем условий применительно к данным, представленным в ОРГАНИЗМ-1. Степень уверенности в выполнении первого условия равна 1.0, второго — 0.8, а третьего — 0.6. Степень уверенности в выполнении совокупности условий принимается равной минимальному из значений, характеризирующих отдельные компоненты, т.е. 0.6.

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

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

В данном случае мы приходим к заключению, что микроорганизм, описанный в узле ОРГАНИЗМ-1, относится к классу энтеробактерий со степенью уверенности, равной 0.6 х 0.8 = 0.48. Сомножитель 0.6 — это степень уверенности в выполнении совокупности условий, перечисленных в правиле, а 0.8 — степень уверенности в том, что правило дает правильное заключение, когда все означенные в нем условия гарантированно удовлетворяются. За сомножителями и результатом этого выражения закрепился термин коэффициента уверенности (CF— certainty factor). Таким образом, в общем случае имеем:

СF(действие) = СF(предпосылка) х СРF(правило)

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

Формулировкподцелей в MYGIN

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

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

Канонические системы

Порождения — это в действительности грамматические правила манипулирования строками символов и потому их иногда называют правилами переписывания (rewrite rules). Пост изучал свойства систем правил, базирующихся на порождениях, которые он назвал каноническими системами [Post, 1943]. Каноническая система — это разновидность формальной системы, основанной на следующих компонентах:

алфавит А, из символов которого формируются строки;

некоторое множество строк, которые рассматриваются как аксиомы,

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

а1$1 ... am$m->b1$'1...bn$'1...bn$'n.

где

(I) каждое ai и bi; есть фиксированная строка;

(II) а1 и am, часто есть нуль;

(III) некоторые или все из ai или bi могут представлять собой нуль;

(IV) каждое $i является переменной строкой, которая также может быть нулем;

(V) каждое $i заменяется определенным $'i .

Определение канонической системы, возможно, станет более понятным, если привести пример. Пусть А — алфавит {а, b, с}, а аксиомы суть:

а, b, с, аа, bb, cc.

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

(Р1)$->а$a (Р2) $ -> ab$ab (РЗ) $ -> с$с.

Более того, в данном случае можно проследить применение правил, которые должны привести к росту определенного палиндрома. Например, чтобы сгенерировать bacab, нужно применить Р1 к аксиоме с, а затем Р2 — к результату. Другими словами, приняв с в качестве аксиомы, можно вывести из нее теорему аса и добавить ее к имеющимся аксиомам. Затем из аса можно вывести новую теорему bacab. Обратите внимание, что эта последовательность порождений не обладает свойством коммутативности, т.е. если применять те же правила, но в ином порядке, получится совсем другой результат. Например, если к аксиоме с применить сначала правило Р2, а затем Р1, то получим abcba.

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

Отсюда следует, что любая формальная система может рассматриваться как каноническая (см., например, [Minsky, 1972, Chapter 12J). В действительности к этому нужно добавить тривиальную оговорку, что такая система может нуждаться еще в дополнительном алфавите, буквы которого будут использоваться в качестве знаков пунктуации в сложных доказательствах. Таким образом, для проверки доказательства в любой формальной системе или для того, чтобы выполнить любую эффективную процедуру, вполне достаточно способности прочесть строку символов, разделить ее на компоненты и переупорядочить (при этом, возможно, придется добавить еще какие-то символы или удалить существующие в исходной строке).

5.1. Смысл порождений

Пусть задано порождающее правило в форме

а1$1...am$m-> b1$'1...bn$'n

В нем a1$1 ... аm$m часто называют антецедентом (antecedent) правила, а b,$'1 ... bn$'n консеквентом (consequent) правила, по аналогии с условным выражением логики высказываний (см. главу 8). Условный оператор обычно записывается в виде

p U q1 что означает, "если р, то q", например "если вы упали в реку, то будете мокрым".

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

Правило в форме Х->У говорит о том, что можно записать, сгенерировать или породить консеквент У при заданном анцеденте X. Оно не говорит о том, что набор X, У является неразрывно связанной последовательностью, как в примере с купанием в реке. Правила переписывания в теоретической лингвистике называются "порождениями", поскольку правило вида

S->NP+ VP

имеет следующую интерпретацию: "один из способов сформировать предложение S состоит в том, чтобы взять существительное (NР) и добавить к нему глагол (VP)".

Лечение заболеваний крови

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

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

выяснить, имеет ли место определенный вид заражения у данного пациента;

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

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

выбрать наиболее эффективный препарат или их комбинацию.

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

Часто программу MYCIN считают диагностической, но это не так. Назначение этой программы — быть ассистентом врача, который не является узким специалистом в области применения антибиотиков при лечении заболеваний крови. В процессе работы программа формирует гипотезы диагноза и придает им определенные веса, но самостоятельно, как правило, не делает окончательного выбора. Работа над программой началась в 1972 году в Станфордеком университете и велась специалистами в области искусственного интеллекта в тесном сотрудничестве с медиками.
Наиболее полное описание этой системы читатель найдет в работе Шортлиффа [Shortliffe, 1976].

После 1976 года система неоднократно модифицировалась и обновлялась, но базовая версия состояла из пяти компонентов (рис. 3.2). Стрелки на рисунке показывают основные потоки информации между модулями.

(1) База знаний содержит фактические знания, касающиеся предметной области, и сведения об имеющихся неопределенностях.

(2) Динамическая база данных пациентов содержит информацию о конкретных пациентах и их заболеваниях.

(3) Консультирующая программа задает вопросы, выводит заключения системы и дает советы для конкретного случая, используя информацию о пациенте и статические знания.

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

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

Рис. 3.2. Структура системы MYC1N ([Buchanan and Shortliffe, 1984])

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

Оценки сравнение характеристик экспертных систем

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

Оценксистемы MYCIN

Еще в 1974 году, на самой ранней стадии разработки системы MYCIN, были получены весьма обнадеживающие результаты. Команда из пяти высококвалифицированных экспертов в области диагностики инфекционных заболеваний подтвердила правильность 72% рекомендаций, сделанных системой, которые относились к 15 реальным заболеваниям. Главной проблемой оказалась не точность диагноза, а отсутствие правил, которые позволяли бы судить о серьезности заболевания.

В 1979 году были организованы более формальные испытания усовершенствованной версии MYCIN по диагностике таких заболеваний, как бактеремия и менингит. Окончательное заключение, вынесенное программой в 10 реальных случаях, сравнивалось с заключениями ведущих медиков Станфордского университета и рядовых врачей, причем рассматривались и такие случаи, в которых лечение уже проводилось. Затем были привлечены восемь других экспертов, которых попросили оценить рейтинг 10 рекомендаций о курсе лечения в каждом из рассмотренных случаев. Для каждого из предлагавшихся наборов рекомендаций была определена максимальная оценка 80 баллов, причем экспертам было неизвестно, что некоторые из них предложены не врачом, а компьютером. Результаты представлены ниже.


Рейтинг по заключению 8 экспертов на основании 10 клинических случаев
Максимально возможная оценка — 80 баллов
MYCIN	52	Курс лечения, назначенный в действительности	46
Faculty-1	50	Faculty-4	44
Faculty-2	48	Resident	36
Inf dis fellow	48	Faculty-5	34
Faculty-3	46	Student	24
Неприемлемый курс лечения	0
Одинаковые курсы лечения	1

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

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

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

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

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

Система MYCIN при всей ее практической направленности была и осталась все-таки экспериментальной исследовательской системой, не рассчитанной на коммерческое применение. Тем не менее на ее основе были созданы другие экспертные диагностические системы, которые реально использовались в лечебной практике (об одной из них — системе PUFF — читайте в главе 13).

В этой книге мы часто будем сталкиваться с оценкой качества отдельных моделей экспертных систем, и вы увидите, что выработать какой-то общий подход к такой оценке, не принимая во внимание специфику области применения, не удается. Однако можно выделить ряд предварительных условий, которые необходимо соблюдать для адекватной оценки качества экспертной системы любого назначения (этот вопрос обсуждается в сборнике под редакцией Хейеса-Рота [Hayes-Roth et al, 1983, Chapter 8]).

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

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

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

Читателю также должно быть ясно, что роль разных экспертных систем в той или иной предметной области может быть совершенно различной, соответственно различными должны быть и требования к ее производительности. Многие экспертные системы выполняют роль советчика и предоставляют пользователю набор возможных вариантов решения проблемы. В таком случае от системы требуется в основном сформировать как можно более "емкий" перечень вариантов решения проблемы при заданных ограничениях, причем система должна уложиться в разумное время. Другие системы предназначены для формирования законченного решения проблемы, которое пользователь может принять или отвергнуть. Учитывая, что последнее слово все-таки остается не за компьютером, а за человеком, система может быть признана вполне работоспособной и в том случае, если не все 100% предлагаемых ею решений правильны, но она должна быть способна достаточно живо реагировать на запросы.

Планировщик STRIPS

Программа STRIPS [Fikes and Nilsson, 1971] демонстрирует один из подходов к представлению проблем. Наименование программы — аббревиатура от Stanford Research Institute Problem Solver (решатель проблем Станфордского исследовательского института). Программа предназначалась для решения проблемы формирования плана поведения робота, перемещающего предметы через множество (анфиладу) помещений. Программа STRIPS оказала очень большое влияние на последующие разработки в области искусственного интеллекта, и те базовые методики представления знаний, которые были в ней использованы для формирования действий, не утратили своей актуальности до настоящего времени.

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

W = { at(po6oт, комнатаА), at(ящик1, комнатаБ), at(ящик2, комнатаВ)}

означает, что робот находится в комнате А и имеются два ящика, один из которых находится в комнате Б, а второй — в комнате В.

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

"Переместить робот из комнаты А в комнату Б"

в модели мира приведет к формированию новой модели W. При этом факт at (робот, комнатаА) будет изъят из модели, а добавлен факт at (робот, комнатаБ). В результате новая модель мира будет иметь вид

W' = { at (робот, комнатаБ), at (ящик1, комнатаБ), аt (ящик2, комнатаВ)}

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

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

Ниже представлено простое метаправило сокращения количества кандидатов в системе MYCIN, заимствованное из книги Бучанана и Шортлиффа [Buchanan and Shortliffe, 1984, Chapter 28].

МЕТАПРАВИЛO001

ЕСЛИ

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

ТО

с совершенной определенностью (1.0) можно предположить, что каждое из этих правил в данном случае не применимо.

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

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

МЕТАПРАВИЛO002

ЕСЛИ

(1)инфекция относится к классу pelvic-abscess, и

(2)существуют правила, в предпосылках которых упоминается enterobacteriaceae, и

(3)существуют правила, в предпосылках которых упоминается грамполохительная окраска,

ТО

есть основания предполагать (0.4), что приоритет следует отдать первым из перечисленных правил.

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

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

МЕТАПРАВИЛO00З

(1)существуют правила, в предпосылках которых не упоминается текущая цель, и

(2)существуют правила, в предпосылках которых упоминается текущая цель,

ТО

с совершенной определенностью (1.0) можно утверждать, что сначала следует активизировать первые из перечисленных правил.

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

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

ЕСЛИ

(1)х алкоголик,

ТО

сначала следует рассмотреть правила, имеющие отношение к болезни А, а затем правила, имеющие отношение к болезни Б может быть сформулировано более абстрактно:

(1) существует определенная причина X, которая склоняет нас к мысли, что Y относится к категории Z, и

(2)существуют специальные правила, связанные именно с категорией Z,

ТО

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

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

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

5.5. Свойство выпуклости в CLIPS: пингвины обретают способность летать (или не обретают)

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

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

(defrule (bird (type ?X))

(assert (yes))

) (defrule

(declare (salience 100))

(bird (type penguin))

=>

(assert (no)) )

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

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

Правили метаправила

Код каждого порождающего правила является самодостаточным, т.е. весь необходимый контекст активизации правила содержится только в его предпосылках. Не существует способа, который позволял бы одному правилу вызывать другое, как если бы правила были процедурами. Правило R, которое активизируется в цикле Сi, может облегчить последующую активизацию правила R' в цикле Ci+1, но единственный способ сделать это — изменить состояние рабочей памяти.

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

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

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

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

ГЛАВА 3.

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

3.1. Представление знаний: принципы и методы

3.2. Планировщик STRIPS

3.3. Формулировка подцелей в MYCIN

3.4. Оценка и сравнение характеристик экспертных систем

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

Упражнения

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

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

Но начнем мы с разъяснения таинственного термина "представление знаний", используя в качестве примера разработанную приблизительно в это же время другую программу искусственного интеллекта — программу планирования STRIPS, — которую еще нельзя было отнести к классу экспертных систем. Затем будет описана система MYCIN, использованные в ней средства представления знаний и алгоритмы. Будет показано, как в процессе эксплуатации совершенствовалась система и с помощью каких средств разработчики пытались повысить ее производительность. В заключение мы сравним обе системы и отметим, что есть в них общего и в чем существенная разница. Анализ отличий между системами поможет проиллюстрировать тот существенный вклад, который внесли разработчики ранних экспертных систем в теорию и практику искусственного интеллекта в начале 70-х годов.

Представление знаний: принципы и методы

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

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

"Посещение тетушки может быть надоедливым"

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

3.1. Молотки, графины и теоремы

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

"Молоток ударил графин, и он разбился".

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

Графин ударился о камень, и он разбился."

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

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

(р & (q=>r)) э ((s v p) & (~r=>-q)).

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

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

"X ударил Y, и он разбился",

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

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

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

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

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

Представление (representation) в работе Уинстона [Winston, 1984] определяется как "множество синтаксических и семантических соглашений, которое делает возможным описание предмета". В искусственном интеллекте под "предметом" понимается состояние в некоторой проблемной области, например объекты в этой области, их свойства, отношения, которые существуют между объектами. Описание (description) "позволяет использовать соглашения из представления для описания определенных предметов" [Winston, 1992].

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

о том, насколько оно соответствует этим правилам. Смысл должны иметь только хорошо сформированные выражения.

Общепринятым в области искусственного интеллекта является синтаксис в виде конструкции предикат-аргумент, которая имеет форму

<фраза> ::= <предикат> (<аргумент>,..., <аргумент>)

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

at(робот, комнатаА)

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

at(робот, комнатаА)

означает: робот находится в комнате А (но не наоборот — комната А находится в роботе).

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

Прямая и обратная цепочки рассуждений

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

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

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

(Р1) $ -> а$а

(Р2) $ -> b$b

(РЗ) $ -> с$с

можно использовать двумя способами.

Во-первых, их можно использовать для формирования палиндромов. Если задаться некоторым начальным символом из имеющегося алфавита, то любая последовательность применения правил приведет к формированию палиндрома. Так, применение правил Р1, Р1, РЗ, Р2, Р3 к исходному символу с приведет к формированию строк

аса, aacaa, caacaac, bcaacaacb, cbcaacaacbc.

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

Во-вторых, можно использовать этот же набор правил не для формирования, а для распознавания палиндромов. Мы уже видели ранее, что, задавшись некоторой строкой, например ЬасаЬ, можно проследить, в какой последовательности применялись правила при построении этой строки. Строка bасаb соответствует правой части правила Р2; можно сказать, что правая часть правила Р2 "допускает" строку bacab. Означенная левая часть правила Р2 — это строка аса, которая соответствует правой части правила PI, a означенная левая часть этого правила — аксиома с. Таким образом, процесс распознавания успешно завершился — мы доказали, что bacab представляет собой палиндром. Описанный процесс распознавания — это пример применения обратной цепочки рассуждений. Начальная строка bacab и каждая очередная подстрока анализируются на соответствие с правыми частями имеющихся правил, а результатом является означивание левой части выбранного правила. Если в качестве исходной мы зададимся строкой acbcb, то для нее не удастся найти в имеющемся наборе правил такое, правая часть которого "допускала" бы эту строку, а значит, исходная строка не может быть палиндромом.

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

В листинге 5.4 показана простая программа построения башни из блоков. Эта программа переключается между двумя задачами: выбором очередного блока и установкой блока в башню.

В разделе шаблонов блоки представлены объектами, обладающими такими свойствами, как цвет, размер и положение.

Если положение блока не определено, предполагается, что он находится в куче блоков (heap), еще не уложенных в башню. Шаблон on предоставляет в наше распоряжение средство, позволяющее описать размещение блоков одного (upper) на другом (lower). Информацию о текущей фазе решения проблемы (поиск или установка) несет шаблон goal.

Листинг 5.4. Набор правил для построения башни из блоков

;; СТРАТЕГИЯ РАЗРЕШЕНИЯ КОНФЛИКТОВ

(declare (strategy mea))

;; Шаблоны

;; Объект block характеризуется цветом, размером и положением,

(deftemplate block

(field color (type SYMBOL))

(field size (type INTEGER))

(field place (type SYMBOL)) )

;; Вектор 'on' указывает, что блок <upper>

;; находится на блоке <lower>. (deftemplate on

(field upper (type SYMBOL»

(field lower (type SYMBOL))

(field place (type SYMBOL) (default heap)] )

;; Текущая цель (goal) может быть либо 'найти' (find),

;; либо 'уложить' (build), (deftemplate goal

(field task (type SYMBOL)) )

;; ИНИЦИАЛИЗАЦИЯ

;; Имеются три блока разных цветов и размеров.

;; Предполагается, что они находятся в куче.

(deffacts the-facts

(block (color red) (size 10))

(block(color yellow) (size 20))

(block (color blue) (size 30))

)

;; ПРАВИЛА

;; Задать первую цель: найти первый блок,

(defrule begin

(initial-fact) =>

(assert (goal (task find))) )

;; Взять самый большой блок в куче (heap),

(defrule pick-up

?my-goal <- (goal (task find))

?my-block <- (block (size ?S1) (place heap))

(not (block (color ?C2) (size ?S2&:(>-?S2 ?S1))

(place heap))) =>

(modify ?my-block (place hand))

(modify ?my-goal (task build)) )

;; Установить первый блок в основание башни (tower).

;; Этот блок не имеет под собой никакого другого,

(defrule place-first

?my-goal <- (goal (task build))

?my-block <- (block (place hand))

(not (block (place tower)))

=>

(modify ?my-block (place tower))

(modify ?my-goal (task find)) )

;; Установить последующие блоки на тот,

;; что лежит в основании башни,

(defrule put-down

?my-goal <- (goal (task build))

?my-block <- (block (color ?C0)

(place hand))

(block (color ?C1) (place tower)))

(not (on (upper ?C2) (lower ?C1)

(place tower)))

=>

(modify ?my-block (place tower))

(assert (on (upper ?CO) (lower ?C1)

(place tower)))

(modify ?my-goal (task find)) )

;; Если в куче больше нет блоков, прекратить процесс,

(defrule stop

?my-goal <- (goal (task find))

(not (block (place heap)))

=>

(retract ?my-goal) )

Обратите внимание на то, что порядок перечисления правил в программе не имеет значения. В программе управления роботом, представленной в листинге 5.3, правило прекращения выполнения стояло в списке первым, а в этой программе оно стоит в самом конце списка. Трассировку выполнения приведенной программы и некоторые комментарии вы найдете во врезке 5.4.

5.4. Трассировка программы строительства башни

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

CLIPS> (reset)

==> f-0 (initial-fact)

==> f-1 (block (color red) (size 10) (place heap))

==>f-2 (block (color yellow) (size 20) (place heap))

==> f-3 (block (color blue) (size 30) (place heap))

CLIPS> (run)

TIRE 1 begin: f-0

==> f-4 (goal (task find))

FIRE 2 pick-up: f-4, f-3,

<== f-3 (block (color blue) (size 30) (place heap))

==> f-5 (block (color blue) (size 30) (place hand))

<== f-4 (goal (task find))

==> f-6 (goal (task build))

FIRE 3 place-first: f-6, f-5,

<== f-5 (block (color blue) (size 30) (place hand))

==> f-7 (block (color blue) (size 30) (place tower))

<== f-6 (goal (task build))

==> f-8 (goal (task find))

FIRE 4 pick-up: f-8, f-2,

<== f-2 (block (color yellow) (size 20) (place heap))

==> f-5 (block (color yellow) (size 20) (place hand))

<== f-8 (goal (task find))

==> f-10 (goal (task build))

FIRE 5 put-down: f-10, f-9, f-7,

<== f-9 (block (color yellow) (size 20) (place hand))

==>. f-11 (block (color yellow) (size 20) (place tower))

==> f-12 (on (upper yellow) (lower blue) (place tower))

<== f-10 (goal (task build))

==> f-13 (goal (task find))

FIRE 6 pick-up: f-13, f-1,

<== f-1 (block (color red) (size 10) (place heap))

==> f-5 (block (color red) (size 10) (place hand))

<== f-13 (goal (task find))

==> f-15 (goal (task build))

FIRE 7 put-down: f-15, f-14, f-11,

<== f-14 (block (color red) (size 10) (place hand))

==> f-16 (block (color red) (size 10) (place tower))

==> f-17 (on (upper red) (lower yellow) (place tower))

<== f-15 (goal (task build))

==> f-18 (goal (task find))

FIRE 8 stop: f-18,

<== f-18 (goal (task find))

CLIPS> (reset)

<== f-0 (initial-fact)

<== f-7 (block (color blue) (size 30) (place tower))

<== f-11 (block (color yellow) (size 20) (place tower))

<== f-12 (on (upper yellow) (lower blue) (place tower))

<== f-16 (block (color red) (size 10) (place tower))

<== f-17 (on (upper red) (lower yellow) (place tower))

Обратите внимание на манипулирование лексемой цели в ходе выполнения программы. Конечное состояние представлено при очистке рабочей памяти. Блоки в башне расположились в таком порядке: красный (red) — самый верхний, он стоит на желтом (yellow), который стоит на синем (blue).

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

(goal (task find)

и

(goal (task build)).

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

Иногда необходимо провести четкую границу между направленностью цепочки и направленностью действительных рассуждений. Эти две операции представляют разные уровни анализа. Очевидно, что цепочка является реализацией рассуждений, а не наоборот, но стратегия рассуждений управляет процессом построения цепочки, что в данном случае выполняется манипулированием лексемами цели. В главе 14 будет продемонстрирован гораздо более сложный пример использования этого метода в системе R1/XCON.

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

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

В главе 3 мы рассказывали о представлении пространства поиска, связанного с набором порождающих правил, с помощью И/ИЛИ-дерева. Узлы такого дерева соответствуют состояниям рабочей памяти, а дуги — правилам, которые при этом возможно применить. Древовидная схема очень хорошо согласуется с методикой обратной цепочки рассуждений, если считать, что корень дерева соответствует целевому состоянию, промежуточные узлы — подцелям, а терминальные узлы (листья) — данным.

В И/ИЛИ-дереве корень представляет исходное состояние проблемы, а листья — возможные варианты ее решения. Нетерминальные узлы могут быть двух видов: И-узлы и ИЛИ-узлы. И-узлы соответствуют применению нескольких правил, которые в совокупности формируют цель как объединение нескольких подцелей, а ИЛИ-узлы соответствуют наличию альтернативы при выборе возможных правил. Таким образом, используя терминологию главы 2, можно говорить о том, что возможные варианты применения правил формируют пространство поиска и определяют его структуру.

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

Рабочая память

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

Пусть в рабочей памяти содержатся векторы

(patient (name Jones) (age 40)

(organism organism-1))

(organism (name organism-1)

(morphology rod) (aerobicity .aerobic)).

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

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

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

(patient (name Jones) (age 40)

(organism organism-1))

удовлетворяет предпосылку в правиле

(patient (name ?pat) (organism ?org))

подстановкой Jones вместо ?pat и Organism-1 вместо ?org.

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

(organism (name organism-1)

(identify enterobacteriaceae) (confidence 0.8))

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

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

Теперь рассмотрим набор правил, представленный в листинге 5.3, вместе с множеством векторов в рабочей памяти.
Этот пример основан на планировщике STRIPS, о котором шла речь в главе 3. Программа состоит из выражений трех типов:

деклараций (или шаблонов), которые определяют формат векторов в рабочей памяти;

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

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

Строки, которые начинаются символами ";;", являются комментариями.

Листинг 5.3. Набор правил для проблемы в системе STRIPS

;; Шаблоны

;; Цель (goal) представляет собой вектор, состоящий из

;; четырех компонентов:

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

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

;; исходное положение;

;; положение, в которое нужно перейти.

(deftemplate goal

(field action (type SYMBOL))

(field object (type SYMBOL))

(field from (type SYMBOL))

(field to (type SYMBOL))

)

;; Вектор 'in' указывает, где находится объект, (deftemplate in

(field object (type SYMBOL))

(field location (type SYMBOL)) )

ФАКТЫ

;;Функция 'deffacts' вводит в рабочую память

;;описание исходного состояния.

;;Функция вызывается при перезапуске системы.

;;Исходное состояние объектов следующее.

;;Робот находится в комнате А,

;;ящик находится в комнате В,

;;цель - вытолкнуть ящик в комнату А.

(deffacts world

(in (object robot)

(location RoomA))

(in (object box)

(location RoomB))

(goal (action push)

(object box)

(from RoomB) (to RoomA))

)

;; ПРАВИЛА

;; Это правило утверждает:

;; Прекратить процесс, когда цель будет достигнута.

(defrule stop

(goal (object ?X) (to ?Y))

(in (object ?X) (location ?Y)) =>

(halt) )

;; Если робот отсутствует в том месте, где находится

;; объект, который нужно передвинуть,

;; переместить туда робот.

(defrule move

(goal (object ?X) (from ?Y))

(in (object ?X) (location ?Y))

?robot-position <- (in (object robot)

(location ?Z&~?Y)) =>

(modify ?robot-position (location ?Y))

;; Если робот и объект не в том помещении,

;; которое указано в цепи,

;; переместить туда робот и объект.

(defrule push

(goal (object ?X) (from ?Y) (to ?Z))

(in (object ?X) (location ?Y))

?object-position <- (in (object ?X) (location ?Y))

?robot-position <- (in (object robot) (location ?Y))

=>

(modify ?robot-position (location ?Z))

(modify ?object-position (location ?Z))

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

введите (reset),

затем введите (run).

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

5.2. Трассировка программы управления роботом

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

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

В карте трассировки каждая строка, которая начинается с символов ==>, представляет добавление вектора в рабочую память, а строка, которая начинается с символов, <==, — удаление вектора из рабочей памяти. Строки, которые начинаются с 'FIRE', представляют активизацию какого-либо правила. Остальные строки пока ,что игнорируйте.

(reset)

==> f-0 (initial-fact)

=> f-1 (in (object robot) (location RoomA))

==> f-2 (in (object box) (location RoomB))

==> f-3 (goal (action push) {object box)

(from RoomB) (to RoomA)) CLIPS>

(run) FIRE 1 move: f-3, f-2, f-1

<== f-1 (in (object robot) (location RoomA))

==> f-4 (in (object robot) (location RoomB))

FIRE 2 push: f-3, f-2, f-4 <== f_4

(in (object robot) (location RoomB))

==> f-5 (in (object robot) (location RoomA))

<== f-2 (in (object box) (location RoomB))

==> f-6 (in (object box) (location RoomA))

FIRE 3 stop: f-3, f-6

[PRCCODE4] Execution halted during the actions of defrule stop.

CLIPS> (reset)

<== f-0 (initial-fact)

<== f-3 (goal {action push)

(object box) (from RoomB) (to RoomA))

<== f-5 (in (object robot) (location RoomA))

<== f-6 (in (object box) (location RoomA))

CLIPS>

Обратите внимание на то, что выполнение программы останавливается правилом 'stop'.

Разрешение конфликтов

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

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

При выработке стратегии разрешения конфликтов обычно используется комбинация разных базовых механизмов, каждый из которых обладает свойственными только ему характеристиками. Производительность экспертной системы зависит от таких ключевых характеристик режима управления, как чувствительность и стабильность. Чувствительность характеризует, как быстро система будет реагировать на изменение среды, которое отражается в рабочей памяти, а стабильность характеризует степень консерватизма в поведении системы ([McDermott andForgy, 1978], [Brownston et al., 1985, Chapter 7]).

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

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

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

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

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

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

5.3. Разрешение конфликтов в CUPS

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

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

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

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

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

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

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

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

МЕА — это аббревиатура от наименования одной из первых методик решения задач искусственного интеллекта путем построения обратной цепочки рассуждений Mean-Ends Analysis (средство — анализ результата). Идея состоит в том, что стратегия должна быть использована вместе со специальными лексемами цели в рабочей памяти, которые направляют процесс рассуждений и которым соответствуют первые условия в предпосылках правил. Пример использования такой методики представлен в главе 14.

В системе OPS5, многие черты которой унаследовали более поздние программные средства построения экспертных систем, использовались только две последние из перечисленных стратегий — LEX и МЕА. Стратегия LEX показала себя как хорошая стратегия общего применения, в то время как МЕА является эффективной стратегией при решении более специфических задач, таких как планирование. Тривиальный пример использования этой стратегии в программе на языке CLIPS представлен в листинге 5.4.

Синтаксис представления правил

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

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

подмножества N имен объектов предметной области;

подмножества Р имен свойств, которые рассматриваются в качестве атрибутов объектов;

подмножества V допустимых значений атрибутов.

На практике подмножества N и V перекрываются.

Используемая грамматика, как правило, имеет вид триад объект-атрибут-значение. Триада (v, л, w) существует, если v принадлежит N и л принадлежит Р, w принадлежит V. Например, триада

(ОРГАНИЗМ-1, морфология, палочка)

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

Представленная синтаксическая форма обобщается в том случае, когда нужно для некоторого объекта v представить « вариантов пар атрибут-значение (л1,w1) ..., (лn,wn). В таком случае они объединяются в вектор в форме

(v, л1, w1,..., лn, wn).

На языке CLIPS тот факт, что определенный микроорганизм имеет форму палочки и активно развивается в воздушной среде, будет представлен вектором

(organism-1 (morphology rod) (aerobicity aerobic)).

В дальнейшем мы будем повсеместно использовать именно такой синтаксис, поскольку CLIPS будет нашим основным программным инструментом.

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

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

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

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

P1,..., Pm,->Q1,..., Qn
которая читается следующим образом:

если предпосылки Р1 и ... и Рт верны, то выполнить действия Q1 и ... и Qn.

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

Предпосылки обычно бывают представлены в форме вектора объект-атрибут— значение, как, например:

(organism-1 (morphology rod) (aerobicity aerobic)).

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

Правило, которое включает такую предпосылку, на языке CLIPS имеет вид, показанный в листинге 5.1.

Листинг 5.1. Оргправило системы MYCIN, записанное на языке CLIPS

(defrule diagnosis

(patient (name Jones)
(organism organism-1))
(organism (name organism-1)
(morphology rod)
(aerobicity aerobic)) => (assert

(organism

(name organism-1)

(identify enterobacteriaceae)

(confidence 0.8)))

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

(defrule <наименование правила> <предпосылка1>

<предпосылка m > =>

<действие 1>

<действие n>

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

(organism (name organism-1)
(identify enterobacteriaceae)
(confidence 0.8)).

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

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

Листинг 5.2. Правило, в котором используются переменные

(defrule diagnosis

(patient (name ?pat)
(organism ?org))
(organism (name ?org)
(morphology rod)
(aerobicity aerobic)) => (assert

(organism

(name ?org)

(identify enterobacteriaceae) (confidence 0.8)))

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

Системы, основанные нзнаниях

5.1. Канонические системы

5.2. Системы порождающих правил для решения проблем

5.3. Управление функционированием интерпретатора

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

Упражнения

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

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

Набор порождающих правил — это формализм, который уже использовался в теории автоматов, формальной грамматике, разработке языков программирования, прежде чем стать на службу моделированию психофизиологической деятельности [Newell and Simon, 1972] и экспертных систем [Buchanan and Feigenbaum, 1978]. В литературе по экспертным системам их иногда называют правилами "условие — действие" или "ситуация — действие". Это связано с тем, что такие правила обычно используются для представления эмпирических ассоциативных связей между данными, предъявленными системе, и действиями, которые система должна предпринять в ответ.

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

Системы порождающих правил для решения проблем

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

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

Сравнение MYCIN и STRIPS

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

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

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

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

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

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

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

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

"Первыми разнести посылки тем адресатам, которые расположены наиболее близко",

а второе:

"Избегать выезда в предместья во время напряженного трафика".

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

Машина логического вывода должна быть спроектирована так, чтобы справляться с подобными противоречиями.

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

Структуры управления в MYCIN

Целевое правило самого верхнего уровня в системе MYCIN можно сформулировать примерно так:

ЕСЛИ 1) существует микроорганизм, который требует проведения курса терапии, и 2) заданы соображения относительно любых других микроорганизмов, которые требуют проведения курса терапии,

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

формируется контекст пациента в форме самого верхнего узла контекстного дерева;

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

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

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

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

Рассмотрим следующий набор правил "условие-действие":

Если

X имеет СЛУЖЕБНОЕ УДОСТОВЕРЕНИЕ И

X имеет ОГНЕСТРЕЛЬНОЕ_ОРУЖИЕ, ТО X - ПОЛИСМЕН.

ЕСЛИ

X имеет РЕВОЛЬВЕР, или

X имеет ПИСТОЛЕТ, или

X имеет ВИНТОВКУ, ТО X имеет ОГНЕСТРЕЛЬНОЕ ОРУЖИЕ.

Если

X имеет ЛИЧНЫЙ_ЖЕТОН, то

X имеет СЛУЖЕБНОЕ_УДОСТОВЕРЕНИЕ.

Эти правила можно представить в виде набора узлов в дереве целей (рис. 3.4), в котором отражены цели, которые выступают в совокупности, и те, которые воспринимаются независимо, по одиночке. Между связями, идущими от узла ПОЛИСМЕН (корневой узел — главная цель) к узлам СЛУЖЕБНОЕ_УДОСТОВЕРЕНИЕ и ОГНЕСТРЕЛЬНОЕ_ОРУЖИЕ, проведена дуга, которая подчеркивает, что для удовлетворения главной цели необходимо удовлетворить обе подцели. Но между связями, проведенными от узла ОГНЕСТРЕЛЬНОЕ_ОРУЖИЕ к узлам РЕВОЛЬВЕР, ПИСТОЛЕТ и ВИНТОВКА, такой дуги нет, поскольку для удовлетворения цели ОГНЕСТРЕЛЬНОЕ_ОРУЖИЕ достаточно удовлетворить любую из присоединенных подцелей. Узел может иметь и единственного наследника, как узел СЛУЖЕБНОЕ_ УДОСТОВЕРЕНИЕ на этом графе.

И/ИЛИ-граф на рис. 3.4 можно рассматривать как способ представления пространства поиска для цели ПОЛИСМЕН, перечислив все способы, которыми можно применить различные операторы, чтобы достичь главной цели.

Рис. 3.4. Представление набора правил в виде И/ИЛИ-графа

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

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

Структура управления правилами в MYCIN использует И/ИЛИ-граф и по сравнению с программами искусственного интеллекта довольно проста — в ней, по сути, использована методика исчерпывающего поиска, описанная в главе 2, в которую внесены только незначительные изменения.

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

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

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

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

3.2. Комбинация гипотез

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

Другое правило, принимая во внимание другие свойства анализируемого объекта, приводит к заключению/что этот микроорганизм — E.Coli, но эта гипотеза характеризуется коэффициентом уверенности 0.5 (или, например, -0.8). Отрицательное значение коэффициента уверенности указывает, что данное правило опровергает сформулированное заключение.

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

	{	X+Y-XY	при X,Y>0
CF(X,Y)=	{	X+Y+XY	при X,Y<0
	{	(X+Y)/(1-min(\|X\|,\|Y\|))	при (X>0 и Y<0) или (X<0 и Y>0)

Здесь |Х| означает абсолютное значение X.

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

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

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

ЕСЛИ микроорганизм идентифицирован как pseudomonas,

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

1 - COLISTIN (0.98)

2 - POLYMIXIN (0.96)

3 - GENTAMICIN (0.96)

4 - CARBENICILLIN (0.65)

5 - SULFISOXAZOLE (0.64)

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

Таблицы операторов и методик"средство -анализ завершения"

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

push(X, Y, Z)

Предварительные условия at(po6oT, Y), at(X, Y)

Список удалений at (робот, Y), at(X, Y)

Список добавлений at (робот, Z), at(X, Z)

Здесь выражение push(X, Y, Z)

означает, что объект X выталкивается (роботом) из положения Y в положение Z, причем X, Y и Z — переменные в области значений, охватывающей доступное множество объектов, в то время как робот, комнатаА, ящик1, комнатаБ, ящик2, комнатаВ — это имена конкретных объектов из этого множества.

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

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

С точки зрения логики элемент push таблицы операторов может быть прочитан в виде формулы, которая утверждает:

"При любых X, Y и Z объект X выталкивается из Y в Z, если робот и объект X находятся в 7, а затем состояние изменятся заменой Y на Z".

Целевое состояние также представляется формулой, например: а1(ящик1, комнатаА), а^ящик2, комнатаБ).

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

обработка списка целей;

выбор очередной цели;

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

анализ соответствия между целью и формулам в списке добавлений в модель;

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

Чтобы представить себе, как на практике использовать подобную "структуру представлений, рассмотрим простую задачу: как готовиться к ленчу с потенциальным клиентом.
Для этого, во-первых, нужно иметь в своем распоряжении определенную сумму наличных денег, чтобы расплатиться, во-вторых, нужно проголодаться, поскольку речь идет о приеме пищи. Сформулированные условия можно рассматривать в качестве предварительных для достижения цели "ленч". Эта цель может быть представлена оператором, как на рис. 3.1. После завершения ленча деньги будут потрачены, а у вас исчезнет чувство голода. Эти простые факты нашли отражение в списках удалений и добавлений для оператора have lanch. Однако обладание известной суммой наличных денег нельзя рассматривать как естественное состояние клиента. Сначала нужно получить их в банкомате, что, в свою очередь, требует передвижения. Следовательно, нужно добавить в таблицу операторов еще два элемента — at cash mashine (передвижение к банкомату) и have money (получение наличности).

Этот простой пример обладает довольно интересными свойствами. Отметим, что формулы для модели мира в исходном состоянии

at(work), have(transport)

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

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

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

Рис. 3.1. Таблица операторов для задачи "Ленч"

По существу, в системе STRIPS при выборе операторов выполняется поиск в пространстве состояний, как это было описано в главе 2. В результате формируется план, т.е. последовательность операторов, приводящая к достижению цели, причем за основу берется стратегия "обратного" прослеживания. Основное отличие STRIPS от других аналогичных программ состоит в том, что вместо методики "генерация —проверка" для передвижения в пространстве состояний используется другой метод, известный как "средство — анализ завершения" (means-ends analisys).

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

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

Такая мера очень походит на оценочную функцию. Если очередная цель сформулирована в виде

at(ящик1, комнатаА),

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

В действительности программа STRIPS считывает список целей наподобие такого:

at(ящик1, комнатаА), аt(ящик2, комнатаБ),

а затем сопоставляет эти цели и список добавления в описании каждого оператора. Так, цель at (ящик!, комнатаА) будет соответствовать элементу at(X, Z) в списке добавлений оператора push (X, Y, Z).

Схема сопоставления будет подробно рассмотрена в главах 4, 5 и 8, но сейчас, не вдаваясь в детали, просто отметим, что существует подстановка значений переменных

Х/ящик1, Z/комнатаА,

которая приводит к равенству выражений at (ящик!, комнатаА) nat(X, Z).

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

(1) Подстановкой {Х/ящик1, Z/комнатаА} означить предварительное условие, которое является производным от соответствия at (ящик!, комнатаА) nat(X, Z), и получить таким образом

at(po6oт , Y), at(ящик1, Y).

(2) Найти в модели мира формулу, которая представляла бы текущее положение ящика а1(ящик1, комнатаБ), сравнить ее с at(ящик1, Y) и в результате этого сравнения сформулировать подстановку {Y/комнатаБ}, которую затем применить к уже частично означенному предварительному условию. В результате будет сформулирована очередная подцель:

at(робот, комнатаБ), at(ящик1, комнатаБ).

Теперь первое предварительное условие даст желаемое (целевое) положение робота, а второе предварительное условие уже выполнено.

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

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

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

Управление функционированием интерпретатора

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

(1) Сопоставить образцы в предпосылках правил и элементы данных в рабочей памяти.

(2) Если окажется, что можно активизировать более одного правила, выбрать одно из них; этот шаг называется разрешением конфликта.

(3) Применить выбранное правило. Результатом, скорее всего, будет добавление нового элемента данных в рабочую память и/или удаление какого-либо существующего элемента из рабочей памяти. Затем перейти к шагу 1.

Обычно перед началом этого циклического процесса в рабочую память вводится элемент, соответствующий исходному состоянию проблемы. На языке CLIPS такой элемент является вектором (initial-fact). Процесс останавливается, если будет обнаружен цикл, в котором ни одно из правил не может быть активизировано, или если активизированное правило явно содержит команду прекращения работы5. На шаге 2 система располагает набором пар, состоящих из правил и подстановок переменных, которые сформированы при сопоставлении образцов. Такие пары называются означиваниями (instantiations). Механизм разрешения конфликтов специфичен для каждой системы, т.е. для каждого интерпретатора правил. Можно, конечно, сформулировать и такой набор правил, что в любой ситуации только одно из них будет удовлетворяться (он называется детерминированным). Но в экспертных системах обычно используются недетерминированные наборы правил, поскольку в реальной жизни очень часто встречаются ситуации, которые позволяют использовать более одного правила.

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

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

Что такое таблица операторов? Можно

1. Что такое таблица операторов? Можно ли в таблице операторов представить любую операцию, выполнение которой хотелось бы потребовать от робота?

2. Что такое порождающее правило? Какое, на ваш взгляд, существует соответствие между набором порождающих правил и деревом решений?

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

4. Представьте себе, что манипуляционный робот смонтирован над столиком с детскими игрушками. В таблице операторов имеется оператор move (В, L, М), который заставляет робот перенести блок В из положения L в положение М.

move (В, L, M)
Предварительные условия on (В, L), clear (В), clear (M)
Список удалений on (В, L), clear (M)
Список добавлений on (В, L), clear (L), clear (столик)

Здесь выражение on (В, L) означает, что блок В устанавливается на объект L, причем в качестве L может выступать или поверхность столика, или другой блок; непосредственно на один блок можно поставить только еще один блок, но на поверхность столика можно ставить сколько угодно блоков; выражение clear (L) означает, что на объекте L ничего не стоит.

I) Выразите сцену, представленную на рис. 3.5, в виде формул модели мира.

II) Пусть перед роботом поставлена цель перестроить башню, показанную на рис. 3.5, установив блоки в следующем порядке: синий— на красном, красный — на зеленом, а зеленый — на поверхности столика. Таким образом, перед роботом стоит цель преобразовать модель мира и привести ее к виду

on(зеленый, стол), on(красный, зеленый), on(синий, красный). Представьте план достижения этой цели.

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

IV) Почему после каждой операции move нужно добавлять формулу clear (столик)?

V) Можно ли, используя представленный элемент move в таблице операторов, выразить "отрицательную" цель, например "зеленый блок не должен стоять

Рис. 3.5. Задача о перемещении блоков

1. Как вы понимаете термин "разрешение конфликтов"?

2. Пусть А — это алфавит {а, b} и пусть в этом алфавите существуют аксиомы ab, bа.

Какие строки будут сформированы следующими порождающими правилами:
(Р1) $a ->$ab
(Р2) $b -> $bа

3. Пусть А — это алфавит {а, b} и пусть в этом алфавите существуют аксиомы аа, bb.

Какой набор порождающих правил может сформировать строки вида аа, bb, aabb, bbaa, aabbaa, bbaabb, aabbaabb, bbaabbaa и т.д.

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

Все Аi являются Вi Все Вi являются Сi Все Аi являются Сi

Все Аi являются Еi Некоторые Аi являются С, Все Сi являются Вi

Все Аi являются Вi

Ни один из Сi не является Вi

Ни один из Сi не является Аi

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

Вам понадобится единственный шаблон, в котором будет определено, что утверждение (statement) состоит из квантификатора (quantifier), который может принимать одно из трех значений: all (все), some (некоторые) или по (ни один) и двух множеств.

(deftemplate statement

(field quantifier (type SYMBOL))

(field setl (type SYMBOL))

(field set2 (type SYMBOL)) )

Так, выражение "Все А1 являются В" примет вид

(statement (quantifier all) (setl As) (set2 Bs))

Проверить, как работает программа, можно на таких фактах:

(deffacts the-facts

(statement (quantifier all) (setl puppies)

(set2 dogs)) (statement (quantifier all) (setl dogs)

(set2 mammals)) (statement (quantifier all) (setl mammals)

(set2 animals)) (statement (quantifier no) (setl sea-cretures)

(set2 dogs)) (statement (quantifier some) (setl sea-cretures)

(set2 mammals)) )

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