- •Введение
- •Глава 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. Нерезолютивные методы вывода на семантических сетях
3.3. Управление процессом решения задачи
Схема управления решением задачи может быть либо формализована в самой модели знаний, либо являться внешней по отношению к ней. В первом случае мы имеем дело с процедурными знаниями, во втором - с декларативными.
Рассмотрим модель процедурных знаний, известную как рекурсивная сеть переходов (recursivetransitionnetwork(RTN)). Каждой дугеRTNприписан некоторый предикат (функция), истинное значение которого необходимо для разрешения перехода по данной дуге. На каждом такте функционирования сети производится оценка всех предикатов. При этом порядок просмотра предикатов не имеет значения. В результате определяется множество маршрутов, соединяющих начальное и конечное состояния, переходы вдоль всех дуг которых разрешены. РассмотримRTNна рис. 3. 1.
Рис. 3.1
Вершины сети соответствуют состояниям системы и образуют множество {начало, S2, S3, конец}. Переходы между состояниями помеченыTR1, TR2, TR3, TR4иTR5. ПереходуTRi приписан предикатTi(). Кроме того, с некоторыми из переходов связываются операторыAi, которые выполняются при активации перехода. Допустим, что все предикатыT1, ..., T5оказались истинными. В этом случае все маршруты, связывающие вершину-начало и вершину-конец, будут разрешены и все операторыА2, А3, А4, А5будут выполнены. При этом оговаривается, что порядок выполнения операторов устанавливается согласно возрастанию их индексов. С другой стороны, если, например, ложен предикатТ2, то будет активирован единственный маршрут(TR1, TR5)и возможно единственное действиеA5. Таким образом, управление выводом вRTNреализуется посредством включения управляющей структуры в модель знаний.
Сеть RTNявляется примером модели знаний со встроенной детерминированной процедурой управления. В графе И-ИЛИ процедура управления является недетерминированной. Пустьx1, x2, ..., xN- объекты некоторой предметной области, причем для каждого объектаxiизвестна одна или несколько процедур его вычисления через другие объекты. Обозначим черезi (xi1, xi2, ..., xit)процедуру вычисления объектаiчерез объектыxi1, xi2, ..., xit. Каждый из объектовxi1, xi2, ..., xitв свою очередь вычисляется аналогичным образом через другие объекты и т.д. Таким образом, имеется следующее функциональное отношение
xi = i (xi1, xi2, ..., xit) (3.3)
Очевидно, что если процедураiне имеет входных данных, то объектхiпредставляет некоторое фиксированное значение, или запрашивается у пользователя. В этом случае
xi = i ( ) (3.4)
Соотношению (3.3) соответствует графический фрагмент, представленный на рисунке 3.3. Двойная дужка на рис. 3.3 соответствует конъюнктивной связке вершин (связке типа "И"). Очевидно, что вполне допустимо более одной процедуры вычисления объектаxi, причем в процедуреjмогут участвовать иные аргументы, чем в процедуреi; графически это соответствует рис. 3.4.
Рис. 3.3 Рис. 3.4
Множество аргументов процедуры iиj, образуют дизъюнктивные связки (связки типа "ИЛИ"). Для вычисления объекта достаточно процедуры над одним альтернативным множеством объектов, входящих в одну общую конъюнктивную связку.
Формализуем задачу управления на функциональном "И - ИЛИ" графе. Пусть x1, x2, ..., xN- множество объектов предметной области. Пусть даны процедуры
вычисления одних объектов через другие с числом аргументов, равным соответственно n1, n2, ..., nk.
Определим состояние системы Siкак множество переменных, значения которых известны на шагеi. ПустьS0- начальное состояние,Se- конечное состояние, причем конечное состояние в общем случае будет обозначаться как
Se = {xe1, xe2, ..., xez, *}, (3.5)
где *- любое, заранее не оговариваемое множество переменных (возможно пустое), аxe1, xe2, ..., xez- множество переменных, которые обязательно должны быть определены в конечном состоянии.
Говорим, что процедура k (xk1, xk2, ..., xkm)валидна (применима) в состоянииSj, если
(xk1, xk2, ..., xkm) Sj. (3.6)
Кратко тот факт обозначается как
Sj . (3.7)
В интересах общности далее положим, что каждая процедураiвычисляет в целом более одной переменной. Ясно, что применениеi- процедуры в состоянииSj, в котором она валидна, приводит в общем случае к новому состояниюSj+1, содержащему результирующие переменные процедуры i.
Задача управления заключается в построении цепочки процедурC = <i0, i1, ..., iz >такой, которая обеспечивает достижение конечного состоянияSeиз начального состоянияS0в результате последовательного выполнения процедур изСв указанном порядке.
Рассмотрим решение этой задачи на конкретном примере. Предварительно договоримся, что обозначение
i <xi1, xi2, ..., xin|xin+1, xi+2, ..., xim> (3.8)
означает, чтоxi1, xi2, ..., xin- это входные объекты-переменные процедуры, на основании которых вычисляются выходные объекты-переменныеxin+1, xin+2, ..., xim.
Пусть задана следующая система функций:
1: <x1, x3|x4>,
2: <|x1, x2, x5>,
3: <x1, x3|x4, x6>,
4: <x2, x5|x4, x6>,
5: <x2, x7|x4>,
6: <x1, x3, x4|x6, x8>,
7: <x3, x6|x5, x7>,
8: <x5, x6|x9>.
Поставим в соответствие ей функциональный граф "И - ИЛИ", показанный на рис. 3.5. Вершины графа соответствуют объектам предметной области, а дуги маркированы таким образом, что над дугой, исходящей из вершины xiи заходящей в вершинуxj, стоят индексы функций, в которыхxiявляется входным аргументом, аxjвыходным результатом. Например, дуга(x1, x4)помечена1,3, поскольку в этих функцияхx1является входным аргументом, аx4- выходным. ПустьS0 = <x1, x3, x5>, а Se = <x7, x9, *>. Построение цепочки функцийС, выполняющей переход
(3.10)
осуществляется в два этапа.
Этап 1. Нормализация функционального графа.
Нормализация заключается в выполнении в произвольном порядке следующих операций, пока это возможно.
(О1)удаление пометок всех тех функций, для которых удалены одна или более входных вершин-переменных;
(О2)удаление всех входных дуг, инцидентных вершинам изS0;
(О3)удаление вершинxiи инцидентных им дуг таких, чтоxi Se, и не имеют выходных дуг;
(О4)удаление тех функций, которые потеряли все свои результирующие вершины-переменные. Удалению функции соответствует удаление идентификатора функции из числа пометок дуг. Если при этом некоторая дуга оказывается непомеченной, то эта дуга удаляется;
(О5)если удалена дуга, помеченная, входящая в вершинуx, то пометкаснимается со всех дуг, входящих вx, если таковые есть;
(О6)удаление (последовательное)альтернативных вершин и инцидентных им дуг. Эта операция - основная. Вершинаxявляется альтернативной, если в результате ее удаления и инцидентных ей дуг каждая вершина, в которую заходила дуга изх, может быть вычислена некоторой цепочкойСiиз состоянияS0.
Рис. 3.5.
Рассмотрим рис.3.5. Так, удаляем вершину х8согласно операцииO3. Удаляем далее входные дуги вершиныx5 S0. Получаем граф на рис.3.6, а. Вершинах2альтернативная и может быть удалена вместе с инцидентными ей дугами. Получаемый в итоге граф на рис. 3.6, б. В нем вершинах4также альтернативная. Это последнее удаление приводит к полностью нормализованному графу на рис 3.6, в.
Рис. 3.6, а Рис. 3.6, б
Рис. 3.6, в
Этап 2. Построение уровнейL0, L1, ..., Lk. ВL0войдут все вершины, которые не имеют входных дуг.
В уровеньLi (i > 0)войдут все те и только те вершиныхi, которые не вошли в уровниL0, L1, ..., Li-1и которые вычислимы произвольной функцией (ями)z, выполнимой в состоянииSi = L0L1...Li-1, т.е.
Si z. (3.11)
Так, из рис. 3.6, в устанавливаем непосредственно, что
L0 = {x1, x3, x5},
L1 = {x6},
L2 = {x7, x9}.
Теперь в каждом уровне, исключая L, каждую вершину заменяем на ту процедуру, с помощью которой она вычислялась. Это дает следующий результат
Окончательно интересующая нас цепочка Сстроится так, чтобы любая функцияt, принадлежащая уронюLm, стояла левее любой функцииq, принадлежащейLn, еслиm < n; еслиm = n, то взаимный порядок расположения функцийtиqвСроли не играет. Из этого правила, устанавливаем, например, что
C = <3, 7, 8>
суть интересующая нас цепочка.
Завершим этот параграф рассмотрением моделей знаний с алгоритмом вывода, управляемым по данным. Поскольку структура управления выводом в таких моделях явно не представлена, то нужны некоторые специальные механизмы: механизм недетерминированного выбора альтернативы (альтернативной продукции), механизм возврата (бэктрекинга) и механизм унификации. Последние два механизма рассмотрены в разделе 1.4 при описании основных понятий языка Пролог.
Механизм недетерминированного выбора альтернативы базируется на моделях, использующих так называемую эвристическую функцию оценки, введенную Н. Нильсоном. К рассмотрению этого вопроса мы приступаем в следующем параграфе.