Продукционная модель знаний
В продукционной модели база знаний представлена совокупностью правил вида
``ЕСЛИ --- ТО''. В системе, основанной на продукционной модели, кроме базы
знаний есть еще, как минимум, две компоненты: 1) механизм логического вывода
и сопоставления; 2) база фактов или рабочая память, содержащая данные,
касающиеся конкретных задач, и результаты выводов, полученные на их
основании. В классической продукционной модели части условий могут
соединяться только связками И. Метод продукций был впервые предложен в 1936
году Постом. Первое его практическое использование связано с теорией
формальных грамматик Хомского (1963). С 1970-х широко используется
при разработке ЭС.
Механизм логического вывода может быть трех типов: прямой, обратный и
двунаправленный. Логический вывод в системе продукций удобно изображать
в виде И/ИЛИ-графов. И/ИЛИ-граф вывода строится следующим образом: каждому
правилу сопоставляется И/ИЛИ-подграф-дерево с корнем-заключением, листья
которого либо факты, либо корни других И/ИЛИ-подграфов-деревьев. Ветви
И/ИЛИ-подграфа-дерева, сопоставленные частям условия, связанных связкой И,
объединяются дугой.
При прямом выводе отправными точками служат представленные факты.
Из этих фактов выводятся новые данные, которые используются как
дополнительные отправные точки. Процесс вывода продолжается до тех пор,
пока не будет получено заключение, требующее подтверждения, или не будут
получены все возможные выводы. Для такого вывода характерно большое
количество получаемых данных, не имеющих прямого отношения к
заключению, выводимость которого проверяется. Преимущество обратных выводов в
том, что строятся только те части И/ИЛИ-графа, которые имеют отношение к
заключению, но если отрицание или утверждение невозможны, то порождение
И/ИЛИ-графа лишено смысла. В двунаправленных выводах сначала оценивается
небольшой объем полученных фактов и выбирается гипотеза, а затем
запрашиваются данные, необходимые для принятия этой гипотезы.
Различают продукционные системы, просто добавляющие получаемые при выводе
данные к базе фактов, и системы, прибавляющие с удалением и замещением ранее
присутствовавших в базе фактов.
Рассмотрим следующий пример. Пусть база знаний системы состоит из следующих
правил:
(R1) A -> E
(R2) B -> D
(R3) H -> A
(R4) E & G -> C
(R5) I & K -> A
(R6) E & K -> B
(R7) D & E & K -> C
(R8) G & K & F -> A. Эту базу знаний можно изобразить при помощи следующих
И/ИЛИ-деревьев:
E D A -- C B
| | / | \ / \ |
1| 2| 3/ 5& 8& 4& 7& 6&
| | / / \ /|\ / \ /|\ / \
A B H I K G K F E G DEK E K.
Требуется проверить выводится ли C из фактов H и K. Построим сначала прямой
вывод:
H
3|
A
1|
E K
6\ /
B
2|
D E K
7\|/
C.
Обратный вывод будет таким:
C
4/ \7
/ \
/\ /|\
E G D E K
1| | 2|
A * B
3| 6/|
H E K.
Работа механизма логических выводов состоит из однообразных элементарных
циклов. Каждый элементарный цикл состоит из последовательности из трех шагов:
1) Применить правила к известным фактам из базы фактов. Если правила содержат
переменные, то необходимо сначала привести правила в соответствие с
фактами путем процедуры унификации;
2) Выбрать такие правила, которые следует выполнить для эффективного решения
задачи;
3) Заключения, полученные на 1-м шаге, использовать для модификации базы
фактов.
Механизм обратного вывода, как правило, эффективнее и используется чаще
прямого.
Программирование на языке Пролог фактически означает работу с продукционной
системой с обратными выводами. Разница между этими системами заключается в
том, что в классической продукционной модели логический вывод основывается
во многом на разнообразных эвристиках, в отличие от четких математических
правил вывода в Прологе. Хотя продукционные системы теоретически не
ограничены рамками предложений Хорна логики предикатов 1-го порядка, на
практике выход за эти рамки сильно снижает и без того низкую эффективность
подобных систем. Широкое использование продукционной модели знаний и
связанных с ней систем обусловлено их более ранним появлением, по сравнению
с системами, основанными на логической модели, возможностью двунаправленных
выводов и характерным для методов искусственного интеллекта тяготением к
эвристикам.
В продукционных системах можно отметить следующие сильные стороны:
- простота создания и понимания отдельных правил;
- модульность правил (их можно менять, добавлять, удалять по отдельности);
- простота механизма логического вывода.
Слабые стороны продукционных систем:
- сложность оценки целостного образа знаний;
- крайне низкая эффективность обработки;
- отличие от человеческой структуры знаний.
Наиболее известны следующие экспертные системы, основанные на продукционной
модели: DENDRAL, MYCIN, GPS, SHRDLU, OPS (инструментальное средство для
создания экспертных систем), HEARSAY (распознание речи), PROSPECTOR (оценка
перспективности горнорудных месторождений).
Большинство продукционных систем можно заменой механизма логических
выводов естественным образом трансформировать в программы на Прологе.
Последнему примеру соответствует Пролог-программа:
H. % F1
K. % F2
E :- A. % R1
D :- B. % R2
A :- H. % R3
C :- E,G. % R4
A :- I,K. % R5
B :- E,K. % R6
C :- D,E,K. % R7
A :- G,K,F. % R8, и запрос ?-C. Линейное резолютивное дерево вывода будет
здесь следующим:
?-C
|R4 \R7 R2 R6 R1
E,G D,E,K--->B,E,K--->E,K,E,K--->A,K,E,K
|R1 |R3
A,G ------ H,K,E,K
/R3 \R5 \R8 |F1
H,G I,K,G G,K,F,G K,E,K
|F1 | | |F2 R1 R3 F1
G * * E,K---->A,K--->H,K--->K
| |F2
* @.
Хотя скорость выполнения пролог-программ намного выше скорости работы
соответствующих им продукционных систем, они имеют ряд очевидных недостатков,
которых продукционные системы лишены: чувствительность к порядку правил,
возможность зацикливания на бесконечном поиске одной и той же подцели.
Двунаправленный вывод в системе продукций можно проиллюстрировать на
примере системы HEARSAY. Вывод в ней связан с понятием доски объявлений, на
которой в определенном порядке выписывают гипотезы. С правой стороны доски
объявлений снизу-вверх реализуется восходящий вывод, т.е. в самом низу
записывают гипотезы, основанные на фактах, выше --- гипотезы, основанные на
выдвинутых уровнем ниже гипотезах, и т.д. Переход от гипотез более низкого
уровня к гипотезам более высокого уровня задается правилами продукционной
системы. На самом низком уровне расположены гипотезы фонемы, на следующем ---
гипотезы слога, на следующем --- слова, на следующем --- словосочетания и на
последнем --- предложения. Образование предложения из последовательности
звуковых сигналов не всегда проходит успешно. Как правило, возникает очень
большое число гипотез предложений с высокой вероятностью их достоверности.
Поэтому, необходимо использовать знания по грамматике и контексту с тем,
чтобы уменьшить число кандидатов на каждом шаге вывода. Для этого
используется нисходящий вывод, который записывается в левой части доски
сверху-вниз в обратном порядке, т.е. от гипотез предложения до гипотез фонем.
Как и во всех продукционных системах, главной проблемой HEARSAY является
способ выбора порядка применения правил.
Продукционные системы часто используются в комбинации с фреймовой
моделью знаний. Это, в частности, имеет место в развитии системы HEARSAY.
Постепенно вытесняются системами с логической моделью знаний. Например,
система MYCIN была переписана на Пролог, что привело к значительному росту
ее эффективности и гибкости.
Фреймовая модель знаний
Фреймовая (frame --- рамка) модель, или модель представления знаний,
основанная на теории М.Минского (Marvin Minsky, MIT, 1975 год),
представляет собой систематизированную в виде единой
теории психологическую модель памяти
человека и его сознания. Основа этой теории --- это понятие фрейма. Фрейм
--- это структура данных для представления некоторого концептуального
объекта. Информация, относящаяся к этому фрейму, содержится в слотах
(составляющих фрейма). Все фреймы взаимосвязаны и образуют единую фреймовую
систему, в которой объединены декларативные и процедурные знания. Пример
фрейма аудитории:
Фрейм аудитории
Потолок Название: 632
Пол Вместимость: 15-30
Задняя стена Назначение: чтение лекций
Левая стена Передняя стена Правая стена
| | |
v v v
Фрейм левой стены Фрейм передней стены Фрейм окна
Центр Центр Высота: 240см ...
Левая сторона Длина: 7.5м
Правая сторона
|
v
Фрейм двери.
Теория фреймов основана на психологических понятиях, касающихся понимания
того, что мы видим и слышим. В основе ее лежит способ восприятия фактов
посредством сопоставления полученной извне информации с конкретными
элементами и значениями, а также с рамками, определенными для каждого
концептуального объекта в нашей памяти. Структура, определяющая эти рамки,
и называется фреймом. Поскольку между различными концептуальными объектами
имеются некоторые аналогии, то образуется иерархическая структура с
классификационными и обобщающими свойствами. Собственно она представляет
собой иерархическую структуру отношений типа ``абстрактное --- конкретное''.
Сложные объекты представляются комбинацией нескольких фреймов, т.е. фреймовой
сетью. Каждый фрейм может дополняться связанными с ним фактами и процедурой,
обеспечивающей выполнение запросов к другим фреймам.
Как было отмечено ее автором, фреймовая теория --- это скорее теория
постановки задачи, чем теория для получения результатов. Минский следующими
словами обрисовал ее основные положения.
``Суть этой теории заключается в следующем. Когда человек попадает в новую
ситуацию (или радикально изменяет свое отношение к текущим обстоятельствам),
он вызывает из своей памяти основную структуру, называемую фреймом (рамкой).
Фрейм --- это единица представления знаний, запомненная в прошлом, детали
которой при необходимости могут быть изменены согласно текущей ситуации.
Фрейм представляет собой структуру данных, с помощью которой можно, например,
описать обстановку в вашей комнате или место, где вы хотите отпраздновать
рождение ребенка. Каждый фрейм может быть дополнен различной информацией. Эта
информация может касаться способов применения данного фрейма, последствий
этого применения, действий, которые необходимо выполнить, если не оправдается
прогноз и т.п. Каждый фрейм можно рассматривать как сеть, состоящую из
нескольких вершин и отношений. На самом верхнем уровне фрейма представлена
фиксированная информация: факт, касающийся состояния объекта, который обычно
считается истинным. На последующих уровнях расположено множество так
называемых терминальных слотов (терминалов), которые обязательно должны быть
заполнены конкретными значениями и данными. В каждом слоте задается условие,
которое должно выполняться при установлении соответствия между значениями.
[...] Соединив множество фреймов отношениями между ними, можно построить
фреймовую систему. Наиболее важный результат такого построения проявляется в
возможности преобразования фреймов в одной системе. Фреймы используются для
экономичного проведения различных расчетов и обработки изображений.
При анализе видимого объекта различные фреймы одной системы описывают его
с разных углов зрения и преобразование от одного фрейма к другому показывает
результат перехода от одного пункта наблюдения к другому. Что касается
фреймов, не связанных со зрительными ощущениями, то различие между фреймами
одной системы указывает на какие-либо действия, причинно-следственные
отношения или изменения концептуальной точки зрения и т.п. В одной системе
различные фреймы могут иметь общие терминалы. Это серьезный момент, на
который следует обратить внимание, поскольку благодаря ему возможно
связывание информации, полученной с различных точек зрения.''
Рассмотрим пример применения теории фреймов к анализу видимых объектов.
Общий фрейм арки может быть получен при удачном сопоставлении с аркой
нескольких фреймов, описывающих ее с различных углов зрения. Например, вид
спереди на арку следующий
-------- ---
| ---- | | |
| | | |, а вид сбоку -- | |
--- --- ---.
Основные особенности организации фреймовой системы
(1) Использование базовых типов. Фреймы для новых состояний строятся
на основе выделенных для представления данной ситуации исходных или
базовых фреймов. Структура внутреннего устройства фреймов позволяет
им совместно использовать одинаковые части друг друга, что позволяет
использовать информацию, полученную одним из фреймов всем фреймам
системы.
(2) Использование процесса сопоставления. Процесс, в ходе которого
проверяется правильность выбора фрейма, называется процессом
сопоставления. Обычно этот процесс осуществляется в соответствии с
текущей целью и значениями, содержащимися в данном фрейме. Иными
словами, фрейм содержит условия, ограничивающие значения слота, а
цель используется для определения, какое из этих условий, имея
отношение к данной ситуации, является релевантным. При неудачном
сопоставлении сначала происходит попытка путем изменения значений
по умолчанию ``подогнать'' фрейм под ситуацию, если же это не помогает,
то происходит передача управления другому подходящему фрейму.
(3) Использование иерархической структуры. Фрейм обычно соответствует
представлению общего понятия с классификационной иерархической
структурой. (см.рис).
- передвигаются
Животные - едят
/ \ - дышат
/ \
имеют клюв - / \ - имеют плавники
Птицы Рыбы - плавают
/ / \ - имеют жабры
/ / \
/ / \ - нерест в реке
Страус Акула Лосось - съедобный
- не летает - кусает
- длинные ноги - опасна
Особенность такой иерархической структуры заключается в том, что
информация об атрибутах, которую содержит фрейм верхнего уровня,
совместно используется всеми фреймами нижних уровней, связанных с
ним. Например, атрибут ``животное передвигается'' является общим для
птиц, рыб, акул и т.п. Подобная структура позволяет сравнительно просто
систематизировать и запоминать схожие понятия, добавлять новые понятия
в соответствующие позиции иерархии.
(4) Использование межфреймовых сетей. Запоминание концептуального объекта,
имеющего классификационную иерархическую структуру, легко вписывается
во фреймовую модель. Но в случаях, когда процесс сопоставления
закончился неудачей, возникает необходимость поиска подобного фрейма.
Такой поиск, осуществляемый с использованием указателей различий,
возможен благодаря соединению фреймов, описывающих объекты с небольшими
различиями, с данными указателями и образованию сети подобных фреймов.
На следующем рисунке показан пример сети подобия Уинстона.
Скамейка
/ - нет спинки, слишком широк
Стул
/ \ - нет спинки, слишком высок
/ Табурет в баре
/ - слишком велик, нет спинки
Стол
\ - выдвижной ящик
Письменный стол
\ - нет подставки для ног
Кухонный стол
Если при сопоставлении фрейма ``стул'' выяснилось, что объект слишком
велик, то с помощью указателя различия ищем фрейм ``стол'' и т.п.
(5) Использование значений по умолчанию. Когда человек рассматривает нечто
и думает о том, что бы это значило, или мысленно представляет себе
что-то и думает, что бы это значило, то данный процесс можно
представить как распределение конкретных значений между терминальными
слотами фрейма. При этом в случае мысленного представления пределы,
касающиеся распределения этих значений, очень широки. В таких случаях
предполагаемое значение называется значением по умолчанию. Например,
при чтении предложения ``Джон взял мяч'' воображение читателя рисует не
абстрактный мяч, а вполне конкретный, например, мяч для игры в теннис.
Кроме того, этот мяч должен в его сознании обладать определенными
атрибутами, например, цветом, массой и размером, значения которых
подразумеваются по умолчанию, на основании личного опыта читателя.
Подобные значения слабо связаны со слотами и далее заменяются на
достоверную информацию. Выводы, основанные на значениях по умолчанию,
называются выводами по умолчанию. Они позволяют восполнить недостаток
информации и продолжить получение вывода, хотя их использование может
приводить к ошибочным заключениям.
(6) Использование отношения ``целое-часть'' в иерархии фреймов, наряду
с отношением ``абстрактное-конкретное'', что порождает две
взаимосвязанные иерархические структуры. Например, фрейм ``Аудитория''
--- это конкретизация абстрактного понятия ``Помещение'', но этот же
фрейм является частью целого фрейма ``Здание института''.
(7) Классический вывод организуется на основе взаимодействия фреймов друг
с другом через присоединенные процедуры.
Структуры данных фрейма
Фрейм представляется на компьютерном уровне определенной структурой данных,
включающей в себя следующие компоненты:
1. Имя фрейма. Это идентификатор, присваиваемый фрейму, фрейм должен иметь
имя, уникальное в данной фреймовой системе.
2. Слоты. Фрейм может состоять из произвольного числа слотов, причем
несколько из них обычно определяются самой системой для выполнения
специфических функций, а остальные определяются пользователем. Среди
специальных слотов можно выделить слоты, указывающие на фрейм-родитель и
дочерние фреймы, слоты дат создания и модификации, слот комментария. Каждый
слот должен иметь имя, уникальное среди прочих слотов фрейма.
3. Указатели наследования. Они касаются только фреймовых систем
иерархического типа и показывают, какую информацию об атрибутах слотов
во фрейме верхнего уровня наследуют слоты с такими же именами во фрейме
нижнего уровня. Типичные указатели наследования --- это Unique (уникальный),
Same (такой же), Range (диапазон), Override (перекрытие). Unique
показывает, что каждый фрейм может иметь слоты с различными значениями,
Same --- что все слоты должны иметь одинаковые значения, Range --- значения
слотов нижнего уровня должны находиться в пределах, указанных значениями
слотов фрейма верхнего уровня, Override --- значением слота нижнего уровня
по умолчанию является значение слота верхнего уровня, но значение по
умолчанию можно переопределить.
4. Типы данных для слотов. Типичные типы данных во фреймовой системе ---
это указатель на фрейм, целые и вещественные числа, логические величины,
указатель на присоединенную процедуру, текст, список, таблица и выражение.
5. Значения слотов. Они должны соответствовать типу слотов и наследованию.
6. Демоны. Демоном называется процедура, автоматически запускаемая при
выполнении некоторого условия. Демоны запускаются при соответствующем
обращении к соответствующему слоту. Например, один демон может запускаться
при занесении нового значения в слот, другой демон --- при считывании
значения, третий --- при стирании и т.п. Демоны --- это разновидности
присоединенных процедур.
7. Присоединенные процедуры. Указатели на них могут быть значениями слотов.
Эти процедуры запускаются по сообщениям, переданным из других фреймов. Они
являются примером процедурных, недекларативных знаний.
Языки управления фреймовыми системами
На основе теории фреймов был создан ряд языков представления знаний.
Например, в языке FMS каждый фрейм описывает один концептуальный объект, а
конкретные свойства этого объекта и факты, относящиеся к нему, описываются в
слотах --- структурных элементах данного фрейма; поскольку концептуальному
представлению свойственна иерархичность, целостный образ знаний строится в
виде одной фреймовой системы, имеющей иерархическую структуру. Каждый
фрейм может иметь специальный слот, содержащий присоединенную к нему
процедуру, использование которой может организовать логический вывод в
системе. Механизм управления выводом в FMS-системе организуется так. Сначала
запускается одна из присоединенных процедур некоторого фрейма, затем
посредством пересылки сообщений последовательно запускаются присоединенные
процедуры других фреймов и таким образом осуществляется вывод. Отсюда
следует, что база знаний должна быть определена так, чтобы правильно
выполнять вывод. В FMS нет встроенного механизма вывода и поэтому задачи
написания соответствующих присоединенных процедур и выбора порядка их
взаимодействия должны решатся пользователем.
В продукционных или логических системах, использующих фреймовую модель
знаний, механизм присоединенных процедур не используется.
Фреймовые системы и объектно-ориентированное программирование
Современные объектно-ориентированные языки программирования, например,
Си++, обладают почти всеми возможностями фреймовых систем. В них
понятию фрейма соответствует понятие объекта класса, слотам --- свойства
объекта, присоединенным процедурам --- методы объекта. Примерами демонов
в Си++ являются конструкторы и деструкторы. Основной стиль программирования
с использованием объектно-ориентированного подхода --- это обработка
сообщений, что соответствует методике получения выводов во фреймовой системе.
Можно сказать, что ООП --- это практичная реализация большей части
возможностей фреймовых систем. Отличия системы представления знаний,
основанной на теории фреймов, от объектно-ориентированных сред
программирования:
1) во фреймовых системах более развиты способы наследования;
2) в объектно-ориентированных средах прямых возможностей по использованию
демонов практически нет, однако, учитывая, что работа с полями объекта
происходит, как правило, не непосредственно, а через методы, можно
считать, что это отличие чисто конструктивное и нефункциональное, т.е.
в объектно-ориентированных средах можно реализовать все возможности
демонов фреймовых систем.
Модели знаний на основе семантических сетей
Изначально семантическая сеть была задумана как модель представления
структуры долговременной памяти в психологии.
Стандартного определения семантической сети не существует, но обычно под
ней понимают систему знаний, имеющую определенный смысл в виде целостного
образа сети, узлы которой соответствуют понятиям, а дуги --- отношениям между
объектами. Все возможные семантические сети можно рассматривать как части
одной гигантской семантической сети.
Пример простейшей семантической сети, соответствующей по смыслу предложению
``Петя --- мальчик'':
Петя -----есть-----> мальчик.
Эта сеть состоит из двух узлов ``Петя'' и ``мальчик'' и дуги ``есть''.
Следующий пример более сложной семантической сети соответствует предложению
``Иван на протяжении периода времени с октября 1980 года по ноябрь 1985 года
владел автомобилем марки 'Запорожец'{}''.
------------>- Множество
/ s/ |s \s
/ Человек Состояние Физический объект
| s/ |s \s
| Мужчина Владеет Автомобиль
| e| |e |s
| Иван <-владелец--- T ---объект- Малолитражка
| / \ \ |e
| начало/ \конец -> 'Запорожец'
| / \
| Октябрь Ноябрь
| 1980г 1985г
| \e e/
\ s \ /
<---------------- Время
Эта семантическая сеть содержит дуги s, e, ``владелец'', ``объект'',
``начало'', ``конец''. Дуги s и e означают соответственно ``быть
подмножеством'' и ``быть конкретизацией понятия''. Узел T соответствует
конкретизации состояния ``владеть''.
Как правило, любую семантическую сеть можно легко представить во фреймовой
модели знаний.
Вывод в модели знаний, основанной на семантической сети, строится по
запросу, представляющему собой часть семантической сети, в нескольких
узлах или дугах которой стоят неопределенные значения, которые следует
определить в результате вывода. Например, запрос ``Какой мужчина владеет
'Запорожцем'?'' к предыдущей семантической сети будет таким:
Мужчина Владеет Малолитражка
e| |e |e
? <-владелец--- T? ---объект--> `Запорожец`.
Модель знаний на основе семантической сети наиболее широко используется
в исследованиях по проблемам понимания языка.