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

ношении R с ( R ) и – в отношении R с ( R ), следует справедливость утверждения “ находится в отношении R с ”, т.е.

( R R ) R .

Например, транзитивность родовидового отношения обеспечивает возможность наследования свойств от родового объекта к виду и подвиду. Механизм наследования свойств обеспечивает проведение простейших дедуктивных заключений типа: “Все люди смертны. Сократ – человек. Следовательно, Сократ смертен” [34].

В базах знаний выделяют интенсиональные и экстенсиональные знания. Если имеется конечное множество атрибутов A={A1,A2,…,An} и конечное множество отношений R={R1,R2,…,Rm}, то схемой или интенсионалом отношения Ri(i=1,2,…,m) называется набор пар вида

INT(Ri ) {...,[Aj ,DOM(Aj )],...},

где DOM(Aj) – домен атрибута Aj, т.е. множество возможных значений атрибута. Экстенсионал отношения Ri – это множество фактов

EXT(Ri ) {F1,F2 ,...,Fp },

где F1,F2,…,Fp – факты отношения Ri, обычно задаваемые в виде совокупности пар “атрибут-значение”. Факт конкретизирует определенное отношение. В графической интерпретации он представляет собой подграф, имеющий звездообразную структуру. Корнем подграфа является вершина предикатного типа с меткой, соответствующей имени отношения. Ребра подграфа отмечены именами атрибутов.

Интенсиональная семантическая сеть представляет моделируемую предметную область на обобщенном, концептуальном уровне, а экстенсиональная – наполняет ее конкретными, фактическими данными. Таким образом, семантическую базу знаний можно рассматривать как совокупность объектов и отношений, часть из которых определена интенсионально, а часть – экстенсионально.

3.4.2.Способы описания семантических сетей

илогический вывод

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

Г.Хендрикса. Блочные структуры подробно описаны в [8,35]. Поэтому рассмотрим описание семантических сетей в виде концептуальных графов.

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

Одно из преимуществ выделения отношений в самостоятельные вершины концептуального графа заключается в упрощении представления n- арных отношений. Такое отношение представляется вершинойотношением с n-ребрами (рисунок 3.10).

Рисунок 3.10 – Примеры концептуальных графов

Обычно каждый концептуальный граф фиксирует одно предложение. Тогда база знаний будет представляться в виде совокупности таких графов. Например, верхний граф на рисунке 3.10 соответствует предложению “Мяч имеет красный цвет”. Граф, изображенный на рисунке 3.11, отражает более сложное предложение: “Иван закрепил деталь стула клеем”.

Рисунок 3.11 – Концептуальный граф предложения

Этот граф использует падежные отношения глагола “закрепить” и демонстрирует возможности концептуальных графов для представления предложений естественного языка.

Каждая вершина-понятие концептуального графа может иметь метку типа. Тип обозначает класс принадлежности вершины. На концептуальном графе метку типа вершины отделяют двоеточием от конкретного имени вершины. На рисунке 3.11 с помощью метки типа показано, что Иван является столяром. На концептуальных графах можно также вводить индивидные вершины-понятия с одинаковыми именами. Чтобы различать экземпляры объектов (понятий) с одинаковыми именами, используется специальный числовой маркер, перед которым записан символ #. Граф на рисунке 3.12 указывает, что конкретный "автомобиль" с маркером #1235 имеет зеленый цвет.

Рисунок 3.12 – Концептуальный граф с числовым маркером

Кроме числового маркера, на концептуальных графах могут применяться обобщенные маркеры, обозначаемые знаком *. В сочетании с переменной, записываемой после этого знака, обобщенный маркер оказывается полезным в ситуациях, когда две различные вершины графа представляют один и тот же объект. В отличие от числовых маркеров, которые применяются для выделения в семантической сети индивидных объектов, обобщенные маркеры позволяют выделять один и тот же обобщенный объект заданного типа (рисунок 3.13). В качестве примера на рисунке изображен концептуальный граф, соответствующий предложению: “Маляр испачкал свою руку краской”.

Рисунок 3.13 – Концептуальный граф с обобщенным маркером

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

Операция копирования позволяет сформировать из исходного графа G его копию, например, G1.

Операция специализации заключается в замене обобщенной вершины ее индивидным (конкретным) вариантом. При этом может быть два случая:

1)если вершина отмечена обобщенным маркером, то обобщенный маркер заменяют конкретным индивидным маркером (именным или числовым).

2)тип вершины можно заменить соответствующими подтипами, об-

ладающими необходимыми свойствами.

Операция объединения позволяет получать из двух графов один. Если на графе G1 имеется вершина-понятие V1, которая аналогична вершинепонятию V2 графа G2, то можно сформировать новый граф G3, удалив V2. При этом все связи V2 необходимо переориентировать с V2 на V1.

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

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

Операции специализации и объединения конкретизируют исходный граф. Если граф G1 – это конкретизация графа G2, то можно сказать, что верно и обратное, т.е. G2 – есть обобщение G1. Обобщение широко используется при обучении СИИ, позволяя выводить правдоподобные умозаключения по частным примерам (см. §4.3).

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

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

Концептуальные графы могут содержать вершины, которые являются предложениями. Такие вершины изображаются в виде прямоугольного блока, содержащего подграф, соответствующий предложению. В качестве примера на рисунке 3.14 изображен граф утверждения: “Алексей полагает, что Татьяне нравится игрушка”.

Рисунок 3.14 – Концептуальный граф, содержащий предложение

Введение отдельных блоков для обозначения предложений позволяет фиксировать отношения между предложениями. В приведенном примере глагол “полагает” представляет не конкретное физическое действие, а выражает ощущения Алексея. Поэтому на графе введено новое отношение “субъект”, представляющее лицо, испытывающее те или иные ощущения. Утверждения, содержащие подобные лексические единицы (доверять, верить, намериваться и т.п.) являются объектом исследований модальной логики.

Концептуальный граф позволяет естественным образом выражать конъюнкцию. Например, с помощью концептуального графа мы легко можем представить предложение “Собака находилась в саду и грызла кость”. Сложнее обстоит дело с другими логическими операциями: дизъюнкцией, логическим отрицанием, кванторами.

Для представления отрицания на концептуальных графах применяется унарный логический оператор “не”. Оператор применяют к предложению. Утверждение, фиксируемое предложением, считается в этом случае ложным. Граф, изображенный на рисунке 3.15, соответствует предложению: “Нет игрушек, которые нравятся Татьяне”.

Используя отрицание и конъюнкцию, можно представить на концептуальных графах дизъюнкцию. Однако для упрощения концептуальных схем дизъюнкцию представляют в виде специального бинарного отношения “или”, аргументами которого являются вершины-предложения.

Рисунок 3.15 – Концептуальный граф с логическим отрицанием

Обобщенные объекты-понятия, отображаемые на концептуальных графах, связаны квантором существования. Так, граф, изображенный на рисунке 3.10, можно описать формулой

x y(мяч (x) цвет (x, y) красный (y)).

Квантор общности получается при отрицании предложений, связанных квантором существования. Например, применив отрицание к графу, изображенному на рисунке 3.10, получим

x y (мяч (x) цвет (x, y) красный ( y)).

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

Методы вывода на семантических сетях используют ассоциативные и сопоставляющие алгоритмы, которые сводятся к нахождению путей на графе, построению транзитивных замыканий, выделению подграфов с определенными свойствами. Основные подходы к построению процедур вывода на семантических сетях изложены в [8,29,34]. Во многих случаях они базируются на простых операциях над графами, как-то: удаление и добавление новых вершин и ребер, специализация, поиск вершины или ребра по имени, переход от одной вершины к другой по связям, объединение подграфов и др.

Одним из простых средств вывода на семантических сетях является

116 Глава 4

поиск по пересечению, который был рассмотрен ранее.

Другим мощным средством вывода является сопоставление с образцом. В данном случае происходит сопоставление отдельных фрагментов семантической сети. При этом запрос к базе знаний представляется в виде автономного подграфа, который строится по тем же правилам, что и семантическая сеть. Поиск ответа на запрос реализуется сопоставлением подграфа запроса с фрагментами семантической сети. Для этого осуществляют наложение подграфа запроса на соответствующий фрагмент сети. Успешным будет то наложение, в результате которого фрагмент сети оказывается идентичным подграфу запроса. При этом допускается использование в запросе переменных. Переменная запроса сопоставляется с константой фрагмента сети. Пусть, например, имеется запрос: “Существует ли такая птица Х, которая умеет петь и имеет желтый цвет?” (рисунок 3.16).

Рисунок 3.16 – Подграф запроса

Изоморфное вложение подграфа запроса в семантическую сеть, изображенную на рисунке 3.7, позволяет дать ответ Х=“канарейка”.

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

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

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

3.5.Фреймы

3.5.1.Структура фрейма

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

Фреймы впервые были предложены для представления знаний в 1975г. М. Минским. Согласно его определению фреймы – это структуры данных, предназначенные для представления стереотипных ситуаций. Когда человек оказывается в новой ситуации, он извлекает из памяти ранее накопленные блоки знаний, имеющие отношение к текущей ситуации, и пытается применить их. Эти блоки знаний и представляют собой фреймы. Вероятно, знания человека организованны в виде сети фреймов, отражающих его прошлый опыт. Например, мы легко можем представить типовой одноместный номер в гостинице. Обычно он имеет кровать, ванную комнату, шкаф для одежды, телефон, план эвакуации в случае пожара и т.п. Детали каждого конкретного номера могут отличаться от приведенного описания. Но они легко уточняются, когда человек оказывается в конкретном номере: цвет обоев и занавесок, положение выключателей света и др.

В простейшем случае под фреймом понимают следующую структуру

{n,(ns1,vs1, ps1),(ns2 ,vs2 , ps2 ),...,(nsk ,vsk , psk )},

где n – имя фрейма, ns1 – имя слота, vs1 – значение слота, ps1 – имя присоединенной процедуры. Фрейм состоит из слотов. Слоты – это некоторые незаполненные подструктуры фрейма. После заполнения слотов конкретными данными, фрейм будет представлять ту или иную ситуацию, явление или объект предметной области. Процедура является необязательным элементом слота. В качестве значений слотов могут выступать имена других фреймов, что обеспечивает построение сети фреймов. В качестве примера на рисунке 3.17 изображен фрагмент сети фреймов, представляющих типовой одноместный номер в гостинице. Здесь “мебель”, “инвентарь”, “санузел”, “оплата” – это имена слотов. Значениями слотов “мебель”, “инвентарь”, “санузел” является список имен других фреймов, которые соответственно описывают предметы и оборудование, находящиеся в номере.

Во фреймовых системах часть фреймов представляет индивидные объекты предметной области. Такие фреймы называют экземплярами

фреймов или фреймами-примерами. Другие фреймы, представляющие обобщенные объекты, называют классами или фреймами-прототипами. Фрейм-прототип соответствует интенсиональному описанию множества фреймов-примеров.

Фрейм может содержать специальный слот, с помощью которого задается отношение данного фрейма с другими фреймам сети. Наиболее часто в сети фреймов используют теоретико-множественные отношения, которые позволяют строить иерархические структуры. Специальный слот, называемый is_a слотом, фиксирует отношение “экземпляр класса”. Слот ako указывает, что данный фрейм является прямым подклассом вышестоящего по иерархии фрейма. Вышестоящий фрейм называют родительским фрей-

мом или суперклассом.

Например, кровать “Эмилия”, установленная в гостиничном номере, является конкретизацией обобщенного объекта “кровать” (рисунок 3.17). Это обозначено с помощью слота is_a, указывающего, что кровать “Эмилия” – экземпляр класса (фрейма-прототипа) “кровать”. Слот ako указывает, что одноместные номера являются подклассом гостиничных номеров.

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

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

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

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

В ряде фреймовых систем в состав слотов включают различные указатели наследования [37]. Указатель наследования фиксирует ту информацию, которая передается от слотов фрейма верхнего уровня к соответствующим слотам фрейма нижнего уровня. Рассмотрим в качестве примера структуру фрейма системы FMS [37]. Здесь выделяют следующие типы указателей наследования: unique, same, range, override и др.

Unique (уникальный) означает, что слоты с одними и теми же именами во фреймах, находящихся на разных уровнях иерархии, могут иметь различные значения. Same (такой же) показывает, что слоты должны иметь одинаковые значения. Range (диапазон) устанавливает некоторые границы, в которых может находится значение слота фрейма нижнего уровня. Override комбинирует свойства указателей unique и same. При описании слотов фрейма в системе FMS указывается также тип данных слота. Типы данных слотов соответствуют типам данных, применяемых в языках программирования высокого уровня. Например, INTEGER (целый), REAL (вещественный), BOOL (логический), STRING (строковый). Однако применяются также и другие типы данных, повышающие эффективность работы с системой. Например, TEXT (текстовый), TABLE (табличный), LIST (списочный), LISP (присоединенная процедура), FRAME (указатель на другой фрейм) и др.

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

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

<слот>::=<имя> <указатель наследования> <тип данных>

<значение> [<процедуры-демоны>]