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

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

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

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

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

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

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

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

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

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

ГЛАВА 3. Представление знаний

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

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

3.2.1. Таблицы операторов и методика "средство — анализ завершения"

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

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

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

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

Структуры управления в MYCIN

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

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

Сравнение MYCIN и STRIPS

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

Упражнения

ГЛАВА 3. Представление знаний

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

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

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

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

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

Упражнения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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