Файл: Методыискусственногоинтеллекта.pdf

58
Гл. 1. Методы представления знаний
содержит имя фрейма, соответствующего множеству объектов; напри- мер, для фрейма ШАРИК это может быть фрейм СОБАКА.
Слот АКО специфицирует отношение между двумя типами; а имен- но, указывает на включение множества объектов, описываемых одним фреймом, в множество объектов, описываемых вторым фреймом. Для этого слот АКО первого фрейма содержит имя второго фрейма. На- пример, для фрейма ЧЕТВЕРОНОГОЕ ЖИВОТНОЕ это может быть фрейм ЖИВОТНОЕ.
3. Слоты могут носить процедурный характер. Например, во фрейме
СОБАКА значение слота КОЛИЧЕСТВО ЕЖЕДНЕВНО ПОТРЕБЛЯ-
ЕМОЙ ПИЩИ вычисляется как функция ее размера, веса и возраста.
Разумеется, фрейм должен содержать соответствующие слоты, а имен- но, ВЕС, РАЗМЕР, ВОЗРАСТ.
Заметим теперь, что один из слотов фрейма СОБАКА должен иметь тип АКО и содержать информацию о том, что собака есть ЧЕТВЕ-
РОНОГОЕ ЖИВОТНОЕ. Это, кстати, означает, что СОБАКА будет наследовать значения именованных слотов фрейма ЧЕТВЕРОНОГОЕ
ЖИВОТНОЕ, таких как ЧИСЛО КОНЕЧНОСТЕЙ, НАЛИЧИЕ ШЕР-
СТИ и других.
Приведем теперь более точное определение фрейма в нотации
Бэкуса–Наура:
hфреймi::=hимя фреймаi{hтело фреймаi}
hтело фреймаi::=hмножество слотовi hмножество слотовi::=hслотi|hслотi,hмножество слотовi hслотi::=hимя слотаi:hзначение слотаi hзначение слотаi::=hимя фреймаi|hимя процедурыi|hмножествоi hмножествоi::=hдискретное множествоi|hплотное множествоi hдискретное множествоi::=hэлемент множестваi,hмножествоi hэлемент множестваi::=hидентификаторi hплотное множествоi::=hинтервалi|hполуинтервалi|hотрезокi
1.5.2. Системы фреймов. Итак, фреймы могут ссылаться друг на друга через свои слоты. На них могут быть заданы отношения ЭЛЕ-
МЕНТ–МНОЖЕСТВО (ISA) и КЛАСС–ПОДКЛАСС (AKO). Фреймы в смысле, определенном выше, принято иногда называть фреймами- прототипами. Помимо этого, вводится понятие фрейм-экземпляра (или примера). Фрейм-экземпляр — это совокупность значений слотов, удо- влетворяющих некоторому фрейму-прототипу. Иначе говоря, фрейм- экземпляр — это кортеж значений признаков, каждый из которых удовлетворяет некоторому слоту.
Агрегатом hR
1
, R
2
, ..., R
k i назовем соединение кортежей R
1
, R
2
,
..., R
k такое, что каждый кортеж R
i является фреймом-экземпляром,
удовлетворяющим какому-либо фрейму-прототипу.

1.6. Элементы дескриптивной логики
59
Элементарным фреймом-прототипом будем называть тот фрейм, на который не ссылается никакой иной фрейм.
Элементарный фрейм является выполнимым, если:
а) значения переменных, подставленных в слоты фрейма, соответ- ствуют областям их возможных значений;
б) на места формальных параметров подставлены фактические пара- метры процедур и выполняются условия их (процедур) активно- сти.
Если два фрейма F
1
и F
2
связаны отношением ISA или AKO, то фрейм F
2
будет считаться выполненным, если выполнен F
1
1.5.3. Основная вычислительная задача в системе фреймов.
Пусть Σ — система фреймов и задан агрегат σ. Основная вычисли- тельная задача в системе фреймов [16] заключается в эффективном вычислении отношения истинности σ Σ.
Процедура вычисления отношения истинности включает сле- дующие шаги:
Шаг 1. Удовлетворение всех областей значений слотов фреймов зна- чениями, входящими в этот агрегат.
Шаг 2. Вычисление значений всех функций, фактическими парамет- рами которых являются соответствующие значения агрегата σ.
Шаг 3. Переход по связям ISA и АКО.
Шаг 4. Переход к шагу 1.
Процедура завершает работу после того, как а) все слоты всех связанных отношениями ISA и AKO фреймов будут удовлетворены и б) не останется неиспользованных ISA и AKO связей.
Отношение истинности считается вычисленным с завершением работы процедуры. Результатом является множество фреймов, выпол- ненных на агрегате σ.
1.6. Элементы дескриптивной логики
Дескриптивные логики возникли как способ описания концепту- альной системы предметной области и некоторых способов вывода в интеллектуальных системах. В определенном смысле дескриптив- ные логики можно рассматривать как логическое основание некоторых методов представления знаний, например, объектно-ориентированных представлений, таких как систем фреймов и достаточно простых се- мантических сетей (главным образом, их декларативной компоненты).
Формулы языка дескриптивной логики являются выражениями, со- стоящими из общеупотребительных и специализированных конструк- тов (операций) над унарными и бинарными предикатными символами

60
Гл. 1. Методы представления знаний
и соответствующими фомулами и над предметными константами. Унар- ные предикатные символы служат для образования концептов (поня- тий), а бинарные — для образования так называемых ролей. Концепты описывают общие свойства коллекций индивидов и интерпретируются как множества объектов. Роли интерпретируются как бинарные отно- шения на множествах объектов.
Одним из основных конструктов является конструкт ограничения
значения. Например, ограничение значения, записываемое как
∀R.C
требует, чтобы все индивиды, находящиеся в отношении R с некоторым концептом, принадлежали концепту C.
С точки зрения семантики концепт имеет следующую теоретико- множественную интерпретацию: он интерпретируется как множество индивидов и ролей, которые, в свою очередь, интерпретируются как множества пар индивидов. Универсум для интерпретации может быть выбран, вообще говоря, произвольно и быть бесконечным [20].
Атомарные концепты интерпретируются как подмножества универ- сума, например интерпретация концепта C ⊓ D есть множество инди- видов, принадлежащих теоретико-множественному пересечению интер- претаций концептов C и D.
Предположим, например, что ЖЕНСКИЙ ПОЛ, ПЕРСОНА и
ЖЕНЩИНА суть атомарные концепты и ИМЕЕТ РЕБЕНКА и ИМЕ-
ЕТ РОДСТВЕННИЦУ суть атомарные роли. С использованием опе- раторов пересечения, объединения и дополнения можно описать кон- цепты ПЕРСОНА НЕ ЖЕНСКОГО ПОЛА и ПЕРСОНА МУЖСКОГО
ИЛИ ЖЕНСКОГО ПОЛА:
ПЕРСОНА ⊓⌉ ЖЕНСКИЙ ПОЛ и ЖЕНСКИЙ ПОЛ ⊔⌉ ЖЕН-
СКИЙ ПОЛ.
Использование квантора существования позволяет описывать кон- цепты, являющиеся экзистенциальными конструкциями типа: ПЕРСО-
НА ИМЕЕТ РЕБЕНКА ЖЕНСКОГО ПОЛА:
∃ ИМЕЕТ РЕБЕНКА. ЖЕНСКИЙ ПОЛ.
Концепт, содержащий утверждение, что у некоторой персоны все дети женского пола, опишется следующим образом:
∀ ИМЕЕТ РЕБЕНКА. ЖЕНСКИЙ ПОЛ.
Описание концепта РОДИТЕЛЬ как множества лиц, имеющих, по крайней мере, одного ребенка, такого, что каждый ребенок является индивидом концепта ПЕРСОНА, будет иметь следующий вид:
∃ ИМЕЕТ РЕБЕНКА. ПЕРСОНА ⊓∀ ИМЕЕТ РЕБЕНКА. ПЕРСО-
НА.
Дескриптивные логики (DL) используютcя в различных прило- жениях методов искусственного интеллекта, в частности, в концеп- туальном моделировании, планировании поведения и онтологической инженерии. Уточним теперь основные понятия дескриптивных логик.

1.6. Элементы дескриптивной логики
61
1.6.1. Основные понятия. Элементарными конструкциями де- скриптивной логики являются атомарные концепты и атомарные
роли. Более сложные конструкции строятся индуктивным образом с помощью конструкторов концептов. Будем далее использовать буквы A и B для атомарных концептов, R, Q, S — для атомарных ролей и C и D — для представления концептов. Далее для описания основных синтаксических конструкций дескиптивной логики использу- ем атрибутивный язык AL. Рассмотрим его синтаксис, следуя [18]:
C, D → A (введение атомарного концепта),
⊤
(универсальный концепт),
⊥
(ложный концепт),
¬A
(атомарное отрицание),
C ⊓ D
(пересечение),
∀R. C
(ограничение значения),
∃R. T
(ограниченный квантор существования).
Приведем некоторые примеры применения введенного синтаксиса,
вспомнив концепты, использованные в качестве примеров в начале настоящего параграфа.
Так, концепт ПЕРСОНА ⊓ ∃ ИМЕЕТ РЕБЕНКА.⊤
означает, что некоторая персона имеет ребенка; концепт
ПЕРСОНА ⊓ ∀ ИМЕЕТ РЕБЕНКА.ЖЕНСКИЙ ПОЛ
означает, что все дети данной персоны женского пола, а концепт
ПЕРСОНА ⊓ ∀ ИМЕЕТ РЕБЕНКА.⊥ означает, что указанная персона не имеет детей.
Введем теперь интерпретацию языка AL.
Будем называть интерпретацией I языка AL пару (µ, Φ), где µ —
непустое множество (универсум) и Φ — интерпретирующее отображе- ние, ставящее в соответствие каждому индивиду элемент множества µ,
имени концепта — некоторое подмножество µ, имени роли — подмно- жество µ × µ.
Пусть I — некоторая интерпретация, например, C
I
–интерпретация концепта C.
Опишем семантику основных конструктов дескриптивной логики
[19, 20].
Будем говорить, что C ⊑ D, если C
I
⊆ D
I
для любой интерпрета- ции I; C эквивалентно D, C ≡ D, если C
I
= D
I
в любой интерпрета- ции I.
Интерпретация I является моделью для концепта C, если множе- ство C
I
, называемое интерпретацией концепта C, не пусто.

62
Гл. 1. Методы представления знаний
Т а б л и ц а 1.2. Семантика конструктов дескриптивной логики
Имя конструкта
Синтаксис
Семантика
Истина
⊤
µ
Ложь
⊥
∅
Имя концепта
A
A
I
⊆ µ
Коньюнкция
C ⊓ D
C
I
∩ D
I
Дизьюнкция (U)
C ⊔ D
C
I
∪ D
I
Отрицание (C)
¬C
µ\C
I
Квантор
∀R. C
{d
1
|d
1
∈ µ, ∀d
2
: (d
1
, d
2
) ∈ R
I
→ d
2
∈ C
I
}
всеобщности
Квантор
∃R. C
{d
1
|d
1
∈ µ, ∃d
2
: (d
1
, d
2
) ∈ R
I
&d
2
∈ C
I
}
существования
Численное
(> nR)
{d
1
|d
1
∈ µ, {d
2
|(d
1
, d
2
) ∈ R
I
} > n}
ограничение
(6 nR)
{d
1
|d
1
∈ µ , {d
2
|(d
1
, d
2
) ∈ R
I
} 6 n}
Имя роли
R
R
I
⊆ µ × µ
Коньюнкция ролей
R ⊓ Q
P
I
∩ Q
I
Композиция ролей
R ◦ S
{(d, c|∃f (d, f ) ∈ R
I
∧ (f , c) ∈ S
I
}
1.6.2. База знаний в дескриптивной логике. Базой знаний бу- дем называть пару Σ = (Tbox, Abox). Первая компонента базы знаний
Tbox (Terminology box) содержит интенсиональные знания: опреде- ления концептов, разбиение их на классы. Вторая компонента Abox
(Assertions box) содержит экстенсиональные знания и включает в себя утверждения об отношениях между элементами и классами элемен- тов [21].
Определение 1.6.1. Интерпретация I называется моделью базы знаний Σ, если I удовлетворяет всем утверждениям, содержащимся в базе знаний.
Определение 1.6.2. База знаний Σ называется выполнимой, если она имеет модель.
Определение 1.6.3. База знаний Σ логически влечет α, где α —
формула из TBox или Abox (обозначение Σ α), если α выполнима в любой модели базы знаний Σ.
1.6.3. Рассуждения в дескриптивной логике. В системах пред- ставления знаний, основанных на дескриптивой логике, возможны некоторые специфические типы рассуждений. Можно выделить рас- суждения о концептах, рассуждения о терминологии, рассуждения об отношениях и совместные рассуждения о терминологии и отношениях.

1.6. Элементы дескриптивной логики
63
Проверка выполнимости концепта является ключевой задачей лю- бого вывода. Большое число важных задач вывода сводится к проверке выполнимости/невыполнимости концептов. Например, для проверки корректности модели предметной области или для оптимизации за- проса, сформулированного в виде концепта, хорошо бы знать — не является ли некоторый концепт более общим, чем другой? Это, по существу, есть формулировка задачи поглощения:
«Концепт
C поглощается концептом D (C ⊑ D), если в каждой
модели
I верно C
I
⊆ D
I
».
Пусть дана база знаний Σ = (Tbox, Abox), концепты C и D, а также индивид a. Определим основные задачи дескриптивной логики [22, 23]:
• проблема выполнимости концепта C в базе знаний Σ (Σ 2 C ≡
≡ ⊥) состоит в проверке, удовлетворяет ли концепт C базе зна- ний Σ, т. е. существует ли модель I базы знаний Σ, где C
I
6= ∅;
• проблема истинности выражения C(a) в базе знаний Σ
(Σ C(a)) состоит в проверке, удовлетворяет ли выражение C(a)
любой модели базы знаний Σ;
• проблема консистентности базы знаний Σ (Σ 2 ∅) состоит в проверке, имеет ли база знаний Σ модель;
• проблема категоризации концептов CD в базе знаний Σ
(Σ CD) состоит в проверке, верно ли C
I
⊆ D
I
в любой модели I базы знаний Σ.
Приведем основные алгоритмы рассуждений в DL. Алгоритм А1,
предназначеный для проверки истинности выражения C ⊑ D, основан на сравнении синтаксической структуры концептов.
Алгоритм А1:
1. Все выражения с вложенными коньюнкциями типа A ⊓ (B ⊓ C)
с помощью очевидных эквивалентных преобразований приво- дятся к нормальной форме A ⊓ B ⊓ C. Все коньюнкции типа
∀P. D ⊓ P. C очевидно приводятся к виду ∀P. (D ⊓ C).
2. Пусть C = C
1
⊓ ... ⊓ C
m и D = D
1
⊓ ... ⊓ D
n
. Тогда C ⊑ D если и только если для каждого D
i верно следующее:
a) если D
i является атомарным концептом или концептом типа
∃P , то существует некоторое C
j такое, что D
i
= C
j
;
b) если D
i является концептом типа ∀P. D
′
, то существует некоторое C
j вида ∀P. C
′
такое, что C
′
D
′
Приведем без доказательства
Утверждение 1.6.4. Сложность алгоритма А1 равна O(|C| ×
× |D|).
Метод семантических таблиц. Описываемый ниже метод можно назвать семантическим: он состоит в проверке, является ли форму-

64
Гл. 1. Методы представления знаний
ла F логическим следствием рассматриваемой теории T ? Для этого требуется построить модель, где F является ложной. Если результат достигнут, то ответ НЕТ, формула не является логическим следствием данной теории. Если же такой интерпретации не найдено, выдается ответ ДА и формула F является логическим следствием теории T . Со- ответствующие правила вывода сконструированы на основе семантики конструктов дескриптивной логики. Рассмотрим, например, конструкт
∃R. C. Если дана интерпретация I, в которой домен содержит элемент a ∈ (∃R. C)
I
, то в соответствии с семантикой конструктов должен существовать элемент b (не обязательно отличный от a), такой что
(a, b) ∈ R и b ∈ C, что должно быть истинно в любой интерпретации.
Таким образом, абстрагировавшись от интерпретации, можно утвер- ждать, что если имеется некоторый элемент x, такой что x ∈ ∃R. C, то должен найтись и элемент y, такой что x и y связаны ролью R(xRy)
и y является элементом C.
Пусть требуется сконструировать интерпретацию S такую, что кон- цепт ∃R. C имеет, по крайней мере, один пример x ∈ ∃R. C. Используя семантические соображения, получаем, что в этом случае S должна содержать элемент y такой, что xRy и y ∈ C. Таким образом, получаем следующее правило трансформации, которое назовем «→
∃
-правило»:
если
Σ содержит выражение ∃R. C(x) и не существует z, та-
кого что
xRz и C(z) содержится в Σ, то добавить в Σ новую
переменную
y. (Здесь Σ — база знаний; C(x) означает, что x
присутствует в
C в качестве переменной.)
Аналогичным образом можно построить правила для каждого из имеющихся конструктов: ⊓, ⊔, ∀, ∃, 6, >. Приведем в качестве приме- ров следующие правила для ⊓ и ⊔:
«→
⊓
-правило»:
если
Σ содержит выражение (C
1
⊓ C
2
)(x), но не содержит C
1
(x)
вместе с
C
2
(x), то в Σ добавить C
1
(x) и C
2
(x).
«→
⊔
-правило»:
если
Σ содержит выражение (C
1
⊔ C
2
(x), но не содержит ни C
1
(x),
ни
C
2
(x), то добавить в Σ либо C
1
(x), либо C
2
(x).
Пусть C
0
— концепт в нормальной форме (с отрицаниями). Для установления выполнимости C
0
алгоритм начнет работу с базы зна- ний Σ (точнее, с той ее компоненты, которую выше мы обозначили как ABox) и применит к ней правила вывода, описанные выше, пока не будут исчерпаны все применимые правила. Если пополненная таким образом база знаний Σ не содержит очевидных противоречий, то она

1.6. Элементы дескриптивной логики
65
консистентна и, следовательно, C
0
выполним, и неконсистентна (и C
0
невыполним) в противном случае.
Приведенные выше правила преобразуют ABox в конечное число новых ABox-ов, так что исходный ABox консистентен, если хотя бы один из новых является консистентным. Каждое правило из приведен- ных выше применяется к текущему конечному множеству S ABox-ов
следующим образом: оно берет некоторый ABox A из S и заменяет его либо одним ABox-ом A
′
, либо двумя ABox-ами A
′
и A
′′
, либо некоторым конечным числом ABox-ов.
Имеет место следующее утверждение:
Если
S
′
получено из конечного множества ABox-ов
S посредством
приведенных выше правил, то
S консистентно, если и только если
S
′
консистентно.