Методы искусственного интеллекта

Осипов Г.С.

Методы

искусственного

интеллекта

МОСКВА

ФИЗМАТЛИТ ®

УДК 519,816
ББК 32,813
О 74

Издание осуществлено при поддержке
Российского фонда фундаментальных
исследований по проекту 10-07-07014

О с и п о в Г. С. Методы искусственного интеллекта.— М.: ФИЗМАТЛИТ,
2011. — 296 с. — ISBN 978-5-9221-1323-6.

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

ISBN 978-5-9221-1323-6

c⃝ ФИЗМАТЛИТ, 2011

c⃝ Г. С. Осипов, 2011

ОГЛАВЛЕНИЕ

Предисловие автора . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. .. .. .
7

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
9

Г л а в а 1.
Методы представления знаний . . . . . . . . . . . . . . . .. .. .. .
23
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
23
1.1. Формальные языки и формальные системы . . . . . . . .. . . . . .. .. .. .
23
1.1.1. Язык
исчисления
предикатов
первого
порядка
(23).
1.1.2. Элементы исчисления
предикатов первого порядка (25).
1.1.3. Формальные системы (27).
1.1.4. Алгебраические системы (28).
1.1.5. Интерпретация (28).
1.1.6. Выполнимость и
истинность (29).
1.2. Системы, основанные на правилах, или продукционные системы . .
31
1.2.1. Правила для представления знаний (32). 1.2.2. Рабочая память (32).
1.2.3. Стратегии управления (33).
1.2.4. Разрешение
конфликтного множества правил (35). 1.2.5. Пример (39).
1.3. Cемантические сети для представления знаний . . . . . . . . . . .. .. .. .
43
1.3.1. Простые
и
расширенные
семантические
сети
(43).
1.3.2. Универсум Эрбрана и семантические сети (45). 1.3.3. Неоднородные семантические сети (48).
1.4. Совместность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
54
1.4.1. Вектор совместности событий (55). 1.4.2. Матрицы совместности элементов (55).
1.5. Представление знаний в системах фреймов . . . . . . .. . . . . . .. .. .. .
57
1.5.1. Фреймы (57). 1.5.2. Системы фреймов (58). 1.5.3. Основная
вычислительная задача в системе фреймов (59).
1.6. Элементы дескриптивной логики . . . . . . . . . . .. . . . . . . . . .. .. .. .
59
1.6.1. Основные понятия (61).
1.6.2. База знаний в дескриптивной логике (61).
1.6.3. Рассуждения в дескриптивной логике (62).
1.6.4. Семейство языков дескриптивных логик (65).
1.6.5. Отображение дескриптивной логики в логику первого порядка (66). 1.6.6. Дескриптивная логика с конкретным доменом (67).
1.6.7. Правила вывода (69).

Оглавление

Г л а в а 2.
Методы автоматизации рассуждений. . . . . . . . . . . .. .. .. .
72
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
72
2.1. Автоматизация дедуктивных рассуждений. Поиск доказательств
теорем методом резолюций . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
75
2.1.1. Скулемовская стандартная форма (76). 2.1.2. Метод резолюций для исчисления высказываний (80).
2.1.3. Метод резолюций
для исчисления предикатов первого порядка (82).
Примеры . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. .. .. .
84
2.2. Индуктивные рассуждения . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
86
2.2.1. Понятие квазиаксиоматической теории (86).
2.2.2. Немонотонные рассуждения (87).
2.2.3. ДСМ — метод индуктивного
вывода (89).
2.3. Аргументационные рассуждения. . . . . . . . . . .. . . . . . . . . . .. .. .. .
93
2.4. Рассуждения на основе прецедентов . . . . . . . . . . . . . . . . . .. .. .. .
97
2.4.1. Метрики на множестве прецедентов (97).
2.4.2. Согласование прецедентов (102).
2.4.3. Предпочтения и глобальная релевантность (103). 2.4.4. Адаптация прецедентов (104).

Г л а в а 3.
Методы интеллектуального планирования . . . . . . . .. .. .. .
107
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
107
3.1. Хронология методов интеллектуального планирования . . . . . .. .. .. .
109
3.2. Планирование как поиск доказательства теорем . . . . . . . . . .. .. .. .
110
3.3. Планирование в пространстве состояний . . . . . . . . . . . . . . .. .. .. .
111
3.3.1. Постановка задачи STRIPS-планирования (111).
3.3.2. Алгоритм STRIPS (113).
3.3.3. Неполнота алгоритма STRIPS (113).
3.3.4. Вычислительная
сложность
задачи
STRIPS-планирования
(116).
3.3.5. Языковые
средства
описания
доменов
планирования (118).
3.4. Поиск в пространстве планов. . . . . . . . . . . . . . . . . . . . . . .. .. .. .
118
3.4.1. Основная
идея
(118).
3.4.2. Алгоритм
SNLP
(121).
3.4.3. Принцип малой связности (122).
3.5. Планирование как задача удовлетворения ограничений . . . . .. .. .. .
122
3.5.1. Постановка
задачи
удовлетворения
ограничений
(122).
3.5.2. Синтез планов на основе техники прямого распространения
ограничений (123). 3.5.3. Алгоритм GraphPlan (127).
3.6. Планирование на основе прецедентов . . . . . . . . .. . . . . . . . .. .. .. .
130
3.6.1. Общая
схема
метода
планирования
на
основе
прецедентов
(130).
3.6.2. Методы
адаптации
прецедентов
(131).
3.6.3. Некоторые системы планирования, основанного на прецедентах (133).

Г л а в а 4.
Интеллектуальные динамические системы. . . . . . . .. .. .. .
150
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
150
4.1. Уточнение постановки задачи. Правила . . . . . . . .. . . . . . . . .. .. .. .
152
4.2. Стратегии применения правил. Состояния и траектория системы . .
153
4.3. Управляемые динамические системы, основанные на правилах . .. .
155

Оглавление
5

4.3.1. Возмущения (156). 4.3.2. Управление как способ компенсации возмущений (156).
4.4. Особенности баз знаний динамических систем, основанных на правилах. . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. .. .. .
157
4.4.1. Синтез обратной связи по траектории (158). 4.4.2. Стратегия
синтеза обратной связи по состояниям (161).
4.5. Элементы теории управляемости интеллектуальных динамических
систем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
163
4.6. Примеры интеллектуальных динамических систем. . . .. . . . . .. .. .. .
165
4.6.1. Описание
агентов
(165).
4.6.2. Функции
и
формулы
(169).
4.6.3. Замыкание
состояний.
Аксиомы
(172).
4.6.4. Крестообразный перекресток равнозначных однополосных
дорог (174).
4.6.5. Движение по попутной проезжей части (177).
4.6.6. Стратегия применения правил (179). 4.6.7. Модели корабля,
станции
и
управления.
Общее
описание (181).
4.6.8. Параметры
модели
орбитальной
станции (183).
4.6.9. Параметры
процесса
стыковки (184).
4.6.10. Правила
замыкания (184).
4.6.11. Правила переходов (185).
4.6.12. Управление. Подцели
и зоны управления (186).
4.6.13. Правила выбора цели (186).
4.6.14. Правила управления (187).
4.6.15. Результаты модельного
эксперимента (189).

Г л а в а 5.
Приобретение знаний и машинное обучение . . . . . .. .. .. .
192
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
192
5.1. Источники знаний для интеллектуальных систем . . . . . . . . .. .. .. .
193
5.2. Прямые методы приобретения знаний . . . . . . . . . . . . . . . . .. .. .. .
194
5.2.1. Имена (194).
5.2.2. Признаки (195).
5.2.3. Виды семантических связей (196).
5.2.4. Типы семантических связей (200).
5.2.5. Метод интервью (204).
5.3. Приобретение знаний из примеров . . . . . . . . . . . . . . . . . . .. .. .. .
214
5.3.1. Задачи машинного обучения (214).
5.3.2. Поиск (218).
5.3.3. Индуктивный
алгоритм
построения
деревьев
решений
(TDIDT)
(223).
5.3.4. Последовательное
покрытие:
AQ-обучение (228).
5.3.5. Оценка обучающих алгоритмов (232).
5.3.6. Машинное обучение в языке исчисления предикатов первого
порядка (234).
5.4. Искусственные нейронные сети и их обучение . . . . . .. . . . . .. .. .. .
244
5.4.1. Область применения искусственных нейронных сетей (244).
5.4.2. Достоинства и недостатки искусственных нейронных сетей (246).
5.4.3. Персептрон (247).
5.4.4. Процедура обратного распространения (247).
5.4.5. Сети встречного распространения (249). 5.4.6. Сети с обратными связями (251).

Г л а в а 6.
Приобретение знаний и анализ текстов . . . . . . . . . .. .. .. .
255
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
255
6.1. Коммуникативная грамматика русского языка. . . . . . . . . . . .. .. .. .
266
6.1.1. Минимальные синтаксические единицы — синтаксемы (266).
6.1.2. Категориальная семантика лексических единиц (267).

Оглавление

6.2. Реляционно-ситуационный анализ текста . . . . . . .. . . . . . . . .. .. .. .
272
6.2.1.
Морфологический
и
синтаксический
анализ
(272).
6.2.2. Установление значений синтаксем (274).
6.3. Установление значений синтаксем в безглагольных предложениях
279
6.3.1. Выбор объектов, признаков и свойств (279).
6.3.2. Обнаружение правил установления значений синтаксем (283).
6.4. Установление отношений на множестве синтаксем. . . .. . . . . .. .. .. .
284

С п и с о к л и т е р а т у р ы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
288

Предисловие автора

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

Предисловие автора

и семантические сети; особенное внимание уделено неоднородным семантическим сетям. Представление знаний в виде систем правил использовалось и при описании методов планирования и моделирования
поведения.
Проблематике моделирования рассуждений было уделено не очень
много внимания, так как на русском языке ей посвящена обширная
литература. Напротив, большое внимание в книге уделено методам
планирования целенаправленного поведения, так как в монографической литературе на русском языке эти вопросы освещены, повидимому,
впервые. Существенное внимание уделено интеллектуальным динамическим системам и основанным на них методам моделирования целенаправленного поведения. В последних двух главах описаны методы
автоматизации приобретения знаний, при этом, по крайней мере в пятой главе, активно применяется аппарат неоднородных семантических
сетей.
Здесь надо сказать, что в основе части книги лежат изданные
в 2009 г. мои «Лекции по искусственному интеллекту», правда существенно переработаные и расширенные. Разумеется, книга содержит
и материал, никаким образом в «Лекциях» не представленный.
Замечу, что книга совершенно не касается архитектур интеллектуальных систем, их инструментальных средств и прикладных интеллектуальных систем. Даже в тех случаях, когда нельзя было обойтись
без кратких сведений о тех или иных системах, речь шла, главным
образом, об используемых в них идеях и методах. Архитектуры интеллектуальных систем и их инструментальных средств — обширная
и важная область деятельности и она заслуживает отдельной книги,
которую следовало бы тогда назвать, например «Интеллектуальные
системы» или «Системы искусственного интеллекта».
В заключение хотелось бы выразить признательность Вадиму Николаевичу Вагину, который не только прочел рукопись и указал ряд
недостатков, но и дал ценные советы по включению дополнительного
материала, что, надеюсь, способствовало улучшению книги.
Книга предназначена как специалистам, так и аспирантам и студентам старших курсов университетов.
Автор

Введение

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

Введение

представления и модели доставляют психологические исследования,
в частности, исследования в области когнитивных наук.
Первые исследования, относящиеся к искусственному интеллекту,
были предприняты почти сразу же после появления первых вычислительных машин.
В 1954 г. американский исследователь А. Ньюэлл (A. Newel) решил
написать программу для игры в шахматы. Этой идеей он поделился с аналитиками корпорации «РЭНД» (RAND Corporation (J. Show)
и Г. Саймоном (H. Simon), которые предложили Ньюэллу свою помощь. В качестве теоретической основы такой программы было решено использовать метод, предложенный в 1950 г. Клодом Шенноном
(К. Shannon), основателем теории информации. Точная формализация
этого метода была выполнена Аланом Тьюрингом (Alan Turing). Он же
промоделировал его вручную.
К работе была привлечена группа голландских психологов под
руководством А. Де Гроота (A. de Groot), изучавших стили игры выдающихся шахматистов. Через два года совместной работы этот коллектив создал язык программирования ИПЛ1 — по-видимому первый
символьный язык обработки списков. Вскоре была написана и первая
программа, которую можно отнести к достижениям в области искусственного интеллекта. Эта была программа «Логик-Теоретик» (1956 г.),
предназначенная для автоматического поиска доказательств теорем
в исчислении высказываний.
Собственно же программа для игры в шахматы, NSS, была завершена в 1957 г. В основе ее работы лежали так называемые эвристики
(правила выбора в отсутствии теоретических оснований) и описания
целей. Управляющий алгоритм пытался уменьшить различия между
оценками текущей ситуации и оценками цели или одной из подцелей.
В 1960 г. та же группа на основе принципов, использованных в NSS,
написала программу, которую ее создатели назвали GPS (General
Problem Solver) — универсальный решатель задач. GPS могла справляться с рядом головоломок, вычислять неопределенные интегралы,
решать некоторые другие задачи. Эти результаты привлекли внимание
специалистов в области вычислений. Появились программы автоматического поиска доказательств теорем из планиметрии и решения
алгебраических задач.
Джона Маккарти (J. McCarty) из Стэнфорда заинтересовали математические основы этих результатов и вообще символьных вычислений. В результате в 1963 г. он разработал язык ЛИСП (LISP, от List
Processing), основу которого составило использование единого спискового представления для программ и данных, применение выражений
для определения функций, скобочный синтаксис.