Software & Systems

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

Дескриптивная логика

Системы, основанные на дескриптивной логике (ДЛ), были предложены как развитие KL-ONE [13] с семантикой Тарского для логики первого порядка. Среди таких систем NIKL [9], CLASSIC [6], LOOM [11]. Идеей усовершенствования языка KL-ONE стало усложнение основных конструкций языка – примитивных концептов. Например, кроме концепта ЧЕ-ЛОВЕК, возможно определить концепт ЧЕЛОВЕК, КОТОРЫЙ ИМЕЕТ НЕ МЕНЕЕ ТРОИХ ДЕТЕЙ, и т.п.

Семейство логик, называемое ДЛ, подходит для описания классов и отношений между ними. ДЛ включает в себя все особенности, необходимые для логической переформулировки моделей данных в различных контекстах.

Некоторые популярные формализмы представления данных, такие как отношение сущности (entity relationships model) и объектно-ориентированные формализмы представления данных могут быть выражены термами специальных логик данного семейства.

Приложения ДЛ можно разделить на семантические модели и инженерию знаний, а также на объектно-ориентированное программирование.

ДЛ использует язык концептов L [8], состоящий из множества конструктов для представления классов и отношений между ними. Синтаксис и семантика основных конструктов приведены в таблице 1. С остальными конструктами можно ознакомиться в работе [12].

Таблица 1

Концепты – это именованные множества элементов, роли – бинарные отношения между ними. Концепты и роли являются одно- и двухместными предикатами соответственно. Интерпретация I=(m,F) – непустое множество m и функция интерпретации F, отображающая каждое индивидное имя в элемент множества m, имя концепта – в некоторое подмножество m, имя роли – в подмножество m´m, каждый индивидуум – в элемент m.

Различается несколько языков ДЛ, имеющих различный набор конструктов и различную сложность вычислений.

Наиболее простой язык FL¾ [7] включает в себя всеобщность, конъюнкцию и неполный квантор существования, то есть $R.T. Язык AL расширяет FL¾ концептами ^, T и отрицанием (ù А, где А – имя простого концепта). Остальные языки ДЛ являются расширениями FL¾ и AL. Например, FLEU¾  – это FL¾ с полной квантификацией существования и дизъюнкцией. Название языков ДЛ различается добавлением символов, соответствующих конструктам логики [10].

База знаний в ДЛ есть пара å = (Tbox, Abox), где Tbox (Terminology box) – интенсиональные знания, включающие определения концептов и разбиение их на классы. Abox (Assertions box) – экстенсиональные знания, включающие в себя утверждения о связях между элементами и классами элементов.

Подробное описание механизмов рассуждения ДЛ можно найти в [6].

ДЛ с конкретным доменом

Средств традиционной ДЛ недостаточно, чтобы выразить отношения с зависимостями между атрибутами, такие вычисления были бы слишком сложными. Для преодоления этих сложностей в работе [5] язык ДЛ пополнен новым понятием – конкретный домен (Concrete Domain) [4]. Если описывается конкретный объект с его свойствами, в язык вводится конкретный домен, который, помимо доменных символов, среди своих значений содержит предикатные символы, наиболее часто используемые в описываемой предметной области либо в конкретной задаче.

Определение. Конкретный домен D состоит из множества dom(D), домена D и множества pred (D), имени предикатов домена D. Каждому имени предиката P соответствует n-местный предикат PDÍdom(D)n. В качестве примера конкретного домена приведем множество натуральных чисел NAT с предикатами < , > , =.

В [5] определены два языка в ДЛ SL(D) – (the schema language) – первый уровень определения примитивных концептов, VL(D) (the view language) – второй уровень сложных концептов и ролей и W (world description) – описание мира. D – имя конкретного домена. База знаний задается как тройка (S,V,W), где S – SL(D), V-VL(D).

Интерпретация I = (mI, ×I) состоит из абстрактного домена mI, не пересекающегося с dom (D), и функции интерпретации ×I, отображающей каждый примитивный концепт А в подмножество A I множества DI, каждую роль Р в подмножество РI множества mI ´mI, каждый признак PD в mI ´ dom (D). Интерпретация I есть S-модель базы знаний, если она является моделью для S, V и W. База знаний S = (S, V, W) выполнима, если она имеет S-модель. Исчисление базируется на синтаксических объектах, называемых ограничениями, которые имеют следующий вид:

s: C           sRt             sRk            P(k1,…, kn)            k:D,

где C – сложный концепт, R – роль, P – конкретный предикат. Конечное непустое множество ограничений называется системой ограничений и обозначается CS. Описание мира W может являться системой ограничений, при этом модели W и CSW эквива- лентны.

Правила вывода

Правила вывода в ДЛ с конкретным доменом работают на парах F.G, где F – факты G – цели; правила организованы в 5 групп и имеют следующий вид:

F.G ®     {A} ÈF.G if B is in F либо

F.G ®     F.GÈ{A} if B is in G

В соответствии с правилами вывода множество фактов F (либо целей G) пополняется неким ограничением А, если при тестировании множества фактов F (либо целей G) находятся примеры выражений, перечисленных после связки “if”. Связка “®” не является импликацией, а означает, каким образом изменяется пара F.G после применения правила вывода. Наличие противоречий в полученной в результате применения правил вывода системе ограничений приводит к выводу, что рассматриваемая формула не является логическим следствием данной системы, а значит, она не выполнима в данной базе знаний.

Сложность вычислений в ДЛ с конкретным доменом равна coNP [5].

Неоднородные семантические сети

Неоднородную семантическую сеть (НС) можно представить как совокупность следующих компонент: W = , где S – множество имен предметов, процессов реального мира, R – множество отношений на S (подробнее см. в [1-3]).

Объекты из множества S называют событиями. Множество событий в НС разделено на два типа: факты и гипотезы. Множество фактов будем обозначать F, множество гипотез – H.

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

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

Определения отношений R на множестве событий S заданы в терминах атрибутов событий, участвующих в отношениях. Каждому из отношений сопоставлено высказывание на естественном языке:

R1(событие1, событие2) – «При наблюдении события1 всегда наблюдается событие2»,

R2(событие1, событие2) – «При наблюдении события1 может наблюдаться событие2»,

R3(событие1, событие2) – «Событие1 иногда увеличивает возможность возникновения события2»,

R4 (событие1, событие2) – «Событие1 отрицает событие2».

Приступим к формальному описанию НС. Задано некоторое (определяемое предметной областью) семейство множеств D={D1, D2, ..., Dn}, где каждое множество Di называется множеством атрибутов, а всякому объекту ставится в соответствие определенное подмножество D кортежей из декартова произведения Dk=Di1´Di2´ ... ´Dik (k£n) некоторых множеств из D, называемое его экстенсионалом, или объемом.

Совокупность индексов множества атрибутов события i= называется его содержанием. Эти индексы не обязательно различны. Будем отождествлять индексы множеств из D с именами соответствующих множеств.

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

Определение 1. Если - событие, то всякое dÎD будем называть экземпляром события .

Экземпляр dÎD события является множеством {,,...,}, в котором первый элемент каждой пары есть индекс некоторого множества из D, а второй элемент – значение признака события с этим индексом.

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

Определение 2. Если d1={,, ..., }, d2={,,...,}, то:

a)    d1Çd2¹Æ, если в d1 и d2 найдутся равные пары, так же будем обозначать данное отношение ZÇ (d1 , d2);

b)    d1Íd2, если для всякой пары из d1 найдется равная ей пара из d2, так же будем обозначать данное отношение ZÍ (d1 , d2);

c)     d1=d2, если для всякой пары из d1 найдется равная ей пара из d2 и обратно, так же будем обозначать данное отношение Z= (d1 , d2);

d)    d1Ìd2, если для всякой пары из d1 найдется равная ей пара из d2 и не имеет места d1=d2, так же будем обозначать данное отношение ZÌ (d1 , d2);

Определенное множество отношений на экземплярах событий назовем Z.

Приступим к формальному описанию отношений из семейства R.

Определение 3. Если "d1 $d2 (d1╞ s1 d2╞ s2 ) такое, что d2Íd1, то будем говорить, что пара (s1,s2) принадлежит отношению R1.

Определение 4. Если $d1 $d2 (d1╞ s1 d2╞ s2 ) такое, что d2Íd1, то будем говорить, что пара (s1,s2) принадлежит отношению R2.

Определение 5. Если "d1 $d2 (d1╞ s1 d2╞ s2 ) такое, что d1Çd2 ¹Æ и при этом d1Ëd2 , d2Ëd1, то будем говорить, что пара (s1, s2) принадлежит отношению R3.

Определение 6. Если "d1 "d2 (d1╞ s1 d2╞ s2 ) найдутся такие p1Î d1 p2Î d2, что, i1=i2 и всякий раз из i1=i2 следует d1 ¹ d2, то будем говорить, что пара (s1, s2) принадлежит отношению R4.

Рассуждения в НС

После того как даны основные базисные определения перейдем к описанию процесса вывода в НС. Для этого приведем еще ряд определений [5].

Определение 1. Событие s1 будем называть положительным признаком события s2, если (s1, s2) ÎR2. Положительные признаки используются для пополнения множества гипотез событиями.

Определение 2. Событие s1 будем называть отрицательным признаком события s2, если (s1, s2) ÎR4. Отрицательные признаки используются для исключения событий из множества гипотез, для редукции этого множества либо для ранжирования событий внутри этого множества.

Определение 3. Событие s1 есть обусловленный признак события s2, если (s1, s2) ÎR1 и не существует события s3 такого, что (s3, s1) ÎR4. Обусловленные признаки – это такие признаки, отсутствие которых имеет гораздо большее значение, чем их присутствие.

Определение 4. Событие s1 есть дифференцирующий признак для события s2 и множества событий S, если для события s2 и " sÎS при прочих совпадающих для s2 и s признаках имеет место одно их двух:

1. (s1, s2) ÎR1  либо

2. (s1, s) ÎR2.

Дифференцирующие признаки – это такие признаки, которые отличают некую гипотезу от других, близких ей гипотез.

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

Пусть S0 – начальное множество событий, то есть некоторое подмножество S, где S – полное множество событий базы знаний; S и S0 строятся на этапе приобретения знаний; H – текущее множество гипотез (для каждой процедуры, кроме GMAX, это множество – результат работы предыдущей процедуры.

1.   GMAX(S0) – процедура генерирования максимального множества гипотез.

2.   RNEG(H) – редукция множества гипотез на основе тестирования и поиска отрицательных признаков.

3.   RIMP(H) – процедура редукции множества гипотез на основе поиска обусловленных признаков.

4.   RDIF(H) – процедура редукции множества гипотез на основе дифференцирующих признаков.

Подробное описание процедур содержится в [3].

Механизм вывода HSN-ALCEN на основе НС и ДЛ с конкретным доменом

Представим новый формализм HSN-ALCEN на основе ДЛ с конкретным доменом, рассмотренной ранее. HSN-ALCEN позволяет моделировать рассуждения в НС.

Синтаксис и семантика HSN-ALCEN Синтаксис HSN-ALCEN соответствует определенному в работе [5] с дополнениями, соответствующими требованиям решаемой задачи описания НС. Синтаксические конструкции задаются следующими символами:

·     предикатные символы Q1-Q4;

·     заглавными латинскими буквами С, D, E будем обозначать cложные концепты;

·     заглавными латинскими буквами Р с нижними индексами будем обозначать роли;

·     c, d, e – примеры сложных концептов;

·     d, d, возможно, с нижними индексами – элементы домена.

В таблице 2 приведен синтаксис и семантика основных конструктов HSN-ALCEN.

Таблица 2

Конструкции подбирались для оптимального сочетания выразительных свойств и вычислительной сложности HSN-ALCEN.

Определим условия истинности предикатов:

Q1(C, D) = T if C = $Р-Í.D

Q2 (C, D) = T if $Р-Í.D ⊑C

Q3 (C, D) = T if C = $РÇ.D

Q4 (C, D) = T if c: C, d: D, and $ PDi ù $ c, d (PDi (c, d) and PDi (d, d.)),

где Р-Í.= {(d, c)½(c, d)Î РÍ).

Далее поясним неформально условия, при которых определенные предикаты принимают значение истина (T). Затем определим алгоритмы вычисления предикатной связи по структуре концептов в соответствии с определением условий истинности предикатов, а также вычислим сложность установления истинности предикатов.

Концепты C и D связаны предикатом Q1, если концепт С в точности состоит из множества элементов, связанных ролью РÍ. с элементами концепта D.

Концепты C и D связаны предикатом Q2, если концепт С содержит элементы, связанные ролью РÍ. с элементами концепта D.

Концепты C и D связаны предикатом Q3, если концепт С содержит элементы, связанные ролью РÇ.с элементами концепта D.

Предикат Q4: Существует пример концепта c: C, пример концепта d: D такие, что существует общий признак PDi, на котором значения в примерах концептов C и D никогда не совпадают.

Общий алгоритм вычисления предикатной зависимости между концептами C и D основывается на сравнении признаков, определяющих концепты, и его максимальная сложность равна О(n2+n2´ôCô´ ôDô).

Правила вывода

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

Определение 1. Рангом концепта H (Rang(H)) будем называть количество утверждений вида СQ1H и СQ2H в базе знаний. Rang(H) = n if (³ n Q1ÈQ2).H is in F.

Опишем правила вывода исчисления HSN-ALCEN

F.G ® F.G È{D: T } if C is in F and Q1(C,D) is in F                 K1

F.G ® F.G È {D: T } if C is in F ÈG and Q2(C,D) is in FÈG    K2

F.G ® F.G È {D: T } if C is in F and Q3(C, D) is in F               K3

F.G ® F.G È {D: ^} if C is in F and Q4(C, D) is in F                K4

F.G.® F.GÈ{H: ^} if C is in F and E is in F and Q1 (C, H)

and Q4 (E, C) are in F                                                               K5

F.G.® F.GÈ{H: ^} if H1 is in F and Rang(H) < Rang(H1)          K6

Интерпретация Функция a. Ранее был представлен синтаксис и семантика основных конструкций HSN-ALCEN, опишем более точно его функцию интерпретации a, отображающую конструкции формализма HSN- ALCEN в конструкции НС.

a:

·     C® S, множество имен сложных концептов отображается во множество имен событий НС. Напомним, что S в НС означает множество имен предметов, процессов реального мира. При этом множество событий в НС разделено на два типа – факты и гипотезы.

·     $PDi®Di, где 0< i £n, концепту существования признака в соответствие ставится множество из множества атрибутов НС. Напомним, что каждое событие S НС однозначно определяется набором атрибутов и диапазоном их значений.

·     Р®Z, множеству ролей HSN-ALCEN ставится в соответствие множество отношений на элементах событий Z в НС.

·     Q®R, множеству предикатов HSN-ALCEN ставится в соответствие множество отношений на событиях НС. В данном случае рассматривается 4 отношения из НС, а именно R1, R2, R3, R4.

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

Ранее были представлены процедуры пополнения и редукции множества гипотез в НС. Предста- вим процедуры пополнения и редукции множества целей в языке ДЛ с конкретным доменом HSN-ALCEN.

1.   GMAX-ALCEN – процедура генерирования максимального множества целей. Выполняется применением правила K2 к паре F.G до стабилизации пары.

2.   RNEG-ALCEN – редукция множества целей. Выполняется применением правила K4 к паре F.G.

3.   RIMP-ALCEN (G) – процедура редукции множества целей. Процедура выполняется применением правила K5 к паре F.G.

4.   RDIF-ALCEN (G) – процедура редукции множества целей на основе сравнения рангов концептов множества целей. Процедура выполняется применением правила K6 к паре F.G до ее стабилизации.

Лемма 1. GMAX-ALCEN сходится, сложность вычислений не превышает О(ôFô´(ôSô-ôFô)). Максимальное количество шагов процедуры до стабилизации пары определяется формулой: ôSô-ôFô.

Лемма 2. RNEG-ALCEN (G) сходится, сложность вычислений не превышает О(n´ôFô´ôGô).

Лемма 3. RIMP-ALCEN (G) сходится, сложность вычислений определяется формулой: О(ôGô´ôFô2).

Лемма 4. RDIF-ALCEN (G) сходится, сложность вычислений определяется формулой: О(ôFô´ôGô+ôGô´lg(ôGô)), гдеôFô – количество элементов множества фактов,ôGô – количество элементов множества целей, ôSô – количество элементов в базе знаний.

Выводимыми назовем формулы, вычисленные процедурами пополнения и редукции множества целей или правилами вывода. Тот факт, что j выводима в базе знаний S, будем обозначать Sú¾ j.

Теорема. Формула j выводима в языке HSN-ALCEN из множества формул базы знаний S тогда и только тогда, когда она является следствием базы знаний в НС. Sú¾ j Û Sú=НС j.

Доказательство проводится индукцией по структуре концепта и анализом каждого из правил вывода.

В заключение отметим, что ДЛ с конкретным доменом пополнена новой группой правил вывода, алгоритмами и процедурами рассуждений из НС. Таким образом, средствами HSN-ALCEN можно решать концептуальные задачи прогнозирования, диагностики и интерпретации знаний. При этом мы не отказываемся от методов рассуждений базового формализма, позволяющего выявлять, является ли концепт логическим следствием базы знаний. HSN-ALCEN является корректным и полным. Сложность вычислений в нем не превышает coNP.

Список литературы

1.   Осипов Г.С. Инструментарий для экспертных систем. Теория SIMER+MIR // Программные продукты и системы.-1990.- №3.-С.23-32.

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

3.   Осипов Г.С. Специальные знания и синтез механизма рассуждений в задачах концептуального анализа // Изв. РАН. Техн. кибернетика.- 1992 №5 .- С. 22-27.

4.   F. Baader, P. Hanschke, “A scheme for integrating concrete domain into concept languages” , Technical report, DFKI Research Report RR-91-10, 1991.

5.   J. Bermudez, A. Illarramendi. "A description logic with concrete domain for a metaclass level of an interoperable data system. ”, In Proceedings of DL’2000, International Workshop of Description Logics, 2000, Aachen, Germany.

6.   Borgida Alexander, Ronald J. Brachman, Deborah L.McGuinness, Lori Alperin Resnick, 1989. CLASSIC: A Structural Data Model for Objects. In Proc. of the ACM SIGMOD Int. Conf. On Management of Data, 59-67.

7.   Brachman, Ronald J., Hector J. Levensque, 1984. The Tractability of Subsumption in Frame-Based Description Languages. In Proc. of the 4th Nat. Conf. On Artificial Intelligence (AAAI-84), 34-37.

8.   Donini F.M., Lenzerini M. Nardi D. Schaerf A. Reasoning in Description Logics // In. Principles of Artificial Intelligence. Ed: G. Brewska, Springer Verlag, 1995.

9.   Kaczmarek, Thomas S., Raymond Bates, Gabriel Robins. 1986 Recent Developments in NIKL. In Proc. of the 5th Nat. Conf. on Artificial Intellegence, (AAAI-86), 978-985.

10.Kurtonona N., Rijke M., Expressivenes of concept espressions in first-order description logics// Artificial Intelligence, v.107, 1999.

11.MacGregor, Robert, R.Bates, 1987. The Loom Knowledge Representations Language. Technical Reports ISI/RS-87-188 Marina del Rey, Cal.: University of Southern California, Information Science Institute.

12.Scherf, Andrea. 1994 Query Answering in Concept- Based Knowledge Representations System: Algorithms, Complexity, and Semanic Issues. Docoral dissertation, Departimento di Informaticd e Sistemisica, Universita di Roma “La Sapienza”.

13.Woods, William A., James G. Schmolze.1992. The KL-ONE Family. In Semantic Networks in Artificial Intellegence, ed. F.W. Lehmann. 133-178. Pergamon Press. Publishe as a special issue of Computers and Mathematics with Applications, v.23, № 2-9.