- •Введение
- •Глава 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. Нерезолютивные методы вывода на семантических сетях
3.5.2.1 Линейная резолюция вL
Определение. Для данного множестваSдизъюнктов и дизъюнктаС0изSлинейный вывод дизъюнктаСnизSс верхним дизъюнктомС0- это вывод, изображенный на рис. 1, где
для i = 0, 1, ..., n-1дизъюнктCi+1есть резольвента дизъюнктаСiиВi; дизъюнктыCiназываетсяцентральнымиВi-боковыми.
Вiлибо принадлежитS, либо естьСjдля некоторогоj < i. Показано, что линейная резолюция является полной, т.е. для любого противоречивого множества дизъюнктов всегда выводится пустой дизъюнкт.
Дополнительное усиление рассмотренной стратегии предложено Лавлендом, Ковальским и Кюнером. Ими установлены условия, при которых центральный дизъюнкт позднее может участвовать в роли бокового дизъюнкта. Это свойство позволяет сократить число лишних дизъюнктов, поскольку становится ясно, будет или нет тот или иной центральный дизъюнкт использован для порождения пустого дизъюнкта. Прежде всего, множество литер произвольным образом упорядочивается, т.е. считается известным, какую литеру поставить левее в записи дизъюнкта, а какую правее. Например, пусть P > Q > R > тогда считаем, что дизъюнктPQзаписан верно, аPQ- нет.
При порождении резольвент отсекаемая литера включается в представление резольвенты, но при этом указывается в рамке. Например, если
C1 = P Q
C2 = R,
то резольвентаС1иС2имеет вид
P R.
Литеры в рамке служат для учета отрезанных литер: они не участвуют в дальнейшем порождении резольвент.
Рассмотрим дизъюнкт специального вида, в котором последняя литера не обрамлена и для этой последней литеры имеется контрарная обрамленная литера, например, .
Дизъюнкт такого типа называется редуцируемым. ЕслиС- редуцируемый дизъюнкт, то его можно сократить за счет отбрасывания последней литеры, а также всех обрамленных литер, за которыми не следует необрамленной литеры. Для редуцируемого дизъюнкта это сразу дает.
Следующая лемма формализует введенные определения.
Лемма. Если в некотором выводеСявляется редуцируемым упорядоченным дизъюнктом, то существует центральный упорядоченный дизъюнктCj (j<1), такой, что редукцияСi+1дизъюнктаCiявляется резольвентойСiиСj.
Доказательство.ЕслиСkиСk+1, два соседних упорядоченных дизъюнкта на рис.7.1, то все литеры дизъюнктаСkсодержатся вСk+1(обрамленные литеры учитываются). Действительно,Сk+1представляется как
I
где I- отсекаемая литера.
П
С учетом доказанной леммы упорядоченный вывод (называемый OL - выводом)определяетсяследующим образом:
Каждый дизъюнкт Вiлибо принадлежитS, либо является ранее порожденным центральным дизъюнктом.
Если Сiредуцируемый упорядоченный дизъюнкт, тоСi+1является результатом редукцииСi. В противном случаеСi+1есть резольвентаСiиВi, причемВiпринадлежит исходному множеству дизъюнктов и отсекаемая литера вСiпоследняя.
В вывод не входят тавтологии.
Пример. ПостроимOL- вывод пустого дизъюнкта из множества дизъюнктов:
C1 = P Q,
C2 = R ,
C3 = R
C4 =
C5 = ;
P > Q > R >
Находим резольвенту дизъюнктов С1иС2, для которых отсекаемая литера последняя
C
Q
Находим резольвенту дизъюнктов С6и С4:
С
Q
R
Поскольку дизъюнкт С7редуцируем, то сразу находим
С8 = Р
как результат редукции С7.
Находим резольвенту дизъюнктов С8и С3:
P
5. Находим резольвенту С9и С5:
P Q
C10является редуцируемым дизъюнктом. Следовательно, его редукция сразу дает
C11=.