- •Введение
- •Глава 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. Формальные модели систем продукций
Среди наиболее известных формальных моделей СП следует указать реляционную модель А.С. Клещева, К-системы В.Е. Кузнецова, реляционные модели S.Vereи модель управляемой СПM.Georgeff. Яхно Т.М. была предложена алгебраическая модель СП, которая обобщает перечисленные выше модели и позволяет описывать поведение СП в самом общем виде [67,69,70].
2.5.9.1. Алгебраическая модель
Рассмотрим основанный на теории алгебраических систем формальный аппарат, который позволяет дать строгую трактовку системам продукций и исследовать свойства, влияющие на эффективность поиска решения в них.
2.5.9.1.1. Основные определения
Введем понятия из теории моделей в том объеме, в котором они понадобятся для дальнейшего изложения. Согласно терминологии работы [129], многосортная алгебра A= <(sA)sS, (fA)fF> состоит из семейства множеств-носителейsAи семейства частичных функцийfA:
fA : s1A s2A ... sn-1A snA, n0,
Сигнатура = (S, F)состоит из непустого множестваS —символов для обозначения индексов множеств-носителей, называемых также сортами, и непустого множестваFфункциональных символов, каждому из которых приписана схема отображения
f : s1 s2 ... sn-1 sn, n0,
означающая запись арности функции, сортность ее аргументов и результата.
Для сигнатуры =(S,F)многосортная алгебраA= <(sA)sS, (fA)fF> называется-алгеброй, если схемы отображений для всехf Fсогласованы с соответствующими отображениямиfA.
Пусть задана сигнатура =(S,F).С каждым сортомs Sсвяжем счетное множествоXsпеременных и определим множество термовTRи функциютип : TR—>Sследующим образом:
всякая переменная х Xsесть терм, причемтип(х)=s;
всякий нульарный функциональный символ (константа) f Fсо схемой отображенияf:х sесть терм, причемmun(f) = s;
если f Fимеет схемуf : s1 ... sn-1 sn и t1, t2, …, tn-1— термы, гдеmun(t1) = s1, ..., mun{tn-1} = sn-1, то f(t1, t2,... , tn-1)— терм,mun(f(t1, t2,..., tn-1)) = sn.
Заметим, что везде в дальнейшем предикатные символы рассматриваются как функциональные со схемой отображения в специальный выделенный сорт BOOL ={0,1}.
В дальнейшем считаем заданными сигнатуру Σ = (S, F) и Σ –алгебру A=<(sA)sS, (fA)fF>.
Определение 1.Назовемфактомупорядоченный список вида(fA,e1,...,en),
где f F, f : s1 s2 ... sn-1 sn, ei TR, mun(ei) = si, i = 1...n.
В этих обозначениях ситуациейназовем конечную конъюнкцию фактов. В дальнейшем черезDбудем обозначать множество всевозможных ситуаций. Заметим, что понятие ситуации соответствует понятию текущего состояния базы данных или рабочей памяти.
Проиллюстрируем введенные понятия простым примером. Рассмотрим алгебраическую систему
A = < (R, BOОLA), (+, -, *, ) >,
где R —множество вещественных чисел,BOOLA={0,1};+, —, *,— обычные операции и отношения над числами. Переменные будем обозначать буквамиx, у, z.Тогда уравнениех+у =5запишется в виде следующего факта:(+, x, y, 5), а система соотношенийх+y=5, y 0, х 3 в виде ситуации:
d0 = (+, x, y,5) (, у, 0,1) (, 3, x, 1)
Если все еi, (i=1...n) в факте суть константы, то факт назовем терминальным. Поскольку среди фактов ситуации могут быть нетерминальные, то, в общем случае, ей соответствует неединственный набор множеств носителей алгебраической системы.
Для простоты изложения в дальнейшем ограничим термы в определении факта константами и переменными, что не нарушает общности изложения, поскольку термы с функциональными символами могут быть записаны в ситуации без них увеличением числа переменных. Например, отношение х+ у 2запишется в виде(+, х, у, z)(, z, 2,1).
Определенная таким образом ситуация представляет собой множество конъюнктивно-связанных фактов, и поэтому в дальнейшем будем обращаться с нею как с множеством, используя операции объединения , пересечения, разности \ и отношение включения.
Обозначим через var{d)множество имен переменных, входящих в ситуациюd,а черезT(d)={mun(x)xvar(d)} —множество типов переменных, входящих в факты ситуацииd.
Традиционным образом введем понятие подстановки
= {t1/v1, t2/v2, ..., tm/vm},
где ti —термы,vi— переменные,mun(ti) = mun(vi), i = 1...т.Записьd означает результат одновременной замены каждого вхождения переменнойvi,вdна соответствующий термti.
Подстановку = {x1/y1, x2/y2, ..., xm/ym}, гдеxi, уi, (i = 1...m)— переменные, назовем алфавитным вариантом. Для каждого алфавитного варианта определена обратная к нему подстановка -1при условии, что между переменными определено взаимно - однозначное соответствие.
Определение 2.Две ситуацииdиd'назовемэквивалентными (dd'),если найдется алфавитный варианттакой, что
d d' и d' d -1.
Пусть, например, задана подстановка ={3/x, z/y}.Тогда ее применение к ситуацииd0,приведенной выше, дает
d0 = (+, 3, z, 5) (, z, 0,1) (, 3, 3, 1).
Очевидно, что относительно терминальных фактов, каким, например, является (,3,3,1), в заданной алгебраической системе всегда можно говорить, истинны они или ложны. Все истинные терминальные факты опускаются при дальнейшем рассмотрении, так как они являются тавтологиями. Таким образом, ситуацияd0 эквивалента ситуации
d0 = (+, 3, z, 5) (, z, 0,1).
Если при подстановке появляется ложный терминальный факт, то считается, что подстановка неприменима к заданной ситуации.