- •Введение
- •Глава 1. Ведение в системы искусственного интеллекта
- •1.1. Архитектура систем искусственного интеллекта
- •1.2. База знаний и данных
- •1.1.1 Понятие модели
- •1.1.2. Логические модели
- •1.1.3 Модели знаний на основе продукций
- •1.1.4 Фреймовая модель знаний
- •1.1.5 Семантические сети
- •1.3. Машина вывода
- •1.3.1. Понятие формальной системы
- •Примеры стратегии вывода
- •Как функционирует машина вывода
- •1.4. Извлечение знаний и обучение
- •1.4.1. Извлечение знаний от многих экспертов
- •1.4.2 Проблема непротиворечивости формализованной базы знаний
- •1.5. Обучение системы
- •1.6. Интерфейс с пользователем
- •1.7. Организация работы
- •1.8. Инструментальные средства создания систем искусственного интеллекта
- •Языки программирования
- •1.8.2. Языки продукционного программирования
- •1. 8. 3. Языки инженерии знаний и инструментальные системы
- •1.8.3.1. Система vpExpert
- •1.8.3.2. Система kas
- •1.8.3.3. Система Expert-Ease
- •Глава 2. База знаний
- •2.1. Методы извлечения знаний
- •2.1.1. Классификация методов извлечения знаний
- •2.1.2. Пассивные методы
- •2.1.2.1. Наблюдения
- •2.1.2.2. Анализ протоколов «мыслей вслух»
- •2.1.2.3. Лекции
- •2.1.3. Активные индивидуальные методы
- •2.1.3.1. Анкетирование
- •2.1.3.2. Интервью
- •2.1.3.3. Свободный диалог
- •2.1.4. Активные групповые методы
- •2.1.4.1. «Круглый стол»
- •2.1.4.2. «Мозговой штурм»
- •2.1.4.3. Экспертные игры
- •2.1.4.3.1. Игры с экспертом
- •2.1.4.3.2. Ролевые игры в группе
- •2.1.4.4. Игры с тренажерами
- •2.1.4.4.1. Компьютерные экспертные игры
- •2.1.5. Текстологические методы
- •2.2.Формальное описание понятий предметной области (по)
- •2.2.1. Методы абстрагирования понятий
- •2.2.1.1.Агрегация и декомпозиция понятий
- •2.2.1.2.Обобщение и специализация понятий
- •2.2.1.3.Типизация и конкретизация понятий
- •2.2.1.4.Ассоциация и индивидуализация понятий
- •2.3.Методы классификации
- •2.3.1. Экстенсиональный и интенсиональный аспекты классификации
- •2.3.2. Таксономия и мерономия
- •2.3.3. Типы классификаций
- •2.3.4. Древовидные классификации
- •2.3.5. Булевы классификации
- •2.3.6. Комбинативные классификации
- •2.4.События и процессы
- •2.4.1. Состояния предметной области
- •2.4.2. Событие
- •2.4.3. Последовательные процессы
- •2.4.4. Рекурсивные процессы
- •2.4.5. Ветвящиеся процессы
- •2.5. Системы продукций: структура, технология, применение
- •2.5.1. Неформальное введение в системы продукций
- •2.5.1.1 Алгоритмические модели
- •2.5.2 Логический вывод
- •2.5.3 Прикладные модели
- •2.5.4. Метамодель систем продукций
- •2.5.4.1. Основные подсистемы
- •2.5.5.2. Метаструктура базы данных и операций
- •2.5.5.2.1. Характер организации данных
- •2.5.5.2.2 Операции над базой данных
- •2.5.5.2.3 Контроль несовместимости
- •2.5.5.2.4 Ассоциативная надстройка
- •2.5.6. Метаструктура модуля правил
- •2.5.6.1 Аппарат активации
- •2.5.6.2 Структура правил
- •2.5.7. Метаструктура модуля управления
- •2.5.8. Технология поддержки разработок продукционных систем
- •2.5.9. Формальные модели систем продукций
- •2.5.9.1. Алгебраическая модель
- •2.5.9.1.1. Основные определения
- •2.5.9.1.2. Операции преобразования ситуации
- •2.5.9.1.3. Условия корректности вычислений над конъюнктивной базой данных
- •2.5.9.1.4. Однозначность вычислений над дизъюнктивной базой
- •2.5.9.2. Управление выводом в системах продукций
- •2.5.9.3. Язык управления применением продукций
- •2.5.9.4. Язык управления выбором данных
- •2.5.9.5. Обзор формальных моделей вычислений
- •2.5.10. Экспериментальные системы продукций
- •2.5.10.1. Система скип
- •2.5.10.2. Система анализа топологических чертежей интегральных схем
- •P(слой) x0, y0 : Dx1, Dy2, .., Dxn-1, Dyn;
- •2.6. Выводы к второй главе
- •3. Машина логического вывода
- •3.1. Формальное определение задачи
- •3.2. Специфика решения задач в сии
- •3.3. Управление процессом решения задачи
- •3.4. Модели эвристического поиска решений
- •3.4.1 Стратегия поиска в глубину
- •3.4.2. Стратегии перебора с отсечениями
- •3.4.2.1. Метод ветвей и границ
- •3.4.2.2. Стратегии поиска на основе эвристической функции оценки
- •3.5. Методы вывода и доказательства теорем
- •3.5.1 Механизм резолюции Робинсона
- •3.5.2. Резолюция в логике высказываний
- •3.5.2.1 Линейная резолюция вL
- •Метод линейного вывода в lЛавленда, Ковальского и Кюнера
- •Эффективная реализация
- •3.5.2.3. Метод поиска в глубину
- •3.5.2.4 Эвристики поиска в дереве
- •3.5.2.5. Семантическая резолюция
- •3.5.3 Резолюция в pl
- •3.6. Методы индуктивного вывода
- •3.6.1. Виды индукции
- •3.6.2. Индукция как вывод и индукция как метод
- •3.6.3. Правила, необходимые для систем автоматического формирования знаний
- •3.7. Дедуктивный вывод на семантических сетях
- •3.7.1. Нерезолютивные методы вывода на семантических сетях
Как функционирует машина вывода
Машина вывода является интерпретатором правил, который использует факты базы знаний для решения проблем. На входе машина вывода получает цель консультации.
На каждом шаге вывода машина вывода строит (наращивает) контекст (трассу вывода) и пытается подобрать правило, применимое к этому контексту. Контекст - это математическая структура, соответствующая образцу (см. предыдущий параграф), которому дополнительно придана цель вывода. При этом цель вывода может также задаваться в виде образца-цели.
Изменение контекста реализуется либо вследствие применения правил вывода, либо путем ввода фактов, запрашиваемых у пользователя. Например, пусть цель консультации - установить физические кондиции пациента. В этом случае, задавая вопросы типа
"Каков возраст пациента?"
"Каков вес пациента?"
"Потребляет ли пациент жиры?" и т.д.
Система создает контекст, представляющий множество переменных и их значений, например:
Возраст = 35
Вес = 85
Потребление жиров = 50 и т.д.
С другой стороны, контекст может быть наращен и с помощью правил. Например, если есть следующее правило:
ЕСЛИ (ВЕС = X) & (ВОЗРАСТ < 40), ТО
(ИДЕАЛЬНЫЙ_РОСТ = 100 + X),
то контекст будет расширен путем вычисления и добавления факта
ИДЕАЛЬНЫЙ_РОСТ = 185
Простейший алгоритм, осуществляющий построение трассы вывода, заключается в следующем:
определить исходный контекст;
занести все переменные исходного контекста в очередь переменных логического вывода, а их значения (если заданы) - в список переменных;
просмотреть список переменных и найти ту переменную, имя которой стоит в начале очереди переменных логического вывода. Если переменная найдена, записать в указатель переменных условия, номер правила и число 1. Если переменная не найдена, перейти к шагу f;
присвоить значения непроинициализированным переменным условной части найденного правила (если такие есть). Имена переменных содержатся в списке переменных условия правила. Проверить все условия правила и в случае их истинности обратиться к части "ТО" правила;
присвоить значение переменной, входящей в часть "ТО" правила, и поместить ее в конец очереди переменных логического вывода;
удалить переменную, стоящую в начале очереди переменных логического вывода, если она больше не встречается в условной части какого-либо правила;
закончить процесс рассуждений, как только опустеет очередь переменных, логического вывода. Если в очереди есть еще переменные, вернуться к шагу 3.
На машину вывода возлагаются следующие основные задачи:
1. Построение трассы вывода.
2. Интерпретация правил вывода и их применение к текущему контексту.
3. Повышение эффективности поиска.
Формальное понятие трассы вывода дается ниже. Задача построения трассы выводазаключается в отображении в памяти ЭВМ последовательности шагов вывода, применяемых правил и получаемых значений переменных. Множество значений переменных, известных на данном шаге вывода образует контекст. Цель построения трассы - возможность ее переопределения с некоторого ранее порожденного контекста.Создание текущего контекстасвязано с выбором правила вывода из множества альтернативных правил - вторая задача. От такого выбора в конечном итоге зависит эффективность системы (быстродействие ЭС), поэтому необходимы меры по обеспечению достаточной эффективности машины вывода.
Существует два базовых подхода к построению трассы вывода. Первый основан на логике решения в направлении "от того, что известно - к тому, что надо найти"; второй подход, наоборот, использует движение в обратном направлении: "от того, что надо найти - к тому, что известно" Первый подход характеризует системы с прямым выводом, второй - системы с обратным выводом. Обратный вывод применяется в тех случаях, когда цели известны и их сравнительно немного.
В системах диагностики чаще применяется прямой вывод, в то время как в планирующих системах более эффективен обратный. Кроме того, используется и комбинированный вывод, основанный на сочетании прямого и обратного поиска. Комбинированный вывод называется также циклическим.
Проблема организации трассы вывода напрямую связана с повышением эффективности поиска. Мы подробно исследуем эти вопросы в последующих разделах. Сейчас формализуем задачу организации трассы вывода. Для этого введем понятие дерева решения. Рассмотрим пятерку
<S0, SF, A, RA, RS>, (1.34)
где S0 - исходное состояние системы (объекта, модели);
SF - конечное (искомое) состояние системы (объекта, модели);
А - алгоритм отображения ;
RA - список ограничений на реализацию алгоритма А;
RS - список ограничений на SF (критерий).
Состояние исследуемой системы (объекта) Sj, непосредственно достигаемое изSk, назовем преемникомSk, а состояниеSk- предшественникомSj. Граф Г(S,) с множеством вершин состоянийSjSи дуг, связывающих предшественников и преемников, образует дерево решения с корнемS1и листомSFесли:
-й ярус в Г образуют те преемники (- 1)-го яруса (= 1,2,...), которые не входят в ярусы (- 2), (- 3) и т.д.;
листьями в Г являются состояния, все преемники которых содержатся в верхних ярусах (исключение, возможно, составляет SF).
Возможными вариантами постановки задачи относительно (1.34) являются (1.5) - (1.8).
Все эти задачи так или иначе упираются в проблему отыскания маршрута М в Г(S,), связывающегоS0иSF. Некоторая (любая) законченная часть этого маршрута называется трассой вывода. Очевидно, что эффективность стратегии вывода определяется в первую очередь тем, насколько "близко" она держится М и, во-вторых, насколько велики затраты (памяти и процессорного времени) для реализации этой стратегии вывода. В качестве одной из оценок эффективности стратегии поиска определена оценка меры близости трассы вывода и М в виде
(1.35)
где L- длина найденного пути к цели (длина М),
Т - общее число вершин, пройденных при поиске цели в Г(S,).
Очевидно, что детерминированная оптимальная стратегия обеспечивает максимальную меру близости Р, равную 1. Повышение эффективности поиска по-разному достигается в существующих системах вывода:
использование эвристических функций оценки;
использование приоритетов для правил;
использование метаправил (правил для правил).
Эти вопросы будут обсуждены в третьей главе данного курса.