- •Иван Братко Программирование на языке Пролог для искусственного интеллекта
- •От редактора перевода
- •Предисловие
- •Предисловие автора
- •Благодарности
- •Упражнения
- •1.2. Расширение программы-примера с помощью правил
- •Упражнения
- •1.3. Рекурсивное определение правил
- •Упражнение
- •1.4. Как пролог-система отвечает на вопросы
- •Упражнение
- •1.5. Декларативный и процедурный смысл программ
- •Литература
- •Глава 2 Синтаксис и семантика Пролог-программ
- •2.1. Объекты данных
- •2.1.1. Атомы и числа
- •2.1.2. Переменные
- •2.1.3. Структуры
- •Упражнения
- •2.2. Сопоставление
- •Упражнения
- •2.3. Декларативный смысл пролог-программ
- •Упражнения
- •2.4. Процедурная семантика
- •Программа
- •Шаги вычисления
- •Упражнение
- •2.5. Пример: обезьяна и банан
- •2.6. Порядок предложений и целей
- •2.6.1. Опасность бесконечного цикла
- •2.6.2. Варианты программы, полученые путем переупорядочивания предложений и целей
- •2.6.3. Сочетание декларативного и процедурного подходов
- •2.7. Замечания о взаимосвязи между Прологом и логикой
- •Упражнение
- •Литература
- •Глава 3 Списки, операторы, арифметика
- •3.1. Представление списков
- •3.2. Некоторые операции над списками
- •3.2.1. Принадлежность к списку
- •3.2.2. Сцепление (конкатенация)
- •Упражнения
- •3.2.3. Добавление элемента
- •3.2.4. Удаление элемента
- •3.2.5. Подсписок
- •3.2.6. Перестановки
- •Упражнения
- •3.3. Операторная запись (нотация)
- •Упражнения
- •3.4. Арифметические действия
- •Упражнения
- •Глава 4 Использование структур: примеры
- •4.1. Получение структурированной информации из базы данных
- •Упражнения
- •4.2. Абстракция данных
- •Упражнение
- •4.3. Моделирование недетерминированного автомата
- •Упражнения
- •4.4. Планирование поездки
- •4.5. Задача о восьми ферзях
- •4.5.1. Программа 1
- •Упражнение
- •4.5.2. Программа 2
- •4.5.3. Программа 3
- •4.5.4. Заключительные замечания
- •Упражнение
- •Глава 5 Управление перебором
- •5.1. Ограничение перебора
- •5.1.1. Эксперимент 1
- •5.1.2. Эксперимент 2
- •5.2. Примеры, использующие отсечение
- •5.2.1. Вычисление максимума
- •5.2.2. Процедура проверки принадлежности списку, дающая единственное решение
- •5.2.3. Добавление элемента к списку, если он в нем отсутствует (добавление без дублирования)
- •5.2.4. Задача классификации объектов
- •Упражнения
- •5.3. Отрицание как неуспех
- •Упражнения
- •5.4. Трудности с отсечением и отрицанием
- •6.2. Обработка файлов термов
- •6.2.2. Вывод списков
- •6.2.3. Формирование термов
- •6.2.4. Обработка произвольного файла термов
- •Упражнения
- •6.3. Обработка символов
- •Упражнение
- •6.4. Создание и декомпозиция атомов
- •Упражнения
- •6.5. Ввод программ: consult, reconsult
- •Глава 7 Другие встроенные процедуры
- •7.1. Проверка типов термов
- •7.1.1. Предикаты var , nоnvar , atom , integer , atomic
- •7.1.2. Решение числового ребуса с использованием nonvar
- •Упражнения
- •Упражнения
- •7.3. Различные виды равенства
- •7.4. Работа с базой данных
- •Упражнения
- •7.5. Средства управления
- •Упражнения
- •Глава 8 Стиль и методы программирования
- •8.1. Общие принципы хорошего программирования
- •8.2. Как представлять себе программы на Прологе
- •8.2.1. Использование рекурсии
- •8.2.2. Обобщение
- •8.2.3. Использование рисунков
- •8.3. Стиль программирования
- •8.3.1. Некоторые правила хорошего стиля
- •8.3.2. Табличная организация длинных процедур
- •8.3.3. Комментирование
- •8.4. Отладка
- •8.5. Эффективность
- •8.5.1. Повышение эффективности решения задачи о восьми ферзях
- •8.5.2. Повышение эффективности программы раскраски карты
- •8.5.3. Повышение эффективности конкатенации списков за счет совершенствования структуры данных
- •8.5.4. Повышение эффективности зa счет добавления вычисленных фактов к базе данных
- •Упражнения
- •9.1. Представление списков. Сортировка
- •9.1.1. Замечания в некоторых альтернативных способах представления списков
- •Упражнения
- •9.1.2. Сортировка списков
- •Упражнения
- •9.2. Представление множеств двоичными деревьями
- •Упражнения
- •9.3. Двоичные справочники: добавление и удаление элемента
- •9.4. Отображение деревьев
- •Упражнение
- •9.5. Графы
- •9.5.1. Представление графов
- •9.5.2. Поиск пути в графе
- •9.5.3. Построение остовного дерева
- •Упражнение
- •Литература
- •Глава 10 Усовершенствованные методы представления множеств деревьями
- •10.1. Двоично-троичные справочники
- •Упражнение
- •Литература
- •Глава 11. Основные стратегии решения задач
- •11.1. Предварительные понятия и примеры
- •11.2. Стратегия поиска в глубину
- •Упражнения
- •11.3. Поиск в ширину
- •11.3.1. Списковое представление множества кандидатов
- •11.3.2. Древовидное представление множества кандидатов
- •Упражнения
- •11.4. Замечания относительно поиска в графах, оптимальности к сложности
- •Литература
- •Глава 12 Поиск с предпочтением: эвристический поиск
- •12.1. Поиск с предпочтением
- •Упражнение
- •12.2. Поиск c предпочтением применительно к головоломке "игра в восемь"
- •Упражнение
- •12.3. Применение поиска с предпочтением к планированию выполнения задач
- •Литература
- •Глава 13 Сведение задач к подзадачам. И/или-Графы
- •13.1. Представление задач в виде и/или-графов
- •13.2. Примеры и/или-представления задач
- •13.2.1. И/или-представление задачи поиска маршрута
- •13.2.2. Задача о ханойской башне
- •13.2.3. Формулировка игровых задач в терминах и/или-графов
- •13.3. Базовые процедуры поиска в и/или-графах
- •Упражнения
- •13.4. Поиск с предпочтением в и/или-графах
- •13.4.1. Эвристические оценки и алгоритм поиска
- •13.4.2. Программа поиска
- •13.4.3. Пример отношений, определяющих конкретную задачу: поиск маршрута
- •Упражнение
- •Литература
- •Глава 14 Экспертные системы
- •14.1. Функции, выполняемые экспертной системой
- •14.2. Грубая структура экспертной системы
- •14.3. Правила типа "если-то" для представления знаний
- •Упражнения
- •14.4. Разработка оболочки
- •14.4.1. Процесс рассуждений
- •14.4.2. Формирование ответа на вопрос "почему"
- •14.4.3. Формирование ответа на вопрос "как"
- •14.5. Реализация
- •14.5.1. Процедура рассмотреть
- •14.5.2. Процедура ответпольз
- •14.5.3. Усовершенствование процедуры ответпольз
- •14.5.4. Процедура выдать
- •14.5.5. Драйвер верхнего уровня
- •14.5.6. Одно замечание по поводу программы-оболочки
- •14.5.7. Цели с отрицанием
- •Упражнение
- •14.6. Работа с неопределенностью
- •14.6.1. Степень достоверности
- •14.6.2. Модель Prospector'а
- •14.6.3. Принципы реализации
- •14.7. Заключительные замечания
- •Проекты
- •Литература
- •Глава 15 Игры
- •15.1. Игры двух лиц с полной информацией
- •15.2. Минимаксный принцип
- •15.3. Альфа-бета алгоритм: эффективная реализация минимаксного принципа
- •15.4. Минимаксные игровые программы: усовершенствования и ограничения
- •15.5. Знания о типовых ситуациях и механизм "советов"
- •15.5.1. Цели и ограничения на ходы
- •15.5.2. Выполнимость совета
- •15.5.3. Правила и таблицы советов
- •15.6. Программа на языке al0 для игры в шахматном эндшпиле
- •15.6.1. Миниатюрный интерпретатор языка al0
- •15.6.2. Программа на языке советов для эндшпиля "король и ладья против короля"
- •Литература
- •Глава 16 Программирование в терминах типовых конфигураций
- •16.1. Архитектура, ориентированная на типовые конфигурации
- •16.1.1. Основные понятия
- •16.1.2. Прологовские программы как системы, управляемые образцами
- •16.1.3. Пример составления программы
- •16.2. Простой интерпретатор программ, управляемых образцами
- •16.3. Простая программа для автоматического доказательства теорем
- •16.4. Заключительные замечания
- •Литература
- •Ответы к некоторым упражнениям Глава 1
- •Глава 2
- •Глава 3
- •Глава 4
- •Глава 5
- •Глава 6
- •Глава 7
- •Глава 8
- •Глава 9
- •Глава 10
- •Глава 11
Проекты
Завершите программирование нашей оболочки в части, касающейся неопределенной информации (процедура ответпольз и другие).
Рассмотрите перечисленные выше критические замечания, а также возможные расширения нашей экспертной системы. Разработайте и реализуйте соответствующие усовершенствования.
Резюме
• Обычно от экспертных систем требуют выполнения следующих функций:
решение задач в заданной предметной области,
объяснение процесса решения задач,
работа с неопределенной и неполной информацией.
• Удобно считать, что экспертная система со стоит из двух модулей: оболочки и базы знаний. Оболочка в свою очередь состоит из механизма логического вывода и интерфейса с пользователем.
• При создании экспертной системы необходимо принять решения о выборе формального языка представления знаний, механизма логического вывода, средств взаимодействия с пользователем и способа работы в условиях неопределенности.
• "Если-то"-правила, или продукции являются наиболее часто применяемой формой представления знаний в экспертных системах.
• Оболочка, разработанная в данной главе, интерпретирует "если-то"-правила, обеспечивает выдачу объяснений типа "как" и "почему" и запрашивает у пользователя необходимую информацию.
• Машина логического вывода была расширена для работы с неопределенной информацией.
• В данной главе были обсуждены следующие понятия:
экспертные системы
база знаний, оболочка,
машина логического вывода
"если-то"-правила, продукции
объяснения типа "как" и "почему"
категорические знания, неопределенные знания
сеть вывода,
распространение оценок достоверности по сети
Литература
Книга Michie (1979) - это сборник статей, относящихся к различным аспектам экспертных систем и инженерии знаний. Две ранние экспертные системы, оказавшие большое влияние на развитие этой области, MYCIN и Prospector, описаны в Shortliffe (1976) и Duda et al (1979). Книга Buchanan and Shortliffe (1984) является хорошим сборником статей, посвященных результатам экспериментов с системой MYCIN. Weiss and Kulikowski (1984) описывают свой практический опыт разработки экспертных систем. Вопрос о работе в условиях неопределенности еще нельзя считать вполне решенным: в статье Quinlan (1983) сравниваются различные подходы к этой проблеме. Способ разработки нашей экспертной системы до некоторой степени аналогичен описанному в Hammond (1984). Некоторые примеры, использовавшиеся в тексте, заимствованы из Winston (1984), Shortliffe (1976), Duda et al (1979), Bratko (1982) и Reiter (1980).
Bratko I. (1982). Knowledge-based problem-solving in AL3. In: Machine Intelligence 10 (J.E. Hayes, D. Michie, Y.H. Pao, eds.). Ellis Horwood.
Buchanan B.G. and Shortliffe E.H. (1984, eds.). Rule-based Expert Systems: The МYСIN Experiments of the Stanford Heuristic Programming Project. Addison-Wesley.
Duda R., Gasschnig J. and Hart P. (1979). Model design in the Prospector consultant system for mineral exploration. In: Expert Systems in the Microelectronic Age (D. Michie, ed.). Edinburgh University Press.
Hammond P. (1984). vMicro-PROLOG for Expert Systems. In: Micro-PROLOG: Programming in Logic (K.L. Clark, F.G. McCabe, eds.). Prentice-Hall.
Michie D. (1979, ed.). Expert Systems in the Microelectronic Age. Edinburgh University Press.
Quinlan J.R. (1983). Inferno: a cautious approach to uncertain reasoning. The Computer Journal 26 : 255-270.
Reiter J. (1980). AL/X: An Expert System Using Plausible Inference. Oxford: Intelligent Terminals Ltd.
Shortliffe E. (1976). Computer-based Medical Consultations: MYCIN. Elsevier.
Weiss S.M. and Kulikowski CA. (1984). A Practical Guide to Designing Expert Systems. Chapman and Hall.
Winston P. H. (1984). Artificial Intelligence (second edition). Addison-Wesley. [Имеется перевод первого издания: Уинстон П. Искусственный интеллект. — М.: Мир, 1980.]
