- •Введение
- •Глава 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.2 Логический вывод
Наиболее полно изученными исчислениями в математической логике являются исчисления высказываний и исчисления предикатов первого порядка [62]. С каждой формулой в этих исчислениях связывается понятие интерпретации (приписывание истинностных значений), через которое определяются такие понятия, как противоречивость, непротиворечивость и общезначимость формул. Логическое следствие определяется следующим образом. Формула G есть логическое следствие формулF1, F2,..., Fn, тогда и только тогда, когда для любой интерпретацииI, если формулаF1 F2...Fnистинна вI, тоGтакже в ней истинна [62].
Логическое следствие получается в результате применения логических правил вывода. Такие правила вывода обладают универсальной истинностью и могут применяться либо для установления истинности некоторого утверждения, либо для порождения новых заключений. В исчислении предикатов первого порядка зафиксировано несколько правил вывода (примером может служить известное правило — modusponens).
В общем случае можно сказать, что рассуждения в исчислении предикатов монотонны — мы никогда не отказываемся от полученных заключений, если становится истинным некоторый дополнительный факт. В этом смысле они отличаются от рассуждений на основе здравого смысла.
Такие исчисления с фиксированным набором логических правил вывода обычно называют чистыми, или логическими, а вывод в них — логическим выводом.
Формулировка задачи в исчислении предикатов рассматривается как теорема. Многие проблемы могут быть сформулированы как проблемы доказательства теорем. Именно это и определило стремление найти общую автоматическую процедуру доказательства теорем. Важный прогресс в этой области был достигнут с момента разработки метода резолюций, который оказался легкодоступным для реализации на ЭВМ. Именно поэтому исчисление предикатов является одним из основных исчислений, ориентированных на построение программ, обладающих интеллектуальными способностями [25].
Однако попытки автоматизации решения разнообразных классов задач в рамках классической логики иногда приводят к громоздким и неестественным формулировкам, превращая простые задачи в практически не решаемые. В частности, именно с этим обстоятельством связан некоторый скепсис в отношении применимости математической логики.
И тем не менее именно логические исчисления положили основу логическому программированию и сделали популярным язык Пролог [25].
2.5.3 Прикладные модели
Идя далее по пути ослабления ограничений, можно ввести исчисления, в которых вместо универсальных правил логического вывода используются проблемно-ориентированные правила вывода. Примером таких исчислений являются системы подстановок.
Система подстановок задается некоторым алфавитом С = {ci, c2,..., сn} и базисными подстановками где,— некоторые (возможно, пустые) слова в алфавите С. Каждую подстановку можно рассматривать как правило вывода Р (х, у), считая, что Р (х,у) истинно, если слово у получается из слова х посредством подстановки в х словавместо какого-либо вхождения слова. Этот класс исчислений привел к активно развиваемым системам переписывания термов [102].
К данному классу можно отнести исчисление, введенное Э.Постом, которое он назвал системами продукций [118]. Система продукций Поста задается своим алфавитом и системой подстановок каждая, из которых называется продукцией и имеет вид
aiWWbi, (i= 1...n),
где ai, bi — слова в алфавите С. Пусть некоторое слово L начинается словом аi. Выполнить над L продукцию — это значит вычеркнуть из L начальный отрезок аi, и к оставшемуся слову приписать справа слово bi. Например, применяя к слову aba продукцию abW —> Wc, получим слово ас. Существуют теоремы, показывающие, что любую систему подстановок можно "вложить" в систему продукций [28]. Характерным для систем продукций Поста является ограничение на форму самих подстановок.
К этому же классу исчислений можно отнести и порождающие грамматики, введенные Н.Хомским [7]. Накладывание ограничений на левые и правые части правил привело к классификации грамматик и соответственно к классификации языков, порождаемых данными грамматики. При этом в фокусе исследований основной являлась проблема распознавания того, принадлежит ли заданное слово языку, порождаемому некоторой заданной грамматикой. Основная сфера применения данного формализма — это анализ формальных и естественных языков [7].
Общим для исчислений указанного вида, называемых иногда нелогическими, является их использование в качестве формальных систем, для которых исследуются математические аспекты и свойства. Так, разные варианты систем подстановок интенсивно изучались в теории алгоритмов, а в программировании использовались в виде разного рода грамматик, в основном для описания синтаксиса языков программирования.
Параллельно с исследованиями, связанными с разработкой нелогических исчислений, в ИИ к середине 70-х годов осознана необходимость разработать средства в инструментальных системах для представления знаний, поскольку сами по себе общие методы поиска решений не привели к практическим успехам. В качестве одной из форм для представлений эвристических знаний были предложены правила вида
условие —> действие
в которых левая часть описывает некоторую ситуацию, а правая — те действия или заключения, которые надо сделать, если имеет место описываемая ситуация.
Общая постановка задач при использовании множества правил формулируется следующим образом. Задается исходное и целевое состояние задачи. Система сама на основе заложенных в нее правил ищет возможные пути решения перевода исходного состояния в целевое. Знания о предметной области задают множество возможных преобразований в пространстве ситуаций, каждое из которых ограничено соответствующими условиями применимости данного преобразования в той или иной ситуации. Такие правила стали называть продукциями, а системы, использующие их для описания знаний — системами продукций [83].
В архитектуре программных систем продукций традиционно выделяют три основных компонента: базу данных — память для хранения текущей информации о решаемой задаче, базу знаний — множество правил (продукций) и интерпретатор, выполняющий преобразование базы данных по заданным правилам.
Такая форма представления информации была принята в некоторых психологических моделях мышления человека. Исследования процессов принятия решений человеком показали, что, рассуждая, человек использует правила вида условие —> действие. А.Ньюэлл первым предложил использовать такое представление знаний для моделирования на ЭВМ процесса принятия решений [114].
Легко заметить, что предлагаемая форма для представления знаний выглядит необычайно похожей на системы подстановок. Поскольку разработки в области ИИ всегда связаны с созданием программных систем, то и для систем, поддерживающих представление знаний в виде правил, потребовалось название. Первоначально такие системы назывались по-разному: rewriting-rules systems, rule-based systems, pattern-directed inference systems, production systems. Больше всех повезло термину "системы продукций". С середины 70-х годов этот термин прочно закрепился за программными системами искусственного интеллекта, знания в которых представлялись в виде правил указанного вида.
Таким образом, в ИИ под термином "системы продукций" понимают, с одной стороны, средство представления знаний. В этом смысле его можно отнести к классу нелогических прикладных исчислений и исследовать его свойства. С другой стороны, этот термин характеризует также и конкретный стиль программирования, принципиально отличающийся от традиционного и обладающий, по сравнению с последним, рядом существенных достоинств, среди которых основными являются следующие:
универсальность метода программирования, что обеспечивает возможность создания многообразия различных проблемно-ориентированных систем продукций, различающихся средствами представления правил и обрабатываемых структур;
естественная модульность организаций знаний в системах продукций: каждая продукция представляет собой законченный фрагмент знаний о предметной области, все множество продукций может очевидным образом структурироваться разбиением на подмножества, объединяющие продукции, которые относятся к одинаковым компонентам знаний;
в значительной степени эта модульность обеспечивается независимостью каждой продукции от содержания других продукций, ограниченностью фрагмента знаний, представляемого каждой продукцией, его функциональной локальностью в общей сумме информации о предметной области. Продукции не взаимодействуют друг с другом, эффект применения каждой из них определяется изменениями, которые она производит в обрабатываемой структуре. Это обеспечивает легкость и естественность спецификации знаний, простоту их модификации и расширения;
присущая системам продукций декларативность позволяет описывать с их помощью саму предметную область, а не соответствующие процедуры обработки;
асинхронность, недетерминированность и естественная параллельность систем продукций делает их весьма перспективными для реализации на параллельных ЭВМ, вернее, для разработки вычислительных систем, рассчитанных на продукционные программы.
В то же время представление знаний в виде продукций имеет два основных недостатка, ограничивающих сферу его применения в современной практике программирования:
относительно низкая эффективность по сравнению с традиционными методами программирования. Однако этот разрыв в эффективности быстро сокращается за счет повышения уровня традиционных средств программирования (и соответствующего понижения "нормы эффективности") — с одной стороны, и прогрессом работ по развитию структуры самих систем продукций и оптимизации соответствующих базовых процессов — с другой. Кроме того, при современной мощности рядовой ЭВМ для многих приложений это различие в эффективности перестает быть значимым;
сложность или даже невозможность контроля правильности систем продукций методом воображаемой или реальной прокрутки соответствующего вычислительного процесса, что характерно для всех недетерминированных систем. У этого недостатка есть своя положительная сторона, поскольку такое свойство систем продукций навязывает программисту дисциплину, при которой контроль программы осуществляется лишь на самом высшем уровне - уровне представления знаний.
За последние годы изучение возможностей систем продукций проводится по нескольким основным направлениям. С одной стороны, это исследование общих принципов и теории, направленное на дальнейшее развитие архитектуры и мощности систем, в основе которых лежат системы продукций, с другой — разработка конкретных систем искусственного интеллекта, являющихся специализированными программными реализациями систем продукций. Все это позволяет сформулировать три основных направления исследований систем продукций, так или иначе присутствующих в большинстве проектов, которые посвящены этой тематике: теоретические, технологические и прикладные. Рассмотрению этих вопросов посвящены следующие разделы данной главы.
Что касается программных реализации систем продукций, то не ставится задача сделать полный обзор существующих систем. В настоящее время существует большое количество монографий, подробно описывающих как широко известные системы продукций типа MYCIN [121], PROSPECTOR [87], HEARSAY [60], так и менее известные, но достаточно интересные как с точки зрения технологии, так и с точки зрения представления знаний. Среди этих монографий следует отметить [49,53,61,69].