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

На правах рукописи

(ьА

ГРИГОРЬЕВ Андрей Викторович

МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ ОПРЕДЕЛЕНИЯ СОГЛАСОВАННОСТИ БАЗ ЗНАНИЙ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

г а ноя 2013

Тюмень - 2013

005540327

005540327

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

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор технических наук, профессор Ивашко Александр Григорьевич

Гун Александр Константинович доктор физико-математических наук, профессор, ФГБОУ ВПО «Омский государственный университет им. Ф.М. Достоевского», заведующий кафедрой кибернетики Захаров Сергей Дмитриевич кандидат физико-математических наук, доцент, ФГБОУ ВПО «Тюменский государственный университет», доцент кафедры программного обеспечения

ФГБОУ ВПО «МАТИ - Российский государственный технологический университет имени К.Э. Циолковского»

Защита диссертации состоится «¿0» декабря 2013 года, в «1Ь -Со» на заседании диссертационного совета Д 212.274.14 при ФБГОУ ВПО «Тюменский государственный университет» по адресу 625003, г. Тюмень, ул. Перекопская 15а, ауд. 410.

С диссертацией можно ознакомиться в Информационно-библиотечном центре ФБГОУ ВПО «Тюменский государственный университет».

Автореферат разослан «15» ноября 2013 года.

Ученый секретарь

диссертационного совета Е.А. Олейников

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. Исследования в области разработки методов определения согласованности баз знаний обусловлены необходимостью решения таких практически значимых задач как семантический поиск, классификация понятий предметной области или поддержка принятия решений в экспертных системах. Для решения задач такого рода успешно применяются методы, основанные на автоматах (D. Calvanese, KRDB Research Center в Университете г. Бозен-Больцано; Т. Either, Институт информационных систем университета г. Вена), методы, основанные на правилах вывода (Е. Kazakov, Вычислительная лаборатория Оксфордского университета), метод резолюций (В. Motik, университет г. Манчестер) и табличные методы (I. Horrocks, университет г. Манчестер). Основная проблема таких методов заключается в том, что все они имеют экспоненциальную вычислительную сложность, поэтому их применение в задачах реального времени весьма затруднительно для больших баз знаний (более 5000 аксиом).

Для того, чтобы снизить время работы представленных методов на практике, учеными предпринимается огромное количество попыток разработки новых алгоритмов. Такие разработки ежегодно представляются на международных конференциях по применению логических формализмов в искусственном интеллекте «Description Logic Workshop» и «International Joint Conference On Automated Reasoning». Наиболее значимыми разработками, представленными на данных форумах, являются: алгоритм кэширования (Y. Ding, V. Haarslev), backJumping-алгоритм (I. Horrocks), алгоритм глобального кэширования (L. A. Nguyen), которые, зачастую, основываются на методах теории множеств и методах логики первого порядка, кроме того ни одна из этих разработок не направлена на снижение теоретической оценки вычислительной сложности.

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

Для достижения поставленной цели необходимо решить задачи:

1. Построение сетевой модели базы знаний, описанной выражениями дескрипционной логики.

2. Разработка метода нахождения максимального потока минимальной - ' стоимости в разработанной сетевой модели базы знаний.

3. Реализация программного комплекса для поддержки деятельности инженера по знаниям, реализующего разработанные методы и алгоритмы.

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

Объектом исследования диссертационного исследования являются базы знаний.

Предметом исследования являются процессы определения согласованности описания баз знаний.

Методология и методы исследования. При исследовании применялись методы теории множеств, теории графов, теории методов оптимизации.

На защиту выносятся следующие результаты соответствующие трем пунктам паспорта специальности 05.13.18 - Математическое моделирование, численные методы и комплексы программ по физико-математическим наукам:

Пункт 1. Разработка новых математических методов моделирования объектов и явлений.

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

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

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

3. Предложен новый численный метод нахождения максимального потока минимальной стоимости в разработанных сетевых моделях баз знаний. Вычислительная сложность разработанного алгоритма составила О(V2).

Пункт 4. Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента.

4. Разработан программный комплекс для поддержки деятельности инженера по знаниям, позволяющий проводить классификацию, проверку согласованности и выполнимость концептов. Описание базы знаний реализовано с помощью языка OWL 2.

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

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

Научная новизна исследования заключается в следующем:

1. Разработана и обоснована сетевая модель базы знаний, представленной аксиомами предметной области, что дает возможность использовать математические методы и алгоритмы, применяемые в теории графов;

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

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

4. Модифицирован алгоритм нахождения автоморфизмов в деревьях (J. Edmonds) для поиска изоморфных концептов базы знаний.

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

5

на языке OWL 2, выполнять проверку согласованности базы знаний, классификацию понятий и проверку их выполнимости.

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

Апробация результатов. Основные результаты исследования докладывались на:

• II международной конференции «OWL Reasoner Evaluation Workshop (ORE 2013)» (Германия, Ульм, 22 июля 2013);

• Международной научно-практической конференции «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании'2012» (Украина, Одесса, 18-27 декабря 2012);

• XIV международной научно-практической конференции «Современные проблемы гуманитарных и естественных наук» (Москва, 26-27 марта 2013 г.);

• Научно-технической конференции «Современные проблемы математического и информационного моделирования. Перспективы разработки и внедрения инновационных IT-решений» (Тюмень, ISIS апреля 2012 г.)

Публикации. Основные результаты диссертации опубликованы в 9 работах, список которых приведен в конце автореферата, в т.ч. 3 статьи в рецензируемых журналах, а также получено 1 свидетельство о государственной регистрации программ для ЭВМ.

Структура и объем диссертации. Диссертация состоит из введения четырех глав, заключения и списка литературы. Общий объем работы составляет 115 страниц, включает 26 рисунков и 18 таблиц. Список литературы содержит 111 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Обзор подходов основанных на графах, показал, что два наиболее эффективных, с точки зрения осуществления вывода знаний, формализма: семантические сети и фреймы имеют ряд недостатков при их использовании на практике, основной из которых заключается в том, что они не всегда однозначно отражают представляемые знания. Кроме того, для описания знаний необходимо использовать специализированные инструменты. В связи с этим существует немного разработок использующих данные формализмы. В отличие от подходов, основанных на графах, в подходах, основанных на формальной логике, существует множество формализмов, которые успешно применяются в различных предметных областях. Формализм дескрипционных логик представляющий основу языка OWL 2, который является стандартом описания баз знаний, рекомендованным консорциумом W3C, успешно применяется при решении задач семантического поиска и классификации понятий предметных областей; решение таких задач получило практическое применение в медицинских экспертных системах. Язык OWL 2 характеризуется однозначностью представления знаний и использованием точных и быстрых методов вывода знаний. На основе этих фактов делается вывод о том, что наиболее перспективным подходом для решения практических задач является язык OWL 2 и дескрипционные логики.

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

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

Глава 2 содержит описание разработанной математической модели. Математическая модель определяет схему построения сети описывающей пересечение двух классов предметной области; такая сеть строится посредством преобразования формул дескрипционной логики в термины теории графов. Схема построения графа определяется с помощью функции Р(С, О), которая ставит в соответствие двум концептам взвешенную сеть в < V, Е, С(£), IV (Е) >. Множество вершин в сети, представленной отображением Р(С,0) обозначается Ру(С, /)), множество ребер сети -РЕ(С, О), символом Рс(С, О) обозначим функцию отображающую множество ребер РЕ(С,0), во множество натуральных чисел, такую функцию назовем пропускной способностью; символом Рцл(С, О) обозначим функцию отображающую множество ребер Ря(С, О), во множество целых чисел, такую функцию назовем весовой.

Для двух концептов, являющимися простыми концептами правила определяются формулами (1)-(5), формула (5) используется вместо формулы (3) в тех случаях, когда во множестве аксиом Т не существует аксиом С Е -10 и С = -10.

Ру(С,^0 = {г7^,5} (1)

Ре(С,-пС) = {(5,У^)} (2)

Рс(С, -,С) = {(с ((ж, = о)}

(3)

(4)

Рс(С,0) = {(с((^°)) = 1)} (5)

Формулы (6)-(9) определяют схему построения графа для двух концептов являющихся кванторами существования и всеобщности, при условии эквивалентности ролей.

РяОЯ.ОЯ.О') = РЯ(С',0') и

(6) (7)

Рс(ЭР.Ой.О') = = і) и Рс(С',0')} (8)

Р„(Эй. С', V/?. О') = {(IV ((^= о) и Рс(С', О')} (9)

Формулы (10)-(13) определяют схему построения графа для двух концептов, один из которых является дизъюнкцией, а второй конъюнкцией.

Р„(С1П...ПСДг,Д1и...и0м) (10)

1=1..лу=1..м

рв(с1п...пс1,ди...иви) (11)

¡=1..ЛГ,У=1..М

Рс(Сх П ... П Сд,, и ... и Дм) (12)

и(с((и/Л0) = А?-1) и У Рс(С^)]

РИг(С1П...ПСд,,01и...и0м) (13)

-{НК^М

и (IV ((и/-0.4'°)) = о) и (с ((и/л 0) = -1)

и У М^)]

Формулы (14)-(17) определяют схему построения графа для двух концептов являющимися конъюнкциями.

Р^ССі П ... П С„, Ві П ... П £>и) (14)

= и (МЗД)^)

І=і..ЛГ,;=І..М

РЕ{Сг П ...ПСл,^! П ...ПВИ) (15)

Рс(Сі П ... П Сдг.Й! п ... п Ом) (16)

= 1)

и У Рс(ад)]

^П-ПЯм) (17)

= = и = о)

І=1.М,]-1..М )

Формулы (18)-(21) определяют схему построения графа для двух концептов являющимися дизъюнкциями.

Р„(Сі и ... и и ... и Эм) (18)

РЕ(Сг и ... и и ... и £>м) (19)

и ((РЕ(сг,я,)

¡=1..ЛГ,;=1..М

рс(сг и... и и ... и Ям) (20)

= и Рс(ад)]

и

р^ и... и о1 и... и ом) (21)

и У Р^йЛ

¡=1..ЛГ,У=1..М ^

Математической моделью двух концептов С и О, назовем взвешенную сеть в <У,Е, С(Е), И^(Я) >, для которой:

{5, С} с у У = УиРк(С,1>) Е = ЯиРЕ(С,£>) С = СиРс(С,£>)

Ух? е К: йед~(у) = 0 или йед~(у) = N и |е(и,¿)| = М, добавить в граф новое ребро е(и, С) с пропускной способностью 1 и весом К, обозначим такое ребро символом г.

Для каждой вершины V 6 V, определим множество т(и), для которого с? е т(и) если Ц & (ц, V) е Е; аналогичным образом определим ои£(у), для которого д е out(v) если д £ V, (17, с/) е Е.

Корректность использования такого графа для непересекаемости двух концептов доказывается в теореме 1.

проверки

Теорема 1. Если Ь максимальный поток в графе Р{С, О) и он имеет отрицательный вес, то концепты С и Э не пересекаются.

Задача нахождения максимального потока минимальной стоимости может быть выполнена путем последовательного решения двух задач линейного программирования. При решении первой задачи выраженной системой линейных ограничений (22) и целевой функцией (23), будет найдена величина максимального потока.

Ve е Е: 1{е) > О Уе 6 Е: 1(е) < /(е)

10*0

чет(у)

1 ™ = 1

мгЕои^р)

1М

(22)

<7Е1П(0

и>Е0иС(5~)

У= X 1(ч)->тах (23)

<7 £¿71(0

Затем необходимо решить вторую задачу линейного программирования, выраженную системой линейных ограничений (24) и целевой функцией (25), в которой необходимо использовать найденную величину V максимального потока.

Ve 6 Е: 1{ё) > 0 Уе е Е: /(е) < /(е)

^ ¿(с?) = ^

¿(IV)

2 10?) = 2

дет(0 шеоиСВД

чет(Г)

(24)

И'(ч') * '07) тт

(25)

Решать задачи линейного программирования можно с использованием классических методов (например, симплекс-метод) или специализированных 12

методов теории графов (метод Форда-Фалкерсона). Однако, минимальная вычислительная сложность среди этих методов пропорциональна полиному 4ой степени (0(Д'4)). Такая вычислительная сложность является не приемлемой для задачи проверки непересекаемости концептов. Исходя из того, что представленная схема строит сети определенной структуры, был предложен алгоритм, который осуществляет поиск максимального потока минимальной стоимости с вычислительной сложностью 0(А/2). Алгоритм нахождения максимального потока минимальной стоимости проходит следующие шаги:

ШАГ 1. Вычисляется величина потокового потенциала вершины 5, равна сумме пропускных способностей исходящих ребер (26).

FP(s) = ^ c(s,u)

(26)

ueout(s")

ШАГ 2. Вершины графа сортируются в порядке увеличения пути от вершины s.

ШАГ 3. В порядке определенном увеличения высоты, вычисляется потоковый потенциал каждой вершины равный (27).

FP(w)= ^ min(c(u, w), FP(u)) (27)

u£in(w)

ШАГ 4. Для каждого ребра (и, w) инцидентного вершине w, вычисляется величина L, по формуле (28).

L(u, w) = min(c(u, w), FP(u)) (28)

ШАГ 5. Если существует ребро (w, t) инцидентное вершине w, то в порядке увеличения стоимости обновляются значения потоковых потенциалов вершин t и w, и поток по ребру (w, t) по формулам (29)-(31).

FP(t) = FP{t) + min {c(w, t), FP(w)) (29)

FP(vv) = FP(w) - min (c(w, t). FP(w)) (30)

L(w, t) = min (c(w, t),FP{w)) (31)

ШАГ 6. Если ребро (w, t) имеет отрицательный вес, и ¿(w, i) > 0, то вес потока устанавливается равным -1.

Корректность работы такого алгоритма доказывается в теореме 2. Оценка вычислительной сложности данного алгоритма представлена в теореме 3.

Теорема 2. /7Р(С) является величиной максимального потока в графе Р(С, О) и значение Ь(у/, £) является величиной максимального потока минимальной стоимости по ребру (и/, £)•

Теорема 3. Вычислительная сложность представленного алгоритма в худшем случае пропорциональна 0(У2).

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

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

Предложение 1. Если для множества литералов концепта С существует автоморфизм / и / - интерпретация данного концепта, то концепт С будет выполним на интерпретации тогда и только тогда, когда он будет выполним на интерпретации /.

Поиск изоморфизмов между концептами или автоморфизмов в концепте осуществляется с помощью модифицированного метода Эдмондсона.

Глава 3 содержит описание программного комплекса реализующего разработанные методы и алгоритмы.

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

1. Описывать знания в виде онтологий;

2. Объединять разработанные онтологии;

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

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

Уровень представлений отвечает за взаимодействие пользователя с системой в рамках ввода данных (формирования онтологий), запуска расчетов и отображения информации. Программы TReasonerVis и Protégé отвечающие за эти задачи разработаны на языке Java для обеспечения переносимости программного комплекса между различными системами, и взаимодействуют с уровнем представлений по протоколу HTTP. Для организации обмена данными используется web-сервер GlassFish.

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

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

Уровень хранения данных организован файловой системой и модулем OWL API поддерживающей управление данными в формате OWL.

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

В качестве входных данных эксперимента были использованы базы знаний из трех репозиториев баз знаний: NCBO BioPortal, Oxford Ontology Library, Manchester Ontology Repository. Из всех онтологий данных хранилищ были отобраны только онтологии OWL 2 трех различных профилей, которые содержали не менее 100 аксиом и 10 имен концептов:

1. 50 небольших онтологий (от 100 до 499 логических аксиом);

2. 100 онтологий средних размеров (от 500 до 4999 логических аксиом);

3. 50 больших онтологий (от 5000 логических аксиом).

Для проведения эксперимента был использован компьютер Intel Xeon QuadCore CPU @2.33 GHz, 12 GB RAM (8 из которых назначались для процесса), под управлением операционной системы Fedora 12, с использованием Java-машины версии 1.6.

Суть эксперимента заключалась в определении количества правильно выполненных задач логического анализа: классификации, выполнимости концептов и согласованности баз знаний, для каждого из профилей OWL 2. Для задачи классификации были использованы 200 баз знаний, для проверки согласованности - 200 баз знаний, и для задачи проверки выполнимости были использованы 200 баз знаний и 10 концептов из каждой базы знаний. Результаты, полученные разработанным программным комплексом, сравнивались с результатами полученными другими современными системами логического анализа OWL баз знаний, такими как HermiT, FaCT++, Konclude, MORe, wsclassifier, chainsaw и д.р.

Результаты эксперимента показали, что разработанные методы и алгоритмы, наиболее эффективно решают задачи классификации баз знаний, описанных с помощью языка OWL 2 RL: из 197 баз знаний, правильно смогли быть классифицированы 181 (91,9%) база знаний (рис. 2), и проверке выполнимости концептов базы знаний описанной с помощью профиля OWL 2 DL: из 2040 концептов, правильный ответ был показан для 1808 концептов (88,6%) из 204 различных баз знаний (рис. 3).

Рис. 2. Результаты эксперимента по классификации OWL 2 RL баз знаний.

Рис. 3. Результаты эксперимента по проверке выполнимости концептов,

Соотношение правильно выполненных задач для всех профилей OWL представлено в таблице 1.

Таблица 1. Результаты вычислительного эксперимента

Профиль OWL Классификация Выполнимость Согласованность

DL 46,3% 89,5% 77,5%

EL 82,0% 97,1% 97,0%

RL 91,8% 99,5% 95,9%

Итого 73,3% 95,4% 90,1%

В заключении сформулированы основные результаты диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработана сетевая модель представления знаний предметной области, в которой узлы графа ассоциированы с конъюнкцией концептов, а вес и стоимость ребер определяются видом операций и кванторов

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

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

3. Модифицирован табличный алгоритм исключением дублирования проверки согласованности изоморфных концептов, который реализован на основе алгоритма Шмидта-Шаусса-Смолки и алгоритма поиска классов изоморфных концептов Эдмондсона.

4. Разработана клиент-серверная трехуровневая архитектура программного комплекса инженера по знаниям: уровень представления реализован в виде кроссплатформенного Desktop-приложения; логический уровень организован в виде серверных Java-библиотек; хранение данных включает инструменты работы с XML-файлами в стандарте OWL2.

5. Использование модуля OWL API и программного продукта стэндфордского университета Protégé в качестве модуля программного комплекса позволяет применять базы знаний, описанные с помощью стандартизированного языка OWL 2.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в рецензируемых журналах, рекомендованных ВАК

1. Григорьев А.В. Модификация табличного алгоритма на основе проверки непересекаемости сложных концептов [Текст] / А.Г. Ивашко, А.В. Григорьев, М.В. Григорьев. // Вестник Тюменского Государственного Университета. - 2012, №4. - С. 143-150.

2. Григорьев А.В. Сокращение пространства поиска интерпретаций за счет обнаружения изоморфных концептов [Текст] / А.Г. Ивашко, А.В. Григорьев. // Вестник Тюменского Государственного Университета. -2013, №7.-С. 187-193.

3. Григорьев А.В. Применение табличного алгоритма для верификации бизнес-процессов [Текст] / А.Г. Ивашко, А.В. Григорьев, А.А. Кропотин, Е.О. Овсянникова // Вестник Тюменского Государственного Университета. - 2013, №7. - С. 202-213.

Публикации в других изданиях:

4. A.V. Grigorev. TReasoner: System Description. / A.V. Grigorev, A.G. Ivashko // Proceedings of the 2nd OWL Reasoner Evaluation Workshop (ORE 2013). -2013, C. 26-31.

5. Григорьев А.В. Извлечение классификационной информации при проверке выполнимости концептов табличным алгоритмом [Текст] / А.В. Григорьев, А.Г. Ивашко // Труды XIV международной научно-практической конференции «Современные проблемы гуманитарных и естественных наук». - Москва: ИСИ, 2013. - С. 122-125.

6. Григорьев А.В. Проблема поиска противоречий на диаграммах классов UML [Текст] / А.В. Григорьев, А.А. Кропотин, Е.О. Овсянникова // Труды международной научно-практической конференции «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании'2012». - № 4. Том 14. - Одесса: КУПРИЕНКО, 2012 - 111 с.

7. Григорьев А.В. Алгоритм упрощения концептов ALC [Текст] / А.В. Григорьев // Труды научно-практической конференции «Современные проблемы математического и информационного моделирования. Перспективы разработки и внедрения инновационных IT-решений». -2012г.

8. Григорьев А.В. Сравнение модификаций табличного алгоритма: BackJumping и семантический выбор [Текст] / А.В. Григорьев // Труды научно-практической конференции «Современные проблемы

математического и информационного моделирования. Перспективы разработки и внедрения инновационных IT-решений». - 2012г.

Свидетельства о регистрации программ для ЭВМ: 9. Григорьев A.B., Ивашко А.Г. Свидетельство об официальной регистрации программы для ЭВМ №2012616455 "Программный модуль для определения непротиворечивости базы знаний описанной на языке дескрипционной логики ALC табличным методом".

ГРИГОРЬЕВ Андрей Викторович

МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ ОПРЕДЕЛЕНИЯ СОГЛАСОВАННОСТИ БАЗ ЗНАНИЙ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать: 18.11.2013

Заказ № 2559 Тираж - 100 экз. Печать трафаретная Типография ОАО «Тюменский издательский дом» ИНН 7202144689 625031, Тюмень, Шишкова 6 (3452) 69-56-73

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

На правах рукописи

04201452223

ГРИГОРЬЕВ Андрей Викторович МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ ОПРЕДЕЛЕНИЯ СОГЛАСОВАННОСТИ БАЗ ЗНАНИЙ

Специальность 05.13.18 - «Математическое моделирование, численные методы и комплексы программ»

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: доктор технических наук, профессор Ивашко Александр Григорьевич

Тюмень - 2013

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ...........................................................................................................4

ГЛАВА 1 МЕТОДЫ ОПРЕДЕЛЕНИЯ СОГЛАСОВАННОСТИ БАЗ ЗНАНИЙ..........................................................................................................................9

1.1 Математические инструменты представления знаний.........................9

1.1.1 Подходы основанные на теории графов................................................9

1.1.2 Подходы основанные на формальной логике.....................................11

1.2 Алгоритмы анализа баз знаний................................................................23

1.2.1 Методы основанные на автоматах........................................................24

1.2.2 Методы основанные на правилах вывода............................................25

1.2.3 Метод резолюций...................................................................................25

1.2.4 Табличные методы.................................................................................25

1.3 Выводы..........................................................................................................28

ГЛАВА 2 МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ.....................................................................................................................30

2.1 Сетевая модель классов предметной области.......................................30

2.2 Разработка метода решения задачи о максимальном потоке минимальной стоимости для разработанной сетевой модели............................43

2.3 Использование изоморфизма концептов для проверки согласованности баз знаний......................................................................................47

2.4 Выводы..........................................................................................................49

ГЛАВА 3 ПРОГРАММНЫЙ КОМПЛЕКС ПОДДЕРЖКИ ДЕЯТЕЛЬНОСТИ ИНЖЕНЕРА ПО ЗНАНИЯМ.................................................51

3.1 Описание архитектуры программного комплекса..............................51

3.2 Описание уровня приложений программного комплекса..................56

3.3 Описание уровня представлений.............................................................62

3.4 Выводы..........................................................................................................68

ГЛАВА 4 ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ.................................70

4.1 Вычислительный эксперимент для базы знаний GALEN..................70

4.2Вычислительный эксперимент на данных DL 98.................................72

4.3Вычислительный эксперимент на данных ORE 2013..........................79

4.4 Выводы..........................................................................................................99

ЗАКЛЮЧЕНИЕ...............................................................................................100

СПИСОК ЛИТЕРАТУРЫ.............................................................................102

ПРИЛОЖЕНИЕА............................................................................................115

Введение

Актуальность темы исследования. Исследования в области разработки методов определения согласованности баз знаний обусловлены необходимостью решения таких практически значимых задач как семантический поиск, классификация понятий предметной области или поддержка принятия решений в экспертных системах. Для решения задач такого рода успешно применяются методы, основанные на автоматах (D. Calvanese, KRDB Research Center в Университете г. Бозен-Больцано; T. Either, Институт информационных систем университета г. Вена), методы, основанные на правилах вывода (Е. Kazakov, Вычислительная лаборатория Оксфордского университета), метод резолюций (В. Motik, университет г. Манчестер) и табличные методы (I. Horrocks, университет г. Манчестер). Основная проблема таких методов заключается в том, что все они имеют экспоненциальную вычислительную сложность, поэтому их применение в задачах реального времени весьма затруднительно для больших баз знаний (более 5000 аксиом).

Для того, чтобы снизить время работы представленных методов на практике, учеными предпринимается огромное количество попыток разработки новых алгоритмов. Такие разработки ежегодно представляются на международных конференциях по применению логических формализмов в искусственном интеллекте «Description Logic Workshop» и «International Joint Conférence On Automated Reasoning». Наиболее значимыми разработками, представленными на данных форумах, являются: алгоритм кэширования (Y. Ding, V. Haarslev), backJumpïng-алгоритм (I. Horrocks), алгоритм глобального кэширования (L. A. Nguyen), которые, зачастую, основываются на методах теории множеств и методах логики первого порядка, кроме того ни одна из этих разработок не направлена на снижение теоретической оценки вычислительной сложности.

Целью исследования является разработка алгоритмов проверки

согласованности баз знаний, сокращающих вычислительную сложность

табличных методов на определенных классах баз знаний.

Для достижения поставленной цели необходимо решить задачи:

1. Построение сетевой модели базы знаний, описанной выражениями дескрипционной логики.

2. Разработка метода нахождения максимального потока минимальной стоимости в разработанной сетевой модели базы знаний.

3. Реализация программного комплекса для поддержки деятельности инженера по знаниям, реализующего разработанные методы и алгоритмы.

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

Научная новизна исследования. Научная новизна исследования

заключается в следующем:

1. Разработана и обоснована сетевая модель базы знаний, представленной аксиомами предметной области, что дает возможность использовать математические методы и алгоритмы, применяемые в теории графов;

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

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

4. Модифицирован алгоритм нахождения автоморфизмов в деревьях (J. Edmonds) для поиска изоморфных концептов базы знаний.

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

Методология и методы исследования. При исследовании применялись методы теории множеств, теории графов, теории методов оптимизации.

На защиту выносятся следующие результаты соответствующие трем пунктам паспорта специальности 05.13.18 - Математическое моделирование, численные методы и комплексы программ по физико-математическим наукам:

Пункт 1. Разработка новых математических методов моделирования объектов и явлений.

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

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

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

3. Предложен новый численный метод нахождения максимального потока минимальной стоимости в разработанных сетевых моделях баз знаний. Вычислительная сложность разработанного алгоритма составила 0(V2).

Пункт 4. Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента.

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

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

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

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

Апробация результатов. Основные результаты исследования докладывались на:

• II международной конференции «OWL Reasoner Evaluation Workshop (ORE 2013)» (Германия, Ульм, 22 июля 2013);

• Международной научно-практической конференции «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании'2012» (Украина, Одесса, 18-27 декабря 2012);

• XIV международной научно-практической конференции «Современные проблемы гуманитарных и естественных наук» (Москва, 26-27 марта 2013

г.);

• Научно-технической конференции «Современные проблемы математического и информационного моделирования. Перспективы разработки и внедрения инновационных 1Т-решений» (Тюмень, 13-15 апреля 2012 г.)

Глава 1 Методы определения согласованности баз знаний

1.1 Математические инструменты представления знаний

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

1.1.1 Подходы, основанные на теории графов

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

Семантические сети являются наиболее популярным формализмом представления знаний, в связи с тем, что они хорошо понимаются и просты в применении. Семантические сети получили широкое распространение в проблемах представления и обработки текстов на естественных языках [1]. Кроме того, семантические сети являются математической основой языка RDF [2], разработанного консорциумом W3C, специально для решения задач семантической паутины. Однако, данный подход обладает рядом недостатков, среди которых стоит выделить тот, что в семантических сетях не существует различий между классами и конкретными объектами классов, это влечет за собой возникновение неоднозначности при описании знаний, например, отношение "является" может означать как принадлежность конкретного индивида некоторому классу, так и то, что некоторый класс является подмножеством другого класса.

Среди алгоритмов вывода знаний в семантических сетях наиболее популярными являются два подхода: структурные методы [3] (методы

определения сходства подграфов), и методы вероятностно-алгебраического моделирования [4].

Наиболее известным примером использования семантических сетей является база знаний А^огс^е! [5], которая была разработана в лаборатории когнитивной науки университета города Принстон. '^гсШе! содержит существительные, прилагательные и глаголы, объединенные в классы синонимии и связанные отношениями между собой. Д\^огс1Ме1 не предоставляет каких-либо инструментов логического вывода или логического анализа и используется лишь как тезаурус, однако, успешно применяется в обработке естественного языка [6].

Ещё одной современной и успешной разработкой основанной на семантических сетях является система МиШ№1;, предоставляющая инструменты, включающие:

• семантический интерпретатор, который автоматически переводит тексты на

естественном немецком языке в сети МиШ№1:;

• браузер;

• синтаксический анализатор для управления структурами [5].

Недостатками подхода семантических сетей является то, что они не всегда способны определить неявно заданные знания из-за применения вероятностного подхода, кроме того, алгоритмы, реализующие структурные методы, являются КЕХРТ1МЕ (то есть имеют экспоненциальную вычислительную сложность), что не позволяет применять их для исследования моделей больших размеров.

Идея формализма фреймов заключается в использовании некоторого алгоритма (фреймворка), называемого фреймом [7], при появлении стереотипных ситуаций, при этом некоторые атрибуты фрейма меняются исходя из поставленной проблемы. Во фреймовой структуре, так же как и в семантической сети, используются понятия-вершины и отношения-ребра; отличие заключаются в том, что вместо вершин, понятия представляются особыми структурами -

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

Практическое применение язык фреймов получил в системе KL-ONE [7], которая является системой представления знаний в искусственном интеллекте и успешно применялась в двух направлениях: как система для интеллектуального представления информации и в качестве модуля понимания естественных языков.

Ещё одной системой, основанной на языке фреймов, является Knowledge Machine [8]. Рассматриваемая система, наряду с системой KL-ONE, является реализацией собственного языка описания знаний, являющегося одним из потомков языка фреймов, при этом Knowledge Machine не привязана к какой-либо конкретной прикладной задаче, но способна осуществлять выполнение задач классификации и вывода новых знаний, на основе алгоритма проверки выполнимости концептов.

Хотя фреймовая система и представлена как независимый формализм описания знаний, при детальном изучении было установлено, что она является всего лишь вариантом синтаксиса фрагмента логики первого порядка, который представлен лишь операциями конъюнкции и квантором существования без предоставления таких операций как дизъюнкция и квантор всеобщности [5]. Тот факт, что системы, основанные на фреймах, не разрабатываются с начала 2000х годов, говорит о том, что рассматриваемый формализм представления знаний не имеет перспектив для продолжения исследований.

1.1.2 Подходы, основанные на формальной логике

Среди формализмов, основанных на логике, прежде всего, стоит отметить такие методы как логика первого порядка, модальная логика, темпоральная логика, логические программы, хорновские логики (язык пролог) и дескрипционная логика, которая является математической основой языка OWL [911], являющегося стандартом для описания онтологий семантической паутины.

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

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

1.1.2.1 Логика первого порядка

Логика первого порядка (или логика предикатов) позволяет описывать любые знания с помощью переменных, предикатов, функций и констант, позволяя задавать взаимосвязи между любым количеством объектов или классов [12-15]. Данная формальная система является мощнейшим инструментом определения любых логических выражений, все остальные, рассматриваемые в данном параграфе формализмы, являются фрагментами логики первого порядка (за исключением модальной и темпоральной л