Часть 13.

затем система CLOS объединяет в общую родовую функцию. Приведем упрощенный синтаксис функции def generic.

(defgeneric имя-функции лямбда-список <описание-метода>*) <описание-метода> ::= (:method специализированный-лямбда-список форма)

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

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

(defclass rectangle ()

((length raccessor get-length :initarg init-length) (width :accessor get-width :initarg init-width))) (defclass circle ()

((radius :accessor get-radius :initarg init-radius))) (defgeneric area (shape)

(:method ((shape rectangle)) (* (get-length shape)

(get-width shape))) (:method ((shape circle))

(* (get-radius shape) (get-radius shape) pi)))

(setq rect (make-instance 'rectangle 'init-length 10 'init-width 5)) (setq circ (make-instance 'circle 'init-radius 7))

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

(area rect)

50

(area circ)

153.93804002589985

Методы определяются с помощью функции def method, синтаксис которой напоминает синтаксис функции defun. Однако здесь для объявления класса, к которому принадлежат аргументы, используется специализированный лямбда-список. Если при определении функции с помощью def method не существует родовой функции с таким именем, она создается. Если же родовая функция с таким именем уже существует, то новый метод добавляется к ней. Например, к приведенному выше определению можно добавить класс квадратов square.

(defclass square ()

((side accessor get-side :initarg init-side))) (defmethod area ((shape square))

(* (get-side shape)

(get-side shape)))

(setq sqr (make-instance 'square 'init-side 6))

754 Часть VI. Языки и технологии программирования для искусственного интеллекта

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

(area sqr)

36

(area rect)

50

(area circ)

153.93804002589985

15.12.3. Наследование в CLOS

Язык CLOS поддерживает множественное наследование. Наряду с гибкой схемой представления данных множественное наследование таит опасность возникновения аномалий, связанных с наследованием элементов и методов. Если для двух предков определен один и тот же метод, то важно знать, какой из них наследуется. Возможные неоднозначности устраняются в CLOS за счет определения списка приоритетности классов (class precedence), в котором упорядочиваются все классы иерархии.

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

Любой прямой родительский класс предшествует любому более дальнему предку.

Порядок приоритетности непосредственных родительских классов соответствует

их указанию при вызове функции def class слева направо.

Система CLOS строит список приоритетности классов для любого объекта путем топологической сортировки его родительских классов согласно следующему алгоритму. Пусть С - это класс, для которого требуется определить список приоритетности.

Пусть Sc - это множество, состоящее из С и всех его суперклассов.

Для каждого класса с из Sc определяется множество упорядоченных пар

Яс = {(с,с,), (с„с2),(с2,с3)...(с„.„сп)},

где С! ...,с„- прямые предки класса с в порядке их перечисления в определении def class. Заметим, что для каждого множества Rc определен глобальный порядок.

Пусть Я - это объединение множеств Яс, составленных для всех элементов Sc.

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

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

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

Строится пустой список приоритетности Р.

Находится класс в Я, не имеющий предков. Он добавляется в конец списка Р и

удаляется из множества Sc, а все содержащие его пары удаляются из Я. Если в

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

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

кущей версии списка Р.

Пункты 4.1 и 4.2 повторяются до тех пор, пока не будут исчерпаны все элемен

ты из Я, не имеющие предков.

Глава 15. Введение в LISP 755

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

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

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

Затем система CLOS сортирует все подходящие методы с учетом списков приоритетности аргументов. Путем сравнения специализированных параметров слева направо определяется, какой из двух методов должен стоять первым. Если первая пара соответствующих специализированных параметров совпадает, система CLOS сравнивает вторую пару. Этот процесс продолжается до тех пор, пока не будет найдена пара различающихся специализированных параметров. Среди них более специализированным считается метод, параметр которого находится левее в списке приоритетности соответствующего аргумента. После сортировки всех подходящих методов по умолчанию применяется наиболее специализированный метод для данных аргументов. Более подробно эта процедура описана в работе [Steele, 1990].

15.12.4. Пример: моделирование термостата

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

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

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

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

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

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

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

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

756 Часть VI. Языки и технологии программирования для искусственного интеллекта

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

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

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

База знаний должна описывать информацию, хранящуюся в классах room и thermostat, экземплярами которых являются объекты room-322 и thermostat-211 соответственно.

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

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

Основу реализации этой модели составляет набор определений классов. Класс термостатов имеет один элемент- setting. Для каждого экземпляра он инициализируется значением 65 с помощью функции initf orm. Для класса thermostat определен производный класс heater-thermostat для управления радиаторами (в противовес кондиционерам воздуха). Единственный элемент этого класса связывается с экземпляром класса heater. Заметим, что элемент класса heater имеет тип размещения : class. Это означает, что термостаты в разных комнатах управляют общим на все здание радиатором.

(defclass thermostat ()

((setting cinitform 65

:accessor therm-setting))) (defclass heater-thermostat (thermostat) ((heater :allocation :class

:initarg heater-obj)))

Класс heater обладает состоянием (on или off), которое изначально принимает значение off, и характеризуется местоположением. Он также включает элемент rooms-heater, связанный со списком объектов типа room. Заметим, что экземпляры классов, как и другие структуры данных LISP, могут быть элементами списков.

(defclass heater ()

((state :initform 'off

:accessor heater-state) (location :initarg loc) (rooms-heated)))

Глава 15. Введение в LISP 757

Элементами класса room являются temperature, принимающий начальное значение 65, thermostat, связанный с экземпляром класса thermostat, и name, описывающий имя комнаты.

(defclass room ()

((temperature :initform 65

:accessor room-temp) (thermostat :initarg therm

:accessor room-thermostat) (name :initarg name

:accessor room-name)))

Иерархия описанных классов приводится на рис. 15.8.

Рис. 15.8. Иерархия классов в модели термостата

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

(setf office-heater (make-instance 'heater 'loc 'office)) (setf room-325 (make-instance 'room

'therm (make-instance 'heater-thermostat 'heater-obj office-heater)

'name 'room-325)) (setf (slot-value office-heater 'rooms-heated) (list room-325))

Определения экземпляров и связи между ними показаны на рис. 15.9.

Поведение комнат описывается методами change-temp, check-temp и change-setting. Метод change-temp устанавливает новое значение температуры в комнате, выводит сообщение пользователю и вызывает метод check-temp, чтобы проверить, не нужно ли включить радиатор. Аналогично метод change-setting изменяет установку термостата и вызывает метод check-temp, моделирующий функцию термостата. Если температура в комнате ниже установки термостата, он передает обогревателю сообщение о включении. В противном случае передается сообщение об отключении.

758 Часть VI. Языки и технологии программирования для искусственного интеллекта

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

(defmethod change-temp ((place room) temp-change)

(let ((new-temp (+ (room-temp place) temp-change))) (setf (room-temp place) new-temp) (terpri)

(prinl "температура в") (prinl (room-name place)) (prinl "составляет") (prinl new-temp) (terpri) (check-temp place)))

(defmethod change-setting ((room room) new-setting) ((let ((therm (room-thermostat room)))

(setf (therm-setting therm) new-setting)

(prinl "изменение установки термостата в")

(prinl (room-name room))

(prinl "на")

(prinl new-setting)

(terpri)

(check-temp room)))

(defmethod check-temp ((room room))

(let* ((therm (room-thermostat room))

(heater (slot-value therm 'heater)))

(cond ((> (therm-setting therm) (room-temp room))

(send-heater heater 'on)) (t (send-heater heater 'off)))))

Глава 15. Введение в LISP

759

Методы класса heater управляют состоянием обогревателя и изменением температуры в комнатах. Аргументами метода send-heater являются экземпляр обогревателя и сообщение, передающее новое состояние. Если новым состоянием является on, вызывается метод turn-on включения обогревателя, в противном случае вызывается метод его отключения turn-off. После включения обогревателя вызывается метод heat-rooms для повышения температуры в комнатах на 1 градус.

(defmethod send-heater ((heater heater) new-state) (case new-state

(on (if (equal (heater-state heater) 'off) (turn-on heater))

(heat-rooms (slot-value heater 'rooms-heated) 1)) (off (if (equal (heater-state heater) 'on)

(turn-off heater))))) (defmethod turn-on ((heater heater)) (setf (heater-state heater) 'on) (prinl "включение обогревателя в") (prinl (slot-value heater 'location)) (terpri))

(defmethod turn-off ((heater heater)) (setf (heater-state heater) 'off) (prinl "отключение обогревателя в") (prinl (slot-value heater 'location)) (terpri)) (defun heat-rooms (rooms amount)

(cond ((null rooms) nil)

(t (change-temp (car rooms) amount)

(heat-rooms (cdr rooms) amount))))

Приведем пример работы модели.

> (change-temp room-325 5)

"температура в "room-325" составляет "60

"включение обогревателя в "office

"температура в "room-325" составляет "61

"температура в "room-325" составляет "62

"температура в "room-325" составляет "63

"температура в "room-325" составляет "64

"температура в "room-325" составляет "65

"отключение обогревателя в "office

nil

> (change-setting room-325 70)

"изменение установки термостата в "room-325" на "70 "включение обогревателя в "office "температура в "room-325" составляет "66 "температура в "room-325" составляет "67 "температура в "room-325" составляет "68 "температура в "room-325" составляет "69 "температура в "room-325" составляет "70 "отключение обогревателя в "office nil

760 Часть VI. Языки и технологии программирования для искусственного интеллекта

15.13. Обучение в LISP: алгоритм ID3

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

В алгоритме ID3 задействованы сложные структуры данных, в том числе объекты, свойства, множества и деревья решений. Основу его реализации составляет набор определений структур - агрегатных типов данных, аналогичных записям в языке Pascal или структурам в С. С помощью функции def struct в Common LISP можно определить тип данных как набор именованных элементов. Форма def struct строит функции, необходимые для создания и управления объектами данного типа.

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

15.13.1. Определение структур с помощью функции def struct

С помощью функции def struct можно определить новый тип данных (data type) сотрудников - employee.

(defstruct employee name address serial-number department salary)

Здесь employee - это имя типа, name, address, serial-number, department и salary- имена его элементов. При оценивании формы defstruct не создается никаких экземпляров записей о сотрудниках. Определяются лишь тип и функции, необходимые для создания и управления его элементами. Параметрами функции defstruct являются символ, который становится именем нового типа, и количество спецификаторов элементов. В данном случае 5 элементов определены по имени. Спецификаторы элементов позволяют также определять различные свойства элементов, включая их тип и информацию для инициализации [Steele, 1990].

Оценивание формы defstruct приводит к нескольким результатам. Рассмотрим для примера следующее определение.

Глава 15. Введение в LISP 761

(defstruct <имя типа> <имя элемента 1> <имя элемента 2>

<имя элемента п>)

Эта форма определяет функцию, имя которой формируется по принципу make-<ил«я muna>. Это позволяет создавать экземпляры данного типа. Например, после определения структуры employee с объектом этого типа можно связать имя new-employee.

(setq new-employee (make-employee))

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

(setq new-employee (make-employee

:name '(Doe Jane)

:address "1234 Main, Randolph, Vt"

:serial-number 98765

:department 'Sales

:salary 4500.00))

При оценивании функции defstruct <имя muna> становится названием типа данных. Это имя можно использовать в функции typep для проверки принадлежности объекта к некоторому типу. Например, так.

> (typep new-employee 'employee)

t

Более того, defstruct определяет функцию <гшя muna>-p, которую тоже можно использовать для проверки принадлежности объекта к данному типу.

(employee-p new-employee)

t

(employee-p '(Doe Jane))

nil

И, наконец, defstruct определяет функции доступа к каждому элементу структуры. Их имена формируются по схеме

<имя типа> <имя элемента>

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

(employee-name new-employee)

(Doe Jane)

(employee-address new-employee)

"1234 Main, Randolph, Vt"

(employee-department new-employee)

Sales

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

(employee-salary new-employee)

4500.0

(setf (employee-salary new-employee) 5000.00)

762 Часть VI. Языки и технологии программирования для искусственного интеллекта

5000.0

> (employee-salary new-employee)

5000.0

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

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

Таблицы - это лишь один из способов представления примеров. В более общем случае их можно рассматривать как объекты, обладающие различными свойствами. Сделаем несколько предположений о представлении объектов. Для каждого свойства определим функцию, зависящую от одного аргумента и применяемую для получения значения этого свойства. Например, если объект credit-prof ile-1 связан с первым примером из табл. 9.1, a history - функция, возвращающая значение кредитной истории, то при вызове этой функции для указанного объекта будет получен следующий результат.

> (history credit-profile-1)

bad

Аналогично зададим функции для других свойств кредитного профиля.

(debt credit-profile-1)

high

(collateral credit-profile-1)

none

(income credit-profile-1)

0-to-15k

(risk credit-profile-1)

high

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

((risk.high) (history.bad) (debt.high)(collateral.none) (income.0-15k))

Для определения примеров из табл. 9.1 в виде структур воспользуемся функцией def struct. Полный набор обучающих примеров представим в виде списка ассоциативных списков и свяжем этот список с именем examples.

(setq examples

'(((risk . high) (history . bad) (debt . high) (collateral . none)

(income . 0-15k))

((risk . high) (history . unknown) (debt . high)

(collateral . none) (income . 15k-35k))

((risk . moderate) (history . unknown)(debt . low)

(collateral . none)(income . 15k-35k))

Глава 15. Введение в LISP 763

((risk . high) (history . unknown) (debt . low) (collateral . none)

(income . 0-15k))

((risk . low) (history . unknown) (debt . low) (collateral . none)

(income . over-35k))

((risk . low) (history . unknown) (debt . low) (collateral . adequate)

(income . over-35k))

((risk . high) (history . bad) (debt . low) (collateral . none)

(income . 0-15k))

((risk . moderate) (history . bad) (debt . low)

(collateral . adequate) (income . over-35k))

((risk . low) (history . good) (debt . low) (collateral . none)

(income . over-35k))

((risk . low) (history . good) (debt . high) (collateral . adequate)

(income . over-35k))

((risk . high) (history . good) (debt . high) (collateral . none)

(income . 0-15k))

((risk . moderate) (history . good) (debt . high) (collateral . none)

(income . 15k-35k))

((risk . low) (history . good) (debt . high) (collateral . none)

(income . over-35k))

((risk . high) (history . bad) (debt . high) (collateral . none)

(income . 15k-35k))))

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

(setq test-instance

'((history . good) (debt . low) (collateral . none) (income . 15k-35k)))

Определим свойства для такого представления объектов.

(defun history (object)

(cdr (assoc 'history object :test #'equal))) (defun debt (object)

(cdr (assoc 'debt object :test #'equal))) (defun collateral (object)

(cdr (assoc 'collateral object :test #'equal))) (defun income (object)

(cdr (assoc 'income object :test #'equal))) (defun risk (object)

(cdr (assoc 'risk object :test tt'equal)))

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

(defstruct property name test values)

Элемент test экземпляра property связан с функцией, возвращающей значение свойства, name - это имя свойства. Оно включается исключительно для удобства пользователя. Элемент values - это список всех значений, которые могут возвращаться функцией test. Требование заблаговременного определения диапазона значений свойства значительно упрощает реализацию.

764 Часть VI. Языки и технологии программирования для искусственного интеллекта

Деревья решений можно определить с помощью следующей структуры.

(defstruct decision-tree

test-name

test

branches) (defstruct leaf

values)

Таким образом, дерево поиска является экземпляром структуры decision-tree или leaf. Структура leaf состоит из одного элемента value, определяющего класс объекта. Экземпляры типа decision-tree представляют внутренние узлы дерева. Их элементами являются test, test-name и множество ветвей branches. Функция test зависит от одного аргумента- объекта- и возвращает значение свойства. При классификации объекта с помощью f uncall вызывается функция test. Возвращаемое ею значение применяется для выбора ветви дерева. Имя этого свойства задает элемент test-name. Этот элемент облегчает пользователю контроль дерева решений. При выполнении программы он не играет никакой существенной роли. Элемент branches - это ассоциативный список поддеревьев. Ключами являются возможные значения, возвращаемые функцией test, а данными - сами поддеревья.

Например, дерево на рис. 9.13 соответствует следующему набору вложенных структур. Обозначение #S применяется при реализации ввода-вывода в Common LISP. Оно означает, что данное s-выражение представляет структуру.

#S(decision-tree

:test-name income

:test #

:branches

((0-15k . #S(leaf rvalue high)) (15k-35k .

#S(decision-tree

:test-name history

:test #

:branches

((good . #S(leaf rvalue moderate)) (bad . #S(leaf rvalue high)) (unknown .

#S(decision-tree

r test-name debt

•.test #

r branches

((high . #S(leaf rvalue high))

(low.#S(leaf rvalue moderate))))))))

(over-35k .

#S(decision-tree rtest-name history

rtest #

#x3514D6>

r branches

((good . #S(leaf rvalue low))

(bad . #S(leaf rvalue moderate)) (unknown . #S(leaf rvalue low)))))))

Глава 15. Введение в LISP 765

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

(defstruct example-frame instances properties classifier size inf ormat i on)

Здесь instances - это список объектов, для которых известно, к какому классу они принадлежат. Эти данные используются в качестве обучающего множества для построения дерева решения. Элемент properties - это список объектов типа property, включающий свойства, которые можно использовать при проходе узлов дерева. Элемент classifier- это тоже экземпляр типа property. Он представляет классификацию, которую должен изучить алгоритм ID3. Поскольку известно, к каким классам принадлежат обучающие примеры, эту информацию можно включить в качестве еще одного свойства. Элемент size задает количество примеров в списке instances, a information- это содержимое данного множества примеров. Значения size и information определяются из примеров. Поскольку их вычисление занимает определенное время, а эти данные используются многократно, имеет смысл сохранить их в отдельных элементах.

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

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

(defstruct partition test-name test

components info-gain)

Элемент test экземпляра структуры partition связан со свойством, используемым для создания разбиения, test-name- это имя теста, включенное для удобства пользователя. Элемент components связывается с подмножествами разбиения. В данной реализации components - это ассоциативный список. Ключами являются различные значения выбранного свойства, а данными- экземпляр структуры example-frame. Элемент gain-info отвечает за информацию, получаемую в результате применения теста для данного узла дерева. Подобно элементам size и information структуры example-frame этот элемент содержит вычисляемое значение, многократно используемое в алгоритме. Благодаря этим типам данных реализация алгоритма более точно отражает его структуру.

766 Часть VI. Языки и технологии программирования для искусственного интеллекта

15.13.2. Алгоритм ID3

Основу реализации алгоритма ID3 составляет рекурсивная функция построения дерева build-tree, параметром которой является структура example-frame.

(defun build-tree (training-frame) (cond

; Вариант 1: пустое множество примеров

((null (example-frame-instances training-frame)) (make-leaf rvalue "невозможно классифицировать: нет примеров")) ; Вариант 2: использованы все тесты

((null (example-frame-properties training-frame)) (make-leaf :value (list-classes training-frame))) ,- Вариант З: все примеры принадлежат одному классу

((zerop (example-frame-information training-frame)) (make-leaf :value (funcall

(property-test (example-frame-classifier training-frame))

(car (example-frame-instances training-frame))))) ; Вариант 4: выбор теста и рекурсивный вызов

(t (let ((part (choose-partition (gen-partitions training-frame)))) (make-decision-tree

:test-name (partition-test-name part)

:test (partition-test part)

:branches (mapcar #'(lambda (x)

(cons (car x) (build-tree (cdr x)))) (partition-components part)))))))

С помощью конструкции cond функция build-tree анализирует четыре возможных случая. В первом случае структура training-frame не содержит обучающих примеров. Такая ситуация может встретиться в том случае, если множество обучающих примеров алгоритма ЮЗ неполно - в нем отсутствуют экземпляры с указанным значением данного свойства. В этом случае создается лист, содержащий сообщение "невозможно классифицировать: нет примеров".

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

Третья ситуация представляет успешное завершение построения ветви дерева. Если содержимое элемента information структуры example-frame равно нулю, значит, все примеры принадлежат одному и тому же классу (согласно определению информации по Шеннону, приведенному в разделе 12.3). Алгоритм завершается и возвращается листовой узел, значение которого соответствует оставшемуся классу.

В первых трех случаях построение дерева завершается. В четвертом случае для построения поддеревьев текущего узла рекурсивно вызывается функция build-tree. Функция gen-partitions с учетом тестов элемента свойств генерирует список всех возможных разбиений множества примеров, а функция choose-partition выбирает

Глава 15. Введение в LISP 767

наиболее информативный тест. После связывания в блоке let полученного разбиения с переменной part строится узел дерева решений, которому соответствует использованный для разбиения тест, а элемент branches связывается с ассоциативным списком поддеревьев. Каждому ключу в списке branches соответствует значение теста, а данные представляют собой дерево решений, построенное в процессе рекурсивного вызова функции build-tree. Поскольку элемент components структуры part уже представляет собой ассоциативный список, ключами которого являются значения свойств, а данными- экземпляры example-frame, построение поддеревьев выполняется с помощью функции mapcar, позволяющей применить функцию build-tree к каждому объекту данных ассоциативного списка.

Функция gen-partitions зависит от одного аргумента training-frame - объекта типа example-frame- и возвращает все разбиения соответствующего подмножества примеров. Каждое разбиение создается с использованием некоторого свойства из списка properties. Функция gen-partitions вызывает функцию partition, аргументами которой являются экземпляр example-frame и выбранное свойство. Она разбивает все множество примеров на основе значений этого свойства. Заметим, что с помощью функции mapcar формируется разбиение для каждого элемента списка свойств экземпляра training-frame.

((defun gen-partitions (training-frame)

(mapcar #'(lambda (x) (partition training-frame x)) (example-frame-properties training-frame)))

Функция choose-partition просматривает список возможных разбиений и выбирает из них наиболее информативное.

(defun choose-partition (candidates) (cond ((null candidates) nil)

((= (list-length candidates) 1)(car candidates)) (t (let ((best (choose-partition (cdr candidates)))) (if (> (partition-info-gain (car candidates)) (partition-info-gain best)) (car candidates) best)))))

Самой сложной функцией при реализации алгоритма ГОЗ является функция partition. Она получает в качестве параметров экземпляр exapmle-frame и некоторое свойство property, а возвращает экземпляр структуры разбиения.

((defun partition (root-frame property)

(let ((parts (mapcar #'(lambda (x) (cons x (make-example-frame)))

(property-values property))))

(dolist (instance (example-frame-instances root-frame)) (push instance (example-frame-instances (cdr (assoc (funcall (property-test property) instance) parts))))) (mapcar #'(lambda (x)

(let ((frame (cdr x)))

(setf (example-frame-properties frame)

(remove property (example-frame-properties root-frame))) (setf (example-frame-classifier frame)

(example-frame-classifier root-frame))

768 Часть VI. Языки и технологии программирования для искусственного интеллекта

(setf (example-frame-size frame)

(list-length (example-frame-instances frame)))

(setf (example-frame-information frame) (compute-information (example-frame-instances frame) (example-frame-classifier root-frame))))) parts)

(make-partition

:test-name (property-name property)

:test (property-test property)

:components parts

:info-gain (compute-info-gain root-frame parts))))

В функции partition сначала в блоке let определяется локальная переменная parts. Она инициализируется ассоциативным списком, ключами которого являются все возможные значения свойства, используемого для теста, а данными - поддеревья разбиения. Это делается с помощью макроса dolist, который связывает с каждым элементом списка локальную переменную и оценивает ее. Пока элементами списка являются пустые экземпляры структуры example-frame, элементы, соответствующие каждой подзадаче, связываются со значением nil. С помощью формы dolist функция partition помещает каждый элемент root-frame в соответствующий элемент поддерева переменной parts. При этом используется макрос LISP push, модифицирующий список за счет добавления нового первого элемента. В отличие от cons функция push постоянно добавляет новые элементы в список.

Этот фрагмент кода отвечает за разбиение множества root-frame. По завершении работы функции dolist переменная parts представляет ассоциативный список, в котором каждый ключ является значением свойства, а каждый элемент данных - множеством примеров, для которых выбранное свойство принимает данное значение. С помощью функции mapcar пополняется информация о каждом подмножестве примеров переменной parts. При этом соответствующие значения присваиваются элементам properties, classifier, size и information. Затем строится экземпляр структуры partition, элемент components которой связывается с переменной parts.

Во второй ветви функции build-tree для создания листового узла при неоднозначной классификации используется функция list-classes. В ней для перечисления классов, которым соответствует список примеров, применяется цикл do. В этом цикле список classes инициализируется всеми значениями классификатора из training-frame. Если в списке training-frame содержится элемент, принадлежащий некоторому классу, то этот класс добавляется в список classes-present.

(defun list-classes (training-frame) (do

((classes (property-values (example-frame-classifier training-frame))

(cdr classes))

(classifier (property-test (example-frame-classifier training-frame))) classes-present) ;результаты накапливаются в локальной

переменной

((null classes) classes-present) ;выход из цикла

Глава 15. Введение в LISP 769

(if (member (car classes) (example-frame-instances training-frame)

:test #'(lambda (x y) (equal x (funcall classifier y)))) (push (car classes) classes-present))))

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

(defun compute-information (examples classifier) (let ((class-count

(mapcar #'(lambda (x) (cons x 0)) (property-values classifier))) (size 0))

; вычисление количества примеров для каждого класса (dolist (instance examples) (incf size)

(incf (cdr (assoc (funcall (property-test classifier) instance)

class-count))))

;вычисление информативности примеров (sum #'(lambda (x) (if (= (cdr x) 0) 0 (* -1

(/ (cdr x) size) (log (/ (cdr x) size) 2)))) class-count)))

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

(defun compute-info-gain (root parts) (- (example-frame-information root)

(sum #'(lambda (x) (* (example-frame-information (cdr x)) (/ (example-frame-size (cdr x) )

(example-frame-size root)))) parts)))

Функция sum вычисляет значения, получаемые в результате применения функции f ко всем элементам списка list-of -numbers.

(defun sum (f list-of-numbers)

(apply '+ (mapcar f list-of-numbers)))

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

770 Часть VI. Языки и технологии программирования для искусственного интеллекта

(defun classify (instance tree) (if (leaf-p tree)

(leaf-value tree) (classify instance

(cdr (assoc (funcall (decision-tree-test tree) instance) (decision-tree-branches tree))))))

Теперь вызовем функцию build-tree для примера из табл. 9.1. Свяжем символ tests со списком определений свойств для кредитной истории, долга, поручительства и дохода, а символ classifier - со значением риска для данного примера. С помощью этих определений примеры из таблицы можно связать с экземпляром example-frame.

(setq tests

(list (make-property

:name 'history

:test #'history

:values '(good bad unknown)) (make-property

:name 'debt

:test #'debt

rvalues '(high low)) (make-property

:name 'collateral

:test #'collateral

rvalues '(none adequate)) (make-property

:name 'income

:test #'income

rvalues '(0-to-15k 15k-to-35k over-35k))))

(setq classifier (make-property rname 'risk rtest #'risk rvalues '(high moderate low)))

(setq credit-examples (make-examp1e-frame

r instances examples

rproperties tests

rclassifier classifier

rsize (list-length examples)

rinformation (compute-information examples class)))

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

> (setq credit-tree (build-tree credit-examples)) #S(decision-tree

rtest-name income

rtest #

r branches

((0-to-15k . #S(leaf rvalue high)) (15k-to-35k .

#S(decision-tree

Глава 15. Введение в LISP 771

:test-name history

:test #

:branches

((good . #S(leaf :value moderate)) (bad . #S(leaf :value high)) (unknown .

#S(decision-tree

:test-name debt

:test #

:branches

(((high . #S(leaf :value high)) (low . #S(leaf rvalue moderate)))))))) (over-35k .

#S(decision-tree :test-name history

:test # :branches

((good . #S(leaf rvalue low))

(bad . #S(leaf rvalue moderate)) (unknown . #S(leaf rvalue low)))))))

>(classify '((history . good) (debt . low (collateral . none)

(income . 15k-to-35k)) credit-tree) moderate

15.14. Резюме и дополнительная литература

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

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

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

.

772 Часть VI. Языки и технологии программирования для искусственного интеллекта

При разработке алгоритмов для этой главы использована книга [Abelson и Sussman, 1985]. Хорошим руководством по изучению Common LISP является [Steele, 1990]. Кроме того, можно порекомендовать такие учебники по программированию на LISP, как [Touretzky, 1990], [Hasemer и Domingue, 1989], [Graham, 1993] и [Graham, 1995].

Многие книги посвящены применению языка LISP для разработки систем решения задач искусственного интеллекта. Так, [Forbus и deKleer, 1993] содержит описание реализации известных алгоритмов ИИ на LISP и является незаменимым пособием для специалистов по практической реализации методов искусственного интеллекта. Кроме того, существует множество книг, посвященных общим проблемам искусственного интеллекта и их решению на основе LISP. К ним относятся [Noyes, 1992] и [Tanimoto, 1990].

15.15. Упражнения

1. Метод Ньютона нахождения квадратного корня из числа предполагает вычисление

значения корня и проверку его точности. Если найденное решение не обладает тре

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

этой процедуры имеет следующий вид.

function root-by-newtons-method (x, tolerance) guess := 1; repeat

guess := 1/2(guess + x/guess) until absolute-value(x - guess * guess) < tolerance

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

2. а. Напишите на LISP рекурсивную функцию обращения элементов списка (не ис

пользуя встроенную функцию reverse). Оцените сложность реализации. Можно ли

реализовать обращение списка за линейное время?

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

> (mirror ' ((a b) (с (d е) ) ) )

(((е d) с) (Ь а))

Напишите на LISP генератор случайных чисел. Эта функция должна поддерживать гло

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

Описание алгоритма генерации случайных чисел найдите в специальной литературе.

Напишите функции initialize, push, top, pop и list-stack, поддерживаю

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

(initialize)

nil

(push 'foo)

foo

(push 'bar)

bar

(top)

bar

(list-stack)

Глава 15. Введение в LISP 773

(bar foo)

(pop)

bar

(list-stack)

(foo)

Множества можно представить с помощью списков, не содержащих повторяющихся

элементов. Напишите на LISP свою реализацию операций объединения, пересечения

и вычитания множеств union, intersection и difference. (He пользуйтесь

встроенными в Common LISP версиями этих функций.)

Задача башен Ханоя основана на следующей легенде.

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

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

Ни один диск не может располагаться поверх диска меньшего размера.

Согласно легенде, когда эта задача будет решена, наступит конец света.

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

7. Напишите компилятор для оценки арифметических выражений вида

(оператор операнд! операнд2),

где оператор - это +, -, * или /, а операндами являются числа или вложенные выражения. Примером допустимого выражения является (*(+ 3 6) (- 7 9)). Допустим, что целевая машина поддерживает инструкции:

(move value register) (add register-1 register-2) (subtract register-1 register-2) (times register-1 register-2) (divide register-1 register-2) ЛЛ|

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

8. Реализуйте алгоритм поиска в глубину с возвратами (аналогичный использованному в

разделе 15.2 при решении задачи переправы человека, волка, козы и капусты) для реше

ния задачи миссионера и каннибала. Задача формулируется следующим образом.

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

9. Реализуйте алгоритм поиска в глубину для решения задачи о кувшинах с водой.

774 Часть VI. Языки и технологии программирования для искусственного интеллекта

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

Реализуйте функции build-solution и eliminate-duplicates для алгорит

ма поиска в ширину из раздела 15.3.

Используйте разработанный в упражнении 10 алгоритм поиска в ширину для реше

ния следующих задач.

Задача переправы человека, волка, козы и капусты (см. раздел 15.2).

Задача миссионера и каннибала (см. упражнение 8).

Задача о двух кувшинах (см. упражнение 9).

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

Завершите реализацию "жадного" алгоритма поиска из подраздела 15.3.3. Исполь

зуйте его с учетом соответствующих эвристик для решения каждой из трех задач,

перечисленных в упражнении 11.

Напишите на LISP программу решения задачи о 8 ферзях. (Задача состоит в нахож

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

друг друга за 1 ход. Следовательно, никакие два ферзя не должны располагаться в

одном ряду, столбце или на одной диагонали.)

Напишите на LISP программу решения полной версии задачи о ходе конем для

доски 8x8.

Реализации алгоритмов поиска в ширину, в глубину и "жадного" алгоритма с ис

пользованием списков open и closed очень близки друг другу. Они различаются

только реализацией списка open. Напишите общую функцию поиска, реализующую

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

качестве параметра.

Перепишите функцию print-solution из реализации интерпретатора для реше

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

вое решение и ожидала запроса пользователя (например, символ возврата каретки)

для вывода второго решения.

Модифицируйте интерпретатор для решения задач логического программирования

таким образом, чтобы он поддерживал операторы or и not. Дизъюнктивное выра

жение должно принимать значение "истина", если такое значение принимает хотя бы

один из дизъюнктов. При обработке дизъюнктивных выражений интерпретатор дол

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

реализовать несколько сложнее, поскольку отрицание цели истинно только в том

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

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

ложения о замкнутости мира, описанного в разделе 12.3.

Реализуйте общие функции отображения и фильтрации map-stream и filter-

stream, описанные в разделе 15.8.

Перепишите программу решения задачи поиска первых л нечетных чисел Фибонач

чи с использованием общего фильтра потока filter-stream вместо функции

Глава 15. Введение в LISP 775

filter-odds. Модифицируйте ее таким образом, чтобы программа возвращала первые п четных чисел Фибоначчи, а затем снова измените программу для вычисления квадратов первых л чисел Фибоначчи.

Дополните интерпретатор для решения задач логического программирования операто

рами LISP write. Это позволит выводить сообщения непосредственно пользователю.

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

целевое утверждение оператором write. При положительном ответе оцените функ

цию write и верните поток, содержащий исходное множество подстановок.

Дополните язык логического программирования, включив в него арифметические опе

раторы сравнения =, < и >. Совет: как и в упражнении 20, сначала модифицируйте

функцию solve для выявления этих операторов до вызова функции infer. Если вы

ражение содержит оператор сравнения, замените все переменные их значениями и оце

ните это выражение. Если результатом оценивания будет nil, функция solve должна

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

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

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

как функцию (подобно оператору is в PROLOG), присваивающую значение несвязан

ной переменной и выполняющую проверку равенства, если все элементы связаны.

Используйте разработанные в упражнении 21 арифметические операторы в интер

претаторе для решения задач логического программирования для решения задачи

консультанта по финансовым вопросам из главы 2.

Выберите задачу (например, диагностики автомобилей или классификации видов

животных) и решите ее с помощью оболочки lisp-shell.

Модифицируйте оболочку экспертной системы из раздела 15.10 таким образом, что

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

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

Для этого нужно изменить функцию ask-for и связанные с ней функции и позво

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

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

Дополните оболочку lisp-shell оператором not. В качестве примера обработки от

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

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

Напишите ATN-анализатор (раздел 11.3) для некоторого подмножества английского

языка.

Добавьте в модель из раздела 15.12 систему охлаждения, понижающую температуру

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

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

от ее объема и изолированности.

Создайте в системе CLOS модель для другой предметной области, например для эко

системы.

Примените алгоритм ГОЗ для решения другой задачи, выбранной по своему усмотрению.