Крывый С. Л., Ходзинский А.Н.
Институт кибернетики им. В.М. Глушкова НАН Украины,
Украина, Киев, пр. акад. Глушкова, 40,
т. (044)-526-22-34, 526-04-58, email: krivoi@i.com.ua, ho@cyber.kiev.ua
Аннотация. Предлагается подход к представлению онтологий в виде конечного автомата.
Такое представление позволяет ввести операции на онтологиях. Операции на онтологиях дают возможность автоматизировать процесс анализа и синтеза онтологий
и их составляющих частей.
Abstract. A representation of ontology by using finite state automata is considered. This representation allows to introduce the operations on ontologies by using regular algebra of languages. The operations over ontologies allow to automatisate the process of analysis and synthesis for ontologies and their members.
Ключевые слова: онтологии,операции, конечные автоматы
Введение
В последнее время в естественных науках и, в частности, в теоретическом программировании появилось столько различных направлений, течений и теоретических результатов, что становится проблематичным охватить хотя бы малую часть поля научной деятельности даже в отдельно взятых областях. Одним из подходов к пониманию взаимосвязей между различными течениями и теориями является онтологический подход [1,2]. Кроме того, в связи с возрастанием сложности программного и технического обеспечения вычислительных процессов требуется интеллектуализация этих процессов и такой интеллектуализации можно достичь, по мнению многих специалистов, путем использования онтолого-управляемых систем поиска, извлечения и обработки знаний, содержащихся в онтологиях. Онтологический подход для построения связей между понятиями некоторой предметной области, как правило, основывается на определении отношения «предметная область – свойства – модели – приложения». В данной работе рассматривается способ представления онтологий с помощью конечных автоматов с одной стороны, и отношений, лежащих в основе каждой онтологии. Этот подход позволяет ввести операции на онтологиях используя операции на языках и автоматах. При таком подходе типы онтологий и их иерархия не детализируется с целью подчеркивания общности рассматриваемых операций. Операции иллюстрируются на простых примерах онтологий,
относящихся к компьютерной математике [3].
Автоматное представление онтологий
Будем предполагать, что онтологии представляются в виде орграфа G = (V, E), где множество вершин V представляет множество предметных областей, а множество ребер E – бинарное отношение между этими предметными областями. С каждым таким орграфом G = (V, E) будем ассоциировать конечный (вообще говоря) частичный детерминированный автомат без выходов A = (V, X=V, f,S, F), где
V – множество состояний, которое также служит входным алфавитом данного автомата, S – подмножество начальных состояний, F – подмножество заключительных состояний (которое, в частности, может быть пустым), а функция переходов данного автомата определяется следующим образом: f(u,v) = v тогда и только тогда, когда (u,v) 
E и не определено в остальных случаях.
Рассмотрим пример представления фрагмента онтологии для предметной области «Комбинаторика» с помощью конечного автомата [5].
Пример 1. Пусть задана онтология, отражающая малую часть предметной области «Комбинаторика», в виде следующего орграфа:
Рис. 1. Онтология О
Соответствующий данной онтологии конечный автомат имеет вид A = (V = {1,2, 3, 4,5, 6,7}, X = {1,2,3,4,5,6,7}, f, {1}, {7}), где f задана таким графом переходов:
Рис. 2. Конечный автомат А для О
Это значит, что f(1,2) = 2, f(1,3) =3, f(1,4) =4, f(3,5) =5, f(5,7) =7,f(4,6) =6. Остальные переходы в данном автомате неопределенны.
Операции на онтологиях в автоматном представлении
Представление онтологий в виде конечного автомата без выходов позволяет ввести операции на онтологиях. Операции на автоматах означают операции на регулярных языках, которые акцептируются этими автоматами. Основными такими операциями являются следующие:
- объединение – теоретико-множественное объединение множества состояний и множества переходов данных автоматов-аргументов;
- пересечение – теоретико-множественное пересечение множества состояний и множества переходов, пополненное транзитивным замыканием отношения достижимости на автоматах-аргументах;
- конкатенация или умножение двух автоматов – частный случай операции объединения, когда объединение выполняется только по множеству начальных состояний второго автомата;
- итерация – повторяемая конечное число раз операция умножения, применяемая в рамках одной онтологии с целью уточнения и пополнения этой онтологии (эта операция практически означает пошаговое уточнение и пополнение онтологий);
- обращение – ориентация в противоположном направлении переходов в автомате, представляющем данную онтологию, т. е. построение функции переходов g(v,u) = u, тогда и только тогда, когда f(u,v) = v и неопределенно в остальных случаях.
Пример 2. Пусть дана онтология вида
Рис. 3. Онтология О1
Рис. 4. Автомат А1 для онтологии О1
где A1=({0,1,7,8,9,10,11},{0,1,…,11},g,{0},{11}).
Тогда введенные выше операции дают такие результаты, если их применить к автоматам A1 и A из предыдущего примера.
Объединение:
Рис. 5. Автомат А
А1
Пересечение:
Рис. 6. Автомат А
A1
Итерация: уточнение онтологии О1:
Рис. 7. Уточнение О2 для онтологии О1
Рис. 8. Автомат А2 для онтологии О2
Конкатенируя автоматы А1 и А2 по начальному состоянию 8 автомата А2, получаем автомат, представляющий уточненную онтологию O1*O2.
Обращение: применяя эту операцию к А1, получаем автомат:
Рис. 9. Автомат обращения для онтологии О1
Краткая характеристика операций
Алгебраические свойства введенных операций на онтологиях вытекают из соответствующих свойств операций алгебры регулярных языков. Это значит, что данные операции удовлетворяют следующим законам: коммутативность и ассоциативность операций объединения и пересечения, ассоциативность умножения, дистрибутивность операции умножения относительно операций объединения и пересечения.
Данное множество операций (в случае надобности) можно расширять по крайней мере в двух направлениях. Одним из таких направлений является расширение операциями на графах (введение и удаление вершины и ребра, соединение графов, изоморфного соединения [6], декартового произведения и т. д.). Другим направлением является алгебра отношений. Поскольку каждая онтология является
представлением некоторой совокупности отношений (в частности: одного), то можно вводить операции реляционной алгебры.
Какое из возможных направлений будет выбрано, зависит от практических потребностей использования онтологий. Прогнозировать что-либо на этот счет не имеет смысла, так как практика оказывается всегда богаче любой теории. Авторы надеются, что представленные операции над онтологиями окажутся полезными при анализе, синтезе и манипулировании онтологиями и онтологическими объектами.
Проблемы реализации операций
Рассмотрим теперь некоторые проблемы, возникающие на пути реализации данных операций.
Первая проблема (и возможно основная при работе с онтологиями) связана с тем, что корректное выполнение описанных выше операций требует создания некоторого общего глоссария предметных областей и понятий, с помощью которого можно было бы однозначно идентифицировать соответствующие объекты. По видимому, эта проблема является не только проблемой на пути реализации введенных операций, но и в некотором смысле общей проблемой на пути построения онтологий и работы с онтологиями.
Вторая проблема, возникающая при реализации операций, связана с имеющейся иерархией областей и понятий. Дело в том, что в различных онтологиях одни и те же понятия и объекты могут находиться на разных уровнях иерархии и это необходимо учитывать при применении операций. В предлагаемом подходе эта проблема решается с помощью построения транзитивного замыкания отношения достижимости на состояниях автоматов, представляющих данные онтологии. Однако, авторы не уверены в том, что этого замыкания достаточно для решения проблемы. Здесь, по-видимому, необходимы
эксперименты на реальных онтологиях и их представлениях.
Третья проблема связана с полнотой знаний, имеющихся в представленных онтологиях. Эта проблема является основной в процессе спецификации и верификации программного и технического обеспечения. Здесь же эта проблема связана с возможностью построения в некотором (хотя бы) смысле полной
онтолого-управляемой информационной системы.
Заключение
Тема данной работы возникла в связи с докладами, которые были представлены на конференциях KDS-2005 и KDS-2007 (Варна, Болгария) [1-4]. Раздел по онтологиям на этих конференциях был одним из самых больших и доклады, представленные в этих разделах, были стимулирующими для разработки представления онтологий и операций на онтологиях с целью автоматизации процесса проектирования и манипулирования этими объектами. Возможно после данной попытки ввести операции на онтологиях появятся и другие подходы к построению алгебры онтологий, что было бы весьма желательным и плодотворным для развития этой области знаний. Наш подход, по видимому, не является самым лучшим, поскольку требует решения перечисленных выше проблем.
Список литературы
[1] Gavrilova T., Puuronen S. In Search of a Vision: Ontological
View on User Modeling Conferences’ Scope. XII-th International Conference KDS
2007, ITHEA, Sofhia, 2007. Volume 2, p.422-427.
[2] Gribova V. Automatic Generation of Context-sensitive Help Using a User Interface Project. XII-th International Conference KDS 2007, ITHEA, Sofhia, 2007. Volume 2, p.417-422.
[3]Кривой С., Матвеева Л., Лукъянова Е., Седлецкая О. Онтологический взгляд на теорию автоматов. XII-th International Conference KDS 2007, ITHEA, Sofhia, 2007. Volume 2, p.427-436.
[4] Artemieva I. XII-th International Conference KDS 2007, ITHEA, Sofhia, 2007. Volume 2, p.403-411.
[5] Кривий С. Л. Дискретна математика. Вибрані питання. Київ.Видавничий дім „Києво-Могилянська академія”. – 2007. – 572 с.
Кроме того, я надеюсь, что идеи, выраженные в статьях, получат дальнейшее развитие…