Достоверный и правдоподобный вывод в интеллектуальных системах

Вагин В.Н.

Головина Е.Ю.

Загорянская А.А.

Фомина М.В.

Достоверный и

правдоподобный

вывод в

интеллектуальных

систем ах

МОСКВА

ФИЗМАТЛИТ ®

УДК 519.816
ББК 32.81
Д 70

А в т о р с к и й к о л л е к т и в :
В а г и н В. Н., Го л о в и н а Е. Ю., З а г о р я н с к а я А. А., Ф о м и н а М. В.

Достоверный и правдоподобный вывод в интеллектуальных системах / Под ред. В.Н. Вагина, Д.А. Поспелова. — 2-е изд., испр. и доп. —
М.: ФИЗМАТЛИТ, 2008. — 712 с. — ISBN 978-5-9221-0962-8.

Рассматриваются методы достоверного (дедуктивного) и правдоподобного
(абдуктивного, индуктивного) выводов в интеллектуальных системах различного назначения. Приводятся методы дедуктивного вывода на графовых структурах. Описываются как классические, так и немонотонные модальные логики:
логики убеждения и знания, немонотонные логики Мак-Дермотта и Дойла,
автоэпистемические логики Мура, логики умолчания Рейтера. Приводятся
основы теории аргументации и методы абдуктивного вывода. Рассматриваются
базовые принципы построения систем обучения и принятия решений и даются
задачи обучения «без учителя» и «с учителем». Излагаются индуктивные
методы для случая с неполной информацией и методы теории приближенных
множеств. Во 2-е издание добавлены главы об исчислении высказываний и об
исчислении предикатов первого порядка, а также о работе с реальными «зашумленными» базами данных в задаче индуктивного формирования понятий.
Допущено Министерством образования Российской Федерации в качестве учебного пособия для студентов вузов, обучающихся по направлениям
«Прикладная математика и информатика», «Информатика и вычислительная
техника» и специальностям «Прикладная информатика» (по направлениям)
и «Прикладная математика и информатика».

Рецензенты: Э. В. Попов, д.т.н., профессор, зам. директора по науке РосНИИ ИТ и АП, Г. С. Плесневич, к.ф.-м.н., профессор МАТИ — Российского
государственного технологического университета им. К. Э. Циолковского.

ISBN 978-5-9221-0962-8

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

c⃝ Коллектив авторов, 2008

ОГЛАВЛЕНИЕ

Предисловие ко второму изданию . .. . . . . . . . . . . . . . . . . . . . . . . . . .
10
Предисловие . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . .
13

I.
ДОСТОВЕРНЫЙ ВЫВОД

Г л а в а 1.
Формальные системы. . . . . . . . . . . . . . . . . . . . . . . . . .
24
1.1. Понятие формальной системы . .. . . . . . . . . . . . . . . . . . . . . . . .
24
1.2. Исчисление высказываний как формальная система. .. . . . . . . . . .
28
1.3. Исчисление предикатов первого порядка как формальная система
31
1.4. Проблема разрешимости . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .
37

Г л а в а 2.
Автоматическое доказательство теорем . . . . . . . . . .. . . .
42
2.1. Нормальные и стандартные формы . .. . . . . . . . . . . . . . . . . . . . .
43
2.2. Логические следствия. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
2.3. Процедура вывода Эрбрана . .. . . . . . . . . . . . . . . . . . . . . . . . . .
55
2.4. Принцип резолюции . .. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
58
2.5. Линейная резолюция . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
2.6. Вывод в языке Пролог . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
2.6.1. SLD-резолюция (70).
2.6.2. Стратегии
поиска в языке
Пролог (74).
2.6.3. Предположение о замкнутости мира (77).
2.6.4. Синтаксис и семантика языка Пролог (78).
2.6.5. Реализация на языке Пролог моделей представления знаний и механизмов
вывода на них (84).

Г л а в а 3.
Вывод на графе связей. . . . . . . . . . . . . . . . . . . . . . . . .
96
3.1. Последовательная процедура доказательства методом графа связей
97
3.2. Стратегии поиска в графе связей . .. .. . . . . . . . . . . . . . . . . . . . .
100
3.3. Достоинства процедуры дедуктивного вывода на графе связей. .. . .
102
3.4. Параллельный вывод на графе связей . .. . . . . . . . . . . . . . . . . . .
103
3.4.1. Метод OR-параллельной резолюции (104).
3.4.2. DCDPпараллельный вывод (105).
3.4.3. AND-параллельная резолюция (108).
3.5. Модификация процедур параллельного вывода . .. . . . . . . . . . . . .
111

Оглавление

3.5.1.
Принципы
создания
эвристической
функции
(111).
3.5.2. Эвристическая функция H1 (112).
3.5.3. Применение эвристической функции H1 при решении задачи «Стимроллер» (115).
3.6. Сравнение эффективности . .. . . . . . . . . . . . . . . . . . . . . . . . . . .
118
3.7. Система параллельного вывода PIS (Parallel Inference System) на
графе связей . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
121
3.7.1. Автоматический выбор параллельных методов вывода (122).
3.7.2. Математический препроцессор (122).
3.7.3. Методы ускорения и анализ результатов для задачи о N ферзях (125). 3.7.4. Полученные результаты (128).

Г л а в а 4.
Вывод на графе дизъюнктов. . . . . . . . . . . . . . . . . . . . .
129
4.1. Типы параллелизма в дедуктивном выводе . .. . . . . . . .. . . . . . . . .
129
4.2. Последовательный алгоритм вывода на раскрашенных графах дизъюнктов. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
132
4.3. Параллелизм в дедуктивном выводе на C-графах. .. . . . . . . . . . . .
137
4.4. Сравнение эффективности процедур дедуктивного вывода . .. . . . .
146

Г л а в а 5.
Вывод на аналитических таблицах . . . . . . . . . . . . . . . .
149
5.1. Метод аналитических таблиц для логики высказываний. .. . . . . . .
149
5.2. Метод аналитических таблиц для логики предикатов первого порядка. .. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
156
5.3. Метод аналитических таблиц в логическом программировании . .. .
165
5.3.1. Реализация метода аналитических таблиц для логики высказываний на языке Пролог (165).
5.3.2. Реализация метода аналитических таблиц для логики предикатов 1-го порядка (171).

Г л а в а 6.
Вывод на иерархических структурах . . . . . . . . . . . . . . .
195
6.1. Многоуровневая упорядоченно-сортная алгебра. .. . . . . . . . . . . . .
195
6.1.1. Необходимость разработки механизмов вывода на иерархических структурах (195).
6.1.2. Введение в многоуровневую алгебру (197).
6.1.3. Моделирование подтипов и наследования (198).
6.1.4. Описание параметрического полиморфизма аппаратом двухуровневой алгебры (199).
6.2. Многоуровневая логика как язык представления знаний в интеллектуальных системах . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
202
6.2.1. Способы задания иерархических структур в многоуровневой логике (202).
6.2.2. Синтаксис многоуровневой логики (206).
6.2.3. Описание двух видов иерархической абстракции и иерархической структуры множеством правильно построенных формул
многоуровневой логики (207).
6.2.4. Логический вывод в многоуровневой логике (211).
6.3. Система моделирования проблемной области «Инфолог». .. . . . . . .
223
6.3.1. Назначение
и
структура
системы
«Инфолог»
(223).
6.3.2. Концептуальный язык описания сложноструктурированной
проблемной области (226).
6.3.3. Реализация системы «Инфолог» (229).

Оглавление
5

II.
АРГУМЕНТАЦИЯ И АБДУКЦИЯ

Г л а в а 7.
Данные и знания в интеллектуальных системах . . . . . . .
231
7.1. Характерные особенности знания . .. . . . . . . . . . . . . . . . . . . . . .
231
7.2. Знание как обоснованное истинное убеждение . .. . . . . . . . . . . . .
240
7.3. Не-факторы знания . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
247
7.4. Зачем нужны нетрадиционные логики? . .. . . . . . . . . . . . . . . . . .
254

Г л а в а 8.
Монотонные классические модальные логики . . . . . . . .
260
8.1. Исчисление предикатов первого порядка как основа построения
модальной логики . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
260
8.2. Вспомогательная логика как основа перехода к модальному исчислению высказываний . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
262
8.3. Постулаты, основные теоремы и правила модального исчисления
высказываний . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
264
8.4. Система S1 . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
266
8.5. Система S4 . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
276
8.6. Система S5 . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . .
280
8.7. Семантика возможных миров Крипке . .. . . . . . . . . . . . . . . . . . .
280

Г л а в а 9.
Немонотонные модальные логики . . . . . . . . . . . . . . . . .
286
9.1. Логики убеждения и знания . .. . . . . . . . . . . . . . . . . . . . . . . . .
286
9.2. Немонотонные логики Мак-Дермотта и Дойла . .. . . . . . . . . . . . .
291
9.3. Автоэпистемические логики. .. . . . . . . . . . . . . . . . .. . . . . . . . . .
297
9.4. Логики умолчаний . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
305
9.5. Системы поддержки истинности . .. . . . . . . . . . . . . . . . . . . . . . .
316
9.5.1. Системы поддержки истинности, основанные на обоснованиях (318). 9.5.2. Системы поддержки истинности, основанные на
предположениях (320).

Г л а в а 10.
Немонотонные логики в логическом программировании
324
10.1. Семантика логических программ: краткий обзор . .. . . . . . . . . . . .
326
10.1.1. Нормальные логические программы (326).
10.1.2. Расширенные логические программы (333).
10.1.3. Зачем нужна новая
семантика для расширенных программ? (339).
10.2. WFSX — фундированная семантика для расширенных логических
программ . .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .
340
10.2.1. Интерпретации
и
модели
(340).
10.2.2. Определение
WFSX
(342).
10.2.3. Существование
семантики
(346).
10.2.4. Нисходящие процедуры вывода для WFSX (347).
10.3. Работа с противоречиями . .. . . . . . . . . . . . . . . . . . . . . . . . . . .
357
10.3.1. Удаление
противоречий (360).
10.3.2. Паранепротиворечивая
WFSX (361).
10.3.3. Декларативные
ревизии (364).
10.3.4. Поддержка и устранение противоречий (371).

Оглавление

10.4. WFSX, семантика логических программ с двумя отрицаниями и
автоэпистемическая логика . .. . . . . . . . . . . . . . . . . . . . . . . . . .
376
10.4.1. Общая семантика для программ с отрицаниями двух видов (376). 10.4.2. Автоэпистемические логики для WFSX (389).
10.5. WFSX и логика умолчаний . .. . . . . . . . . . . . . . . . . . . . . . . . . .
400
10.5.1. Язык умолчаний (401).
10.5.2. Некоторые необходимые
принципы для теорий умолчаний (404).
10.5.3. Ω-теория умолчаний (407).
10.5.4. Сравнение с семантикой Рейтера (411).
10.5.5. Сравнение со стационарной семантикой умолчаний (412).
10.5.6. Связь семантики теории умолчаний и логических программ
с явным отрицанием (413).
10.5.7. Определение WFSX с помощью Γ (414).

Г л а в а 11.
Системы аргументации и абдуктивный вывод. . . . . . . .
417
11.1. Системы пересматриваемой аргументации . .. . . . . . . . . . . . . . . .
418
11.1.1. Основы теории аргументации (418).
11.1.2. Обзор систем
аргументации (433).
11.2. Организация абдуктивного вывода . .. . . . . . . . . .. . . . . . . . . . . .
440
11.2.1. Понятие абдуктивного вывода (440).
11.2.2. Подходы к
характеризации абдукции (443).
11.2.3. Подходы к вычислению
абдуктивных объяснений (451).
11.2.4. Метод вероятностных абдуктивных рассуждений в сложноструктурированных проблемных
областях (460).
11.3. Абдукция и аргументация в логическом программировании. .. . . . .
475
11.3.1. Аргументационная семантика логических программ и ее вычисление (475).
11.3.2. Роль аргументации в организации абдуктивного вывода (488).

III.
ИНДУКЦИЯ И ОБОБЩЕНИЕ

Г л а в а 12.
Базовые принципы построения систем обучения и принятия решений. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
495
12.1. Системы поддержки принятия решений . .. . . . . . . . . . . . . . . . . .
497
12.2. Задачи извлечения знаний из баз данных . .. . . . . . . . . . . . . . . .
502
12.3. Способы представления исходной информации в интеллектуальных
системах . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
509
12.4. Структурно-логические методы обобщения. .. . . . . . . . . . . . . . . .
514

Г л а в а 13.
Задача обучения «без учителя» . . . . . . . . . . . . . . . . . .
524
13.1. Алгоритм, основанный на понятии порогового расстояния . .. . . . .
525
13.2. Алгоритм MAXMIN. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
527
13.3. Алгоритм «K средних» . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . .
531
13.4. Распознавание с использованием решающих функций . .. . . . . . . .
534
13.4.1. Построение решающих функций по критерию минимального
расстояния (535). 13.4.2. Разделяющие решающие функции (536).

Оглавление
7

13.4.3. Линейные решающие функции (538).
13.4.4. Построение
решающих функций методом потенциалов (540).
13.5. Распознавание на основе приближенных признаков . .. . . . . . . . . .
545

Г л а в а 14.
Обучение с учителем . . . . . . . . . . . . . . . . . . . . . . . . .
547
14.1. Постановка задачи . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
547
14.2. Алгоритм ДРЕВ . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . .
552
14.3. Построение решающего дерева с использованием метрики Хемминга. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
554
14.4. Индукция решающих деревьев . .. . . . . . . . . . . . . . . . . . . . . . . .
557
14.5. Модификация алгоритма Куинлана — ID5R . .. . . . . . . . . . . . . . .
562
14.6. Алгоритм Reduce . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .
567
14.7. Фокусирование . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
570
14.8. Алгоритм EG2. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
575

Г л а в а 15.
Индуктивные методы для случая неполной информации
582
15.1. Проблемы извлечения знаний из баз данных . .. . . . . . . . . . . . . .
582
15.1.1. Ограниченная
информация (583).
15.1.2. Искаженная
информация (583).
15.1.3. Большой размер баз данных (584).
15.1.4. Изменение баз данных со временем (585).
15.2. Алгоритм извлечения продукционных правил из большой базы данных . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
586
15.3. Подход с использованием приближенных множеств . .. . . . . . . . . .
589
15.3.1. Основные понятия теории приближенных множеств (589).
15.3.2. Алгоритм
RS1,
использующий
приближенные
множества (593).
15.3.3. Информационные системы с неопределенностью (597).
15.4. Алгоритм распознавания объектов в условиях неполноты информации . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .
606

Г л а в а 16.
Индуктивное формирование понятий в «зашумленных»
базах данных
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
617
16.1. Общая классификация недостаточной информации . .. . . . . . . . . .
618
16.2. Моделирование неточной и неполной информации в задаче индуктивного формирования понятий . .. . . . . . . . . . . . . . . . . . . . . . .
620
16.2.1. Внесение шума в поле атрибута, содержащего дискретные значения (621).
16.2.2. Внесение шума в поле атрибута, содержащего непрерывные значения (622).
16.2.3. Моделирование
шума в обучающей выборке (622).
16.3. Методы построения деревьев решений при наличии шума в обучающей выборке
. .. . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
628
16.3.1. Постановка задачи индуктивного построения понятий при
наличии шума (628). 16.3.2. Алгоритм предсказания неизвестных
значений по методу «ближайших соседей» (630).
16.3.3. Использование алгоритма ВОССТАНОВЛЕНИЕ при построении дерева
решений (635).

Оглавление

16.4. Программная реализация алгоритма IDTUV. .. . . . . . . . . . . . . . .
637
16.5. Эксперименты на тестовых наборах данных . .. . . . . . . . . . . . . . .
639
16.5.1. Эксперименты
на
данных
«задач
монахов»
(640).
16.5.2. Медицинские
данные (641).
16.5.3. Данные
проекта
StatLog (641). 16.5.4. Другие наборы данных (642).
16.6. Методы проверки. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
643
16.6.1. Перекрестная проверка (643).
16.6.2. Проверка исключением одного примера (643).
16.6.3. Метод бутстрепа (644).
16.6.4. Методика проведения эксперимента по внесению шума в
обучающие выборки (644).
Литература и комментарии . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
648
К введению . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
648
К части I . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
649
К главе 1 . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
649
К главе 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
649
К главе 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
652
К главе 4 . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
654
К главе 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
655
К главе 6 . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
655
К части II. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
658
К главе 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
658
К главе 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
659
К главе 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
660
К главе 10 . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . .
662
К главе 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
665
К части III . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
669
К главе 12 . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
669
К главе 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
672
К главе 14 . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .
673
К главе 15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
675
К главе 16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
677
Предметный указатель . .. . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
679

Низкий поклон тебе, Учитель.

Предисловие ко второму изданию

Второе издание книги вызвано непрекращающимся ростом интереса к трем основным механизмам рассуждений человека: дедукции,
абдукции и индукции, ибо без глубокого изучения и понимания этих
механизмов навряд ли возможно создание действительно интеллектуальных систем управления и принятия решений. В книгу добавлены две главы: формальные системы и индуктивное формирование
понятий в «зашумленных» базах данных. Так как значительную часть
читателей составляют студенты и аспиранты, то как с педагогической,
так и с научной точек зрения разумно начинать книгу не с методов
автоматического доказательства теорем, а с основ математической логики, изложить основные сведения по логике, нашедшие применение
в последующих главах. Поэтому книга начинается с главы, посвященной двум классам формальных систем: исчислению высказываний и
исчислению предикатов первого порядка. Особое внимание уделено
проблеме разрешимости формальных систем, так как после прочтения
этого параграфа и понимания теоремы А. Чёрча о неразрешимости
исчисления предикатов первого порядка в дальнейшем более прозрачными становятся ограничения, положенные в основу автоматического
доказательства теорем.
Последняя глава книги посвящена проблеме работы с реальными,
«зашумленными» базами данных в задаче индуктивного формирования
понятий. Умение работать с неточными и неопределенными данными
очень важно как для дедуктивных баз данных, так и для систем
принятия решений, в частности, экспертных систем. Наряду с методами построения деревьев решений при наличии шума в обучающей
выборке в главе приводятся результаты экспериментов, выполненных
на множествах данных из известной коллекции тестовых наборов данных Калифорнийского университета информатики и вычислительной
техники UCI Machine Learning Repository.
Глава 1 написана Вагиным В. Н., а глава 16 — Фоминой М. В.
В книге были исправлены найденные описки и опечатки, допущенные
в первом издании, которые были указаны читателями, за что авторы
приносят им искреннюю благодарность и признательность.