Аннотация В работе предлагается алгебраический подход к построению онтологий, способных к эволюции под влиянием новых фактов и обладающих внутренними механизмами валидации. Для этой цели строится формальная модель взаимодействия объектов и выясняются ограничения на операции с объектами, накладываемые такой моделью. Затем в контексте формальной модели определяются основные понятия модели представления знаний: концепты, экземпляры, свойства и отношения. При этом формальные ограничения переносятся в модель представления знаний естественным образом. Ключевые слова: эволюционирующие онтологии, представление знаний, формальные системы.
эффекты вносимых изменений, поэтому необходима реализация специальных механизмов, отвечающих за поддержание согласованности онтологии в процессе её актуализации.
Можно выделить два основных подхода к представлению онтологий: логический и объектный [3]. Логический подход связан с представлением онтологии как формальной системы со своим синтаксисом, аксиомами и правилами вывода, он находится в русле классического искусственного интеллекта, изучающего способы представления знаний. Объектный подход предполагает представление онтологии в виде графа, состоящего из классов, объектов и связей между ними, он удобнее для реализации и чаще используется в прикладных разработках, в рамках него обычно создаются сверхбольшие ресурсы, используемые в широких предметных областях: различного рода словари, таксономии, рубрикаторы и тезаурусы.
Обладая лучшей наглядностью и удобством, объектный подход имеет серьёзный недостаток: он не предоставляет никаких внутренних механизмов контроля непротиворечивости в отличие от формальных систем, имеющих средства контроля полноты и непротиворечивости. Поэтому при объектном подходе инженер по знаниям должен определить систему внешних ограничений, описывающих допущения предметной области. Но проблема в том, что предметная область сама зависит от вновь прибывающих фактов, она всё время меняется. Поэтому система внешних ограничений также должна всё время меняться. Но тогда возникает проблема контроля непротиворечивости изменений уже этой системы ограничений получается замкнутый круг. 1
Постановка задачи Несложно показать, что онтологии, создаваемые в рамках обоих подходов, могут быть преобразованы от одного вида к другому путём перехода к отношениям: каждая непротиворечивая формальная теория имеет модель в теоретико-множественном представлении, с другой стороны, каждый объект может быть представлен как набор записей реляционной базы данных. Поэтому корректней говорить о различных представлениях одной и той же онтологии логическом и объектном. Вопрос состоит в том, какой возможный механизм контроля в объектном представлении может соответствовать концепции противоречивости в логическом представлении. 2
Состояние исследований Большинство работ по эволюции онтологии, известных в настоящее время, описывают различные эвристические подходы их обзор дан в работе Ф. Заблиса и др. [4]. Как правило, в этих работах предлагается некий сложный эвристический алгоритм, берущий на себя рутинную часть работы по согласованию изменений, и предполагается участие инженера по знаниям, выполняющего интеллектуальную часть работы. Другие системы такие
Более перспективно выглядят методы эволюции онтологий, обоснованные теоретически. В работе П. Хаазе и Л. Стояновича [5] выделяется три вида непротиворечивости: структурная (синтаксическая), логическая (семантическая) и определяемая пользователем (внешняя). Большинство динамических онтологий обеспечивают только синтаксическую непротиворечивость на основе соответствия языку описания онтологии или схеме данных. В работе не предлагается решения, обеспечивающего логическую непротиворечивость, однако приводятся эффективные алгоритмы локализации и устранения логических противоречий с помощью исключения конфликтующих аксиом.
В работах Т. Шарренбаха и др. [6,7] конфликты аксиом не запрещаются, поэтому их исключение из онтологии не требуется. Вместо исключения аксиом (явных знаний) авторы предлагают объявлять недействительными конкретные выводы (неявные знания), которые вызывают противоречие в онтологии. Так, оба заключения A и ¬A могут оказаться выводимы, невыводимым останется только противоречие A&¬A. Это приводит к неоднозначности онтологии.
Задача поиска механизма контроля онтологии в объектном представлении, который соответствовал бы концепции противоречивости в логическом представлении, в явном виде ранее не ставилась. 3
Мир как динамическая система 3.1
Формальная логика и клеточные автоматы Машина Тьюринга как универсальный вычислитель способна реализовать как систему продукций аксиоматизируемой формальной логической системы, так и систему продукций клеточного автомата. Отсюда следует, что выразительные способности тьюринг-полных клеточных автоматов достаточны для представления логических ограничений на структуру знаний.
Далее мы будем рассматривать явления предметной области в терминах динамических систем как изменения состояния динамической системы, эволюционирующей с течением времени. Покажем, что клеточный автомат также может рассматриваться как динамическая система, введём в этой модели понятие объектов, опишем их взаимодействия. Поскольку возможностей тьюринг-полного клеточного автомата достаточно для моделирования произвольного процесса эволюции, то найденные закономерности будут справедливы и в общем случае. 3.2 Динамические системы T В самом общем смысле динамическая система есть тройка (T, X, φ), где аддитивный моноид, X множество, а φ функция такая что
φ : T × X → X, φ(0, x)
= x, φ(t2, φ(t1, x)) = φ(t1 + t2, x), где T множество неотрицательных вещественных чисел R+ (непрерывное время), либо натуральных чисел с нулём N (дискретное время) [8,9].
Функция φ(t, x) называется оператором эволюции динамической системы, она ставит в соответствие каждой точке множества X единственный образ, зависящий от переменной t, называемой параметром эволюции. Множество X называется фазовым пространством (или пространством состояний), в котором переменная x определяет начальное состояние системы. 3.3 Клеточные автоматы Пусть G группа, а A
множество. Тогда (см. [10]) Определение 1. Клеточный автомат над группой G и алфавитом A есть отображение τ : AG → AG, обладающее свойством: существует конечное подмножество S ⊂ G и отображение μ : AS → A, такие что
τ (x)(g) = μ((g−1x)|S) для всех x ∈ AG и g ∈ G, где запись (g−1x)|S означает сужение конфигурации g−1x на множество S.
Путём последовательных итераций клеточного автомата τ : AG → AG
можно получить дискретную динамическую систему. Это означает, что
конфигурация может пониматься эволюционирующей во времени в
соответствии с τ : если x ∈ AG конфигурация в момент времени t ∈ N, то τ (x)
конфигурация в момент времени t + 1. Суперпозиция τ t = τ ◦ τ ◦ · · · ◦ τ
итераций по параметру t даёт оператор эволюции динамической системы во
времени
φ(t, x) = τ t(x).
(
Неформально говоря, объектом будем считать глайдер в конфигурационном пространстве. Глайдеры это хорошо известные стабильные динамические структуры (паттерны) в клеточном пространстве игры Конвея ¾Жизнь¿. Глайдер (солитон) является возмущением в активной среде, распространяющимся в этой среде с постоянной скоростью и сохраняющим свою целостность в течение некоторого времени.
Отображение μ : AS → A в формуле (
O(O(g)) =
[ q∈O(g)
q ∪ Sq .
P(t, g) = {Ot(g) : t ∈ N, g ∈ G}.
(
Модель взаимодействия объектов 4.1
Взаимодействие как эволюция состояния Будем рассматривать изменение объектов их взаимное превращение в результате взаимодействия в некоторой области конфигурационного пространства G с заданной на этом пространстве конфигурацией x ∈ AG, эволюционирующей под действием моноида времени T .
Нас будет интересовать только конечный результат взаимодействия после того, как объекты разойдутся в конфигурационном пространстве на достаточное расстояние, чтобы не оказывать влияния друг на друга. Обозначим через Ψ множество конфигураций всех возможных объектов Ψ = {AO : O ∈ P}.
ψ0 = U ψ, Тогда процесс изменения конфигурации ψ = ψ1 ⊗ . . . ⊗ ψn системы взаимодействующих объектов можно записать в привычном виде
Если для gt, g0 ∈ G выполняется условие gt ∈ Ot(g0), то будем говорить, что элемент gt причинно зависит от g0 на интервале времени t. Определение 2. Объектом O назовём динамическую область конфигурационного пространства O(gi) ∈ P, где gi пробегает последовательность причинно зависимых элементов g0, . . . , gt, такую что все конфигурации AO(gi) равны между собой. где U = U (t, x) оператор эволюции состояния x ∈ AG за время t ∈ T , а ψ ∈ Ψ функция состояния системы объектов. 4.2 Взаимодействие как преобразование объектов
Произвольным образом разобьём исходную динамическую систему на две подсистемы ψa и ψb так, чтобы ψaψb = ψ (для удобства будем опускать знак операции ¾⊗¿). Взаимодействие систем ψb и ψa тогда может быть задано с помощью операции ¾ ¿ в виде (ψa0 = ψa ψb
ψb0 = ψb ψa, где первое равенство описывает трансформацию ψa в ψa0 с помощью системы ψb, а второе обратное влияние системы ψa на ψb.
Модель взаимодействия тогда вполне определяется двумя операциями ⊗ : Ψ 2 → Ψ, ¾из чего состоит¿ в пространстве,
: Ψ 2 → Ψ, ¾как изменяется¿ во времени.
Операция ¾⊗¿ ассоциативна, поскольку свойство ¾из чего состоит¿, очевидно, удовлетворяет тождеству (ψa ⊗ ψb) ⊗ ψc = ψa ⊗ (ψb ⊗ ψc). Но не коммутативна порядок аргументов важен, поскольку задаёт расположение объектов в пространстве. Свойства операции ¾ ¿ будут установлены далее (очевидна лишь некоммутативность).
Правила преобразования конфигураций могут быть заданы функциями на множестве Ψ . Иначе говоря, существует инъекция
ξ : Ψ → F(Ψ ), позволяющая отождествить конфигурации объектов Ψ с элементами симметрической полугруппы F(Ψ ) преобразований над ними. 4.3 Связь двух операций ¾⊗¿ и ¾ ¿ Теорема 1. Инъекция ξ : Ψ → F(Ψ ) множества конфигураций объектов в симметрическую полугруппу преобразований является гомоморфизмом относительно операции ¾ ¿, если эта операция действует в пространстве T , связанном с пространством G преобразованием масштаба. Доказательство. Зададим начальное разбиение системы ψ ∈ Ψ в пространстве G так, чтобы она состояла из трёх подсистем следующим образом: ψaψbψc = ψ. Будем попарно объединять эти подсистемы и описывать взаимодействие такого объединения с оставшейся частью полной системы.
Поскольку результат операции ¾⊗¿ зависит от порядка аргументов, при
объединении необходимо следить за тем, в какой системе координат
производится данное действие. Для удобства введём унарную операцию ¬ : Ψ → Ψ
поворота системы координат, связанную с операцией ¾⊗¿ тождеством
¬(ψaψb) = ¬ψb¬ψa.
(
ψc0 = ¬(¬ψc ¬ψab) = ¬ψ¬b¬a(ψ¬c). Во втором уравнении появляется операция обращения аргументов, поскольку относительно подсистемы ψc, на которую действует объединённая подсистема, подсистемы ψa и ψb расположены в порядке ψb, ψa именно в таком порядке и происходит действие. Операция обращения всего выражения отвечает за возврат системы координат в исходное положение.
Теперь объединим подсистемы ψbψc = ψbc, тогда правила трансформации динамической системы ψaψbψc = ψaψbc запишутся в виде (ψa0 = ψa
ψbc = ψbc(ψa) ψb0c = ¬(¬ψbc ¬ψa) = ¬ψ¬a(ψ¬c¬b). (13) (14) (15) (16) (17) (18) (19) (20) (21) Во втором уравнении также появляется операция обращения аргументов по аналогичной причине: подсистема ψa действует сперва на ближайшую к ней подсистему ψb, и только затем на ψc. Операция обращения всего выражения отвечает за возврат системы координат в исходное положение.
Поскольку ψa0bψc0 = ψa0ψb0c = ψ0 = U ψ, то можно приравнять правила трансформации первой и второй систем уравнений:
((ψa ⊗ ψb) ψc) ⊗¬(¬ψc (¬ψb ⊗ ¬ψa)) = = (ψa (ψb ⊗ ψc)) ⊗¬((¬ψc ⊗ ¬ψb) ¬ψa). Равенство выполняется, если и только если существует унарная операция ∝ : Ψ → Ψ , связывающая операции ¾ ¿ и ¾⊗¿ тождеством
∝ (ψaψb) = ψa ψb, тогда равенство можно преобразовать к очевидной форме:
∝ ((ψa ⊗ ψb) ⊗ ψc) ⊗¬ ∝ (¬ψc ⊗ (¬ψb ⊗ ¬ψa)) = =∝ (ψa ⊗ (ψb ⊗ ψc)) ⊗¬ ∝ ((¬ψc ⊗ ¬ψb) ⊗ ¬ψa).
Унарная операция ¾∝¿ существенно ограничивает возможный вид операции ¾ ¿, в частности, должно соблюдаться условие (∀ψx, ψy ∈ Ψ ) ψxψy = ψa → ψx ψy =∝ ψa, которое означает, что все решения уравнения x ⊗ y = ψa с двумя неизвестными также являются решениями уравнения x y =∝ ψa. В этом смысле операции ¾⊗¿ и ¾ ¿ эквивалентны с точностью до преобразования масштаба, определяемого операцией ¾∝¿. При этом операция ¾ ¿ оказывается, вообще говоря, неассоциативной: (ψa ψb) ψc 6= ψa (ψb ψc), Введём формальное обозначение ∝−1∝ ψa = ψa и перепишем тождество (17) в виде
∝ (ψaψb) =∝−1∝ ψa ∝−1∝ ψb, обозначим операцию ¾ ¿ вместе с преобразованием ¾∝−1¿ обратного масштабирования её аргументов через ˜ : Ψ 2 → Ψ , тогда станет очевиден изоморфизм
∝ (ψa ⊗ ψb) =∝ ψa ˜ ∝ ψb.
Также, после замены переменных ψa →∝ ψa и ψb →∝ ψb в тождестве (17) и перехода к обозначению ⊗˜ : Ψ 2 → Ψ , объединяющему операцию ¾⊗¿ вместе с преобразованием ¾∝¿ прямого масштабирования её аргументов, выявляется изоморфизм
∝ (ψa⊗˜ ψb) =∝ ψa ∝ ψb.
Изоморфизмы (24) и (25) связывают пространства T и G преобразованием масштаба, определяемом операцией (17).
Операция ¾⊗¿ ассоциативна, поэтому полугруппа hΨ, ⊗i вкладывается в симметрическую полугруппу F(Ψ ) трансформаций множества Ψ . В силу изоморфизма (24) операция ¾ ¿ тождественна операции ¾⊗¿, если все её аргументы переведены в пространство T преобразованием ¾∝−1¿. Следовательно, инъекция ξ : Ψ → F(Ψ ) (11) является однозначным гомоморфизмом относительно операции ¾ ˜ ¿. (23) (24) (25) 4.4 Спецификация модели взаимодействия объектов
Таким образом, построенная модель включает:
– алгебру hΨ, ⊗, i динамических систем (
Модель представления знаний Построенная модель взаимодействия объектов сводится к подполугруппе J симметрической полугруппы J ⊂ F(Ψ ) преобразований множества Ψ , которая равномощна этому множеству |Ψ | = |J | < |2Ψ |. Такое сокращение числа допустимых преобразований указывает на существование естественных модельных ограничений, что может быть использовано для целей контроля онтологии, однако число степеней свободы всё ещё очень велико. (∀ψb ∈ ΨB)(ψa ψb = ψa0), то множество ΨB будем называть классом со свойством ψa → ψa0.
Совокупность всех свойств объекта ψb полностью определяет преобразование ψb : Ψ → Ψ из полугруппы J . Совокупность всех свойств класса также определяет преобразование, частично определённое на множестве Ψ , которое является пересечением преобразований всех объектов данного класса ψB =
\ ψb∈ΨB ψb.
(27) В эволюционирующей онтологии ни один объект не определён окончательно, под влиянием новых фактов отношения достраиваются и перестраиваются. Поэтому между объектами и классами нет принципиальной разницы те и другие являются частично определёнными преобразованиями.
В прикладных задачах построения онтологий часто приходится иметь дело не с функциями, а с отношениями. Можно показать, что такой переход правомерен, если в теореме 1 перейти к гомоморфизму ξ : Ψ → 2Ψ . В силу однозначного гомоморфизма ξ : Ψ → 2Ψ операция ¾⊗¿ является суперпозицией отношений соответствующих объектов. С другой стороны, она выражается через операцию ¾ ¿ с помощью унарной операции ¾∝−1¿ преобразования масштаба (26). Тождество ψb ◦ ψa = ψa ⊗ ψb = (∝−1 ψa) (∝−1 ψb), (28) где слева стоят отношения, а справа соответствующие им объекты, является мощным средством обеспечения непротиворечивости онтологии, для чего даже не требуется просматривать весь ресурс знаний.
Для организации хранения знаний можно предложить следующую базовую структуру из двух таблиц.
Таблица 1. Структура хранения знаний (с валидацией) head id Идентификатор label Наименование body subj Subject (→ head.id) obj Object (→ head.id) prop Result subj obj (→ head.id) test Result subj ⊗ obj (→ head.id) На начальном этапе все таблицы пусты. В процессе работы каждое новое понятие фиксируется в таблице head, а каждое его свойство попадает в таблицу body. Пока функция ∝−1 не определена, поле body.test не заполняется это можно сделать позже на основе значения body.prop. Классы можно получать динамически как пересечение нескольких отношений, однако из соображений быстродействия имеет смысл запустить автономный процесс, который бы создавал и удалял классы на основе устойчивых корреляций между объектами. Этот же процесс мог бы выполнять трудоёмкую задачу вычисления полей body.test пока быстрое вычисление с использованием функции ∝−1 не станет возможным.
Тождество (28) позволяет вычислять значения функции ∝−1 : Ψ → Ψ динамически по мере добавления новых фактов: поскольку все объекты являются отношениями, кажется, что их суперпозиция тоже должна задавать объект; это почти так если отношения предварительно масштабировать функцией ∝−1, а результат масштабировать обратно с помощью ∝. Для всех пар ψa ◦ ψb данная функция должна быть одной и той же если так не получается, то можно констатировать наличие в онтологии противоречия. 6 Заключение
В работе предложен алгебраический подход к построению онтологий, способных к эволюции под влиянием новых фактов и обладающих внутренними механизмами валидации. Для этой цели установлено соответствие между двумя основными подходами к представлению онтологий: логическим и объектным. В результате этого в объектном представлении удалось отыскать такой механизм контроля непротиворечивости онтологии, который соответствует концепции противоречивости в логическом представлении на основе функции ∝−1. В терминах алгебраического подхода определены основные понятия модели представления знаний: концепты, экземпляры, свойства и отношения. При таком подходе формальные ограничения переносятся в модель представления знаний естественным образом.
Найденное решение является новым, его можно использовать для построения больших прикладных онтологий, не пренебрегая средствами контроля непротиворечивости. Что, в свою очередь, открывает возможности к организации процесса эволюции такой онтологии в автоматическом режиме, что до сих пор было невозможным.
Построенная алгебра с двумя операциями суперпозицией отображений ¾⊗¿ и неассоциативной операцией ¾ ¿ является программной алгеброй. Программные алгебры интенсивно исследуются в настоящее время в контексте построения высокопроизводительных параллельных вычислительных систем [11].
Результаты данной работы планируется использовать при построении ресурса знаний большого объёма для системы извлечения информации из текстов ИСИДА-Т [12]. Благодарности. Работа выполнена в рамках НИР ¾Моделирование модально– временного аспекта описания ситуаций в задаче извлечения информации из текстов¿, номер гос. регистрации 01201455353. Список литературы Abstract. We propose an algebraic approach to building ontologies which capable of evolution under the influence of new facts and which have some internal mechanisms of validation. For this purpose we build a formal model of the interactions of objects, and find out the limitations on transactions with objects imposed by this model. Then, in the context of the formal model, we define basic entities of the model of knowledge representation: concepts, samples, properties, and relationships. In this case the formal limitations are induced into the model of knowledge representation in a natural way.