Введение в экспертные системы

Введение
Рядовым читателям
Инженерам-программистам

Что такое экспертная система?

ГЛАВА 1. Что такое экспертная система?
Что такое экспертная система?
Текущее состояние проблемы
Распределение материала книги по главам
Таблица 1.1. Содержание глав
Рекомендуемая литература
Упражнения
Смысл экспертного анализа

Экспертная система — это программа

Характеристики экспертных систем
Базовые функции экспертных систем
Приобретение знаний
"[Приобретение знаний это]
Забытый пароль
Представление знаний

Синтаксис и семантика представления семейных отношений
Управление процессом поиска решения
Обслуживание автомобиля
Разъяснение принятого решения
Загадка одного портрета
Резюме и структура книги

Обзор исследований в области искусственного интеллекта

ГЛАВА 2. Обзор исследований в области искусственного интеллекта
Обзор исследований в области искусственного интеллекта
"Искусственный интеллект
Периоды "зимней спячки"
Рекомендуемая литература
Упражнения
Головоломка "миссионеры и каннибалы "

Построение пространства поиска в головоломке "миссионеры и каннибалы"
Законченное пространство поиска
Головоломка "Восьмерка"
Классический период: игры и доказательство теорем
Поиск в пространстве состояний
Дерево пространства состояний головоломки Scrabble с буквами Т, С и А
Граф пространства состояний при использовании алгоритма поиска в ширину
Граф пространства состояний при использовании алгоритма поиска в глубину

Комбинаторный взрыв
Эвристический поиск
Алгоритм А
Существует хорошо известный алгоритм
s — узел начального состояния;
(1) OPEN:={s}. (2) Если ОРЕМ:={}
Романтический период: компьютер начинает понимать

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

Представление знаний

ГЛАВА 3. Представление знаний
Представление знаний
Оценка и сравнение характеристик экспертных систем
Оценка системы MYCIN
Сравнение MYCIN и STRIPS
Рекомендуемая литература
Упражнения

Список добавлений
Задача о перемещении блоков
Представление знаний: принципы и методы
Молотки, графины и теоремы
Планировщик STRIPS
Таблицы операторов и методика "средство -анализ завершения"
Таблица операторов для задачи
Анализ метода представления и управления в STRIPS
Формулировка подцелей в MYGIN

Лечение заболеваний крови
Структура системы MYC1N ([Buchanan and Shortliffe, 1984])
База знаний системы MYCIN
Типичное контекстное дерево в системе MYCIN ([Buchanan and Shortliffe, 1984])
Структуры управления в MYCIN
Представление набора правил в виде И/ИЛИ-графа
Комбинация гипотез

Символические вычисления

ГЛАВА 4. Символические вычисления
Символические вычисления
Почему. LISP не является языком представления знаний
Символический уровень и уровень знаний
LISP и разработка программ
Гипотеза Смита
Языки представления знаний
Рекомендуемая литература

Упражнения
Символическое представление
Физическая символическая система
Главная гипотеза
Реализация символических структур на языке LISP
Структуры данных в языке LISP

Списки и точечные пары
Структура LISP-программы
Функции, их вычисление и проблема цитирования в CLIPS
Функции, их вычисление и проблема цитирования в CLIPS
Приложение функции и лямбда-исчисление

Обработка списков
Примитивы в LISP
Примитивы в LISP
Сопоставление с образцом

Системы, основанные на знаниях

ГЛАВА 5. Системы, основанные на знаниях
Системы, основанные на знаниях
Рекомендуемая литература
Упражнения
Листинг 5.5. Набор диагностических правил заболеваний брюшной полости на языке CLIPS
Канонические системы
Смысл порождений
Системы порождающих правил для решения проблем

Синтаксис представления правил
Листинг 5.1. Оргправило системы MYCIN, записанное на языке CLIPS
Листинг 5.2. Правило, в котором используются переменные
Рабочая память
Листинг 5.3. Набор правил для проблемы в системе STRIPS
Трассировка программы управления роботом
Управление функционированием интерпретатора
Разрешение конфликтов
Разрешение конфликтов в CUPS
Прямая и обратная цепочки рассуждений

Листинг 5.4. Набор правил для построения башни из блоков
Трассировка программы строительства башни
Правила и метаправила
Свойство выпуклости в CLIPS: пингвины обретают способность летать (или не обретают)

Ассоциативные сети и системы фреймов

ГЛАВА 6. Ассоциативные сети и системы фреймов
Ассоциативные сети и системы фреймов
Множественное наследование
Гетерархическое представление множества геометрических фигур
Конфликт при множественном наследовании свойств
Представление "проблемы Никсона" в виде сети с наследованием
Сравнение сетей и фреймов
Рекомендуемая литература
Упражнения
Сеть с наследованием, в которой имеется каскад неоднозачностей

Проблема "королевского слона"
Проблема "корабельного капеллана "
Графы, деревья и сети
Некоторые виды графов: а) обыкновенный...
Определение 6.1. Если N— множество...
Определение 6.2. Если G— обыкновенный...
Определение 6.3. Если L — это...
Участок сети причинно-следственных связей ([Pople, 1982P
Обыкновенное дерево классификации болезней
Фрагменты семантической сети...

Ассоциативные сети
Разделение видов узлов и когнитивная экономия
Анализ адекватности ассоциативных сетей
Представление типовых объектов и ситуаций
Основные понятия концепции фреймов
Изменение "типичности" прямоугольников разного вида
Фреймы и графы
Значения по умолчанию и демоны
Иерархия плоских геометрических фигур
Реализация фреймов и наследования в языке CLIPS

Объектно-ориентированное программирование

ГЛАВА 7. Объектно-ориентированное программирование
Объектно-ориентированное программирование
Метаклассы в CLOS и CLIPS
Верхние уровни иерархической системы классов языка COOL

Множественное наследование в C++
Отношения между классами в примере "Алмаз Никсона"
Листинг 7.2. Файл nixon.h. Объявление классов, версия 1
Листинг 7.3. Файл nixon.h. Объявление классов, версия 2
Листинг 7.4. Файл nixon.h. Объявление классов, версия 3
Листинг 7.5. Файл nixon.h. Объявление классов, версия 4
Объектно-ориентированный анализ и конструирование экспертных систем
Рекомендуемая литература
Упражнения
Схема структуры классов для упражнения 7

Язык KRL
"...Анализ последствий объектно-центрической...
Процедуры и объекты
Процедурно- и объектно-ориентированные...
Языки LOOPS и FLAVORS
Передача сообщений
Формирование объекта класса на языке CLIPS
Проблема наложения методов
Иерархическая система классов окон
Гетерархическая система классов окон

Метаклассы
Структура классов в языке LOOPS
Вставка метакласса, определенного пользователем
Языки CLIPS и CLOS
Множественное наследование в CLOS и CLIPS
Листинг 7.1. Объявление классов на языке CLIPS
Наложение методов в CLOS и CLIPS
Стандартная схема наложения методов в языках CLOS и CLIPS ([Keene,1989])
Как сделать людей вежливыми

Логическое программирование

ГЛАВА 8. Логическое программирование
Логическое программирование
PROLOG и MBASE
Правила поиска в языке PROLOG
Управление поиском в системе MBASE

Рекомендуемая литература
Упражнения
Формальные языки
Исчисление высказываний
Исчисление предикатов
Снова о роботах и комнатах
Язык PROLOG
Литерал цели сопоставляется с литералом р (унифицируется с р), который называется головой фразы.
Листинг 8.1. Простая программа на языке PROLOG, определяющая отношение on (на)
Опровержение резолюций

Принцип резолюций
Таблица 8.1. Обобщение резолюции
Поиск доказательства в системе резолюций
Дерево доказательства методом опровержения резолюций
Процедурная дедукция в системе PLANNER

Представление неопределенности знаний и данных

ГЛАВА 9. Представление неопределенности знаний и данных
Представление неопределенности знаний и данных
Теория возможности
Неопределенное состояние проблемы неопределенности
Рекомендуемая литература
Упражнения
Источники неопределенности
Экспертные системы и теория вероятностей
Условная вероятность

Коэффициенты уверенности
Коэффициенты уверенности и условные вероятности
Популяции, позволяющие использовать P(d | е; = P(d| h)P(h| z)
Сомнительность и возможность
Нечеткие множества
Нечеткое множество "быстрых" автомобилей
Нечеткая логика

Приобретение знаний

ГЛАВА 10. Приобретение знаний
Приобретение знаний
Использование опроса экспертов для извлечения знаний в системе COMPASS
Циклическая процедура приобретения знаний в системе COMPASS
Автоматизация процесса извлечения знаний в системе OPAL
Графический интерфейс модели предметной области
Процесс приобретения знаний с использованием модели предметной области

Эффективность программы OPAL
Приобретение новых знаний на основе существующих
Рекомендуемая литература
Упражнения
Теоретический анализ процесса приобретения знаний
Стадии приобретения знаний
Стадии приобретения знаний
Уровни анализа знаний
Таблица 10.1. Четырехуровневая схема дифференциации знании в системе KADS Категория знаний
Оболочки CommonKADS и KASTUS

Онтологический анализ
Оболочки экспертных систем
Система EMYCIN
Сопровождение и редактирование баз знаний с помощью программы TEIRESIAS
Методы приобретения знаний

Эвристическая классификация

ГЛАВА 11. Эвристическая классификация (I)
Эвристическая классификация (I)
Классификация задач экспертных систем
Иерархия родовых аналитических...
Классификация методов решения проблем
Эвристическое сопоставление
Структура логических связей при эвристической классификации ([Clancey, 1985])
Общность эвристической классификации
Структура логических связей в системе MYCIN ([Clancey, 1985])

Структура логических связей в системе SOPHIE ([Clancey, 1985])
Определение понятия "оружие нападения"
Классификация или конструирование?
Рекомендуемая литература
Упражнения

Эвристическая классификация (II)

ГЛАВА 12. Эвристическая классификация (II)
Эвристическая классификация (II)
Структура задач в системе NEOMYCIN
Рекомендуемая литература
Упражнения
Модель событий
Модель событий
Инструментальные средства и задачи, решаемые экспертной системой
Эвристическая классификация в системах MUD и MORE

Модель предметной области выполнения буровых работ
Фрагмент модели предметной области, которая используется в программе MORE
Диагностические правила в М U D
Стратегии приобретения знаний
Использование коэффициентов уверенности в программе MORE
Отрицательные коэффициенты достоверности...
Опыт эксплуатации системы MORE
Совершенствование стратегий
Уроки проекта GUIDON

Иерархическое построение и проверка гипотез

ГЛАВА 13. Иерархическое построение и проверка гипотез
Иерархическое построение и проверка гипотез
Рабочая среда инженерии знаний TDE
Иерархическая организация узлов отказов в системе TEST
Рекомендуемая литература

Упражнения
Влияние сложности пространства гипотез на организацию работы системы
Иерархическое представление заболеваний органов дыхания
Обход дерева
Структурированные объекты в CENTAUR
Структура фреймов в CENTAUR
Правила, включенные в прототипы
Формирование суждений на базе модели в системе INTERNIST
Представление знаний в дереве заболеваний
Методика выделения правдоподобных гипотез в INTERNIST

Разделение узлов в дереве гипотез...
Проблемы, обнаруженные в процессе эксплуатации системы INTERNIST

Решение проблем конструирования

ГЛАВА 14. Решение проблем конструирования (I)
Решение проблем конструирования (I)

Рекомендуемая литература
Упражнения
Дерево анализа задачи проектирования конфигурации музыкального комплекса
Области применения методов конструктивного решения проблем
Система R1/XCON
Компоненты и ограничения
Использование текущего контекста для управления структурой задачи
Пример применения стратегии специфики: правило Rule 1 доминирует над правилом Rule 2
Стратегии разрешения конфликтов LEX и МЕА

Формирование суждений с учетом ограничений: метод Match
Использование знаний, развитие и расширение системы XCON
Извлечение знаний в системе R1/XCON
Совершенствование и расширение системы R1/XCON
Совершенствование системы XCON

Решение проблем конструирования (II)

ГЛАВА 15. Решение проблем конструирования (II)
Решение проблем конструирования (II)
Стратегии конструирования
Архитектура систем планирования и метапланирования
Организация пространств планирования в системе MOLGEN ([Stefik, 1981,b])
Программа планирования мероприятий
Извлечение, представление и применение знаний о проектировании
Реализация обратного прослеживания в системе VT
Приобретение знаний с помощью системы SALT

Итоги анализа систем решения проблем конструирования
Рекомендуемая литература
Упражнения

Средства формирования пояснений

ГЛАВА 16. Средства формирования пояснений

Средства формирования пояснений
Проект Explainable Expert Systems
Структура оболочки EES ([Neches et al., 1985])
Включение нового концепта в семантическую сеть знаний
Фрагмент предыстории разработки...
Планирование текстов пояснений и модели пользователей в PEA
Уточнение целей при планировании диалога с пользователем
Перспективы дальнейших исследований методов формирования пояснений
Рекомендуемая литература
Упражнения

Формирование пояснений на основе знаний
Подсистема формирования пояснений в MYCIN
Формирование ответов на основе дерева целей в системе MYCIN
Формирование пояснений в системах, производных от MYCIN
Формирование пояснений на основе фреймов
Организация вывода пояснений в системе CENTAUR
Использование мультимедийного интерфейса для формирования пояснений
Трехуровневая структура фреймов экспертной системы JETA
Формирование пояснений и автоматическое программирование
Автоматическое программирование в системе XPLAN

Инструментальные средства разработки экспертных систем

ГЛАВА 17. Инструментальные средства разработки экспертных систем
Инструментальные средства разработки экспертных систем
Использование инструментальных средств
Характерные сложности и способы их избежать

Выбор подходящего инструментария для разработки экспертной системы
Схема выбора инструментальной среды проектирования экспертной системы
Практическое освоение инструментальных средств
Правила и процедуры в инструментальной среде М.4
Стиль программирования
Некоторые максимы разработки экспертных систем
Рекомендуемая литература
Упражнения
Общая характеристика инструментальных средств для построения экспертных систем
Оболочки экспертных систем

Языки программирования высокого уровня
Языки описания порождающих правил
Объектно-ориентированные языки
Языки логического программирования экспертных систем
Многофункциональные программные среды
CUPS как многофункциональная среда программирования
Дополнительные модули
Пример множества контекстов
Логический вывод в разных контекстах

Системы с доской объявлений

Система отслеживания истинности предположений

ГЛАВА 19. Система отслеживания истинности предположений
Система отслеживания истинности предположений
Сравнение различных вариантов организации систем отслеживания истинности предположений
Рекомендуемая литература
Упражнения
Структура представления связей между высказываниями для упр. 5
Отслеживание зависимостей

Релаксация в сети
Пересмотр допущений
Запись информации о связях
Пересмотр теорий высказываний
Структура представления связей между высказываниями
Немонотонное обоснование
Пара конфликтующих выражений
Приведенная ниже программа на языке CLIPS реализует простой алгоритм
Работа со множеством контекстов
Отслеживание истинности предположений, основанное на анализе допущений

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

Формирование знаний на основе машинного обучения

ГЛАВА 20. Формирование знаний на основе машинного обучения
Формирование знаний на основе машинного обучения
Алгоритм формирования дерева решений по обучающей выборке
Дерево разделения объектов обучающей выборки
Уточнение наборов правил
Рекомендуемая литература
Упражнения
Пары образцов
Индуктивное обучение

Таблица 20.1. Обучающая выборка примеров Экземпляр
Система Meta-DENDRAL
Формирование и уточнение правил
Пространство версий
Отношения между образцами
Алгоритм отсеивания кандидатов
Сопоставление экземпляров с образцами в Meta-DENDRAL
Построение дерева решений и порождающих правил
Структура дерева решений
Дерево решений (заимствовано из [Quinlan, 1986, a])

Сети доверия

ГЛАВА 21. Сети доверия
Сети доверия
Теория Демпстера—Шефера
Функции доверия

Применение теории Демпстера—Шефера к системе MYCIN
Методика Перла
Байесовские сети
Сравнение методов неточных рассуждений
Резюме
Рекомендуемая литература
Упражнения
Пространство гипотез о неисправностях в автомобиле

Рассуждения, основанные на прецедентах

ГЛАВА 22. Рассуждения, основанные на прецедентах
Рассуждения, основанные на прецедентах
Сравнение систем, основанных на правилах и прецедентах
Рекомендуемая литература
Упражнения
База прецедентов

Программа CHEF
Архитектура программы CHEF
Методы извлечения и адаптации прецедентов
Возвратить MATCH.
Обучение с помощью компьютера: система САТО
Предметная область программы САТО
Расследования и рассуждения в юриспруденции
Обучение с помощью системы САТО
Фрагмент иерархии факторов в системе САТО ([Ashley and Aleven, 1997])
Формирование отчетов в системе FRANK

Архитектура системы FRANK

Гибридные системы

ГЛАВА 23. Гибридные системы
Гибридные системы
Организация обучения в системе SCALIR

Будущее гибридных систем
Рекомендуемая литература
Упражнения
Фрагмент нейронной сети
Методы обучения в системе ODYSSEUS
Системы ODYSSEUS и MINERVA
Оболочка экспертной системы MINERVA
Обучение в системе ODYSSEUS
Использование прецедентов для обработки исключений
Архитектура гибридной системы, использующей правила и прецеденты

Гибридный символический подход и нейронные сети
Нейронные сети
Фрагмент нейронной сети с возбуждающими и тормозящими связями
Простая функция вычисления состояния активности узла i
SCALIR — гибридная система для извлечения правовой информации
Сеть связности в системе SCAUR ([Rose, 1994])

Заключение

ГЛАВА 24. Заключение
Заключение
Загадка искусственного интеллекта
Представление знаний
Языки программирования систем искусственного интеллекта
Решение практических проблем
Архитектура экспертных систем
Рекомендуемая литература

Программирование на языке CLIPS

ПРИЛОЖЕНИЕ. Программирование на языке CLIPS
Программирование на языке CLIPS
А.4. Задача "Правдолюбцы и лжецы"
А.4.1. Анализ проблемы

А.4.2. Онтологический анализ и представление знаний
А.4.3. Разработка правил
Листинг А.1. Трассировка решения задачи Р0
А.4.4. Расширение набора правил — работа с составными высказываниями
Листинг А.2. Трассировка решения задачи Р4
A.4.5. Обратное прослеживание и множество контекстов
А.4.6. Обработка метавысказываний
А.4.7. Полный листинг программы
А.5. Стиль программирования на языке CLIPS
Упражнения

А.1. Краткая история CLIPS
А.2. Правила и функции в CLIPS
А.2.1. Факты
А.2.2. Правила
А.2.3. Наблюдение за процессом интерпретации
А.2.4. Использование шаблонов
A.2.5. Определение функций
А.3. Объектно-ориентированные средства в CLIPS