- •Введение
- •Глава 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. Нерезолютивные методы вывода на семантических сетях
2.5.9.5. Обзор формальных моделей вычислений
Описанная выше алгебраическая модель СП является обобщением ряда известных моделей, среди которых отметим реляционную модель А.С. Клещева, К-системы В.Е. Кузнецова, реляционную модель S.Vere, и модель управляемой СПV.Georgeff.
Реляционная модель вычислений, предложенная А. С. Клещевым, в качестве языка описания использует язык исчисления предикатов первого порядка. Элементами множества состояний являются конституанты, которые представляют собой атомные формулы вида:
P(c1,…, ck),
где р— некоторыйk-арный предикатный символ,aci, с2, ..., сk— константы. Множество переходов между элементами множества состояний задается с помощью теории Т в языке исчисления предикатов первого порядкаL, каждое предложение которой содержит в точности один знак импликации.
Для каждого множества конституант Sопределим связанную с ним структуруMsязыкаL спомощью следующих условий
все ms имеют один и тот же счетный универсум;
в Msистинны те и только те конституанты, которые входят вS.
Через Mбудем обозначать структуру, соответствующую пустому множеству конституант. ПустьТ —множество предложений языкаL вида
ψ,
где фи ψ —конъюнкции конституант,S0 —конечное множество конституант такое, что, не является модельюТ.Тогда процесс вычислений по программеТнад исходными даннымиS0определяется следующим образом.
Для каждого ееТобозначим:, —множества конституант, входящих в условие и в следствие а соответственно. Пусть наi-м шаге вычислено множество конституантSiтакое, чтоS0 Si.Если некотороеТложно в структуре,то
.
Выбор на i-ом шаге предложенийТ,ложных в структуресоответствует различному порядку выполнения действий при вычислениях.
Процесс вычислений заканчивается, если для некоторого tструктура, — модельТ; Stбудем называть результатом вычисления.
Аналогично определяется вывод в случае, когда в правилах языка используются переменные и кванторы, т.е. правила имеют вид 1, …,n(u1, …,um).
А..С. Клещевым исследована корректность вычислений в реляционной модели и доказано, что результат вычислений не зависит от порядка применения продукций. Эти исследования послужили теоретической основой для технологического комплекса СИНАП, успешно реализованного в ИАПУ ДВНЦ СССР.
Другой интересной формальной моделью СП являются К-системы, предложенные Кузнецовым В.Е.
Как уже было отмечено, одна из основных проблем при выводе в СП — это выбор соответствующих правил для применения. Замечено, что база продукций, представленная в виде сотен локальных правил, не описывает в явном виде отношение "общее-частное" над правилами. В К-системах введено отношение "общее-частное" над продукциями следующим образом: если ={xi/ti} —подстановка, ар, q —продукции, и
p =q,
где q —это продукция, получаемая изqзаменой всех вхождений переменныхxiнаtiто продукциярявляется частным случаем продукцииq, аq —обобщение продукциир.
В К-системах введено несколько типов обобщений: подстановочное, категориальный синтез, отбрасывание посылок, исследованы свойства этих обобщений. На основании этих понятий вводится понятие исключение из правила.
Правило рявляется исключением изq(aq —общее правило по отношению кр), если область определения правиларявляется строго частным случаем области определения правилаq.В К-системах реализована (встроена) следующая стратегия выбора правил: исключения всегда имеют больший приоритет чем общие правила. Данная стратегия близка к стратегии, реализованной в языке РЕФАЛ [З].
Предложенный подход оправдан с точки зрения здравого смысла и был успешно применен к задачам, связанным с синтаксическим анализом естественных языков.
Формальная модель СП, предложенная S.Vere[128], называется реляционной СП и определяется как пятерка
(C, V, L,0 , P).
Здесь С —множество констант (обозначаемых строчными буквами);V -конечное множество символов переменных, принимающих значения в области констант (обозначаются заглавными буквами);L —множество литералов вида(е1 e2 ... еn)или(e1 e2 . . . еn),п 1,еiСV; 0
— начальная ситуация, определяемая как конъюнкция литералов; Р — конечное множество правил вида
,
где — условие применимости (антецедент), —следствие (консеквент),— аспект (грань),, , —конъюнкции литералов. Для того чтобы отделить аспект от антецедента, будем его подчеркивать в правилах.
Продукции предназначены для описания всевозможных преобразований исходной ситуации к некоторой ситуации .
Продукция применима к ситуациитогда и только тогда, когда , где —подходящая подстановка вида
{t1/1, …, tn/n},
где ti— термы,ui— переменные.
Например, пусть = (асе)(bес).Продукция(асХ)()—>(саХ)применима к этой ситуации, так как
(асе) = (acX){e/X},(ace) .
Заметим, что в общем случае продукция может применяться к ситуации несколькими способами, поскольку различные подстановки могут удовлетворять условию .
В дальнейшем конъюнкция литералов рассматривается как множество. Определим над ними такие операции как объединение (), пересечение (), подмножество () и дополнение (—).
Если продукция р = применима к ситуации , то р преобразует в
Будем говорить, что непосредственно выводимо из по продукцииp.
Рассмотрим пример. Если = (ace)(bec),a
тогда , где
(caX){e/X} = (cae)(bec)
Основное направление исследований в рамках регуляционных моделей состоит в определении синтаксических условий вложенности регуляционных систем друг в друга и возможности декомпозиции регуляционной системы продукций на независимые подсистемы.
Все описанные модели описываются как частные случаи предложенной алгебраической модели.
Исследование формальных моделей сопровождалось проведением серии экспериментов по созданию прикладных систем продукций для предметных различных областей.