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

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

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

В качестве наиболее доступного руководства по языку LISP я бы рекомендовал книгу Уинстона и Хорна [Winston and Horn, 1988], а в книгах Чарняка [Charniak et al., 1987] и Грехема [Graham, 1994] можно уточнить многие детали применения LISP для решения задач искусственного интеллекта.

В прекрасной книге Норвига [Norvig, 1992] подробно описан базовый диалект Common LISP, а в книге Рассела и Норвига [Russel and Norvig, 1995] основное внимание уделено программированию задач искусственного интеллекта.

В книге Кратко [Braico, 1990] читатель найдет обширный материал по использованию языка PROLOG для решения задач искусственного интеллекта. Кроме того, желающим изучить язык PROLOG я также рекомендую прочесть книгу Стерлинга и Шапиро [Sterling and Shapiro, 1994].

Упражнения

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

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

Пусть 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)).

ГЛАВА 5. Системы, основанные на знаниях

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

Системы порождающих правил для решения проблем

Синтаксис представления правил

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

Управление функционированием интерпретатора

Разрешение конфликтов

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

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

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

Упражнения

ГЛАВА 5. Системы, основанные на знаниях

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

Системы порождающих правил для решения проблем

Управление функционированием интерпретатора

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

Упражнения

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

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

Набор порождающих правил — это формализм, который уже использовался в теории автоматов, формальной грамматике, разработке языков программирования, прежде чем стать на службу моделированию психофизиологической деятельности [Newell and Simon, 1972] и экспертных систем [Buchanan and Feigenbaum, 1978]. В литературе по экспертным системам их иногда называют правилами "условие — действие" или "ситуация — действие". Это связано с тем, что такие правила обычно используются для представления эмпирических ассоциативных связей между данными, предъявленными системе, и действиями, которые система должна предпринять в ответ.

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

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

Порождения — это в действительности грамматические правила манипулирования строками символов и потому их иногда называют правилами переписывания (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). В действительности к этому нужно добавить тривиальную оговорку, что такая система может нуждаться еще в дополнительном алфавите, буквы которого будут использоваться в качестве знаков пунктуации в сложных доказательствах. Таким образом, для проверки доказательства в любой формальной системе или для того, чтобы выполнить любую эффективную процедуру, вполне достаточно способности прочесть строку символов, разделить ее на компоненты и переупорядочить (при этом, возможно, придется добавить еще какие-то символы или удалить существующие в исходной строке).

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