- •Введение
- •Глава 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.1.3. Условия корректности вычислений над конъюнктивной базой данных
Пусть дано исходное состояние d0и система продукций
Рr = {рri = < qi , ri >}, i=1...n, n 0
Определение 5.НазовемРr корректнойнаd0,если не существует бесконечной последовательности применимых кd0продукций, и для любых двух результирующих ситуацийd'иd",выводимых изd0, выполненоd'=d".
Определение 6.Систему продукций назовемконфлюэнтной,если для любых состояний базыd, d',d",таких, чтои,следует, что найдетсяd'"такое, чтои[104].
В общем случае множество продукций не упорядочено, а, следовательно, любая из них может оказаться применимой к текущему состоянию базы (d).
Множество продукций < qi ,ri >,для которых найдется такая подстановка, чтоdqi, называетсяконфликтныммножеством продукций относительноd,CS{d)={<q,r >|dq},а конфликтное множество фрагментовFr(d)определяется следующим образом:
Fr(d) = {d' d <q,r> d'=q}.
Так, в описанном выше примере, на втором шаге вывода конфликтное множество фрагментов состоит из двух ситуаций, описывающих наличие следующих веществ: {{MgO,H2}, {CuO,H2}}.
Для каждой пары элементов d'иd"изFr(d)выполнено одно из следующих условий:
d'd" =, либо
d'd".
По определению, продукция может добавить любые новые фрагменты в базу, но исключать может только те, которые описаны в ее условии применимости. Поэтому если две продукции применимы к непересекающимся фрагментам базы, то применение их к этим фрагментам в любом порядке дает один и тот же результат.
Пусть d' d" —общая часть фрагментовd' иd",к которым применимыpr1 =< q1, r1 >, рr2 = < q2, r2>,соответственно. Если программыr1иr2не исключают элементы изdиd", то такие продукции можно применять кd'иd" влюбом порядке.
Если одна из продукций удаляет элементы базы, которые другая использует в условиях применимости, то, очевидно, что такие продукции невозможно применять к d'иd"в одном выводе, а, следовательно, результат вывода зависит от выбора продукции и фрагмента, что иллюстрирует рассмотренный выше пример.
В работе [104] сформулированы три достаточных в совокупности локальных условия конфлюэнтности асинхронных моделей вычислений. Для систем продукций эти условия примут вид:
д
d
pr
d''
d
pr
d'
к
d
pr1pr2
d'
d
pr2pr1
d'',
d pr1pr2
d'''
d pr2pr1
d''';
устойчивость: d D pr1, pr2 Pr,еслиpr1 pr2иd',d"такие, чтои,тоd"'такое, что
Очевидным следствием этих условий является следующая теорема.
Теорема 1.ПустьРr —система продукций такая, что каждая <q,r>Рrимеет позитивную программу. Тогда система продукций конфлюэнтна.
Доказательство.Поскольку каждая продукция содержит программу, состоящую только из операцийadd[d], которые по определению коммутативны и ассоциативны, то для позитивных программ определение вывода по продукции можно заменить на эквивалентное ему в этих ограничениях, а именно, будем говорить, чтоd1d2по продукциирr= <q,r+ >,если
,
где = {diq}. При такой модификации вывода система продукций с позитивными программами обладает свойством 1. Проверка условий 2 и 3 также очевидна, откуда следует, что система продукций конфлюэнтна. Этот класс систем продукций аналогичен реляционнымСП предложенным А. С. Клещевым.
Выполнение условий 1 и 2 исключает неоднозначность, связанную с выбором подстановки, выполнение условий 2 и 3 исключает неоднозначность, связанную с выбором продукции. Следующая теорема формулирует достаточные условия отсутствия неоднозначности второго типа.
Теорема 2:Пусть Рr— система продукций, в которой выполнено условие: для любыхpr1= <q1, r1>,pr2=<q2,r2>,pr1pr2(T(q1)T(q2) =)(T(out(r1))T(q2) =). Тогда Рr— коммутативна и устойчива.
Доказательство.Пусть выполнено условие(T(q1) T(q2)=.
Проверка условия коммутативности. Пусть имеем . Так какT(q1) T(q2)= , то существуютd'иd" такие, чтоd' = q1 1d1,d"=q22 d1 для некоторых подстановок1и2причем,d' d"=, а, следовательно,
d' d1\ d", d" d1\d'.
Тогда, по определению вывода, имеем
d3= r11 ( d') r22( d") ((d1\d')\d"),
d'3 = r22(d") r11(d') ((d1\ d")\d'), откуда следует, чтоd3=d.
Проверка условия устойчивости. Пусть Аналогично выше приведенным рассуждениям можно утверждать, что существует путь , где
Доказательствотеоремы для случая(T(out(r1))Т(q2)==)проводится аналогично.
Замечание.Система продукций, для которой на каждом шаге вывода для любой продукции <р, q>существует единственная подстановкатакая, чтоq diгдеdi— текущее состояние базы, удовлетворяет условию детерминированности. Однако проверка этого условия осуществляется на текущем состоянии базы и, следовательно, это условие невозможно проверить статически на множестве продукций независимо от базы.
Теорема 3.ПустьPr={pri}— система продукций, для которой выполнены условия теоремы 2. Если дополнительно для любыхрri =< qi,ri >, prj =< qj,rj >, i, j = 1 . . . n
T(qi) T(in(rj)) = для исходного состояния базы d0 выполнено условие: для всех подстановокi, j,еслиqiI d0иqjj d0, то qii qjj =. ТогдаPrнаd0 корректна.
Доказательствоочевидным образом следует из теоремы 2 и представляет собой модификацию для систем продукций условия корректности вычислений асинхронных программ.
Вернемся к примеру. Легко заметить, что условия теоремы 2 для него выполнены, т.е. различные продукции можно применить в такой системе внутри одного варианта вывода в любом порядке. Однако условия теоремы 3 не выполнены. Это означает, что в этой системе результат зависит от состояния базы, т.е. от выбора подстановки.