Экстенсивное развитие онтологических структур

Материал из Semantic Future


Д. А. Павлов

Содержание

Введение

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

Возможность дополнять существующие структуры новыми знаниями, резко отличающимися от ранее представленных, была отправной точкой для множества исследований и разработок. [1] [2] В ряде работ раскрывается процесс развития онтологических структур, как с точки формальной логики [3], так и с точки зрения общего понимания сути развития. [2] [4] Также существует множество прикладных исследований в рамках разработок сред создания онтологий. [5] [6] [7] Эти работы, не смотря на существенный вклад в данном направлении, имеют некоторые недостатки, среди которых хотелось бы отметить низкий уровень формализации процессов развития, а также поверхностный анализ сложных онтологических структур, что не позволяет обобщить методики работы с ними.

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

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

Постановка задачи

С учетом цели работы, необходимо:

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

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

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

Графовая модель распределенной онтологической структуры

Онтология ~Ont есть пара ~ \mathcal {h} T, A \mathcal {i}, где ~ T (TBox) — таксономия концептов данной онтологии и множество отношений, определенных на данной таксономии, ~ A (ABox) — множество аксиом, основанных на заданном ~T [8]. Интерпретация ~I онтологии ~Ont есть пара ~ \mathcal {h} \Delta ^I , \bullet ^I \mathcal {i}, где ~ \Delta ^I непустое множество предметной области, и ~ \bullet ^I функция, которая присваивает каждому концепту ~c из ~T подмножество из ~ \Delta ^I , каждому отношению ~r из ~T подмножество из ~ \Delta ^I \times \Delta ^I, и каждой аксиоме ~a элемент из ~ \Delta ^I [8]

Утверждение 1. Две онтологии эквивалентны тогда, когда их интерпретации эквивалентны.

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

Отметим, что [8]

~Ont_{1}^I \cup Ont_{2}^I = (Ont_{1} \cup Ont_{2})^I,

~Ont_{1}^I \cap Ont_{2}^I = (Ont_{1} \cap Ont_{2})^I.

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

Определение 1. Отношение импорта онтологий

~RI = imp(Ont, Ont_{base}) = 1, (1)

где ~Ont_{base} — импортируемая онтология, а ~Ont — импортирующая, есть некоторое мета-описание, утверждающее, что в рамках ~Ont принимаются все соглашения, действующие в ~Ont_{base}, здесь и далее ~1 = “true” = “истина”.

Пусть конечное множество всех ~RI заданных на данной онтологической структуре есть

~MRI = \mathcal {f} RI_{i} \mathcal {g} = 1, где ~i=1,N (2)

Отметим, что:

если imp(Ont_{x}, Ont_{y}) \cap imp(Ont_{y}, Ont_{z}) = 1, то ~ imp(Ont_{x}, Ont_{z}) = 1; (3)

RI_{i} \neq RI_{j}, если i \neq j, где RI_{i}, RI_{j} \in MRI \mathcal {8} i,j = 1,N (4)

Для упрощения записи пусть

~RI = imp(RI^- , RI^+).

А также пусть для некоторой онтологии ~Ont множество входных или импортирующих отношений — ~ \mathcal {f} RI_{i} \mathcal {g} ^+ и множество выходных — ~ \mathcal {f} RI_{j} \mathcal {g} ^-.

Отношения полученные из (3), такие что

~nRI = imp(Ont_{x}, Ont_{y}) = 1,nRI \not\in MRI, (5)

будем называть неявным импортом.

Введем следующую интерпретацию графа онтологической структуры: узлы — онтологии, ориентированные дуги — отношения импорта, где начало — импортируемая онтология, конец — импортирующая онтология,

Struct = \mathcal {h}MO, MRI \mathcal {i}, (6)

где MO = \mathcal {f} Ont_{i} \mathcal {g} — множество всех онтологий входящих в структуру.

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

Тогда мы имеем право говорить об эквивалентных преобразованиях в рамках графового представления.

Определение 2. Дублирующими дугами мы будем считать те дуги, отсутствие которых на графе (6) может быть в любой момент восстановлено в силу (3).

~dubl(RI) = 1, если дляStruct = \mathcal {h}MO, (MRI - RI) \mathcal {i}, ~imp(RI^- , RI^+) = 1. (7)

Определим множество импортов без дублирующих дуг

MRI_{elim} = MRI - \mathcal {f} RI_{i} \mathcal {g}, dubl(RI_{i}) = 1, \mathcal {8} i = 1,N (8)

Формирование множества ~ \mathcal {f} RI_{i} \mathcal {g} включает в себя задачу поиска наименьшего пути ~ \mathcal {f} RI_{j} \mathcal {g} для каждого ~ RI_{i} \not\in \mathcal {f} RI_{j} \mathcal {g} такого, чтобы ~ dubl(RI_{i}) = 1. Схожие задачи решались в работах [8].

Согласно утверждению 1

Struct = \mathcal {h}MO, MRI \mathcal {i} = \mathcal {h}MO, MRI_{elim} \mathcal {i}.

Развитие онтологий

Аддитивное развитие

Для любых двух онтологий, связанных отношением импорта (1), естественно, что одна из них использует вторую как базу для построения своей структуры знаний. Создавая такую структуру, первая онтология тем самым развивает знания, хранящиеся в базовой. Такого рода развитие мы будем называть аддитивным, то есть которое непосредственно наращивает знания. Формально аддитивное развитие онтологий (Рисунок 1) есть любое импортирование, для которого верны следующие утверждения:

а) ~\mathcal {9}!RI \in MRI_{elim}, такое что ~RI^- = Ont, то есть ~Ont импортирует только одну онтологию;

б) ~Ont не содержит циклических ссылок импорта на саму себя.


РИСУНОК 1 ВСТАВИТЬ


Введем далее необходимые определения независимости элементов и множеств элементов онтологий.

Определение 3. Независимым элементом ~A и от элемента ~B онтологии ~Ont будем называть такой элемент, для которого верно:

~nezav(A, B) = 1, если ~A^I = const, \mathcal {8} B,

где ~A^I интерпретация данного элемента онтологии с помощью ~\bullet ^I, ~\mathcal {8} B значит, что ~B может принимать любые значения, возможные в рамках данной онтологии.

Определение 4. Независимым множеством элементов ~ U = \{A_{i}\} от множества элементов ~ V =\{B_{j}\} онтологии ~Ont будем называть такое ~U, для которого верно:

~nezav(U, V) = 1, если ~ \bigcap_{i} \bigcap_{j} nezav(A_{i}, B_{j}) = 1.

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

Определение 5. Псевдоимпорт ~pRI — это такой ~RI, что.

~pRI = RI = 1, если ~nezav(RI^-, RI^+) = 1. (9)

Утверждение 2. Связь развития вида (9) может быть элиминирована в ходе некоторых этапов анализа общей структуры со следующим условием: удаляя некоторую pRI, нужно сохранять транзитивную целостность структуры.

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

Сохранение транзитивной целостности при удалении отношения вида (9) обеспечивается перенаправленим связи на все расширения онтологии ~pRI^-, у которой удаляется ~pRI. То есть, пусть существует удаляемая связь ~pRI. ~ \{ Ont_{i} \} есть множество расширений ~pRI^-, тогда

~MRI_{elim} = MRI - pRI + \{RI_{i}\} , (10)

где ~RI^{+}_{i} = pRI^{-}, ~RI^{-}_{i} = Ont_{i}, ~\mathcal {8}i = 1,N, ~N = |\{Ont_{i}\}|.

Тогда в общем виде, с учетом (8) и (10)

~MRI_{elim} = MRI - \{RI_{i}\} - \{pRI_{j}\} + \{RI_{jk}\}, dubl(RI_{i}) = 1, \mathcal {8}i=1,N.

Детализируем уровеь рассмотрения развития онтологий. Представление онтологии в виде ~ \mathcal {h} T, A \mathcal {i} имеет ряд достоинств применительно к поставленным задачам, а именно:

  • такая конфигурация отвечает обобщенным подходам к описанию онтологий;
  • оно позволяет увеличить детализацию рассмотрения распределенной онтологической структуры, без использования сложных моделей и программных средств;
  • данное представление является наглядным
  • данное представление эффективно используется в ряде уже существующих прикладных приложений. [7],[9]

Тогда, на более детальном уровне, аддитивное расширение базовой онтологии есть

~Ont_{ext} = \mathcal {h}T_{b} + T_{e}, A_{b} + A_{e} \mathcal {i}, (11)

где ~\mathcal {h}T_{b}, A_{b}\mathcal {i} = Ont_{base}, а ~\mathcal {h}T_{e}, A_{e}\mathcal {i} - непосредственно элементы расширения.

На практике зачастую расширение базовой онтологии (11) редуцировано и осуществляется только за счет добавления аксиом:

~Ont_{ext} = \mathcal {h}T_{b}, A_{b} + A_{e} \mathcal {i}. (12)

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

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

Интеграционное развитие

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

Формально интеграционное развитие онтологий (Рисунок 2) есть

~RI_{j} = 1, ~RI^{-}_{j} = Ont, ~RI^{+}_{j} = Ont_{base j}, \mathcal {8}j=1,M (13)

где ~Ont_{base j} j-ая базовая онтология, ~Ont общее расширение для всех ~Ont_{base j}, ~M – число онтологий, интегрируемых в ~Ont.


РИСУНОК 2 ВСТАВИТЬ


Для упрощения записи введем множественные функцию импорта


~imp(\{Ont_{j}\}, Ont_{b}) = imp(Ont_{1}, Ont_{b}) \cap ... \cap imp(Ont_{M}, Ont_{b})

~imp(Ont, \{Ont_{bj}\}) = imp(Ont, Ont_{b1}) \cap ... \cap imp(Ont, Ont_{bM})

Интеграционное развитие на более детальном уровне можно представить как

~Ont_{ext} = \mathcal {h}T_{b1} + ... + T_{bM} + T_{e}, Ab1 + ... + A_{bM} + A_{e}\mathcal {i},

при чем ~Ont_{base j} = \mathcal {h}T_{bj}, A_{bj} \mathcal {i} , \mathcal {8}j=1,M, являются системно согласуемыми.

Определение 7. Системно согласуемыми онтологиями будем называть множество онтологий такое, что для него можно создать хотя бы один интегрирующий ресурс (12), содержащий хотя бы одну непротиворечивую аксиому.

Определение 8. Противоречивой аксиомой будем называть такую аксиому которая в данных условиях эквивалентна пустому множеству.

Помимо интеграции онтологий, возможен обратный искусственный процесс — дезинтеграция. Для осуществления дезинтеграции необходимы понятия несвязности элементов и множеств элементов онтологий.

Определение 9. Несвязанными элементами ~A и ~B онтологии ~Ont будем называть такие элементы, для которых верно:

~nesv(A,B) = 1, если ~nezav(A,B) \cap nezav(B,A) = 1.

Определение 10. Несвязанными множествами элементов ~U = \{A_{i}\} и ~V = \{B_{j}\} онтологии Ont будем называть такие множества, для которых верно:

~nesv(U,V) = 1, если ~nezav(U,V) \cap nezav(V,U) = 1.

Определение 11. Под дезинтеграцией элемента онтологической структуры мы будем понимать


~Ont = \bigcup_{i}Ont_{i}, ~\bigcap_{i}\bigcap_{j}nesv(Ont_{i},Ont_{j}) = 1, \mathcal {8}i, j=1, N, i \not= j,

где ~Ont_{i}, Ont_{j} \in \{Ont_{k}\}, ~\{Ont_{k}\} множество онтологий, на которые распадается ~Ont.

Возвращаясь к графовой модели, дезинтеграция — есть ничто иное, как разделение некоторого узла на множество узлов.

Тогда (14) для (2) это:

~Struct = \mathcal {h} (MO - Ont + \{Ont_{k}\}), (MRI + imp(Ont_{k}, \{RI_{i}\}^{+}) + imp(\{RI_{j}\}^{-}, Ont_{k})) \mathcal {i}, \mathcal {8},j,k. (15)

Для (15) характерно наличие псевдоимпортов среди вновь добавленных дуг.

После дезинтеграции могут возникать некоторые узлы ~Ont_{x} и ~Ont_{y} такие, что ~\{RI_{i}\}^{-}_{x} = \{RI_{i}\}^{-}_{y} и ~\{RI_{j}\}^{+}_{x} = \{RI_{j}\}^{+}_{y}, \mathcal {8}i,j, то есть структуры, для которых одинаковы все базовые и все развивающие онтологии. Такие узлы мы не будем рассматривать как различные.

Совместное развитие

Совместное развитие (Рисунок 3) является важной особенностью онтологических структур. В таком развитии отсутствует иерархия, то есть каждая из двух онтологий являются друг для друга, как базовой, так и расширением.

~imp(Ont_{x}, Ont_{y}) \cap imp(Ont_{y}, Ont_{x}) = 1

где ~Ont_{x}, ~Ont_{y} совместно развиваемые онтологии.


РИСУНОК 3


Замечание 1. Заметим, что пространственно существуют две различные онтологические подструктуры ~Ont_{1} и ~Ont_{2}, но всегда, кроме случаев использования (14), они семантически неразделимы и являются некоторой обобщенной структурой.

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

~Ont_{joint} = \{Ont_{l}\}, \mathcal {8}l=1,L, (17)

где ~Ont_{joint} общая онтологическая структура, ~Ont_{l} элемент, принадлежащий некоторому замкнутому пути импортов, ~L – общая длина цикла, при чем ~imp(Ont_{i}, Ont_{i+1}) = 1, \mathcal {8}i=\bar{1,L-1}, и ~imp(Ont_{L}, Ont_{l}) = 1.

Теорема 1. О вхождении элемента в цикл (необходимая и достаточная). Некоторое расширение ~Ont онтологической структуры входит в некоторое совместное развитие ~Ont_{joint} (11), тогда и только тогда, когда ~imp(Ont, Ont) = 1, то есть ~Ont является для себя же базовой.

Доказательство необходимости. Пусть некоторая ~Ont_{joint} (17). Предположим, что ~imp(Ont_{l}, Ont_{l}) = 0. Но в силу (3)

~(\cap imp(Ont_{i}, Ont_{i+1})) \cap imp(Ont_{L}, Ont_{l}) = 1

следовательно ~imp(Ont_{l}, Ont_{l}) = 1.

Получаем противоречие. Следовательно ~Ont_{l} является для себя базовой.

Доказательство достаточности. Пусть ~imp(Ont, Ont) = 1 и ~ Ont \not= \oslash. Предположим, что ~Ont не входит ни в один из циклов онтологии. Тогда множества импортируемых и импортирующих элементов не пересекаются:~\{Ont_{i}\}^{+} \cap \{Ont_{j}\}^{-} = \oslash. Но в силу (3) предположения ~imp(Ont, Ont) = 1, ~Ont \in \{Ont_{i}\}^{+} и ~Ont \in \{Ont_{j}\}^{-}. Следовательно ~\{Ont_{i}\}^{+} \cap \{Ont_{j}\}^{-} \supseteq Ont Имеем противоречие. Следовательно ~Ont входит по крайне мере в один из циклов онтологии. Теорема доказана.

Учитывая замечание 1 предлагается два подхода к упрощению циклов:

а) при возможности эффективного использования дезинтеграции (14) – разрывать цикл;

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

~Struct = \mathcal {h}
(MO – \{Ont_{l}\} + Ont_{joint}),
(MRI – \{RI_{i}\}^{+}_{l} – \{RI_{j}\}^{-}_{l} + imp(\{RI^{-}_{j}\}^{l},Ont{joint}) + imp(Ont{joint}, \{RI^{+}_{i}\}^{+}_{l})) \mathcal {i} , (18)

где запись ~\{RI^{+}_{i}\}^{+}_{l} множество онтологий, которые импортирует l-я онтология цикла, ~\{RI^{-}_{j}\}^{-}_{j} множество онтологий, которые импортируют l-ю онтологию цикла.

Комплексное развитие и реструктуризация онтологий

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

Итак выше уже был предложен ряд механизмов упрощения и преобразования онтологических структур, а именно:

  • элиминация дублирующихся импортов (8);
  • элиминация псевдоимпортов (10);
  • дезинтеграция структур (14);
  • разрыв циклов (14);
  • преобразование циклов в точку (18).

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

~Ont = \mathcal {h} T, A, \{Ont_{base}\} \mathcal {i},


где ~imp(Ont,\{Ont_{base}\}) = 1.

Онтологию, для которой ~\{Ont_{base}\} = \oslash, мы будем называть базовой нулевого уровня импорта.

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

Например (Рисунок 4), в прямоугольниках обозначены уровни импорта для каждого элемента структуры.


РИСУНОК 4 ВСТАВИТЬ


Развитие нечетких онтологий

ТЕКСТ


Особенности практической реализации

ТЕКСТ

РИСУНОК 5

РИСУНОК 6

Выводы

В данной статье:

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

Аналитическую обработку предлагается производить на двух уровнях декомпозиции структур.

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

Дальнейшими этапами исследований в данном направлении могут быть:

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



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

  1. Gruber, T. Ontolingua: A mechanism to support portable ontologies // Technical report, Technical Report KSL91-66, Stanford University, Knowledge Systems Laboratory. 1992. http://citeseer.ist.psu.edu/gruber92ontolingua.html (03.01.2005).
  2. Berners-Lee, T., Hendler, J., Lassila, O. The Semantic Web // Scientific American, 2001. P. 34-43.
  3. Heflin, J.D. Towards the semantic web: knowledge representation in a dynamic, distributed environment // PhD thesis, University of Maryland, 2001. 137 p.
  4. Sowa. J. F. Building, Sharing, and Merging Ontologies // 2001, http://www.jfsowa.com/ontology/ontoshar.htm (08.12.2005)
  5. Noy N. F., Sintek M., Decker S., Crubezy M., Fergerson R. W., Musen M. A.. Creating Semantic Web Contents with Protege-2000 // IEEE Intelligent Systems, 2001, 16(2). P. 60-71.
  6. Noy N. F., Musen M. A. PROMPT: Algorithm and Tool for Automated Ontology Merging and Alignment // Seventeenth National Conference on Artificial Intelligence (AAAI-2000), Austin, TX, 2000. http://dit.unitn.it/~p2p/RelatedWork/Matching/SMI-2000-0831.pdf (03.01.2005)
  7. Hustadt U., Motik B., Sattler U. Reasoning in Description Logics with a Concrete Domain in the Framework of Resolution // Proc. of the 16th European Conference on Artificial Intelligence (ECAI 2004), August, 2004, Valencia, Spain, pp. 353 357.
  8. Specification of Coordination of Rule and Ontology Languages // Technical Report. IST Project IST-2004-507482, June 2004. http://dl-web.man.ac.uk/~panz/Zhilin/paper.php?epdf=PFTS*04 (15.12.2005).
  9. Sirin E., Parsia B., Grau B. C., Kalyanpur A., and Katz Y. Pellet: A practical owl-dl reasoner. // http://www.mindswap.org/papers/PelletJWS.pdf (08.12.2005)

затем

  1. 9 Кристофидес Н. Теория графов. Алгоритмический подход // Москва, 1978. – 432 с.
  1. 11 Кучеренко Е.И., Павлов Д.А. Некоторые аспекты анализа развития нечетких онтологий. // Искусственный интеллект. Донецк. 2005. – C.162-169
  2. Straccia U. Towards a Fuzzy Description Logic for the Semantic Web // 2nd European Semantic Web Conference, 2005. – P. 167-181.
  3. Mazzieri M. A Fuzzy RDF Semantics to Represent Trust Metadata // Proceedings of the Workshop Fuzzy Logic and the Semantic Web, Marseille, February 11, 2005. http://semanticweb.deit.univpm.it/swap2004/cameraready/mazzieri.pdf (03.01.2006)
  4. Zadeh L.A. Fuzzy Sets // Information and Control, 8(3). 1965. – P. 338-353.
  5. Кофман А. Введение в теорию нечетких множеств // Пер. с франц. М: Радио и связь, 1982. – 432 с.
  6. EON Ontology Alignment Contest // http://oaei.inrialpes.fr/2004/Contest/ (29.12.2005)