Математические методы и алгоритмы определения согласованности баз знаний

• Автор: Григорьев, Андрей Викторович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Тюмень
• Количество страниц: 115 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

1.3 Выводы
ГЛАВА 2 МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ
2.1 Сетевая модель классов предметной области
2.2 Разработка метода решения задачи о максимальном потоке минимальной стоимости для разработанной сетевой модели
2.3 Использование изоморфизма концептов для проверки согласованности баз знаний
2.4 Выводы
ГЛАВА 3 ПРОГРАММНЫЙ КОМПЛЕКС ПОДДЕРЖКИ ДЕЯТЕЛЬНОСТИ ИНЖЕНЕРА ПО ЗНАНИЯМ

3.1 Описание архитектуры программного комплекса
3.2 Описание уровня приложений программного комплекса
3.3 Описание уровня представлений
3.4 Выводы
ГЛАВА 4 ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ
4.1 Вычислительный эксперимент для базы знаний GALEN
4.2Вычислительный эксперимент на данных DL
4.3Вычислительный эксперимент на данных ORE 2
4.4 Выводы
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕА

Введение
Актуальность темы исследования. Исследования в области разработки методов определения согласованности баз знаний обусловлены необходимостью решения таких практически значимых задач как семантический поиск, классификация понятий предметной области или поддержка принятия решений в экспертных системах. Для решения задач такого рода успешно применяются методы, основанные на автоматах (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), backJumping-алгоритм (I. Horrocks), алгоритм глобального кэширования (L. A. Nguyen), которые, зачастую, основываются на методах теории множеств и методах логики первого порядка, кроме того ни одна из этих разработок не направлена на снижение теоретической оценки вычислительной сложности.

И весом 0, ребер РЕ(Сі,0>у) С пропускной способностью Рс(Сі,0>у) Оу):
и ■■■ и £дг, 01 и ... и Ом)
= К’> и Ыс,.Ц)и
І=.М,)=1..М
РЕ(сг и ... и Сдг, и ... и ом)
={6.«}
и и С(Рг(С„Й/)и(17^,г5'0)
і=1..ЛГ,;=1..М і і ,,С,Ол
и (Уіі ,ък ))
Рс(Сі и ...и С*,О, и ...и£>м)
-{(«(С*. О) - 1) и (« »§"))- 2)
и (= 05° О) = і) и и ад. О;)}
і=1..ЛГ,;'=і..м
1-і ■■■ 1-1 СдП и ■■■ 1-1 £>м)
= {(ш((5,г£о)) = 0)
и (и/ ((^^5°)) = °)
и (и/ (0#%£°)) = о) и У Р^ВД
£=1..ЛГ,;'=1..М
И весом

(16) (17)
Соответствующее графическое изображение такого графа представлено на рисунке 4.