Барыкин С.Г., Плотникова Н.В. Системы искусственного интеллекта

Подождите немного. Документ загружается.

1.2.

ФРЕЙМЫ ДЛЯ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ

Термин «фрейм» был предложен для обозначения описания какого-либо

объекта или явления, обладающего тем свойством, что удаление из этого описа-

ния любой его части приводит к потере свойств, характеризующих объект опи-

сания.

Фрейм чаще всего определяют как структуру данных, для представления

стереотипных ситуаций. При этом способ группирования множества конкретных

ситуаций в стереотипную, как правило, не может быть определён строго. Чаще

всего стереотипные для данной предметной области ситуации выделяет исследо-

ватель, опираясь на опыт и данные наблюдений. Неформальные знания исследо-

вателя о предметной области можно рассматривать как систему понятий, опре-

деляющих представление о конкретных ситуациях. Каждое понятие связывается

с конкретной ситуацией, а конкретные ситуации согласуются с соответствующей

стереотипной. Если понятия представляют собой неформальные знания о стерео-

типной ситуации, то фреймы – формализованные знания. Таким образом, фрей-

мы соответствуют понятиям, отражающим объекты, явления, характеристики

предметной области. Это даёт основания рассматривать фрейм как семантиче-

ский блок или модуль модели представления знаний. Модель представления зна-

ний строится в виде сети фреймов, т.е. системы определённым образом взаимо-

связанных фреймов. Поэтому в моделях представления знаний на базе фреймов

выделяют две части: набор фреймов, образующих библиотеку внутреннего пред-

ставления знаний, и механизм их преобразования, связывания и т.д. [9].

В общем случае фрейм содержит как информационные, так и процедурные

элементы, которые обеспечивают преобразование информации внутри фрейма и

связь его с другими фреймами. Важной особенностью фреймов является наличие

в информационных и процедуральных элементах незаполненных частей – слотов

(пустот, щелей). Слоты могут заполняться в процессе активизации фрейма в со-

ответствии с определёнными условиями. Это придаёт свойство адаптивности

модели представления знаний как на модульном уровне, так и на уровне всей се-

ти фреймов.

Таким образом, фреймы представляют собой декларативно-

процедуральные структуры, т.е. совокупность описаний и (в некоторых случаях)

связанных с ними процедур, доступ к которым выполняется прямо из фрейма.

Существует большое число концепций, определений и моделей фреймов. При

этом различаются не только формы записи и представления фреймов, но и в некото-

рой степени их содержательный смысл. В наиболее общем виде фреймом называют

структуру представления знаний следующего вида [5]:

()

(

)

(

){}

kkk

pgvpgvpgvn ,,.....,,,,,,,,

222111

где n – имя фрейма; v

– имя слота; g

– значение слота; p

– процедура.

Процедура является возможным, но не обязательным элементом слота. Имена

фреймов используются как мнемонические элементы для конструирования сети

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

обеспечивает связи между фреймами, их «вкладываемость» друг в друга. Различают

два типа фреймов: фрейм-прототип и фрейм-пример.

Фрейм-прототип – это интенсиональное описание некоторого множества

фреймов-примеров, а фрейм-пример – это экстенсиональное описание соответствую-

щего фрейма-прототипа.

Рассмотрим концепцию фреймов, принятую в диалоговой системе GUX. Струк-

тура фрейма имеет здесь следующий вид:

<фрейм>:: = [<имя>] <ссылка на прототип>

<слот>{<слот>}

Квадратные скобки означают необязательность элемента, так как в фрейме-

примере имя может отсутствовать; фигурные скобки означают некоторое множество

(возможно пустое) элементов; знак:: = читается «по определению есть».

Структура слота

<слот>:: = <имя слота><значение>[{<процедура>}].

В качестве примера рассмотрим упрощённую схему фрейма-прототипа понятия

ДАТА. <ДАТА> (<МЕСЯЦ> <ИМЯ>) (<ДЕНЬ> <{целые числа}>) (<ГОД>

<функция>)

<ДЕНЬ НЕДЕЛИ> <перечень {ПНД, ВТР,…, ВСК}> <функция>)

Имя фрейма-прототипа – ДАТА. В слоте МЕСЯЦ на месте значения запи-

сано ИМЯ, т.е. значением слота может быть любое буквенное выражение. Значе-

нием слота ДЕНЬ являются целые числа, причём перечень их приведён в слоте.

В качестве функции в GUX используются любые функции языка LIXP[8]. Так, в

слове ГОД с использованием LIXP могут быть организованы следующие проце-

дуры. Если во входном предложении указан год, то он вносится в поле значения

слота во фрейме-примере; если год не указан, то активизируется процедура, ко-

торая заполняет отсутствующее значение текущим годом. Такого рода функции

называются функциями, выполняемыми «по умолчанию».

В слоте ДЕНЬ НЕДЕЛИ с использованием LIXP можно организовать, на-

пример процедуры, которые при обработке входного сообщения будут вызы-

ваться автоматически, для проверки на непротиворечивость значения дня недели,

указанного пользователем, либо вычисления этого значения, если пользователь

его не указал.

Конкретный фрейм-пример фрейма ДАТА может выглядеть следующим

образом:

<IXA ДАТА> (<МЕСЯЦ> <ИЮНЬ>) (<ДЕНЬ> <5>).

Метка IXA обозначает, что данный фрейм является фреймом-примером.

Здесь заполнены только два слота. Значения остальных могут быть вычислены с

помощью соответствующих процедур.

Процедуры, включаемые в слот, принято делить на два типа: процедуры-

демоны и процедуры-слуги.

Процедуры-демоны активизируются автоматически каждый раз, когда дан-

ные попадают в соответствующий фрейм-пример или удаляются из него. Так,

процедура, встроенная в слот ДЕНЬ НЕДЕЛИ в описанном выше примере, явля-

ется типичным представителем процедуры-демона. С помощью процедур этого

типа автоматически выполняются, в частности, все рутинные операции связан-

ные с ведением баз данных и знаний. Пусть, например, база данных описывает

транспортно-складскую систему, в которой одни и те же детали в процессе обра-

ботки меняют адреса хранения. С помощью процедур-демонов общение с систе-

мой можно организовать так, что пользователь будет сообщать лишь адрес, по

которому отправляется конкретная партия деталей. Соответствующая процедура-

демон активизируется автоматически как только будет заполнен слот АДРЕСА

ПОЛУЧАТЕЛЯ соответствующего фрейма. В результате выполнения процедуры

имя данной партии будет удалено из фрейма, описывающего предыдущее место

хранения, и добавлено в фрейм нового места хранения.

Процедуры-слуги активизируются только по запросу. Примером такой про-

цедуры является функция, встроенная в слот ГОД в фрейме-прототипе ДАТА,

которая вызывается только в том случае, если пользователь не указал год.

Эксперименты с системой GUX стимулировали создание новых средств

программирования для представления знаний типа KRL, FRL и других, бази-

рующихся на концепциях фреймов, отличных от принятой в GUX [9].

Описание знаний в системе KRL выполняется с помощью так называемых

единиц, имеющих фреймоподобную структуру (рис. 1.2). Единица (фрейм) ха-

рактеризуется категорией. В KRL выделены такие категории, как основной, аб-

страктный, индивидуальный, отношение, утверждение и ряд других. Категории

определяют способы обработки информации в системе. В частности, в процессе

поиска информации при составлении пары фреймов несовпадение их категорий

позволяет не анализировать более глубокие элементы их структуры.

Имя единицы Категория единицы

Имя описания Описатель … Описатель

Слот

Рис. 1.2. Структура фрейма в системе KRL

Так же как и в GUX, слоты (описания) в KRL могут иметь связанные про-

цедуры, организованные с помощью функций LIXP. Слот в KRL может включать

несколько описателей, позволяющих характеризовать объект с различных точек

зрения, таких, как класс, категория, отношение, в которых участвует объект. Все-

го в KRL выделено 12 типов описаний. Их использование значительно расширяет

возможности по определению свойств объектов.

Концепция фреймов, принятая в системе FRL, предоставляет широкие воз-

можности для построения иерархических структур фреймов. Это достигается

тем, что один из слотов фрейма отводится для ссылки на иерархически преды-

дущий фрейм. Таким образом обеспечивается «вкладываемость» фреймов. До-

пускается до пяти уровней вложенности. Указанные свойства позволяют органи-

зовать механизм так называемого наследования свойств.

Поясним действие механизма наследования на примере. Предположим, что

у большого числа деталей почти полностью совпадают адреса хранения. Одина-

ковыми являются номер склада, номер секции в складе и номер блока в секции.

Различаются лишь номера ячеек хранения. Ясно, что записывать полный адрес

хранения для каждой детали неэкономично. Целесообразно разбить адрес на час-

ти и создать специальный фрейм для общей части. При формировании адреса

конкретной детали указывается лишь уникальная компонента адреса, т.е. номер

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

процессе наследования, который заключается в получении информации при дви-

жении вверх по иерархии фреймов.

Рассмотрим в качестве примера некоторые типы фреймов, разработанные

для представления знаний в технических системах.

Фрейм здесь представляется в виде ориентированного графа с помеченны-

ми вершинами и дугами. Одна из вершин выделена для предикатного (функцио-

нального) символа, остальные – для аргументов выделенного символа. Для каж-

дой аргументной вершины задана область допустимых значений, что позволяет

интерпретировать данную вершину как слот. Заметим, что такое определение

фрейма очень близко к понятию факта в семантической сети. Это заставляет не-

которых специалистов считать фреймы частным видом специально организован-

ных сетей.

Рассмотрим конкретные фреймы.

Фрейм-соединение предназначен для описания различных типов соедине-

ний (механических, гидравлических и т.п.), встречающихся в технических сис-

темах. Прототип фрейма-соединения представлен на рис. 1.3. он отражает сте-

реотипную ситуацию: «Субъект

X соединяет объект Y с объектом Z спосо-

бом

W». На рисунке предикатная вершина помечена символом F и именем фрей-

ма. Дуги имеют метки падежных отношений:

s – субъект, o – объект, k –

отношение «посредством чего». Вершины, обозначенные прямоугольниками с

меткой

D, описывают область допустимых значений соответствующего аргумен-

та.

Фрейм-назначение служит для описания процессов через назначение от-

дельных элементов, участвующих в них. Пусть требуется описать ситуацию:

«Насос (Н) перекачивает газ (Г) от источника тепла (ИТ) к теплообменнику

(ТО)». Прототип фрейма-назначения представлен на рис. 1.4. символами

u и d

обозначены падежные отношения соответственно «источник действия» и «при-

емник действия».

Фрейм-закон функционирования предназначен для описания аналитиче-

ских законов изменения определённых параметров во времени. Прототип фрей-

ма–закона функционирования представлен на рис. 1.5. Он описывает ситуацию:

«Вычислить значение параметра

p в момент времени t с использованием функ-

ции

f, имеющей аргументы

,....

». Метки дуг обозначают отношения: v

–

вид функции,

– время, arg – аргумент функции, res – результат применения функ-

ции.

Соединять

Рис. 1.3. Фрейм-соединение

ит

то

Перекачивать

Рис. 1.4. Фрейм-назначение

•

Вычислить

res

arg

Рис. 1.5. Фрейм-закон функционирования

В системах представления знаний, базирующихся на фреймах, используют

три основных подхода для организации процессов обработки информации и вы-

числений [15]. При первом подходе информационно-вычислительный процесс

организуется пользователем с привлечением какого-либо языка программирова-

ния. Чаще всего этим языком бывает LIXP [6]. Такой подход принят в системе

FRL. При втором подходе для систем фреймов вводится единый информацион-

но-вычислительный процесс, основой которого является выбор фреймов, управ-

ляющих дальнейшими вычислениями. Так, в системе KRL в ходе построения

информационной модели конкретной ситуации вначале производится грубый

выбор базовых фреймов и дальнейшее сопоставление их (с использованием по-

нятия «категория») с построенными фреймами-примерами.

Задача сопоставления может быть разбита на подзадачи, что позволяет ис-

пользовать стратегии поиска в пространстве подзадач. При третьем подходе

выделяются подклассы систем фреймов, для которых разрабатываются специфи-

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

подклассов.

1.3. СЕМАНТИЧЕСКИЕ СЕТИ

Основой формализации семантических знаний о предметной области часто

является направленный граф с помеченными вершинами и дугами, называемый

семантической сетью. Вершинам ставятся в соответствие конкретные объекты, а

дугам — семантические отношения между ними. Метки вершин имеют ссылоч-

ный характер и представляют собой некоторые имена. В роли имен могут высту-

пать, например, слова естественного языка. Метки дуг обозначают элементы

множества отношений.

Рассмотрим более строгое определение семантической сети [9]. Пусть за-

даны конечные множества символов {А

, …, А

}, называемых атрибутами, и ко-

нечное множество R={R

, …, R

} отношений. Схемой или интенсионалом отно-

шений R

называют набор пар

INT (R

)={…, [A

, DOM(A

)], …}, (1.1)

где R

– имя отношений; DOM(A

) – домен A

, т.е. множество значений атрибута A

отношения R

Объединение всех доменов называют базовым множеством модели или

множеством объектов, на которых задаются отношения R

Экстенсионалом отношения R

называют множество

EXT(R

) = {F

, …, F

где

)р 1,=( kF

– факт отношения R

. Факт задается совокупностью пар вида

«атрибут – значение», называемых атрибутивными парами. Под фактом пони-

мают конкретизацию определенного отношения между указанными объектами.

В графической интерпретации факт – это подграф семантической сети, имеющий

звездообразную структуру. Корень подграфа – вершина предикатного типа, по-

меченная уникальной меткой, включающей имя соответствующего отношения.

Из вершины факта выходят ребра, помеченные именами атрибутов данного фак-

та, ведущие в вершины базового множества, которые являются значениями этих

атрибутов.

Рассмотрим пример, иллюстрирующий введенные определения. Пусть за-

даны базовое множество модели (множество объектов) – совокупность целых

чисел {0, 1, 2}; множество отношений R, включающее два отношения «боль-

ше – меньше» и «сумма» (обозначим их соответственно «<» и «+»). Интенсионал

этих отношений в соответствии с (1.1) запишется, очевидно, следующим обра-

зом:

INT(+) = {[1-е слагаемое, (0, 1, 2)], [2-е слагаемое, (0, 1, 2)], [сумма, (0, 1,

2)]};

INT(<) = {[меньше, (0, 1)], [больше, (1, 2)]}.

Экстенсионалы этих отношений могут быть записаны в виде фактов, на-

пример, следующим образом:

F1: (<, меньше 0, больше 1);

F2: (<, меньше 1, больше 2);

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

F9: (+, 1-е слагаемое 2, 2-е слагаемое 0, сумма 2).

Иногда удобна табличная форма записи (табл. 1.1, 1.2).

Таблица 1.1

Метка Отношение «меньше»

факта 1 2

0 1

1 2

0 2

Таблица 1.2

Метка Отношение «сумма»

факта 1-е слагаемое 2-е слагаемое Сумма

0 0 0

0 1 1

0 2 2

1 0 1

1 1 2

2 0 2

Графическое представление экстенсиональной семантической сети приве-

дено на рис. 1.6. При ее построении использованы следующие правила и обозна-

чения. Базовому множеству модели поставлены в соответствие вершины 0, 1, 2,

обозначенные квадратами. Вершины с фактами обозначены кружками с метками,

образованными парой идентификаторов – факта и отношения. Дугам присвоены

метки соответствующих атрибутов.

1-е слагаемое

2-е слагаемое

мма

2-е слагаемое

1-е слагаемое

2-е слагаемое

мма

1-е слагаемое

мма

1-е

слагаемое

Меньше

2-е

слагаемое

1-е сла-

гаемое

Меньше

Больше

2-е слагаемое

Рис. 1.6. Экстенсиональная семантическая сеть

Экстенсиональная семантическая сеть описывает экстенсиональные знания

о моделируемых объектах, являясь как бы «фотографией» его текущего состоя-

ния. Интенсиональная семантическая сеть содержит интенсиональные знания и

описывает общую структуру моделируемой предметной области на основе абст-

рактных объектов и отношений, т.е. обобщенных представителей некоторых

классов объектов и отношений. Например, такие объекты, как ПРОИЗВОДСТ-

ВЕННЫЙ УЧАСТОК, ГРУЗ, ДЕТАЛЬ, могут являться обобщенными понятиями,

множество значений которых образует множество имен конкретных производст-

венных участков (токарный участок, кузнечно–прессовый участок), множество

имен грузов (кассета, заготовка), множество имен деталей (болт, вал, шасси).

В семантических сетях используют три основных типа объектов: понятия,

события, свойства.

Понятия представляют собой сведения об абстрактных или физических

объектах предметной области. Общие понятия интерпретируются как множество

доменов (параметров или констант).

События – это действия, которые могут внести изменения в предметную

область. Результатом события является некоторое новое состояние предметной

области. Можно задать некоторое желаемое (целевое) состояние предметной об-

ласти и поставить задачу отыскания на семантической сети последовательности

событий, приводящей к целевому состоянию.

Свойства используются для уточнения понятий, событий или других

свойств. Применительно к понятиям свойства описывают их особенности или

характеристики – цвет, размеры, качество; применительно к событиям свойства –

продолжительность, место, время и т. д.

Многообразие семантических отношений условно делят на четыре класса:

лингвистические, логические, теоретико–множественные, квантифицирован-

ные [9].

Лингвистические отношения. Наиболее употребительными лингвистиче-

скими отношениями являются падежные, к которым относятся, в частности, сле-

дующие: агент – отношение между событием и тем, что (кто) его вызывает;

объект – отношение между событием и тем, над чем производится действие; ус-

ловие – отношение, указывающее логическую зависимость между событиями;

инструмент – объект, с помощью которого совершается событие; место – ме-

сто совершения события. Другой тип лингвистических отношений – это харак-

теризация глаголов и атрибутивные отношения. К характеризации глаголов от-

носится наклонение, время, род, число, залог. Атрибутивные отношения – это

цвет, размер, форма, модификация, и т.д. Например, фраза «Большие красные

шары» с использованием атрибутивных отношений может быть представлена

структурой, изображенной на рис. 1.7.

Логические отношения – это операции, используемые в исчислении выска-

зываний: дизъюнкция, конъюнкция, импликация, отрицание.

Теоретико-множественные отношения – это подмножество (обозначается

XUB), супермножество (обозначается XUP), элемент множества, отношение час-

ти и целого и др. Этот класс отношений используется для построения иерархиче-

ских таксономических (соподчиненных) структур для представления обобщен-

ной информации. На рис. 1.8 изображен фрагмент таксономической структуры

понятия «роботы». В таких структурах все свойства XUB-понятия автоматически

приписываются XUP-понятию, что позволяет исключить из базы данных повто-

ряющиеся сведения.

Квантифицированные отношения – это логические кванторы общности и

существования. Логические кванторы применяются для представления знаний

декларативного типа, например при записи таких утверждений, как «Каждый

станок требует профилактического ремонта» или «Существует робот А, который

может обслуживать все станки группы В». Формальная запись таких предложе-

ний опирается на язык исчисления предикатов первого порядка.

Ш А Р

жской

Большой

Множественное

Чис ло

асный

Род

Размер

Цвет

Рис. 1.7. Схема, иллюстрирующая атрибутивные отношения

РОБОТЫ

Манип

ля

ионные Ин

ма

ионныеЛокомо

ионные

Промышленные Медицинские Шагающие Колесные Подводные Космические

Сборочные Погр

зочные

Рис. 1.8. Фрагмент таксономической структуры понятия «робот»

В качестве примера семантической сети рассмотрим представление знаний,

содержащихся в предложении «Если станок закончил обработку, робот грузит

кассету с деталями на робокар, который перевозит их на склад, где штабелер по-

мещает кассету в ячейку». Выделим пять факторов: станок закончил обработку

(F1), робот грузит (F2), робокар перевозит (F3), кассета содержит (F4), штабелер

размещает (F5). Заметим, что при описании фраз естественного языка факты час-

то называют высказываниями. Как и в предыдущем примере, факты будем обо-

значать кружком, а связанные с ними понятия – прямоугольником. Дуги пометим

наименованиями отношений, которые они выражают. Схема семантической сети

приведена на рис. 1.9.