ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 437
Скачиваний: 22
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
1.3.3. Неоднородные семантические сети. Неоднородная семан- тическая сеть (НСС) — семейство графов, имеющих общее множество вершин; вершинам сопоставлены объекты моделируемой действитель- ности, ребрам — элементы некоторых бинарных отношений на мно- жестве вершин; им же сопоставлены процедуры, предназначенные для проверки корректности сети и порождения различного рода гипотез,
повышающих эффективность процесса построения сети. Подробнее о роли таких процедур будет сказано в главе, посвященной приобрете- нию знаний.
НСС предназначены для описания, главным образом, таких пред- метных областей, которые можно отнести к плохо структурирован-
ным, т. е. областей, для которых не известен полный набор свойств их элементов, не полностью известна структура самих элементов,
а знания об элементах и их взаимосвязях и зависимостях не имеют
«готового», завершенного вида, такого, например, который описывается с помощью правил. При этом предполагается, что те связи и зависимо- сти, которые удается все же установить, носят локальный характер.
Определение 1.3.1. Неоднородной семантической сетью будем называть алгебраическую систему
H = hD, N, R, Fi,
где D = {D
1
, D
2
, ... , D
n
} — семейство непустых множеств; N ⊆ N —
выделенное подмножество множества слов конечной длины над неко- торым алфавитом; R — семейство бинарных отношений R
1
, R
2
, ... , R
q на N
2
; R
i
⊆ N
2
; i ∈ {1, 2, ..., q}. F = {f
1
, f
2
, ... , f m
} — семейство функ- ций, каждой из которых приписан некоторый тип. А именно, функция f
i
(i ∈ {1, 2, ..., m}) имеет тип hτ , ωi, где τ = hk1, k2, ..., kmi, если она определена на декартовом произведении D
k1
× D
k2
× ... × D
km
,
а областью ее значений является множество D
ω
, так что каждому
1.3. Cемантические сети для представления знаний
49
кортежу δ ∈ D
k1
× D
k2
× ... × D
km функция f i
типa hτ, ωi из F ставит в соответствие некоторое f(δ) ∈ D
ω
Назначение слов из N — именование элементов предметной обла- сти; каждое из множеств D соответствует некоторому свойству, а эле- менты этого множества — значениям свойства; отношения из семейства
R — бинарные отношения на множестве имен и, наконец, функции из семейства F предназначены для пополнения описания элементов предметной области, например, для вычисления значений некоторых свойств по значениям других.
Неоднородную семантическую сеть, определенную таким образом,
будем называть интенсиональной семантической сетью.
Свяжем, далее, с каждым именем n ∈ N свой тип τ =
= hk1, k2, ..., kmi, ki ∈ {1, 2, ..., n}, и поставим ему в соответ- ствие e — некоторое подмножество декартового произведения
D
k1
× D
k2
× ... × D
km
; того же типа τ, где D
ki
∈ D. Тогда e
будем называть экстенсионалом (или множеством экземпляров или множеством примеров) элемента c именем n типа τ. Понятно, что в этом случае декартовому произведению D
k1
× D
k2
× ... × D
km
,
каждому его подмножеству e и каждому элементу δ ∈ е также следует приписать тип τ = hk1, k2, ..., kmi. Множество экстенсионалов для всех элементов из N обозначим через E.
Расширим на Е семейство отношений R так, что каждому отноше- нию R
i
⊆ N
2
будет соответствовать отношение R
i
⊆ Е
2
таким образом,
что если пара (n j
, n k
) ∈ R
i
, то соответствующая пара (e j
, e k
) ∈ R
i
Обозначим семейство отношений R
i
, где i ∈ {1, 2, ..., q}, через R.
Заменив в определении 1.3.1 N на E и R на R, получим конструк- цию
H = hD, E, R, Fi,
которую будем называть экстенсиональной семантической сетью. Для всякого e ∈ E, поскольку это не приведет к недоразумениям, мы сохра- ним название «элемент».
Рассмотрим более детально отношения из R. Для этого исполь- зуем то обстоятельство, что элементы из E (входящие в пары из отношений R
i
) имеют некоторую внутреннюю структуру, т. е. по су- ществу, также являются отношениями, определенными на множествах из D. Это позволяет выразить отношения, определенные на E через отношения на множествах из D. Такой подход позволит построить порождающие процедуры для некоторых классов отношений, которые уместно считать отношениями структурного сходства, ассоциативными отношениями и каузальными отношениями.
Впрочем, последние, как мы увидим, окажутся подклассом класса ассоциативных отношений.
50
Гл. 1. Методы представления знаний
Отношения структурного сходства. Пусть e
1
, e
2
∈ E, δ и γ —
примеры e
1
и e
2
, δ ∈ e
1
, γ ∈ e
2
Положим δ = hδ
1
, δ
2
, ..., δ
k1
i, γ = hγ
1
, γ
2
, ..., γ
k2
i (здесь нижний ин- декс у компонент примеров означает индекс множества D из семей- ства D. Таким образом, совпадение индексов компонент примеров сведетельствует о принадлежности последних одному и тому же мно- жеству D).
Определение 1.3.2. Отношением R
1
на Е будем называть та- кое X ⊆ Е
2
, в котором для всякой пары (e
1
, e
2
) ∈ X имеет место
∀δ∃γ ∀γ
i
∃δ
i такие, что (i = j) и (δ
i
= γ
j
).
Определение 1.3.3. Отношением R
2
на Е будем называть та- кое X ⊆ Е
2
, в котором для всякой пары (e
1
, e
2
) ∈ X имеет место
∀δ∃γ ∃γ
i
∃δ
i такие, что (i = j) и (δ
i
= γ
j
).
Определение 1.3.4. Отношением R
3
на Е будем называть такое
X ⊆ Е
2
, что для всякой пары (e
1
, e
2
) ∈ X имеет место ∃δ ∃γ (γ = δ).
Определение 1.3.5. Отношением R
4
на Е будем называть такое
X ⊆ Е
2
, что для всякой пары (e
1
, e
2
) ∈ X имеет место ∀δ ∃γ∀ δ
i
∃γ
i такие, что (i = j) и (δ
i
= γ
j
).
Определение 1.3.6. Отношением R
5
на Е будем называть такое
X ⊆ Е
2
, что для всякой пары (e
1
, e
2
) ∈ X имеет место ∀δ ∀γ ∀γ
i
∀δ
j такие, что (i = j) и (δ
i
6= γ
j
).
Определение 1.3.7. Отношением R
6
на Е будем называть такое
X ⊆ Е
2
, что для всякой пары (e
1
, e
2
) ∈ X ∀δ ∀γ ∃γ
i
∃δ
j такие, что
(i = j) и (δ
i
6= γ
j
).
Далее будем полагать, что читателю известны такие свойства би- нарных отношений как транзитивность, рефлексивность и симметрич- ность. Обычно, когда говорят о свойстве симметричности, имеют ввиду одно из трех значений: либо собственно симметричность, либо несим- метричность, либо антисимметричность. Свойство транзитивности име- ет три значения: транзитивно, нетранзитивно и антитранзитивно; ре- флексивность также имеет три значения: рефлексивно, нерефлексивно и антирефлексивно.
Установим свойства введенных отношений.
Утверждение 1.3.1. R
1
и
R
4
— частичные порядки.
Утверждение 1.3.2. R
2
нетранзитивно, рефлексивно, несиммет-
рично.
Утверждение 1.3.3. R
3
нетранзитивно, рефлексивно, симмет-
рично.
1.3. Cемантические сети для представления знаний
51
Утверждение 1.3.5. R
5
нетранзитивно, антирефлексивно, сим-
метрично.
Утверждение 1.3.6. R
6
нетранзитивно, антирефлексивно, не-
симметрично.
Д о к а з а т е л ь с т в а приведенных утверждений достаточно просты.
Докажем, например, что отношение R
1
— частичный порядок.
Пусть пары (e
1
, e
2
) и (e
2
, e
3
) принадлежат R
1
. Задача состоит в том,
чтобы показать, что (e
1
, e
3
) ∈ R
1
. Пусть λ ∈ e
3
и λ = hλ
1
, λ
2
, ..., λ
k3
i.
Так как ∀δ ∃γ такое, что ∀γ
i
∃δ
i
(δ
i
= γ
i
), то пусть для произвольного
δ
∗
найдется γ
∗
такое, что δ
∗
i
= γ
∗
i
. Но в силу того, что (e
2
, e
3
) ∈ R
1
,
∀γ ∃λ такое, что ∀λ
i
∃γ
i
(λ
i
= γ
i
), т. е. это справедливо и для γ
∗
. Если
λ
∗
— то самое λ, которое нашлось для γ
∗
и для которого λ
∗
i
= γ
∗
i
, то из этого равенства и из δ
∗
i
= γ
∗
I
следует, что λ
∗
i
= δ
∗
i
, а так как δ
∗
был выбран произвольно, то это и означает, что ∀δ ∃λ ∀λ
i
∃δ
i
(λ
i
= δ
i
), т. е.
(e
2
, e
3
) ∈ R
1
, что и означает транзитивность R
1
Рефлексивность R
1
следует из того, что в качестве γ можно вы- брать δ, а антисимметричность легко доказывается от противного.
Понятно, что всех возможных комбинаций таких свойств — 27.
Однако не все свойства определенных таким образом отношений неза- висимы. Например, антирефлексивное отношение не может быть анти- симметричным. В результате таких рассуждений получим 20 отноше- ний, определяемых наборами своих свойств. Можно показать также,
что указанные свойства определяют отошения не единственным об- разом, т. е. существуют различным образом определенные отношения,
обладающие одними и теми же наборами свойств. Поэтому ниже мы введем еще одно свойство отношений такого рода — свойство совмест- ности.
Введем теперь специальные диаграммы для графического представ- ления таких отношений. Для этого каждое из событий e i
представим в виде плоской фигуры с двумя измерениями, например, в виде пря- моугольника, по горизонтальной стороне которого будем откладывать свойства событий, по вертикали — множества значений по каждому из свойств или объемы. (Здесь для нас несущественно то обстоятельство,
что эти объемы различны.) Тогда общим свойствам двух событий бу- дет соответствовать проекция их пересечения на горизонтальную ось,
общим значениям свойств — проекция пересечения событий на вер- тикальную ось. Так, например, то обстоятельство, что среди примеров события e
1
и среди примеров события e
2
найдутся такие, что пример события e
2
являются подмножеством некоторого примера события e
1
,
будет отражено на следующей диаграмме (рис. 1.6).
Теперь представим в виде диаграмм некоторые из отношений струк- турного сходства R
1
–R
6
(рис. 1.7).
52
Гл. 1. Методы представления знаний
Рис. 1.6
Рис. 1.7
Как мы видим, отношения структурного сходства порождены нали- чием/отсутствием общих признаков у тех пар элементов предметной области, которые им принадлежат, при этом эти общие признаки про- являются «одновременно» у обоих элементов пары. Это означает, что пары событий, принадлежащие отношениям R
1
–R
6
, всегда являются событиями одного и того же состояния.
В отличие от этого отношения, рассматриваемые ниже, порождены функциональными зависимостями на множествах атрибутов. Свойства их зависят, главным образом, от характера функций из F. В частности,
если функции из F представляют собой временные функции, т. е.
вырабатывают свои значения через некоторые промежутки времени, то
R
7
и R
8
описывают связи событий различных состояний, т. е. в этом
1.3. Cемантические сети для представления знаний
53
смысле являются отношениями, отражающими динамику системы. Да- дим соответствующие определения.
Ассоциативные и каузальные отношения. Пусть
δ ∈ D
k1
× D
k2
×
× ... × D
km
; τ(δ) — тип δ; τ(β), τ(γ), ..., τ(λ) — типы β, γ, ... и λ
соответственно, так что τ(β) ⊆ τ(δ), τ(γ) ⊆ τ(δ), ..., τ(λ) ⊆ τ(δ),
и f p
, f q
, ..., f r
— функции из F, определеные на декартовых произведе- ниях типов β, γ, ..., λ и действующие в D
q
, D
p
, ... , D
r
, соответственно.
Функцию f
∗
(δ) = hf p
(β), f q
(γ), ... , f r
(λ)i будем называть композицией функций f q
, f p
, ..., f r
. Понятно, что значением f
∗
(δ) является неко- торый экземпяр декартового произведения D
q
× D
p
× ... × D
r
. Будем полагать здесь, что f
∗
(δ) = hδ
1
, δ
2
, ..., δ
k1
i, γ = hγ
1
, γ
2
, ..., γ
k2
i, δ ∈ e
1
,
γ ∈ e
2
Из множества ассоциативных и каузальных отношений рассмотрим только следующие.
Определение 1.3.8. Отношением R
7
на Е будем называть такое
X ⊆ Е
2
, что для всякой пары (e
1
, e
2
) ∈ X найдется композиция f
∗
функций из F такая, что ∀δ ∃γ ∀γ
i
∃δ
i такие, что (i = j) и (δ
i
= γ
j
).
Отношение R
7
будем называть каузальным отношением.
Определение 1.3.9. Отношением R
8
на Е будем называть такое
X ⊆ Е
2
, что для всякой пары (e
1
, e
2
) ∈ X существует композиция f
∗
функций из F такая, что ∃δ ∃γ ∃γ
i
∃δ
i такие, что (i = j) и (δ
i
= γ
j
).
Отношение R
8
будем называть ассоциативным отношением.
Приведем без доказательств следующие утверждения.
Утверждение 1.3.8. R
7
транзитивно, нерефлексивно, несиммет-
рично.
Утверждение 1.3.9. R
8
нетранзитивно, нерефлексивно, несим-
метрично.
Понятно, что взяв за основу схему определения отношений струк- турного сходства, можно определить и иные ассоциативные отношения.
Рассмотрим теперь введенные отношения c менее формальной точки зрения. Можно привести естественно-языковое описание введенных отношений. То обстоятельство, что пара событий принадлежит отно- шению R
1
означает, что событие e
1
всегда сопровождается собы-
тием
e
2
; если пара событий принадлежит отношению R
2
, то событие
e
1
всегда увеличивает возможность появления события
e
2
; R
3
—
событие
e
1
иногда сопровождается событием
e
2
; R
4
— событие e
1
иногда может увеличивать возможность появления
e
2
; R
5
— собы-
тие
e
1
исключает событие
e
2
; R
6
— событие e
1
может исключать
событие
e
2
54
Гл. 1. Методы представления знаний
Примеры. Приведем в качестве примера упрощенные описания отношений из фрагментов некоторых баз знаний, в качестве языка представления знаний в которых использованы неоднородные семанти- ческие сети:
а) в области медицинской диагностики.
При наблюдении события «Боль при пальпации остистого от-
ростка пораженного позвонка» может наблюдаться событие «Бо-
лезнь Кольве».
При наблюдении события «Болезнь Кольве» всегда наблюдается
событие «Боль при пальпации остистого отростка пораженного
позвонка».
При наблюдении события «Болезненность при перкусии одного
или двух смежных остистых отростков» может наблюдаться со-
бытие «Ядро эпидурита».
При наблюдении события «Ядро эпидурита» всегда наблюдается
событие «Болезненность при перкусии одного или двух смежных
остистых отростков: болезненность»;
б) в области прогнозирования социальной напряженности.
При наблюдении события «Увеличение налогообложения на пред-
приятия» всегда наблюдается событие «Крупные предприниматели
не поддерживают», а при наблюдении события «Крупные предпри-
ниматели не поддерживают», может наблюдаться событие «Уве-
личение налогообложения на предприятии»;
в) в области психодиагностики.
При наблюдении события «Экзотическое место жизни» может
наблюдаться событие «Комплекс демонстративность».
При наблюдении события «Комплекс демонстративность» все-
гда наблюдается событие «Экзотическое место жизни».
При наблюдении события «Дружит с агрессивными животными
или героями» может наблюдаться событие «Комплекс спонтанная
агрессия».
При наблюдении события «Комплекс спонтанная агрессия» все-
гда наблюдается событие «Дружит с агрессивными животными
или героями».
1.4. Совместность
Можно показать, что наборов свойств симметричности/несим- метричности/антисимметричности, рефлексивности/нерефлексивности и т. д. недостаточно для установления взаимнооднозначного соответ- ствия между множеством всех отношений, определенных так, как это было сделано в п. 1.3.3, и множеством всех допустимых комбинаций их свойств. Поэтому в работе [15] было предложено новое свойство —
совместность компонентов каждой пары, являющейся элементом неко-
1.4. Совместность
55
торого отношения. Это свойство можно задать с помощью понятия матрицы совместности элементов. Дадим соответствующие определе- ния, следуя [15].
1.4.1. Вектор совместности событий. Рассмотрим вначале поня- тие вектора совместности элементов.
Пусть F есть отображение R → V , где R — множество отношений,
определеных выше, а V — множество векторов v = (a, b) длины два,
таких, что a ∈ {0, 1, ε}, b ∈ {0, 1, τ}; i k
, j r
— индексы свойств эле- ментов.
Тогда F (R) = (a, b), где a =
1, если ∀r ∃k такое, что i k
= j r
,
ε, если ∃k ∃r такие, что i k
= j r
Иначе говоря, если множество индексов свойств второго элемента вложено во множество индексов свойств первого элемента, то a = 1;
если множества свойств пересекаются, то a = ε.
Случай a = 0 подразумевает отсутствие общих свойств у элемен- тов. Это обстоятельство свидетельствует о том, что рассматриваемая пара элементов не принадлежит какому-либо отношению структурного сходства.
Будем предполагать, что элементы e
1
и e
2
имеют хотя бы одно общее свойство. Определим b — второй компонент вектора V — следу- ющим образом:
b =
1, если ∀k ∀r таких, что i k
= j r
,
⇒ Di k
⊆ Dj r
,
τ
если ∀k ∀r таких, что i k
= j r
,
⇒ Di k
∩ Dj r
6= ∅,
0, если ∀k ∀r таких, что i k
= j r
,
⇒ Di k
∩ Dj r
= ∅,
где Dik — проекция pr i
(e) элемента e на множество D
i
(или область
значений
i-го признака элемента e).
Отображение F делит семейство отношений
R на шесть классов:
1. F (R) = (1, 1);
4. F (R) = (ε, 1);
2. F (R) = (1, τ);
5. F (R) = (ε, τ);
3. F (R) = (1, 0);
6. F (R) = (ε, 0).
Приведем соответствующие диаграммы (рис. 1.8).
1.4.2. Матрицы совместности элементов. Такое разбиение отно- шений на шесть групп не является полным. Оно не различает некото- рые диаграммы и соответствующие им отношения. Например, диаграм- мы, приведенные ниже, нельзя различить с помощью отображения F .
Для более тонкого различения отношений такого рода рассмотрим отображение G: R → М, где М — множество матриц 2 × 2, состоящих
56
Гл. 1. Методы представления знаний
Рис. 1.8
из двух векторов пространства V , первый из которых равен F (R),
а второй равен F (R
−
1
).
Всего таких матриц 6 2
. Но некоторые из них не определяют никако- го отношения. Так, например, если второй компонент вектора v = F (R)
равен нулю, то и второй компонент вектора w = F (R
−
1
) также должен быть равен нулю. Следовательно, в матрице
M =
a
1
a
2
b
1
b
2
нижняя строка либо нулевая, либо ни b
1
, ни b
2
не равны нулю.
Рис. 1.9
1.5. Представление знаний в системах фреймов
57
При перестановке местами векторов v и w получим матрицу обра- щенного отношения R
−
1
. Его свойства описываются матрицей отноше- ния R.
Можно показать, что существует всего 11 различных матриц, Од- нако поскольку каждая матрица описывает два отношения — прямое и обращенное, то, на самом деле, таких отношений в два раза больше.
В случае, если отношение симметрично, то обращенное отношение совпадает с прямым; в иных случаях — с каким-нибудь другим от- ношением из числа исходных, а может быть, с новым уникальным отношением.
Обозначим множество таких матриц через М = {M
1
, M
2
, ..., M
11
}.
Можно показать, что:
Теорема 1.4.1. Для каждого отношения R
i
∈ R, порожденно-
го свойствами элементов предметной области, существуют един-
ственные матрица совместности
M
i
∈ M и набор значений свойств
рефлексивности, симметричности и транзитивности, определяю-
щие отношение
R
i
Теорема 1.4.2. Каждые матрица M
i
∈ M и набор свойств ре-
флексивности, симметричности и транзитивности определяют не
более одного отношения
R
i
∈ R.
1.5. Представление знаний в системах фреймов
1.5.1. Фреймы. Понятие фрейма было введено известным амери- канским ученым Марвином Минским в 1975 г.
М. Минский рассматривал фрейм как структуру данных для пред- ставления множества стереотипных ситуаций, событий и объектов,
а также их характеристик, признаков и свойств. Эта информация (о ха- рактеристикак, признаках и свойствах) хранится в слотах фрейма.
Можно говорить о существовании трех типов слотов:
1. Именованные слоты, которые могут заполняться данными, на- пример, слот ЧИСЛО КОНЕЧНОСТЕЙ во фрейме ЧЕТВЕРОНОГОЕ
ЖИВОТНОЕ. Данные, заполняющие слот, могут быть строкового типа,
целого, булевского и т. д. Некоторые слоты могут заполняться по умол- чанию. Например, в том же фрейме слот НАЛИЧИЕ ШЕРСТИ может заполняться по умолчанию, так как это справедливо в большинстве случаев.
2. Слоты могут иметь тип ISA или АКО. Слот ISA указывает на принадлежность объекта к определенному типу или на принадлеж- ность объекта, описываемого одним фреймом, к множеству объектов,
описываемым другим фреймом. Для этого слот ISA первого фрейма
повышающих эффективность процесса построения сети. Подробнее о роли таких процедур будет сказано в главе, посвященной приобрете- нию знаний.
НСС предназначены для описания, главным образом, таких пред- метных областей, которые можно отнести к плохо структурирован-
ным, т. е. областей, для которых не известен полный набор свойств их элементов, не полностью известна структура самих элементов,
а знания об элементах и их взаимосвязях и зависимостях не имеют
«готового», завершенного вида, такого, например, который описывается с помощью правил. При этом предполагается, что те связи и зависимо- сти, которые удается все же установить, носят локальный характер.
Определение 1.3.1. Неоднородной семантической сетью будем называть алгебраическую систему
H = hD, N, R, Fi,
где D = {D
1
, D
2
, ... , D
n
} — семейство непустых множеств; N ⊆ N —
выделенное подмножество множества слов конечной длины над неко- торым алфавитом; R — семейство бинарных отношений R
1
, R
2
, ... , R
q на N
2
; R
i
⊆ N
2
; i ∈ {1, 2, ..., q}. F = {f
1
, f
2
, ... , f m
} — семейство функ- ций, каждой из которых приписан некоторый тип. А именно, функция f
i
(i ∈ {1, 2, ..., m}) имеет тип hτ , ωi, где τ = hk1, k2, ..., kmi, если она определена на декартовом произведении D
k1
× D
k2
× ... × D
km
,
а областью ее значений является множество D
ω
, так что каждому
1.3. Cемантические сети для представления знаний
49
кортежу δ ∈ D
k1
× D
k2
× ... × D
km функция f i
типa hτ, ωi из F ставит в соответствие некоторое f(δ) ∈ D
ω
Назначение слов из N — именование элементов предметной обла- сти; каждое из множеств D соответствует некоторому свойству, а эле- менты этого множества — значениям свойства; отношения из семейства
R — бинарные отношения на множестве имен и, наконец, функции из семейства F предназначены для пополнения описания элементов предметной области, например, для вычисления значений некоторых свойств по значениям других.
Неоднородную семантическую сеть, определенную таким образом,
будем называть интенсиональной семантической сетью.
Свяжем, далее, с каждым именем n ∈ N свой тип τ =
= hk1, k2, ..., kmi, ki ∈ {1, 2, ..., n}, и поставим ему в соответ- ствие e — некоторое подмножество декартового произведения
D
k1
× D
k2
× ... × D
km
; того же типа τ, где D
ki
∈ D. Тогда e
будем называть экстенсионалом (или множеством экземпляров или множеством примеров) элемента c именем n типа τ. Понятно, что в этом случае декартовому произведению D
k1
× D
k2
× ... × D
km
,
каждому его подмножеству e и каждому элементу δ ∈ е также следует приписать тип τ = hk1, k2, ..., kmi. Множество экстенсионалов для всех элементов из N обозначим через E.
Расширим на Е семейство отношений R так, что каждому отноше- нию R
i
⊆ N
2
будет соответствовать отношение R
i
⊆ Е
2
таким образом,
что если пара (n j
, n k
) ∈ R
i
, то соответствующая пара (e j
, e k
) ∈ R
i
Обозначим семейство отношений R
i
, где i ∈ {1, 2, ..., q}, через R.
Заменив в определении 1.3.1 N на E и R на R, получим конструк- цию
H = hD, E, R, Fi,
которую будем называть экстенсиональной семантической сетью. Для всякого e ∈ E, поскольку это не приведет к недоразумениям, мы сохра- ним название «элемент».
Рассмотрим более детально отношения из R. Для этого исполь- зуем то обстоятельство, что элементы из E (входящие в пары из отношений R
i
) имеют некоторую внутреннюю структуру, т. е. по су- ществу, также являются отношениями, определенными на множествах из D. Это позволяет выразить отношения, определенные на E через отношения на множествах из D. Такой подход позволит построить порождающие процедуры для некоторых классов отношений, которые уместно считать отношениями структурного сходства, ассоциативными отношениями и каузальными отношениями.
Впрочем, последние, как мы увидим, окажутся подклассом класса ассоциативных отношений.
50
Гл. 1. Методы представления знаний
Отношения структурного сходства. Пусть e
1
, e
2
∈ E, δ и γ —
примеры e
1
и e
2
, δ ∈ e
1
, γ ∈ e
2
Положим δ = hδ
1
, δ
2
, ..., δ
k1
i, γ = hγ
1
, γ
2
, ..., γ
k2
i (здесь нижний ин- декс у компонент примеров означает индекс множества D из семей- ства D. Таким образом, совпадение индексов компонент примеров сведетельствует о принадлежности последних одному и тому же мно- жеству D).
Определение 1.3.2. Отношением R
1
на Е будем называть та- кое X ⊆ Е
2
, в котором для всякой пары (e
1
, e
2
) ∈ X имеет место
∀δ∃γ ∀γ
i
∃δ
i такие, что (i = j) и (δ
i
= γ
j
).
Определение 1.3.3. Отношением R
2
на Е будем называть та- кое X ⊆ Е
2
, в котором для всякой пары (e
1
, e
2
) ∈ X имеет место
∀δ∃γ ∃γ
i
∃δ
i такие, что (i = j) и (δ
i
= γ
j
).
Определение 1.3.4. Отношением R
3
на Е будем называть такое
X ⊆ Е
2
, что для всякой пары (e
1
, e
2
) ∈ X имеет место ∃δ ∃γ (γ = δ).
Определение 1.3.5. Отношением R
4
на Е будем называть такое
X ⊆ Е
2
, что для всякой пары (e
1
, e
2
) ∈ X имеет место ∀δ ∃γ∀ δ
i
∃γ
i такие, что (i = j) и (δ
i
= γ
j
).
Определение 1.3.6. Отношением R
5
на Е будем называть такое
X ⊆ Е
2
, что для всякой пары (e
1
, e
2
) ∈ X имеет место ∀δ ∀γ ∀γ
i
∀δ
j такие, что (i = j) и (δ
i
6= γ
j
).
Определение 1.3.7. Отношением R
6
на Е будем называть такое
X ⊆ Е
2
, что для всякой пары (e
1
, e
2
) ∈ X ∀δ ∀γ ∃γ
i
∃δ
j такие, что
(i = j) и (δ
i
6= γ
j
).
Далее будем полагать, что читателю известны такие свойства би- нарных отношений как транзитивность, рефлексивность и симметрич- ность. Обычно, когда говорят о свойстве симметричности, имеют ввиду одно из трех значений: либо собственно симметричность, либо несим- метричность, либо антисимметричность. Свойство транзитивности име- ет три значения: транзитивно, нетранзитивно и антитранзитивно; ре- флексивность также имеет три значения: рефлексивно, нерефлексивно и антирефлексивно.
Установим свойства введенных отношений.
Утверждение 1.3.1. R
1
и
R
4
— частичные порядки.
Утверждение 1.3.2. R
2
нетранзитивно, рефлексивно, несиммет-
рично.
Утверждение 1.3.3. R
3
нетранзитивно, рефлексивно, симмет-
рично.
1.3. Cемантические сети для представления знаний
51
Утверждение 1.3.5. R
5
нетранзитивно, антирефлексивно, сим-
метрично.
Утверждение 1.3.6. R
6
нетранзитивно, антирефлексивно, не-
симметрично.
Д о к а з а т е л ь с т в а приведенных утверждений достаточно просты.
Докажем, например, что отношение R
1
— частичный порядок.
Пусть пары (e
1
, e
2
) и (e
2
, e
3
) принадлежат R
1
. Задача состоит в том,
чтобы показать, что (e
1
, e
3
) ∈ R
1
. Пусть λ ∈ e
3
и λ = hλ
1
, λ
2
, ..., λ
k3
i.
Так как ∀δ ∃γ такое, что ∀γ
i
∃δ
i
(δ
i
= γ
i
), то пусть для произвольного
δ
∗
найдется γ
∗
такое, что δ
∗
i
= γ
∗
i
. Но в силу того, что (e
2
, e
3
) ∈ R
1
,
∀γ ∃λ такое, что ∀λ
i
∃γ
i
(λ
i
= γ
i
), т. е. это справедливо и для γ
∗
. Если
λ
∗
— то самое λ, которое нашлось для γ
∗
и для которого λ
∗
i
= γ
∗
i
, то из этого равенства и из δ
∗
i
= γ
∗
I
следует, что λ
∗
i
= δ
∗
i
, а так как δ
∗
был выбран произвольно, то это и означает, что ∀δ ∃λ ∀λ
i
∃δ
i
(λ
i
= δ
i
), т. е.
(e
2
, e
3
) ∈ R
1
, что и означает транзитивность R
1
Рефлексивность R
1
следует из того, что в качестве γ можно вы- брать δ, а антисимметричность легко доказывается от противного.
Понятно, что всех возможных комбинаций таких свойств — 27.
Однако не все свойства определенных таким образом отношений неза- висимы. Например, антирефлексивное отношение не может быть анти- симметричным. В результате таких рассуждений получим 20 отноше- ний, определяемых наборами своих свойств. Можно показать также,
что указанные свойства определяют отошения не единственным об- разом, т. е. существуют различным образом определенные отношения,
обладающие одними и теми же наборами свойств. Поэтому ниже мы введем еще одно свойство отношений такого рода — свойство совмест- ности.
Введем теперь специальные диаграммы для графического представ- ления таких отношений. Для этого каждое из событий e i
представим в виде плоской фигуры с двумя измерениями, например, в виде пря- моугольника, по горизонтальной стороне которого будем откладывать свойства событий, по вертикали — множества значений по каждому из свойств или объемы. (Здесь для нас несущественно то обстоятельство,
что эти объемы различны.) Тогда общим свойствам двух событий бу- дет соответствовать проекция их пересечения на горизонтальную ось,
общим значениям свойств — проекция пересечения событий на вер- тикальную ось. Так, например, то обстоятельство, что среди примеров события e
1
и среди примеров события e
2
найдутся такие, что пример события e
2
являются подмножеством некоторого примера события e
1
,
будет отражено на следующей диаграмме (рис. 1.6).
Теперь представим в виде диаграмм некоторые из отношений струк- турного сходства R
1
–R
6
(рис. 1.7).
52
Гл. 1. Методы представления знаний
Рис. 1.6
Рис. 1.7
Как мы видим, отношения структурного сходства порождены нали- чием/отсутствием общих признаков у тех пар элементов предметной области, которые им принадлежат, при этом эти общие признаки про- являются «одновременно» у обоих элементов пары. Это означает, что пары событий, принадлежащие отношениям R
1
–R
6
, всегда являются событиями одного и того же состояния.
В отличие от этого отношения, рассматриваемые ниже, порождены функциональными зависимостями на множествах атрибутов. Свойства их зависят, главным образом, от характера функций из F. В частности,
если функции из F представляют собой временные функции, т. е.
вырабатывают свои значения через некоторые промежутки времени, то
R
7
и R
8
описывают связи событий различных состояний, т. е. в этом
1.3. Cемантические сети для представления знаний
53
смысле являются отношениями, отражающими динамику системы. Да- дим соответствующие определения.
Ассоциативные и каузальные отношения. Пусть
δ ∈ D
k1
× D
k2
×
× ... × D
km
; τ(δ) — тип δ; τ(β), τ(γ), ..., τ(λ) — типы β, γ, ... и λ
соответственно, так что τ(β) ⊆ τ(δ), τ(γ) ⊆ τ(δ), ..., τ(λ) ⊆ τ(δ),
и f p
, f q
, ..., f r
— функции из F, определеные на декартовых произведе- ниях типов β, γ, ..., λ и действующие в D
q
, D
p
, ... , D
r
, соответственно.
Функцию f
∗
(δ) = hf p
(β), f q
(γ), ... , f r
(λ)i будем называть композицией функций f q
, f p
, ..., f r
. Понятно, что значением f
∗
(δ) является неко- торый экземпяр декартового произведения D
q
× D
p
× ... × D
r
. Будем полагать здесь, что f
∗
(δ) = hδ
1
, δ
2
, ..., δ
k1
i, γ = hγ
1
, γ
2
, ..., γ
k2
i, δ ∈ e
1
,
γ ∈ e
2
Из множества ассоциативных и каузальных отношений рассмотрим только следующие.
Определение 1.3.8. Отношением R
7
на Е будем называть такое
X ⊆ Е
2
, что для всякой пары (e
1
, e
2
) ∈ X найдется композиция f
∗
функций из F такая, что ∀δ ∃γ ∀γ
i
∃δ
i такие, что (i = j) и (δ
i
= γ
j
).
Отношение R
7
будем называть каузальным отношением.
Определение 1.3.9. Отношением R
8
на Е будем называть такое
X ⊆ Е
2
, что для всякой пары (e
1
, e
2
) ∈ X существует композиция f
∗
функций из F такая, что ∃δ ∃γ ∃γ
i
∃δ
i такие, что (i = j) и (δ
i
= γ
j
).
Отношение R
8
будем называть ассоциативным отношением.
Приведем без доказательств следующие утверждения.
Утверждение 1.3.8. R
7
транзитивно, нерефлексивно, несиммет-
рично.
Утверждение 1.3.9. R
8
нетранзитивно, нерефлексивно, несим-
метрично.
Понятно, что взяв за основу схему определения отношений струк- турного сходства, можно определить и иные ассоциативные отношения.
Рассмотрим теперь введенные отношения c менее формальной точки зрения. Можно привести естественно-языковое описание введенных отношений. То обстоятельство, что пара событий принадлежит отно- шению R
1
означает, что событие e
1
всегда сопровождается собы-
тием
e
2
; если пара событий принадлежит отношению R
2
, то событие
e
1
всегда увеличивает возможность появления события
e
2
; R
3
—
событие
e
1
иногда сопровождается событием
e
2
; R
4
— событие e
1
иногда может увеличивать возможность появления
e
2
; R
5
— собы-
тие
e
1
исключает событие
e
2
; R
6
— событие e
1
может исключать
событие
e
2
54
Гл. 1. Методы представления знаний
Примеры. Приведем в качестве примера упрощенные описания отношений из фрагментов некоторых баз знаний, в качестве языка представления знаний в которых использованы неоднородные семанти- ческие сети:
а) в области медицинской диагностики.
При наблюдении события «Боль при пальпации остистого от-
ростка пораженного позвонка» может наблюдаться событие «Бо-
лезнь Кольве».
При наблюдении события «Болезнь Кольве» всегда наблюдается
событие «Боль при пальпации остистого отростка пораженного
позвонка».
При наблюдении события «Болезненность при перкусии одного
или двух смежных остистых отростков» может наблюдаться со-
бытие «Ядро эпидурита».
При наблюдении события «Ядро эпидурита» всегда наблюдается
событие «Болезненность при перкусии одного или двух смежных
остистых отростков: болезненность»;
б) в области прогнозирования социальной напряженности.
При наблюдении события «Увеличение налогообложения на пред-
приятия» всегда наблюдается событие «Крупные предприниматели
не поддерживают», а при наблюдении события «Крупные предпри-
ниматели не поддерживают», может наблюдаться событие «Уве-
личение налогообложения на предприятии»;
в) в области психодиагностики.
При наблюдении события «Экзотическое место жизни» может
наблюдаться событие «Комплекс демонстративность».
При наблюдении события «Комплекс демонстративность» все-
гда наблюдается событие «Экзотическое место жизни».
При наблюдении события «Дружит с агрессивными животными
или героями» может наблюдаться событие «Комплекс спонтанная
агрессия».
При наблюдении события «Комплекс спонтанная агрессия» все-
гда наблюдается событие «Дружит с агрессивными животными
или героями».
1.4. Совместность
Можно показать, что наборов свойств симметричности/несим- метричности/антисимметричности, рефлексивности/нерефлексивности и т. д. недостаточно для установления взаимнооднозначного соответ- ствия между множеством всех отношений, определенных так, как это было сделано в п. 1.3.3, и множеством всех допустимых комбинаций их свойств. Поэтому в работе [15] было предложено новое свойство —
совместность компонентов каждой пары, являющейся элементом неко-
1.4. Совместность
55
торого отношения. Это свойство можно задать с помощью понятия матрицы совместности элементов. Дадим соответствующие определе- ния, следуя [15].
1.4.1. Вектор совместности событий. Рассмотрим вначале поня- тие вектора совместности элементов.
Пусть F есть отображение R → V , где R — множество отношений,
определеных выше, а V — множество векторов v = (a, b) длины два,
таких, что a ∈ {0, 1, ε}, b ∈ {0, 1, τ}; i k
, j r
— индексы свойств эле- ментов.
Тогда F (R) = (a, b), где a =
1, если ∀r ∃k такое, что i k
= j r
,
ε, если ∃k ∃r такие, что i k
= j r
Иначе говоря, если множество индексов свойств второго элемента вложено во множество индексов свойств первого элемента, то a = 1;
если множества свойств пересекаются, то a = ε.
Случай a = 0 подразумевает отсутствие общих свойств у элемен- тов. Это обстоятельство свидетельствует о том, что рассматриваемая пара элементов не принадлежит какому-либо отношению структурного сходства.
Будем предполагать, что элементы e
1
и e
2
имеют хотя бы одно общее свойство. Определим b — второй компонент вектора V — следу- ющим образом:
b =
1, если ∀k ∀r таких, что i k
= j r
,
⇒ Di k
⊆ Dj r
,
τ
если ∀k ∀r таких, что i k
= j r
,
⇒ Di k
∩ Dj r
6= ∅,
0, если ∀k ∀r таких, что i k
= j r
,
⇒ Di k
∩ Dj r
= ∅,
где Dik — проекция pr i
(e) элемента e на множество D
i
(или область
значений
i-го признака элемента e).
Отображение F делит семейство отношений
1 2 3 4 5 6 7 8 9 ... 33
R на шесть классов:
1. F (R) = (1, 1);
4. F (R) = (ε, 1);
2. F (R) = (1, τ);
5. F (R) = (ε, τ);
3. F (R) = (1, 0);
6. F (R) = (ε, 0).
Приведем соответствующие диаграммы (рис. 1.8).
1.4.2. Матрицы совместности элементов. Такое разбиение отно- шений на шесть групп не является полным. Оно не различает некото- рые диаграммы и соответствующие им отношения. Например, диаграм- мы, приведенные ниже, нельзя различить с помощью отображения F .
Для более тонкого различения отношений такого рода рассмотрим отображение G: R → М, где М — множество матриц 2 × 2, состоящих
56
Гл. 1. Методы представления знаний
Рис. 1.8
из двух векторов пространства V , первый из которых равен F (R),
а второй равен F (R
−
1
).
Всего таких матриц 6 2
. Но некоторые из них не определяют никако- го отношения. Так, например, если второй компонент вектора v = F (R)
равен нулю, то и второй компонент вектора w = F (R
−
1
) также должен быть равен нулю. Следовательно, в матрице
M =
a
1
a
2
b
1
b
2
нижняя строка либо нулевая, либо ни b
1
, ни b
2
не равны нулю.
Рис. 1.9
1.5. Представление знаний в системах фреймов
57
При перестановке местами векторов v и w получим матрицу обра- щенного отношения R
−
1
. Его свойства описываются матрицей отноше- ния R.
Можно показать, что существует всего 11 различных матриц, Од- нако поскольку каждая матрица описывает два отношения — прямое и обращенное, то, на самом деле, таких отношений в два раза больше.
В случае, если отношение симметрично, то обращенное отношение совпадает с прямым; в иных случаях — с каким-нибудь другим от- ношением из числа исходных, а может быть, с новым уникальным отношением.
Обозначим множество таких матриц через М = {M
1
, M
2
, ..., M
11
}.
Можно показать, что:
Теорема 1.4.1. Для каждого отношения R
i
∈ R, порожденно-
го свойствами элементов предметной области, существуют един-
ственные матрица совместности
M
i
∈ M и набор значений свойств
рефлексивности, симметричности и транзитивности, определяю-
щие отношение
R
i
Теорема 1.4.2. Каждые матрица M
i
∈ M и набор свойств ре-
флексивности, симметричности и транзитивности определяют не
более одного отношения
R
i
∈ R.
1.5. Представление знаний в системах фреймов
1.5.1. Фреймы. Понятие фрейма было введено известным амери- канским ученым Марвином Минским в 1975 г.
М. Минский рассматривал фрейм как структуру данных для пред- ставления множества стереотипных ситуаций, событий и объектов,
а также их характеристик, признаков и свойств. Эта информация (о ха- рактеристикак, признаках и свойствах) хранится в слотах фрейма.
Можно говорить о существовании трех типов слотов:
1. Именованные слоты, которые могут заполняться данными, на- пример, слот ЧИСЛО КОНЕЧНОСТЕЙ во фрейме ЧЕТВЕРОНОГОЕ
ЖИВОТНОЕ. Данные, заполняющие слот, могут быть строкового типа,
целого, булевского и т. д. Некоторые слоты могут заполняться по умол- чанию. Например, в том же фрейме слот НАЛИЧИЕ ШЕРСТИ может заполняться по умолчанию, так как это справедливо в большинстве случаев.
2. Слоты могут иметь тип ISA или АКО. Слот ISA указывает на принадлежность объекта к определенному типу или на принадлеж- ность объекта, описываемого одним фреймом, к множеству объектов,
описываемым другим фреймом. Для этого слот ISA первого фрейма