Proceedings 2000

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

 

 

 

Лезин Г.В., Мамедниязова Н.С.

Санкт-Петербургский экономико-математический институт РАН

lezin@emi.spb.su

 

 

1. Введение.

 

Термином “концептуальные модели” (или, как их называют в последнее время, “модели вычислительной онтологии“) охватывается класс языков для представления знаний в той или иной предметной области. Эти модели часто рассматриваются как одно из подходящих средств семантико-синтаксического (глубинно-синтаксического  по И.А Мельчуку) представления ЕЯ-текстов. Разрабатываются методы описания семантики базовых отношений моделей и техника логического вывода на основе этих описаний [1, 2]. Модели используются в качестве основы для формальных языков описания семантики лексем естественного языка в семантических словарях [3].

Основные принципы построения языков этого класса были впервые реализованы в системе KL-ONE [4]. Основными элементами модели являются объекты (сущности) предметной области, классы объектов и бинарные отношения. Наряду с этим предусматривается ограниченный набор конструктов для построения более сложных объектов и отношений. Особенностью этого языка является разделение знаний на терминологическую часть (“T‑box”), содержащую определения классов и отношений, и базу фактов (“A‑box”). Семантика определений в “T‑box” задается трансляцией их на язык логики предикатов. Вычислительной полноте языка логического программирования  в языках типа KL-ONE противопоставляется логическая разрешимость, возможность получения определенного (ДА или НЕТ) ответа на запрос.

В данной работе делается попытка совмещения дескриптивных возможностей языков типа KL-ONE и вычислительной мощности прологоподобного языка. Рассматриваемый здесь язык разрабатывался как средство представления формализованных знаний в системе гипертекста [5].

Тексту в системе может быть сопоставлена его концептуальная модель — формализованное представление смыслового содержания текста, которое пользователь желает зафиксировать в базе знаний системы. Концептуальные модели текстов, написанные на формальном языке, содержат фактографические данные и правила их об­работки. В отличие от KL-ONE, представленная моделями информация накапливается в единой концепту­альной памяти системы. Модели текстов представлены в концепту­альной памяти в нормализованной (канонической) форме в виде общей конъюнкции терминальных двух-, трех- или четырехместных предикатов, образованных отношениями языка. Факты представляются значениями предикатов. Правила представляют собой конструкции, посылка и следствие которых представлены конъюнкциями таких предикатов. Обработка накопленной информации по заданным правилам инициализируется запросами к концептуальной памяти.

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

Далее в работе рассматриваются:

— некоторые элементы языка, достаточные для иллюстрации рассматриваемого подхода;

— функционирование концептуальной памяти;

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

 

2. Объекты и отношения.

 

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

Допускается определение следующих видов объектов: понятия (классы, множества), экземпляры понятий, бинарные отношения, числа. Вид объекта явно указывается в его обозначении. Например, обозначения понятий записываются прописными буквами, а экземпляров — строчными .

Текущее состояние объектов концептуальной памяти описывается наборами предикатов. Для обозначения переменных в предикатах мы зарезервируем буквы X , x, Y, y, Z, z, и в случае необходимости будем индексировать эти буквы цифрами 1, ..., 9. Переменные, обозначенные прописными буквами X, Y, Z, определены на множестве понятий (классов) концептуальной памяти, а переменные, обозначенные строчными буквами x, y, z - на множестве экземпляров.

Факт принадлежности понятия Е1 или экземпляра v понятию E устанавливается отношением E:E1 и, соответственно, Е:v. Далее мы будем говорить в таких случаях, что объект Е1 конкретизирует  объект Е (является его подклассом), объект v – конкретный пример, экземпляр объекта E; само отношение мы будем называть отношениемконкретизации.

Пример 1

СУДЕБНЫЙ_ПРОЦЕСС: УГОЛОВНЫЙ;

СУДЕБНЫЙ_ПРОЦЕСС: ГРАЖДАНСКИЙ;

 

Значения предикатов X:Е и Е:X определяют текущее множество классов, связанных отношением конкретизации с заданным понятием Е в концептуальной памяти. Отметим, что предикат e:X ложен при любых значениях X, а Е:x определяет имеющееся в концептуальной памяти множество экземпляров E.

 Формальную семантику отношения можно задать формулой логики предикатов первого порядка.  Отношению конкретизации класса экземпляром сопоставляется двухместный денотативный (свободный от обозначений конкретных объектов) предикат X : y, а отношению конкретизации между классами —  двухместный денотативный предикат X : Y. Тогда отношение конкретизации между классами можно определить через отношение конкретизации между классом и экземпляром:

("X, Y) [ X:Y « ("y) (Y : y ® X : y) ],

то есть предикат X:Y истинен тогда и только тогда, когда для любых экземпляров соблюдается приведенное правило.

Пример 2

Предположим, что концептуальная память содержит факты A:B и B:b и нас интересуют возможные значения предиката A:x. Фактом A:B устанавливается существование правила, заданного  денотативной семантикой отношения конкретизации:

("y) (B : y ® A : y),

а факт B:b соответствует истинному значению предиката B:y, указанного в этом правиле. Вычисляя значение предиката A:x, мы, имея факт   A:B и подставляя в полученное из него правило факт B:b , могли бы из фактов, существующих в базе, получить x=b.

 

Объект-понятие представляет в концептуальной памяти множество элементов, имеющих общие атрибуты. Записью Е(Е1) мы утверждаем факт наличия атрибута Е1 у объекта Е. Утверждение Е(Е1,...,Еk) задает для объекта Е список атрибутов. В качестве атрибутов могут указываться лишь объекты типа "понятие".

Пример 3

СУДЕБНЫЙ_ПРОЦЕСС(СОСТАВ_СУДА, СВИДЕТЕЛИ, ЗАКЛЮЧЕНИЕ_СУДА);

СУДЕБНЫЙ_ПРОЦЕСС: ГРАЖДАНСКИЙ(ИСТЕЦ, ОТВЕТЧИК, ДЕЛО);

 

Отметим, что список атрибутов никогда не считается завершенным и может пополняться по мере поступления новых сообщений. Текущее состояние списка атрибутов понятия Е определяется предикатом Е(X). В предыдущем примере, в частности, предикат СУДЕБНЫЙ_ПРОЦЕСС(X) истинен для X = СОСТАВ_СУДА, СВИДЕТЕЛИ, ЗАКЛЮЧЕНИЕ_СУДА.

Предикат X(Е) позволяет установить наличие в концептуальной памяти понятий, а предикат x(E) — экземпляров, для которых Е определено в качестве атрибута. В нашем примере X(ИСТЕЦ) истинен для X = ГРАЖДАНСКИЙ.

 Денотативная семантика отношения <понятие>(<атрибут>):

("X, Y) [ X(Y) « ("x) ( X : x®  x(Y) ) ].

В соответствии с приведенным определением, класс имеет некий атрибут тогда и только тогда, когда этот атрибут имеют все экземпляры заданного класса .

 

Для каждого экземпляра e класса E(A) существует вполне конкретный экземпляр a атрибута A. Для задания  значений атрибутов в языке предусмотрено трехместное отношение вида e(A.a). Распространяя это отношение на классы, мы получаем отношение вида X(Y.Z) с денотативной семантикой

"(X, Y) [ X(Y.Z) « "(x) (X : x ® x(Y) Ù $(z)( x(Y.z) Ù Z : z Ù Y : z) ) ]

В концептуальной памяти текущее состояние понятия E в отношении X(Y.Z) определено значениями предикатов E(Y.Z), X(E.Z) и X(Y.E).

Пример 4

Пусть концептуальная память содержит факты A(B) и C(B.D), и нас интересует  вопрос, какие из классов имеют атрибут B. Непосредственное обращение к концептуальной памяти с запросом X(B) даст в качестве ответа только X=A, поскольку алгоритмы работы памяти не учитывают семантику отношений.

Пытаясь учесть семантику отношений, мы можем рассматривать запрос  X(B) как утверждение

$(X) [ "(y)(X:y ® y(B)],

истинность которого должна быть подтверждена значениями X, извлеченными из концептуальной памяти. Иными словами, найдя значения X, для которых приведенное правило истинно, мы получим ответ на искомый вопрос. Факт А(B) прямо (по определению)  подтверждает истинность этого правила при X=A . В концептуальной памяти имеется также факт C(B.D), устанавливающий истинность правила

"(x) [C : x® x(B) Ù $(z) ( x(B.z) Ù D : z Ù B : z)],

включающего в себя правило

"(x) [C : x® x(B)].

Последнее  с точностью до значения X и обозначения переменной под квантором всеобщности совпадает с доказываемым. Проунифицировав обозначения в этих двух правилах мы получаем X=C в качестве очередного искомого ответа.

 

 Объекты (классы и экземпляры) могут связываться произвольными бинарными отношениями. Обозначение бинарного отношения задается в кавычках.

Пример 5

ЛИСА  “МЕНЬШЕ” ВОЛК

SOME ЖИВОТНЫЕ “ЕДЯТ” ЗЛАКИ

Денотативная семантика произвольных бинарных отношений:

("X, Y) [ X ”Y” Z « ("x, z) (X : x Ù Z : z® x”Y”z ) ]

("X, Y) [ SOME X ”Y” Z « ("z) ( Z : z ® ($x) (X : x Ù x”Y”z) ) ]

("X, Y) [ X ”Y” SOME Z « ("x) (X : x --> ($z) (Z : z Ù x”Y”z) ) ]

В концептуальной памяти состояние бинарного отношения “B” определяется значениями предиката X”B”Y; бинарные отношения сущности E  с прочими — значениями предикатов E”X”Y и Y”X”E.

 

Логика зависимостей между объектами и отношениями конкретной предметной области задается  правилами, устанавливаемыми пользователем. Структурa правила имеет вид:

<конъюнкция предикатов> Ü (< конъюнкция предикатов> OR

                                                                       . . .                             OR

                                                       < конъюнкция предикатов>);

 

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

 

3. Концептуальная память.

 

Как уже упоминалось, факты и правила  описания предметной области накапливаются в концептуальной памяти. Запрос к этой памяти имеет форму посылки правила — дизъюнкции конъюнкций предикатов. Поиск ответа на запрос сводится к последовательному вычислению значений предикатов в каждой из конъюнкций запроса.

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

Пример 6

Предикат X:Y не принимается к вычислению.

Предикаты же E:X или Y:E, где E — константа, являются вычислимыми, и для них концептуальная память вырабатывает значения переменных X и Y, при которых эти предикаты истинны, а при отсутствии таких значений вырабатывает значение “false”.

 

Ограничение вычислимости предиката обусловлено устройством концептуальной памяти. Факты, на которых предикаты отношений принимают значение “истина”, и сами предикаты отношений, используемые в правилах, в концептуальной памяти собираются относительно тех объектов, которые входят в соответствующие отношения. Объекты, входящие в отношения предикатов запроса, являются информационными ключами поиска как  фактов, так и правил, применение которых необходимо при поиске ответа на запрос.

Правило R применяется при вычислении предиката P, если конъюнкция следствия R содержит вычислимый предикат T, совместимый с P.  Два предиката, T и P, совместимы, если:

а) существует унифицирующая подстановка q: Pq = Tq;

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

Пусть в данный момент вычисляется предикат P_i  запроса P₁; …; P_k и в концептуальной памяти есть правило T₁;...;T_s Ü L₁;...;L_n, в следствии которого имеется предикат T_j , совместимый с P_i  (P_iq = T_jq). Применим подстановку q к запросу P₁; …; P_k и к правилу T₁q,...,T_sq Ü L₁q,...,L_nq. Тогда правило можем переписать в виде:

T₁q;...;T_j-1q; P_iq; T_j+1q;...;T_sq Ü L₁q;...,L_nq;

что эквивалентно конъюнкции правил:

T₁q;...;T_j-1q Ü L₁q;...;L_nq;

P_iq Ü L₁q;...;L_nq;

T_j+1q;...;T_sq Ü L₁q;...;L_nq.

Следовательно, отобранное правило может быть применено, и результирующий запрос имеет вид:

P₁q; …; P_i-1q; L₁q; …; L_nq; P_i+1q; …; P_kq.

 

В алгоритме выполнения запроса к концептуальной памяти реализуется стандартный (прологоподобный) механизм вывода на основе резолюции, с учетом описанной выше особенности вызова правил. Далее этот алгоритм будет использоваться как функция Query(P), выполняемая над содержимым концептуальной памяти. Результатом вычисления функции является набор подстановок q={q1,...,qk} — значения переменных предиката P, при которых истинность предиката выводится из истинности фактов и пользовательских правил в концептуальной памяти; набор q пуст при отсутствии таких значений.

Функция  Query(P) используется для поиска ответа на запрос без учета формальной семантики отношений.

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

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

 

4. Операционная семантика отношений

 

Введем обозначения.

P(X) - произвольный n-местный (1<n<5)  предикат отношения, аргументные места которого замещены  переменными из  набора X. Переменные из набора X могут быть определены в концептуальной памяти как на множестве классов, так и на множестве экземпляров.

P(Xl) — вычислимый предикат, некоторые из аргументных мест которого применением унифицирующей подстановки l замещены константами; Xl — набор (возможно пустой) переменных этого предиката, оставшихся незамещенными.

Query(P(Xl)) = {q₁,...,q_m} — результат запроса к концептуальной памяти, представленный множеством унифицирующих подстановок, удовлетворяющих условиям:

— P(Xlq_i)=true  (1£ i £m);

— набор (X)lq_i  пуст, т.е. все аргументные места P замещены константами;

В частности, если (X)l пуст, т.е. P(Xl) — константный предикат, то Query(P(Xl)) или пуст (P=false), или равен {l}.

A(X,x)= a₁(X,x)Ù...Ù a_k(X,x), B(X,x)=b₁(X,x)Ù...Ùb_l(X,x),... — обозначения компонент формул, представляющие конъюнкцию нескольких терминальных отношений (в частном случае одно).

 

С учетом введенных обозначений  денотативную семантику отношения, заданного предикатом P, можно записать в виде:

"(X) [P(X) « "(x) (A(X,x)® B(X,x) )]             (1)

Примечания:

1)Некоторые из конъюнктов в A или B могут быть объединены квантором существования, см., например определение денотативной семантики для бинарного отношения.

2) В общем случае правая часть отношения  ‘«’ (“если и только если”) может содержать конъюнкцию отношений следования вида A®B.

Предположим теперь, что предикат P(Xl) вычислим, и для текущего состояния концептуальной памяти известны все возможные подстановки {q₁,...,q_m}, при использовании которых P(Xlq_i)=true. Тогда из (1)  следует истинность отношений следования

"(x) (A(Xlq_i , x)® B(Xlq_i , x), (1£ i £m).

 

С другой стороны, предположим, что нас интересуют все возможные наборы значений переменных из Xl, при которых для текущего состояния концептуальной памяти P(Xl)=true. Мы решим поставленную задачу, если сможем найти полный набор {q₁,...,q_n} подстановок, для каждой из которых истинно  

"(x) (A(Xlq_j , x)® B(Xlq_j , x), (1£j£n).

Далее мы рассмотрим некоторые методы решения этой задачи.

Преобразуем  выражение  "(x)(A(X,x)®B(X,x)) из (1)  следующим образом:

а) Переобозначим переменные из набора x, связанные квантором всеобщности, снабдив их специальным значком, например, значком $, и уберем этот квантор из выражения.

б) Переменные, связанные квантором существования, заменим сколемовскими  функциями от переменных из набора x.

Выражение (1) с учетом сделанных преобразований перепишем в виде:

 P(X):{ A(X)®B(X)}      (2)

Запись вида (2) мы будем называть шаблоном операционной  семантики предиката P(X), а сам предикат — владельцем шаблона.

Пример 7

Денотативная семантика  бинарного отношения X ”Y” SOME Z:

"(X, Y) [X ”Y” SOME Z«"(x) (X : x --> $(z) ( Z : z Ù x”Y”z))]

Шаблон операционной семантики этого отношения имеет вид

X ”Y” SOME Z:{X : x$ ® Z : f(x$); x$ “Y” f(x$)}

В этом выражении  f — сколемовская функция, X ”Y” SOME Z — владелец шаблона.

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

 

Пусть  Query(P(Xl)) = {q₁,...,q_m}.

Полученные из (2) выражения вида

P(Xlq_i):{ A(Xlq_i)®B(Xlq_i)}, (1£ i £m),

мы будем называть операционной семантикой отношений P(Xlq_i).

Истинность P(Xlq_i) подтверждена соответствующими фактами в концептуальной памяти, следовательно, выражения A(Xlq_i)®B(Xlq_i) истинны по определению для всех 1£ i £m.

Вернемся к исходной задаче: нам необходимо по текущему состоянию концептуальной памяти  установить полный набор  подстановок q={q₁,...,q_n}, для каждой из которых выполняется P(Xlq_j)=true, (1£ j £n), и мы будем строить q, доказывая истинность выражений A(Xlq_i)®B(Xlq_i).

Утверждение 1. Пусть P(X):{A(X)®B(X)} и P(Xl) — вычислимый предикат. Выражение A(Xlq)®B(Xlq)истинно, если в семантической памяти найдется шаблон Q(X):{C(X)®D1(X)ÙD2(X)} для которого выполняются условия:

а) найдется унифицирующая подстановка p, в результате которой

 B(Xlp)= D1(Xlp);

б) Query(Q(Xlp))={f₁,... f_k};

в) для любого c_i в конъюнкции C(X) найдется a_j в конъюнкции A(X) такой, что c_i(Xlpf)=a_j(Xlpf), где fÎ{f₁,... f_k}.

В этих условиях q=lpf.

 В самом деле, применим к исходному выражению A(Xl)®B(Xl) подстановку  pf и подставим в него D1(Xlpf) вместо B(Xlpf), а конъюнкцию A(Xlpf) представим парой конъюнкций C(Xlpf) ÙE(Xlpf). Получим:

A(Xlpf)®B(Xlpf)= (C(Xlpf) ÙE(Xlpf))® D(Xlpf)=

=C(Xlpf) ® D1(Xlpf)ÚE(Xlpf))® D(Xlpf)=true, т.к.

C(Xlpf) ® D1(Xlpf)ÙD2(Xlpf)=true в соответствии с фактом в концептуальной памяти.

Рассмотрим подробнее условия использования утверждения 1.

Условие а) определяет шаблон операционной семантики в качестве кандидата на использование в доказательстве истинности правила (совместимость правила и шаблона). Условием б) для выбранного шаблона определяется множество операционных семантик, истинность которых установлена фактами {f₁,... f_k} концептуальной памяти. И, наконец, условие в)  позволяет отобрать из этих фактов подходящие для доказательства истинности правила.

Утверждение 1 накладывает достаточно жесткие ограничения на операционную семантику, используемую для доказательства истинности A(Xlq)®B(Xlq). Следующие утверждения позволяют   расширить список операционных семантик, используемых для доказательства.

Утверждение 2.

Если существуют подстановки p и f, такие, что правила A(Xp)®B1(Xp) и A(Xpf)®B2(Xpf) являются истинными, то правило A(Xq)®(B1(Xq)ÙB2(Xq) истинно для подстановки  q=pf.

Утверждение 3.

Если существует подстановка q, при использовании которой истинны правила C(Xq) ® B(Xq) и A(Xq)® С(Xq), то истинным является и правило A(Xq)® B(Xq).

Опираясь на Утверждение 2, мы при необходимости доказать истинность правила A(Xl)®(B1(Xl)ÙB2(Xl)можем пытаться доказывать его по частям: найдя подстановкуp, при использовании которой  A(Xlp)®(B1(Xlp) истинно, мы могли бы уточнить ее подстановкой f до искомого значения q=lpf, доказав истинность A(Xlpf)®B2(Xlpf).

Утверждение 3 обосновывает смену цели при поиске доказательства. Пусть нам необходимо доказать истинность A(Xl)®B(Xl) и в семантической памяти имеется шаблон Q(X):{C(X)®D1(X)ÙD2(X)}, для которого:

а) найдется унифицирующая подстановка p, такая что

 B(Xlp)= D1(Xlp);

б) Query(Q(Xlp))={f₁,... f_k}.

В результате мы имеем набор истинных правил C(Xlpf)®B(Xlpf), fÎ{f₁,... f_k}. Доказав истинность A(Xlpf)® C(Xlpf), мы, в соответствии с утверждением 3, докажем истинность A(Xlpf)®B(Xlpf).

 

5. Заключение.

 

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

Используя прологоподобные механизмы вывода,  мы вернулись к совместному хранению фактов и пользовательских правил в общей концептуальной памяти. Общий список констант, на основе которого строятся факты и правила концептуальной памяти,  объединяет обозначения понятий, их экземпляров и введенных пользователем бинарных отношений. Атомарный элемент хранения в концептуальной памяти — это либо константное значение отношения (заданного в языке или пользователем), либо предикат отношения в том или ином правиле пользователя.  Правила операционной семантики отношений  в виде образцов, независимых от конкретного наполнения базы знаний, хранятся в отдельной семантической памяти. Построение конкретных правил на основе образцов и их последующее применение осуществляется в процессе доказательства запроса к базе знаний. Возможность применения этих правил определяется фактами концептуальной памяти.

 Изложенный в работе подход  позволяет:

— обрабатывать запросы к базе знаний в двух режимах: либо используя только правила пользователя (область поиска доказательства существенно сужается, а быстродействие столь же существенно возрастает), либо с учетом семантики отношений;

— отделить работу по определению понятий и правил пользователя от работы по определению формальной семантики отношений;

— снизить затраты на представление информации в базе знаний для тех задач, в которых объем информации по определению понятий и правил соизмерим с объемом информации о принадлежности экземпляров понятиям.

Предлагаемые в работе алгоритмы реализуются в гипертекстовой картотеке MAZE — экспериментальной системе управления базой знаний, предназначенной для применения в гуманитарных исследованиях.

 

Литература.

 

Плесневич Г.С. Логика моделей “классы-бинарные отношения”. I // Изв. РАН. Теория и системы управления, 1997, №5, с.17-26.

Плесневич Г.С. Логика моделей “классы-бинарные отношения”. II // Изв. РАН. Теория и системы управления, 1998, №5, с.69-80.

Рубашкин В.Ш., Лахути Д.Г. Семантический (концептуальный) словарь для информационных технологий. II // НТИ, сер.2, 1999, №5, с.1-12.

Baader F. Logic-based Knowledge Representation, ftp://www-lti.informatik.rwth-aachen.de/pub/papers/1999/Baader-LNAI-1999.ps.gz

Лезин Г.В., Боярский К.К, Каневский Е.А., Попова А.И. Анализ текстов: представление и обработка концептуальной информации // Труды Международного семинара Диалог’97 по компьютерной лингвистике и ее приложениям. М.:Рос.НИИ ИИ, 1997, с.170-174.