| Д. А. Павлов |
Содержание |
Различают качественный и количественный рост информационных структур, либо интенсивный и экстенсивный. Такое же поведение присуще онтологиям. Рассмотрим экстенсивную составляющую развития онтологических структур, которая является основной задачей их использования в качестве средств представления знаний.
Возможность дополнять существующие структуры новыми знаниями, резко отличающимися от ранее представленных, была отправной точкой для множества исследований и разработок. [1] [2] В ряде работ раскрывается процесс развития онтологических структур, как с точки формальной логики [3], так и с точки зрения общего понимания сути развития. [2] [4] Также существует множество прикладных исследований в рамках разработок сред создания онтологий. [5] [6] [7] Эти работы, не смотря на существенный вклад в данном направлении, имеют некоторые недостатки, среди которых хотелось бы отметить низкий уровень формализации процессов развития, а также поверхностный анализ сложных онтологических структур, что не позволяет обобщить методики работы с ними.
Разработка современных сложных онтологических структур представляет собой достаточно стихийный и слабо формализованный характер, что порождает создание уникальных структурных решений. Зачастую такие решения являются неоптимальными и требуют дополнительной обработки для снижения сложности применяемых алгоритмов. Таким образом, исследование в данном направлении актуально.
Целью работы является разработка и обоснование строгой формальной базы экстенсивного развития онтологических структур, с целью последующего использования в построении методов и алгоритмов работы с распределенными онтологиями. Также в работе должны быть предоставлены методы реструктуризации онтологии с целью упрощения ее формальной модели.
С учетом цели работы, необходимо:
Учитывая прикладную направленность исследований онтологий, также необходимо предложить пример практической реализации результатов исследования.
Ограничение 1. В данной статье рассматриваются непротиворечивые онтологии, то есть все отдельные элементы онтологий, о которых будет идти речь, непротиворечивы. Данное ограничение не сужает область применения результатов данного исследования, а определяет декомпозиционный уровень их использования.
Онтология
есть пара
, где
— таксономия концептов данной онтологии и множество отношений, определенных на данной таксономии,
— множество аксиом, основанных на заданном
[8].
Интерпретация
онтологии
есть пара
, где
непустое множество предметной области, и
функция, которая присваивает каждому концепту
из
подмножество из
, каждому отношению
из
подмножество из
, и каждой аксиоме
элемент из
[8]
Утверждение 1. Две онтологии эквивалентны тогда, когда их интерпретации эквивалентны.
Действительно, если некоторая предметная область разделяется одинаковым образом на классы и отношения между ними различными онтологиями, то одна из онтологий может без ограничений быть заменена другой.
Отметим, что [8]
,
.
Всякая распределенная онтологическая структура может быть интегрирована в единое целое за счет использования отношений импорта.
Определение 1. Отношение импорта онтологий
, (1)
где
— импортируемая онтология, а
— импортирующая, есть некоторое мета-описание, утверждающее, что в рамках
принимаются все соглашения, действующие в
, здесь и далее
= “true” = “истина”.
Пусть конечное множество всех
заданных на данной онтологической структуре есть
, где
(2)
Отметим, что:
если
то
(3)
, если
, где
(4)
Для упрощения записи пусть
.
А также пусть для некоторой онтологии
множество входных или импортирующих отношений —
и множество выходных —
.
Отношения полученные из (3), такие что
, (5)
будем называть неявным импортом.
Введем следующую интерпретацию графа онтологической структуры: узлы — онтологии, ориентированные дуги — отношения импорта, где начало — импортируемая онтология, конец — импортирующая онтология,
, (6)
где
— множество всех онтологий входящих в структуру.
Графовая модель представления однозначно и кратко описывает распределенную онтологию, и ее выбор для решения поставленных задач очевиден.
Тогда мы имеем право говорить об эквивалентных преобразованиях в рамках графового представления.
Определение 2. Дублирующими дугами мы будем считать те дуги, отсутствие которых на графе (6) может быть в любой момент восстановлено в силу (3).
, если для
,
. (7)
Определим множество импортов без дублирующих дуг
(8)
Формирование множества
включает в себя задачу поиска наименьшего пути
для каждого
такого, чтобы
.
Схожие задачи решались в работах [8].
Согласно утверждению 1
.
Для любых двух онтологий, связанных отношением импорта (1), естественно, что одна из них использует вторую как базу для построения своей структуры знаний. Создавая такую структуру, первая онтология тем самым развивает знания, хранящиеся в базовой. Такого рода развитие мы будем называть аддитивным, то есть которое непосредственно наращивает знания. Формально аддитивное развитие онтологий (Рисунок 1) есть любое импортирование, для которого верны следующие утверждения:
а)
, такое что
, то есть
импортирует только одну онтологию;
б)
не содержит циклических ссылок импорта на саму себя.
РИСУНОК 1 ВСТАВИТЬ
Введем далее необходимые определения независимости элементов и множеств элементов онтологий.
Определение 3.
Независимым элементом
и от элемента
онтологии
будем называть такой элемент, для которого верно:
, если
,
где
интерпретация данного элемента онтологии с помощью
,
значит, что
может принимать любые значения, возможные в рамках данной онтологии.
Определение 4.
Независимым множеством элементов
от множества элементов
онтологии
будем называть такое
, для которого верно:
, если
.
Итак, возвращаясь к развитию онтологий, очевидно, что элементы расширения могут не зависеть от базовой онтологии. Возможны случаи, что ни один из элементов расширения не зависит от базовой онтологии.
Определение 5.
Псевдоимпорт
— это такой
, что.
, если
. (9)
Утверждение 2. Связь развития вида (9) может быть элиминирована в ходе некоторых этапов анализа общей структуры со следующим условием: удаляя некоторую pRI, нужно сохранять транзитивную целостность структуры.
Действительно, удаление набора элементов, от которых не зависит ни один из элементов онтологии, никак не отразится на интерпретации этой онтологии, то есть семантика сохранится.
Сохранение транзитивной целостности при удалении отношения вида (9) обеспечивается перенаправленим связи на все расширения онтологии
, у которой удаляется
. То есть, пусть существует удаляемая связь
.
есть множество расширений
, тогда
, (10)
где
,
,
,
.
Тогда в общем виде, с учетом (8) и (10)
Детализируем уровеь рассмотрения развития онтологий.
Представление онтологии в виде
имеет ряд достоинств применительно к поставленным задачам, а именно:
Тогда, на более детальном уровне, аддитивное расширение базовой онтологии есть
, (11)
где
, а
- непосредственно элементы расширения.
На практике зачастую расширение базовой онтологии (11) редуцировано и осуществляется только за счет добавления аксиом:
. (12)
Определение 6. Совокупность всех элементов расширения в случае (12) будем называть ресурсом Res.
Расширение онтологии с помощью ресурсов соответствует использованию базовой онтологии в качестве схемы данных.
Более сложным видом развития онтологической структуры, нежели аддитивное, является интеграционное. Возможность интеграции — это одно из основных требований предъявляемых к онтологиям. Для такого него характерно импортирование некоторого множества базовых онтологий.
Формально интеграционное развитие онтологий (Рисунок 2) есть
,
,
где
j-ая базовая онтология,
общее расширение для всех
,
– число онтологий, интегрируемых в
.
РИСУНОК 2 ВСТАВИТЬ
Для упрощения записи введем множественные функцию импорта
Интеграционное развитие на более детальном уровне можно представить как
,
при чем
, являются системно согласуемыми.
Определение 7. Системно согласуемыми онтологиями будем называть множество онтологий такое, что для него можно создать хотя бы один интегрирующий ресурс (12), содержащий хотя бы одну непротиворечивую аксиому.
Определение 8. Противоречивой аксиомой будем называть такую аксиому которая в данных условиях эквивалентна пустому множеству.
Помимо интеграции онтологий, возможен обратный искусственный процесс — дезинтеграция. Для осуществления дезинтеграции необходимы понятия несвязности элементов и множеств элементов онтологий.
Определение 9.
Несвязанными элементами
и
онтологии
будем называть такие элементы, для которых верно:
, если
.
Определение 10.
Несвязанными множествами элементов
и
онтологии Ont будем называть такие множества, для которых верно:
, если
.
Определение 11. Под дезинтеграцией элемента онтологической структуры мы будем понимать
,
,
где
,
множество онтологий, на которые распадается
.
Возвращаясь к графовой модели, дезинтеграция — есть ничто иное, как разделение некоторого узла на множество узлов.
Тогда (14) для (2) это:
. (15)
Для (15) характерно наличие псевдоимпортов среди вновь добавленных дуг.
После дезинтеграции могут возникать некоторые узлы
и
такие, что
и
, то есть структуры, для которых одинаковы все базовые и все развивающие онтологии.
Такие узлы мы не будем рассматривать как различные.
Совместное развитие (Рисунок 3) является важной особенностью онтологических структур. В таком развитии отсутствует иерархия, то есть каждая из двух онтологий являются друг для друга, как базовой, так и расширением.
где
,
совместно развиваемые онтологии.
РИСУНОК 3
Замечание 1.
Заметим, что пространственно существуют две различные онтологические подструктуры
и
, но всегда, кроме случаев использования (14), они семантически неразделимы и являются некоторой обобщенной структурой.
Совместно развиваемые онтологии не ограничиваются наличием только двух подструктур. Они могут состоять из цикла любой длины:
, (17)
где
общая онтологическая структура,
элемент, принадлежащий некоторому замкнутому пути импортов,
– общая длина цикла, при чем
, и
.
Теорема 1.
О вхождении элемента в цикл (необходимая и достаточная).
Некоторое расширение
онтологической структуры входит в некоторое совместное развитие
(11), тогда и только тогда, когда
, то есть
является для себя же базовой.
Доказательство необходимости.
Пусть некоторая
(17). Предположим, что
. Но в силу (3)
следовательно
.
Получаем противоречие. Следовательно
является для себя базовой.
Доказательство достаточности. Пусть
и
.
Предположим, что
не входит ни в один из циклов онтологии.
Тогда множества импортируемых и импортирующих элементов не пересекаются:
.
Но в силу (3) предположения
,
и
.
Следовательно
Имеем противоречие.
Следовательно
входит по крайне мере в один из циклов онтологии.
Теорема доказана.
Учитывая замечание 1 предлагается два подхода к упрощению циклов:
а) при возможности эффективного использования дезинтеграции (14) – разрывать цикл;
б) не теряя общности, рассматривать цепочку онтологических расширений в качестве единой структуры, заменяя при этом цикл узлом, сохраняя при этом все связи импорта (1) не входящие в цепочку. Тогда для (2) это
, (18)
где запись
множество онтологий, которые импортирует l-я онтология цикла,
множество онтологий, которые импортируют l-ю онтологию цикла.
Комплексное развитие онтологических структур является сложнейшим из экстенсивных развитий и содержит одновременно все черты ранее описанных. Очевидно, что большинство распределенных онтологий развиваются комплексно, и поэтому такой вид развития требует особого внимания.
Итак выше уже был предложен ряд механизмов упрощения и преобразования онтологических структур, а именно:
Выполняя данные преобразования над комплексно развитой онтологией, мы получаем упрощенную онтологическую структуру без циклов и с более информативным набором импортов.
Расширение
в такой упрощенной структуре можно представить следующим образом
,
где
.
Онтологию, для которой
, мы будем называть базовой нулевого уровня импорта.
Уровень импорта будем определять, как максимальную длину пути на графе от данного расширения до самой дальней базовой онтологии нулевого уровня.
Например (Рисунок 4), в прямоугольниках обозначены уровни импорта для каждого элемента структуры.
РИСУНОК 4 ВСТАВИТЬ
ТЕКСТ
ТЕКСТ
РИСУНОК 5
РИСУНОК 6
В данной статье:
Аналитическую обработку предлагается производить на двух уровнях декомпозиции структур.
Результаты данной работы могут быть использованы при автоматизации процессов в распределенных онтологических структурах. Формальная модель экстенсивного развития онтологии применима в системах, обеспечивающих ее функционирование, а также непосредственно развитие.
Дальнейшими этапами исследований в данном направлении могут быть:
| | Это незавершённая статья. Это примечание по возможности следует заменить более точным. |