Точно Не проект 2 / Не books / Источник_1

<указатель наследования>::= unique| same| range| override

<тип данных>::= INTEGER| REAL| BOOL| STRING| TEXT| TABLE|

LISP| LIST| FRAME

<процедуры-демоны>::=<если-добавлено>| <если-удалено>|

<если-нужно>|

Другим примером фреймовой системы является язык FRL (Frame Representation Language), представляющий расширение языка Лисп. Объекты предметной области в языке FRL называются фреймами, а их свойства – слотами. Слот содержит несколько “фацет” (англ. facet – аспект, грань, сторона), характеризуемых значением. Так, предложение “Лошадь серого цвета” можно представить на языке FRL в виде: frame Лошадь, slot цвет, facet $value, value серый. В состав слота входит шесть фацет:

$value – текущее значение слота;

$require – допустимые значения фацета value; $default – значение по умолчанию для фацета value; $if-added – процедура-демон “если-добавлено”; $if-removed – процедура-демон “если-удалено”; $if-needed – процедура-демон “если-нужно”.

Каждый фрейм, создаваемый на языке FRL, содержит предварительно определенный слот ako, позволяющий наследовать значения слотов в соответствии с иерархией фреймов.

В моделях представления знаний фреймами объединяются преимущества декларативного и процедурного подходов представления знаний. Фреймовый подход широко используется на практике, о чем свидетельствует наличие развитых фреймовых языков, например, GUS, KRL, CONSUL и др. Однако во фреймовых системах отсутствует специальный механизм управления выводом. Поэтому вывод обычно реализуется с помощью процедур, встроенных во фреймы.

3.5.2. Управление выводом

Во фреймовых системах используется три способа управления выводом [37]: с помощью механизма наследования; с помощью процедурдемонов; с помощью присоединенных процедур.

Механизм наследования является основным встроенным средством вывода, которым оснащаются фреймовые системы. Он обеспечивает значительную экономию памяти и автоматическое определение значений для слотов фреймов нижних уровней.

Фреймовые системы также оснащаются набором специальных процедур, к которым относят процедуры: конструирования класса, конструирования экземпляра класса, записи значения в слот, чтения слота. Процедура конструирования класса формирует фрейм-прототип с необходимым набором слотов и соответствующими ссылками на суперклассы. Фрейм может быть связан с несколькими суперклассами. Процедура конструирования экземпляра класса позволяет формировать фреймы-примеры. Она автоматически устанавливает связь всех таких фреймов с соответствующим классом посредством is_a слота. Процедуры записи и чтения значений слотов осуществляют доступ к слотам соответствующих фреймов и позволяют пользователю ввести или определить значение соответствующего слота. Для этого, при их вызове, им передаётся имя фрейма и имя соответствующего слота. В случае если значение какого-либо слота при вызове соответствующей процедуры конструирования не задается, то автоматически вызывается процедура, позволяющая установить значения слота по умолчанию. Это часто выполняется с помощью механизма наследования. Рассмотрим некоторые особенности функционирования механизма наследования.

На рисунке 3.18 изображена простейшая иерархическая структура, в которой каждый фрейм имеет только один суперкласс.

Рисунок 3.18 – Простейшая иерархия фреймов

Каждый подкласс или экземпляр класса наследует слоты своего суперкласса. Если подкласс (экземпляр класса) и суперкласс имеют слоты, с совпадающими именами, то определения значений слотов, сделанные внутри подкласса (экземпляра класса), перекрывают определения суперкласса. Например, ответ на вопрос: “Способен ли пингвин Чилли-Вилли летать?” будет отрицательным. При поиске ответа на этот вопрос фреймэкземпляр “пингвин Чилли-Вилли” наследует все слоты фрейма “пингви-

ны”. Значение слота “способность летать” фрейма “пингвины” перекры-

вает значение одноименного слота “птицы”.

В общем случае порядок наследования определяется с помощью списка предшествований. В случае линейной иерархической схемы этот список формируется в соответствии с направлением is_a и ako связей. Для рассматриваемого случая его можно записать в виде:

(“пингвин Чилли-Вилли”, “пингвины”, “птицы”).

Более сложная ситуация возникает, если фрейм имеет несколько is_a или ako связей. В этом случае говорят о множественном наследовании. Правила формирования списка предшествований в этом случае будут сложнее. Предположим, что пингвин “Чилли-Вилли” – это персонаж мультфильма. Тогда фрейм-экземпляр “пингвин Чилли-Вилли” будет иметь две is_a связи (рисунок 3.19).

Рисунок 3.19 – Множественное наследование

При попытке установить зону обитания этого пингвина возникает двусмысленность, которая разрешается с помощью списка предшествований, формируемого с учетом иерархии фреймов. Просмотр иерархии

фреймов выполняется сначала в глубину, а затем слева – направо. Тогда список предшествований будет иметь вид:

(“пингвин Чилли-Вилли”, “пингвины”, “птицы”, “персонаж мультфильма”).

При таком способе разрешения неопределенности зона обитания пингвина по имени Чилли-Вилли – это морские побережья. Если пользователя не удовлетворяет результат наследования, то можно ввести дополнительный класс, явно указав значение соответствующего слота. Например, можно ввести класс “пингвины-мультяшки” (рисунок 3.20) и явно указать значение слота “зона обитания”. Однако это исключает возмож-

ность передачи значения слота по умолчанию и требует дополнительной памяти1).

Рисунок 3.20 – Введение дополнительного класса

В реальных ситуациях взаимосвязь фреймов оказывается значительно сложнее, чем в рассмотренных примерах. Поэтому правила формирования

1) Конечно, в данном примере требуемый результат можно получить проще. Необходимо лишь изменить порядок следования имен фреймов в слоте is_a фрейма “пингвин Чилли-Вилли”. Т.е. порядок слева направо соответствует порядку следования имен фреймов в слоте is_a или ako.

списка предшествований усложняются. В этом случае, наряду с поиском в глубину и слева направо, применяется принцип исключения из списка предшествований повторяющихся элементов. В списке всегда остается только та повторяющаяся вершина, которая встретилась последней. Например, для рисунка 3.21 список предшествований можно представить в виде:

(экземпляр, суперкласс 2, суперкласс 4, суперкласс 3, суперкласс 5,

суперкласс 1, универсальный класс).

Рисунок 3.21 – Иерархия фреймов с несколькими is_a отношениями

Данный принцип позволяет реализовать требование, заключающееся в том, что любой класс должен появляться в списке предшествований раньше, чем его непосредственный суперкласс [94]. Реализация этого требования обеспечивает передачу по умолчанию наиболее специфичных данных, что соответствует нашему интуитивному представлению о наследовании свойств. Вместе с тем применение рассмотренной процедуры наследования к иерархии фреймов, изображенной на рисунке 3.22, приведет к формированию следующего списка предшествований:

(экземпляр, суперкласс 5, суперкласс 3, суперкласс 6, суперкласс 2, суперкласс 4, суперкласс 1).

В этом списке нарушено требование, состоящее в том, что любой

непосредственный суперкласс некоторого класса должен появиться в списке предшествований раньше, чем другой непосредственный суперкласс этого же класса, расположенный правее (суперкласс 2 следует после суперкласса 3). Чтобы удовлетворить указанное требование, необходимо использовать процедуру топологической сортировки [94].

Рисунок 3.22 – Иерархия фреймов с несколькими ako отношениями

Идея такой сортировки состоит в следующем. На первом шаге составляется список экземпляров и суперклассов, которые (для рассматриваемого фрейма) достижимы посредством is_a и ako связей. Для рассматриваемого примера (рисунок 3.22) получим

(экземпляр, суперкласс 5, суперкласс 2, суперкласс 1, суперкласс 3, суперкласс 6, суперкласс 4, универсальный класс).

На втором шаге для каждого элемента полученного списка формируется список пар в соответствии с принципом, изображенным на рисунке 3.23. Данный принцип называют принципом “рыболовецкого крючка”, так как схема объединения суперклассов и экземпляров в соответствующие пары напоминает нанизывание наживки на рыболовецкий крючок. Следуя указанному принципу, для каждого элемента списка получим список соответствующих пар (таблица 3.2).

На третьем шаге просматривают элементы таблицы 3.2 и выделяют элемент, который встречается только с левой стороны пары и никогда не встречается с правой стороны. Таким элементом является “экземпляр”. Будем называть этот элемент текущим. Текущий элемент добавляется в конец списка предшествований, и все пары, в которых он встречается, вычер-

киваются. В рассматриваемом случае это пара “экземпляр–суперкласс 5”. Затем действия повторяются. Текущим элементом становится суперкласс 5, и вычеркиваются пары “суперкласс 5 – суперкласс 6” и “суперкласс 5 – суперкласс 2” и т.д. В итоге формируется следующий список предшествований:

(экземпляр, суперкласс 5, суперкласс 6, суперкласс 2, суперкласс 4,

суперкласс 3, суперкласс 1, универсальный класс).

Рисунок 3.23 – Принцип “рыболовецкого крючка”

Таблица 3.2 – Список пар

Если на некотором шаге описанной процедуры на роль текущего элемента претендуют сразу несколько суперклассов, то конфликт разрешается в пользу того суперкласса, который является непосредственным суперклассом для самого правого суперкласса, уже находящегося в списке предшествований. В рассматриваемом примере конфликт возникает между суперклассом 3 и суперклассом 4 после того, как в список предшествований будет помещен суперкласс 2. Предпочтение отдается суперклассу 4, так как он является суперклассом самого правого суперкласса, уже находящегося в списке предшествований, т.е. суперкласса 6.

Вывод значений слотов на основе наследования является, по своей сути, немонотонным, так как перекрытие значений в процессе наследования может менять истинность ранее установленных фактов. Например, из рисунка 3.18 следует, что пингвин Чилли-Вилли покрыт перьями. Однако

если мы добавим слот “покров” со значением ”пух” во фрейм “пингвины”, то исходное утверждение уже будет неправильным.

Другая возможность вывода во фреймовых системах основана на использовании процедур-демонов: “если-нужно”, “если-добавлено”, “еслиудалено”.

Процедура “если-нужно” вызывается, когда поступает запрос, требующий установления значений соответствующего слота. Данная процедура, как и значение слота, наследуется подклассами и экземплярами классов. Поэтому связывание ее с одним из суперклассов может оказать влияние на значение соответствующих слотов фреймов, расположенных ниже по иерархии. При этом процедура непосредственно не меняет значений слота, а каждый раз вычисляет его заново, учитывая определенные условия. В частности, для слота “рост” экземпляра фрейма “пингвин” (рисунок 3.18) процедура может устанавливать рост пингвина в зависимости от значения слота “вид”. Например, если значением слота “вид” является “императорский пингвин”, то вернуть значение 100 – 120см, иначе вернуть значение 40 – 50см.

Процедуры “если-добавлено” и “если-удалено” активизируются при записи и удалении значений из слота. Например, процедура “еслидобавлено” может активизироваться, когда слот “вид” получит значение (рисунок 3.18). Если новое значение – “галапагосский пингвин”, то записать в слот “красная книга” значение “да”. Очевидно, что данная процедура устанавливает ограничивающие отношения между значениями слотов “вид” и “красная книга”. Можно сказать, что процедуры “еслидобавлено” и “если-удалено” устанавливают зависимость значений одного слота от значений другого и играют роль хранителя отношений ограничения во фреймовых системах.

Третья возможность вывода во фреймовых системах основана на применении присоединенных (служебных) процедур. Имя присоединенной процедуры выступает в качестве значения слота. Присоединенная процедура запускается по сообщению, переданному из другого фрейма. Для этого может использоваться специальная функция MSG, формат вызова которой имеет вид:

MSG(<имя фрейма>,<имя слота>,<параметры>).

Данная функция обеспечивает запуск присоединенной процедуры, находящейся в соответствующем слоте соответствующего фрейма. При этом присоединенная процедура получает необходимые параметры. В свою очередь, вызванная присоединенная процедура может также передать сообщение в другой фрейм и вызвать другую присоединенную процедуру и т.д. Возникает цепочка передач сообщений от одного фрейма к другому и

возврат ответов. В итоге ответ возвращается в точку первоначального вызова функции MSG и сообщается пользователю. Таким образом, во фреймовых системах на каждый из фреймов посредством присоединенных процедур возлагаются определенные обязанности, и обеспечивается их согласованное исполнение.

В заключение отметим, что если во фреймовых системах не использовать процедуры-демоны и присоединенные процедуры, то фреймовая модель представления знаний будет соответствовать семантической сети. Использование процедурных знаний во фреймовых системах повышает их гибкость, но усложняет управление. Свое дальнейшее развитие фреймовые системы получили в системах объектно-ориентированного программирования. В главе 5 мы рассмотрим систему объектно-ориентированного программирования языка Коммон Лисп.

Вопросы для самопроверки

1.Приведите определение понятия “знание”. Объясните отличие знаний от данных.

2.Перечислите основные модели представления знаний и дайте их краткую характеристику.

3.Что понимают под формальной системой?

4.Охарактеризуйте исчисление высказываний как формальную систему.

5.Какие формулы исчисления высказываний называют общезначимыми?

6.Объясните понятие “логическое следствие” теории исчисления высказываний.

7.Сформулируйте правила вывода исчисления высказываний.

8.Запишите предложения Хорна в общем виде.

9.Охарактеризуйте исчисление предикатов как формальную систему.

10.Дайте определения следующим понятиям исчисления предикатов: терм, элементарная формула, формула.

11.Какие формулы исчисления предикатов называют выполнимыми, опровержимыми?

12.Сформулируйте правила вывода исчисления предикатов.

13.Приведите пример продукционного правила.

14.Назовите основные компоненты продукционной системы и объясните процесс вывода на основе сопоставления с образцом.

15.Что понимают под конфликтным множеством?

16.Объясните на примере схему прямого вывода на множестве продукционных правил.

17.Объясните на примере схему обратного вывода на множестве продукционных правил.

18.Объясните, что понимают под семантической сетью.

19.Какие виды отношений используют в семантических сетях?

20.Что такое “падежная рамка”?

21.Приведите пример концептуального графа.

22.Какие операции вводятся над концептуальными графами?

23.Как учитываются на концептуальных графах логические операции и кванторы?

24.Как осуществляют вывод в семантических сетях?

25.Что понимают под “фреймом”? Приведите пример фрейма.

26.Какие отношения используются в сети фреймов?

27.Объясните структуру фрейма на примере системы FMS или FRL.

28.Какие способы управления выводом применяются во фреймовых системах.

29.Объясните механизм множественного наследования.

30.Объясните принцип топологической сортировки.