Файл: Методыискусственногоинтеллекта.pdf

Осипов Г.С.
Методы
искусственного
интеллекта
МОСКВА
ФИЗМАТЛИТ ®

УДК 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).

4
Оглавление
Г л а в а 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
Оглавление
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

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

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

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