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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Будем рассматривать неоднородную семантическую сеть [Осипов, 1997] как семейство ориентированных графов с помеченными дугами и общим множеством вершин с именами из множества S, элементы которого именуют предметы и процессы реального мира. Дуги графов соответствуют бинарным отношениям из некоторого конечного семейства R₁, R₂, … R_n отношений на множестве S={S₁, S₂, …}.

Элементы множества S есть имена объектов, которые, как правило, имеют определенную внутреннюю структуру и характеризуются рядом признаков и свойств. Они задаются семейством множеств D={D₁, D₂, …D_n}, где каждое множество D_i называется множеством атрибутов, а всякому объекту или процессу ставится в соответствие некоторое подмножество кортежей из декартова произведения D_k = D_i1 D_i2 … D_ik (k n) некоторых подмножеств из D, называемое его экстенсионалом или объемом.

Совокупность индексов множества атрибутов события i = <i₁, i₂,… i_k> называется его содержанием. Будем отождествлять индексы множеств из D с именами соответствующих множеств.

Имя события S будем считать функцией как его объема, так и содержания: S=S (i,).

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

W = < D, S, R>.

Отношения как множества упорядоченных пар

Введем следующие обозначения: под Rf будем понимать свойство рефлексивности, nRf - нерефлексивности, aRf - антирефлексивности. Аналогично, Tr, nTr, aTr - свойства транзитивности, нетранзитивности и антитранзитивности соответственно; у свойства симметричности четыре градации: Sm, nSm, anSm и aSm. ASm - свойство асимметричности.

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

Далее используется представление отношений в виде (0,1) - матриц R={r_ij}, где

В таком случае рефлексивность означает наличие единиц на главной диагонали, симметричность - симметричное расположение единиц относительно главной диагонали, а транзитивность означает, что если элементы (i, j) и (j, k) равны единицам, то на месте (i, k) тоже должна стоять единица.

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

На рис. 1 представлены матрицы трех наиболее распространенных отношений - нестрогого порядка (Rf, Tr, anSm), эквивалентности (Rf, Tr, Sm) и квазипорядка (Rf, Tr, nSm) соответственно.

Рис. 1. Матрицы отношений нестрогого порядка, эквивалентности и квазипорядка

После рассмотрения всех возможных комбинаций оказалось, что существует 23 отношения с непротиворечивыми свойствами.

Отношения, выражаемые через атрибуты

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

Введем ограничение на множества R и S следующим образом:

между событиями и их именами существует взаимно однозначное соответствие, то есть S_i и S_j обязательно называют разные объекты;

отношения R_i таковы, что они выполняются только на парах различных объектов, и выражение вида R_i(S_j, S_j) не имеет смысла (R_i - антирефлексивны по своей природе).

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

Рассмотрим отношение R, обладающее свойствами aRf, nTr, Sm. В свете сказанного выше, это отношение «антирефлексивной» толерантности. С другой стороны, такими же свойствами описывается отношение отрицания.

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

Введем дополнительные определения:

Если <S,> - событие, то всякое будем называть экземпляром события <S,>.

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

Пусть ₁= S₁, ₂= S₂ и

₁={<i₁, d₁>,<i₂, d₂>,…,<i_l, d_l>},

₂={<j₁, e₁>,<j₂, e₂>,…,<j_m, e_m>}

Введем отображение F: R V, где V - множество векторов v=(a, b) длины 2, таких, что

a{1, }, b{0, 1, }.

Тогда F(R_p)=(a, b), где

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Иначе говоря, если множество индексов атрибутов второго события вложено во множество индексов атрибутов первого события, то a=1; если множества атрибутов пересекаются, то a=.

Случай a=0 означает, что множества атрибутов не пересекаются и, следовательно, не удовлетворяет поставленным требованиям. Мы предполагаем, что объекты S₁ и S₂ имеют хотя бы один общий атрибут.

Второй элемент вектора - b - определяется следующим образом:

Отображение F делит семейство отношений R на шесть классов:

F(R)=(1,1)

F(R)=(1,)

F(R)=(1,0)

F(R)=(, 1)

F(R)=(,)

F(R)=(, 0)

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

R_i^-1(S₁, S₂)=R_j(S₂, S₁).

Поэтому выделенное отношение R характеризуется двумя векторами: F(R) и F(R^-1) или, что то же самое, матрицей M размера 22, где M(R)={F(R), F(R^-1)}.

Из 36 матриц такого рода реально имеют смысл только 10.

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

О рефлексивности нельзя сказать ничего определенного из-за отсутствия четкого разделения и в определении элементов матрицы М. Если строгое и нестрогое вложения рассматривать отдельно, то данным матрицам соответствуют 16 различных отношений. Из них только восемь имеют разные свойства рефлексивности, симметричности и транзитивности. То есть, в терминах таких отображений M(R) можно получить более детальное разделение отношений, чем просто основываясь на их свойствах.

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

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

семантический алгебраический сеть

1) R: _{1 2}: ₂₁.

Применив к этому выражению отображение Ф, получим высказывательную форму «Х имеет свойство Y». Она соответствует канонической форме PROP (X, Y). Само же отношение R антирефлексивно, антисимметрично и транзитивно.

2) R: _{1 2}: ₂₁.

Это отношение соответствует комитативной семантической связи: «Х сопровождается Y» (СОМ (X, Y)). Оно рефлексивно, антисимметрично и транзитивно.

Комбинации отношений

Иногда при выполнении нескольких событий одновременно необходимо оценить влияние их совокупности на наступление интересующего нас события.

Поскольку рассматриваемая семантическая сеть позволяет реализовать только бинарные отношения, необходима совокупность дополнительных методов и процедур для представления тернарных (в общем случае n-местных) отношений.

На данном этапе воспользуемся введенным отображением M(R) для определения и классификации комбинаций отношений.

Пусть R - неизвестное отношение, являющееся комбинацией двух или более отношений R₁, R₂ (R₃,…, R_n), связывающих события S₁, S₂ (S₃,…, S_n) с событием S₀. С помощью отображения M(R) можно определить свойства вновь полученного отношения R(S₁&S₂&,…, S₀), связывающего события S₁&S₂&… и S₀.

Сгруппируем все имеющиеся отношения исходя из свойства транзитивности.

Все транзитивные отношения характеризуются отсутствием модальности в соответствующих им семантических связях. Если хотя бы одно из транзитивных отношений R_i входит в множество R₁, R₂ (R₃,… R_n) и при этом ни одно из остальных отношений не соответствует негативной связи («А отрицает В»), то отношение R(S₁&S₂&…, S₀) можно считать эквивалентным отношению R_i.

Основным объектом рассмотрения в данном случае являются нетранзитивные отношения.

В общем случае, комбинация нескольких нетранзитивных отношений одинакового типа, является также нетранзитивным отношением того же типа. На рис. 3.А. представлена комбинация двух отношений, соответствующих коррелятивной связи (nTr, Sm). Эта комбинация тоже является отношением того же типа (также nTr, Sm). Это определяется видом матрицы M(R)

Введем дополнительное условие на М, такое, что объединение содержаний событий S₁&S₂&… из левой части отношения должно полностью покрывать содержание целевого события S₀ (рис. 3.В). То есть, в данном случае, +=1.

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

Комбинации симметричных нетранзитивных отношений, соответствующих коррелятивной семантической связи, дают более сильное несимметричное нетранзитивное отношение, соответствующее модально-каузальной семантической связи.

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

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

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

Литература

1. Осипов Г.С. Построение модели предметных областей. Неоднородные семантические сети. - Изв. АН СССР. Техн. Кибернетика, 1990. №5. С 32-45.

2. Осипов Г.С. Приобретение знаний интеллектуальными системами - М., Наука - Физматлит, 1997.

3. Ronald J. Brachman. On the epistemological status of semantic networks. «Associative Networks: Representation and Use of Knowledge by Computers», Academic Press. New York. - 1979. Edited by Findler N.V.

Размещено на Allbest.ru