- •Введение
- •Глава 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.10. Экспериментальные системы продукций
2.5.10.1. Система скип
Система СКИП является инструментальной системой, средствами которой можно конструировать проблемно-ориентированные системы продукций. Она представляет собой набор средств (функциональных и информационных), выбор и настройка, которых на заданную предметную область, дает нужную разработчику систему продукций.
Система СКИП содержит пять блоков: монитор, библиотеку интерпретаторов, компилятор, словарь и базу для хранения данных о решаемой задаче (базу данных).
Все блоки системы ориентированы на обработку продукций, которые могут храниться в виде одного или нескольких связанных файлов, называющихся в системе архивом правил. Архив правил создается пользователем на входном языке пакета (язык ПРОЗА). Библиотека интерпретаторов включает в себя несколько интерпретаторов, отличающихся друг от друга способами применения правил и структурой используемой базы данных. Для реализации предварительного этапа обработки входного текста, преобразующего символьную строку в последовательность компонент, созданы два интерпретатора: MNLECS- определяющий типы символов во входном запросе и образующий одну компоненту для каждого символа;MMLECSв отличие от предыдущего соединяет все однотипные символы в одну компоненту.
Для этапа основного анализа библиотека включает несколько интерпретаторов:
NPOISK— исходная последовательность компонент сканируется слева направо. Если найдется продукция, применяемая к текущему фрагменту, то она выполняется. При этом не происходит возврата па начало строки;
WNPOISK- аналогичен предыдущему, но с возвратом на начало последовательности компонент после применения продукции. Можно заметить, что посредством этого интерпретатора в СКИПе можно промоделировать порядок применения правил, заложенный в нормальных алгоритмах Маркова;
KNPOISK,KWPOISC— работают аналогично двум предыдущим, но начинают анализ цепочки компонент справа налево;
OSN— перебирает правила по группам. Внутри групп правила выбираются последовательно друг за другом. Переход к следующей группе правил происходит в случае, когда невозможно применить ни одно правило из текущей группы;
SETOSN— выбор правил аналогичен выбору в предыдущем интерпретаторе. Отличие в структуре используемой базы данных: считается, что компоненты образуют множество. При этом отыскиваются все возможные комбинации компонент, удовлетворяющие условиям текущей продукции, независимо от порядка их расположения.
Каждый интерпретатор библиотеки представляет собой настраиваемый модуль. При этом настройка интерпретатора состоит в том, что с ним связывается некоторый список номеров правил из архива. Выбранные и настроенные интерпретаторы задают конфигурацию проблемно-ориентированной системы продукций. Приведем пример описания конфигурации:
NPOISC = 1, 2, 4;
WNPOISCC = 10, 20, 30, 40;
OSN = GROUP, 100, 110, 120, GROUP, 20, 210, 220.
В левых частях равенств указываются имена интерпретаторов, а в правых — списки имен (номеров) продукций из архива. Каждая строка является описанием настраиваемого модуля генерируемой системы продукций. Компилятор СКИПа переводит продукции и описание конфигурации из описания на языке ПРОЗА во внутреннее, являющееся текстом на языке ПЛ/1. Такой подход обеспечивает быстродействие работы интерпретаторов. С этой точки зрения компилятopпродукций является генератором ПЛ/1 программ. Словарь системы обеспечивает хранение и доступ к словарной информации, связанной с описанием предметной области для которой конструируется проблемно-ориентированной системы продукций. Технология формирования проблемно-ориентированной системы продукций состоит в том, что разработчик описывает множество правил на языке ПРОЗА и задает конфигурацию из подмножества интерпретаторов библиотеки с привязкой их к конкретным правилам архива. Взаимодействие модулей управляется монитором, который в соответствии с конфигурацией последовательно выполняет настроенные модули и таким образом организует функционирование проблемно-ориентированной системы продукций. Общая схема формирования такой системы приведена на рис. 1.8.
В разрабатываемых в ВЦ СО АН СССР пакетах прикладных программ для задач математической физики был создан язык автоматической идентификации данных (АИДА). Полная информация о краевой задаче состоит из описания расчетной области, подобластей, вида и функций граничных условий и ряда других параметров [8].
Например, область цилиндра, отсекаемая двумя плоскостями, задается следующим описанием [9]:
Переменные R1 = 0.5;
Точки T0 = (0,0,0); T1 =(1,0,0); T3 = (-1,0,0);
Отрезок X = (T0, T1);
Плоскости Пл1 = (X, T0); Пл2 = (X, T3);
Цилиндр Цил3 = (X, R1);
Подобласть K1 = <Цил3, -Пл1, Пл2>;
С помощью пакета СКИП построен языковый процессор (компилятор), переводящий описание исходной задачи, написанное на входном языке АИДА, в структуры данных, представляющие собой особым образом организованные наборы числовых данных, которые передаются модулям пакета.
На основе СКИПа Голубевой Л.А. реализована целая серия препроцессоров к пакетам прикладных программ для задач математической физики [8].
Особый интерес с точки зрения создания систем продукций представляет собой эксперимент, в котором была сделана попытка расширить область применения СКИПа, используя его для задач проектирования интегральных схем.