Геловани В.А. и др. Интеллектуальные системы поддержки принятия решений в нештатных ситуациях

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

2.2.

Модели представления знаний 51

фундаментальными отношениями, хотя именно они образуют «скелет»,

позволяющий более свободно ориентироваться даже в сложной и большой

модели. Типизация обеспечивает и реальные осязаемые преимущества,

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

обобщенного объекта, являющегося видом некоторого другого, нет не-

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

можно получить благодаря механизму наследования. Для такого объекта

целесообразно представлять в базе лишь его собственные (ненаследуе-

мые) свойства, а также свойства, которые хотя и являются наследуемыми,

но несут дополнительную информацию.

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

тивностью родо-видового отношения и отношения «является частью».

Отношение а называется транзитивным тогда и только тогда, когда для

любой тройки объектов А, В иС таких, что А находится в отношении

«а»

с В,

а.

В — в отношении «а» с С, выполняется утверждение «А нахо-

дится в отношении "а" с С». Упомянутые фундаментальные отноше-

ния транзитивны. Свойство транзитивности позволяет отображать в базе

знаний не все фундаментальные отношения между объектами, а лишь

небольшую часть их. Остальные могут быть получены из представленных

в базе с помощью специального механизма поддержки транзитивно-

сти,

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

отношения обеспечивает возможность наследования свойств не только

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

для родового и

т.

д.

Интересно отметить также связь механизма наследования при ис-

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

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

дедуктивных рассуждений типа: «Все люди смертны. Сократ — человек.

Следовательно, Сократ смертен».

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

ся к удалению и добавлению новых вершин и ребер. Базовые операции

поиска информации в сети обеспечивают поиск вершины или ребра

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

ной связи к другой через смежные вершины. Цель поиска — получение

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

Одним из мощных средств манипуляции знаниями является опе-

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

Информационная потребность, определяющая содержание и цель запро-

са к базе знаний, описывается автономной семантической сетью

—

сетью

запроса, построенной по тем же правилам и отображающей те же объек-

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

сетью. Поиск ответа на запрос реализуется сопоставлением сети запроса

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

Положительный результат сопоставления позволяет получить один из от-

ветов на запрос. Все ответы можно получить путем обнаружения всех

сопоставимых с сетью запроса фрагментов.

52 Глава 2. Представление знаний в системах

поддержки

решений

2.2.2.3.

Реализация запроса в семантических сетях

Операция сопоставления редко сводится к выявлению фрагментов

базы знаний, изоморфных сети запроса; как правило, оно сложнее. Так,

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

шения «является частью», не представленные в системе знаний (и в се-

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

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

объектов, для получения которых в базе знаний необходимо включать ме-

ханизм наследования свойств. В обш;ем виде операцию сопоставления для

семантических сетей можно описать следующим образом. Для сети, пред-

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

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

валентную. Операция сопоставления выявляет все фрагметъ! исходной

или эквивалентных ей сетей, изоморфные сети запроса Набор допусти-

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

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

и наследования свойств, но не ограничивается этим. В зависимости

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

ного средства набор эквивалентных преобразований может существенно

расширяться. Поскольку теория семантических сетей не дает универ-

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

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

вая лишь методически (в том смысле, что поиск в семантической сети

всегда есть какое-то сопоставление), но не технически (в том смысле,

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

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

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

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

хода по сети. Фактически совокупность последних в каждом конкретном

случае поиска реализует то или иное требуемое сопоставление.

2.2.2.4. Модель семантической сети М. Р. Квиллиана

Исследования по семантическим сетям начались с работы М. Р. Квил-

лиана в 1966 г. [95, 961, в которой он попытался формально представить

семантику английских слов. М. Р Квиллиан ввел термин «семантическая

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

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

формальные выражения этого языка бьши составлены из вершин, кото-

рым отвечали «понятия-слова», и из «ассоциативных дуг», соединяющих

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

которых одни слова-понятия ссьшаются на другие. Эта структура вза-

имных ссылок между словами-понятиями и дает определение исходного

слова-понятия. Аналогичное наблюдается в толковых словарях, в которых

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

толкования которых разбросаны в разных частях словаря.

В структуре Квиллиана каждое слово-понятие представлялось как

заголовок «страницы», содержащей его определение. Пример выражения

2.2.

Модели представления знаний

PLANT

: APPARATUS

13С1 '—

;

...FOR 5

PEOPLE

= A •

->•

PROCCESS

INDUSTRY

Рис.

2.1

языка Квиллиана дан на рис. 2.1. Указатели, лежащие в «странице»

(сплошные стрелки на рис. 2.1), формируют структуру определения.

Квшишан постулировал небольшой набор таких указателей:

о подкласс (например, отношение PLANT (завод) к APPARATUS (ап-

паратура));

о модификации (например, APPARATUS модифицируется структурой

USE (использовать));

о дизъюнкция (OR); конъюнкция (AND); субъект/объект (например,

от USE к PEOPLE (люди) (субъект) м к = А (объект)). Указатели,

лежащие вне «страницы» (пунктирные стрелки на рис. 2.1), ссы-

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

«страницах».

Одним из главных намерений Квиллиана было развитие инферен-

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

Он дал несколько примеров техники вывода, основанной на поиске

по пересечению с использованием распространения активности. Поиск

ведется по направлению дуг из двух начальных «страниц» до тех пор, по-

ка не будет найдено пересечение — общая вершина. Пути от начальных

вершин к общей вершине определяют потенциальное отношение между

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

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

54 Глава 2.

Представление знаний

системах поддержки решений

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

принятия решений.

Дедуктивные возможности модели Квиллиана фактически опреде-

лялись отношением «подкласс» и отношением «модификации». Понятие

может быть определено в терминах более общего понятия (т. е. первое

есть подкласс второго) и с помощью модифицирующего свойства, ко-

торое является комбинацией «атрибут—значение атрибута». При этом

свойство, истинное для элементов класса, также истинно и для элемен-

тов любого его подкласса. Таким образом, семантическая сеть Квиллиана

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

основанной на отношении «класс—подкласс», и описания свойств (как

пара «атрибут—значение») элементов класса.

Некоторым развитием первоначальной модели Квиллиана стала его

система TLC (Teachable Language Comprehender).

этой системе свойство

определялось как атрибут (некоторое понятие — отношение), его значе-

ние и, возможно, некоторые дополнительные «подсвойства». Определе-

ние свойств давалось с использованием «блоков», которые представляли

понятия, объекты, события, идеи, утверждения и т. п.

Практический успех TLC был ограничен, что частично вызывалось

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

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

связок). Однако значение работ Квиллиана заключается в содержащихся

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

2.2.2.5.

Модель семантической

сети

Г.

Хендрикса

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

тико-графовую структуру с помеченными вершинами и

дугами.

Вершина-

ми могут быть понятия (предметы), события (действия), свойства (места),

а дугами

—

отношения, которые делятся на лингвистические, логические,

теоретико-множественные, квантификационные. В свою очередь лин-

гвистические отношения делятся на глагольные (время, вид, род, число,

залог, наклонение) и атрибутивные (цвет, размер, форма, модификация);

логические — на дизъюнкцию, конъюнкцию, отрицание, импликацию;

теоретико-множественные — на подмножества, и квантификационные

отношения делятся на логические кванторы общности и существования,

нелогические кванторы (много, несколько) и числовые характеристики.

Рассмотрим структуру семантической сети, предложенную Г. Хен-

дриксом [36, 94], в которой можно записывать таксономическую ин-

формацию о процессах и процедурах, модальности (мнения, желания),

информацию о границах локальных контекстов и т. п. Структура этой

сети обладает большой выразительностью, в ней наиболее полно нашли

отражение основные принципы построения таких сетей и, кроме то-

го,

она явится базой для дальнейшего развития процесса представления

знаний в виде сети фреймов.

Начнем изложение с примера сети

Г.

Хендрикса, на котором будут

пояснены основные понятия структуры (см. рис. 2.2). Здесь UNIVERSAL

обозначает универсальный класс (универсум), который объединяет раз-

личные объекты. Класс UNIVERSAL содержит три подкласса: LEGAL

2.2.

Модели представления знаний

База знаний

Рис. 2.2

PERSONS (юридические лица), SITUATIONS (ситуации) и PHYSOBS

(физические объекты). Метка s обозначает отношение включения, а мет-

ка ds кроме отношения включения подразумевает, что элементы одного

класса отличны от элементов другого (например, элементы подкласса

SITUATIONS отличны от элементов LEGAL PERSON и PHYSOBS). Мет-

ка е обозначает элемент класса. Метка de обозначает, что данный элемент

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

e(de)-flyraMH для данного класса (например, FORD и G. М.-General Mo-

tors обозначают различные элементы класса COMPANIES (компании)).

Метки agt и obj используются для обозначения семантических падежей,

агент, т. е. лицо, вызывающее действие, и объект — предмет, подвер-

гающийся действию, соответственно. Метки conse и ante обозначают

соответственно консеквент и антецедент импликации.

2.2.3.

Блочный характер семантических сетей

Семантическая сеть имеет блочный характер, и каждый блок имеет

вершину входа (например, вершины Р, В

тл

М для трех блоков соответ-

ственно). Блок — одна из основных структурных единиц сети (наравне

с вершинами и дугами). Каждая вершина и каждая дуга сети принадле-

жит одному или нескольким блокам (например, вершина М принадлежит

трем блокам)

56 Глава 2.

Представление знаний

системах поддержки решений

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

саны внутри прямоугольника (например, дуга, связывающая М с MUS-

TANGS,

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

угольником, но не принадлежит блоку, ограниченному большим прямо-

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

для образования иерархии блоков.

К двум блокам с вершинами В и М добавим классы IMPLICATIONS

(импликация) и BUILDS (строит). Тогда мы получим утверждение, ко-

торое читается: «Если М является элементом класса MUSTANGS, то для

некоторой ситуации В из класса BUILDS агентом В является FORD,

а объектом В является М». На языке логики предикатов первого порядка

это утверждение запишется следующим образом:

(VM С MUSTANGS)(3B С BUILDS) arg(B) = FORD & obj(B) = М.

Таким образом, в сети имеется возможность представлять комбинацию

кванторов общности и существования. Иногда удобно скомбинировать

несколько блоков в один «пучок» блоков. Такую комбинацию блоков

Хендрикс назвал «видом» (vista). Эта идея применяется при извлечении

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

блоков

—

«вид», из которых и выбирается информация, т. е. говорят, что

вид «видим» в данный момент. Все структуры, лежащие вне этого вида,

и, следовательно, заключенная в них информация, будут игнорироваться.

Механика разбиения сети на блоки позволяет создавать иерархию

видов, причем вид наследует информацию родительского вида. На рис. 2.3

AVTOMOBII.ES

NP1

7Т

V1=(B}

NP2

V4={NP2, В)

VPi

V6={S1,

VPI, NPl, VI, NP2, В}

Рис.

2.3

2.2.

Модели представления знаний

дан пример использования иерархии видов. Жирные стрелки указывают

на наследование способности выборки информации. Внизу от каждого

блока помещен список блоков, составляющих вид. Так, блок В связан

с видом Vi, содержащим только этот блок. Аналогично, вид

содержит

блоки NP\ и J3 и, следовательно, из него «видима» информация, содер-

жащаяся как в NPy, так и В. Однако информация, содержащаяся в U\,

«невидима» из Vj за исключением случая, когда блоки В и NP\ содержат

те же самые вершины и

дуги,

что и

?7i).

Таким образом, из вида

«видна»

глагольная часть фразы: «Некоторый человек М владеет машиной С»,

а сама фраза видна из V^.

В рассматриваемой семантической сети могут присутствовать бло-

ки логических операций: отрицания, дизъюнкции и импликации. Эти

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

принятия решений. Что касается конъюнкции, то она реализуется в сети

довольно просто с помощью механизма наследования.

Дизъюнкция, входящая в некоторый блок S, описывает альтернатив-

ные наборы понятий и отношений и утверждает, что понятия и отноше-

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

в мире, представленном блоком S.

Пример сети с дизъюнкцией D = «или OLD.BLACK была построена

компанией Форд, или OLD.BLACK принадлежит Джону» представлен

на

рис.

2.4.

С;^^^]]"

BUILDS

J2^

C;^^[^2oWNIN(M~~^

Рнс.2.4

58 Глава 2.

Представление знаний

системах поддержки решений

Компоненты дизъюнкции D представлены здесь блоками (супер-

вершинами) 52 и Sf, причем они являются различными элементами D.

Структура дизъюнкции вложена в конъюнкцию блока S\. Блок 5] обес-

печивает частичное описание некоторого мира (т.е. набора понятий и их

отношений) и каждая структура в Si представляет собой некоторое по-

нятие или ситуацию, встречающуюся в этом мире. Таким образом, при

рассмотрении сети из 5j такие понятия как OLD.BLACK и D становятся

«видимыми». Однако структуры в блоках S2 и 5з не «видны» из 5j. Так

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

в одном из компонентов D, например в ^2, то мир будет включать все

ситуации, описанные структурами, которые «видимы» из S2- Следова-

тельно, в данном случае сюда будут включены структуры из 52 и St,

но исключены структуры из 5з.

В семантической сети отрицание включает в себя описание не-

которого множества понятий и отношений, имеющих место в блоке 5,

и означает, что ни одно множество, удовлетворяющее описанию, не может

существовать в мире, выраженном блоком 5. На рис. 2.5 дана сеть, пред-

ставляющяя утверждение: «Компания G. М. не строила OLD.BLACK».

Как в примере с операцией дизъюнкции, структуры с отрицанием вну-

три 52 не «видимы» при рассмотрении сети из Si, хотя отрицание само

по себе «видимо». При обработке такой негативной информации будем

полагать, что верно предложение о замкнутом мире Рейтера.

Одной из важных особенностей сети является ее способность для

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

ществования. Квантор существования является «встроенным» понятием

в том смысле, что если некоторый элемент (вершина или дуга) входит

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

данный блок представляет.

Квантор существования и отрицания могут использоваться для пред-

ставления любой формулы с квантором общности V(a; С Х)Р{х), имея

в виду следующее преобразование:

V (ж

С Х)Р{х) = -. ^

(а;

С Х)Р(х)] ^ -.

[Э

(ж С X)-i Р(х)].

Эта формула представлена на рис. 2.6. Такое представление логически

верно, но не наглядно. Рассмотрим другое представление квантора общ-

ности: \/(х С Х)Р{х) = V(a;)[(a; С Х) ~* Р{х)]. Здесь переменная х

встречается как в антецеденте, так и в консеквенте. Это свойство исполь-

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

Если в формуле основная связка — импликация, то вторую такую

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

(ж С X) [Q{x) -* R(x)] -

(х)

[{х

С X) ^ (Q(x) -. R{x))]

--= V

(х) [{(х С X)&Q{x)) - R{x)].

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

мещением импликаций в области консеквентов других импликаций. На-

пример, V(a; С Х)3(у С y)V(z С Z)P{x,y,z) = У(а;){(ж С X) -»

^(y)\iyCY)&Viz){(z С Z) ^ P{x,y,z))]}. На рис. 2.7а, б дано пред-

ставление формул 3 (ж с X) Р(х) и

(ж С Х)Р(ж).

2.2.

Модели представления знаний

C[|^]0La BLACK^ C[^^UILDS~~^

NEGATIONS

Рис. 2.5

Рис. 2.6

60 Глава 2. Представление знаний в системах

поддержки

решений

rMPLICATION

arg

Рис.

2.7 а

Рис.

2.7 б

2.2.3.1.

Дальнейшее развитие теории семантических сетей'

Идея разбиения сети на блоки находит свое дальнейшее выражение

в использовании многосортной логики предикатов для более эффектив-

ного представления знаний. Введение многосортной логики в процесс

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

повысить эффективную мощь семантических сетей. При этом выполня-

ются следующие цели:

• отвергаются вопросы, утверждения БД и общие аксиомы вывода,

предикаты, которые имеют переменные, несовместимые с семанти-

ческими ограничениями, накладываемыми на сеть;

• отыскиваются и применяются только те утверждения и общие зако-

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

вопроса;

• определяются все семантически возможные ответы на вопрос.

Область (универсум) рассуждений D распадается на ряд различных

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

(Дж. Минкер и Дж. Мак-Скимин [88, 90]. В сущности понятие «се-

мантической категории» эквивалентно понятию «сорта», применяемому

в логике. Семантическая категория — это имя, данное совокупности