УДК 004.021
ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ЛОГІЧНОГО АНАЛІЗУ ОНТОЛОГІЙ З ТИПІЗОВАНИМИ ВИРАЗАМИ
Каплунов А. В., Лупинос А. Г.
Національно технічний університет України «Київський політехнічний інститут», Україна, Київ
Використання метаданих і онтологій дозволить здійснити машинну обробку велетенських обсягів інформації, що призведе до революції в даній області. Онтологія містить велику кількість незалежних типізованих виразів різних типів, які відносяться до різних типізованих зв`язків онтології. Для підвищення продуктивності логічного аналізу онтології запропоновано індексувати типізовані вирази вихідної онтології, щоб максимально прискорити пошук відповідних виразів.
Ключові слова: онтологія, типізовані вирази, кореневий тип данних, EL-онтологія, інтервальне дерево.
Каплунов А. В., Лупинос А. Г. Повышение эффективности логического анализа онтологий с типизированными выражениями / НТУУ “КПИ”. Украина, г. Киев
Использование метаданных и онтологий позволит осуществить машинную обработку огромных объемов информации, что произведет революцию в данной области. Онтология содержит большое количество независимых типизированных выражений различных типов, которые относятся к различным типизированным связям онтологии. Для повышения производительности логического анализа онтологии предложено индексировать типизированные выражения исходной онтологии, чтобы максимально ускорить поиск соответствующих выражений.
Ключевые слова: онтология, типизированные выражения, корневой тип данных, EL-онтология, интервальное дерево.
Kaplunov A. V., Lupynos A. H. Improving the efficiency of the logical analysis of ontologies with typed expressions / NTUU “KPI”. Ukraine, Kyiv
Using metadata and ontologies allow computer processing huge volumes of information, leading to a revolution in this field. Ontology contains a large number of independent typed expressions of different types, which belong to different typed ties of ontology. To improve performance of logical analysis was proposed to index typed expressions of original ontology to accelerate search of the most relevant expressions.
Keywords: ontology, typed expression, root data type, EL-ontology, interval tree.
Вступ
Дослідження в області подання знань в значній мірі засновані на методах опису навколишнього світу, його об'єктів і властивостей у формі, придатній для використання в інтелектуальних системах. У даному контексті під інтелектуальною системою мається на увазі система, здатна витягти неявно зазначену інформацію з множини явно заданих тверджень.
Методи представлення знань можна умовно розділити на дві категорії: в першу категорію входять методи, засновані на формальній логіці, а в другу - неформальні методи. На відміну від формальних моделей, в основі яких лежить математична теорія, неформальні методи найчастіше використовують когнітивні прийоми для представлення знань у вигляді спеціальних структур, наприклад семантичних мереж або фреймів. При цьому, незважаючи на наочність неформальних методів, відсутність чітких універсальних правил їх інтерпретації дозволяло ефективно застосовувати такі методи лише для деяких конкретних завдань. Формальні ж методи представлення знань спочатку розвивалися на основі механізмів логіки предикатів першого порядку, що зумовило їх універсальність.
Згодом бажання впровадити семантику в інтерпретацію семантичних мереж і фреймів призвело до появи нового сімейства мов подання знань - дескриптивної логіки [1] (раніше відомої як термінологічна система, а потім - логіка концептів). У цьому новому формалізмі були скомбіновані фреймові структури з фрагментами логіки першого порядку, що дозволило створити гнучку і виразну мову подання знань з добре вивченими властивостями, при цьому обчислювальна складність мови безпосередньо залежить від того, які саме фрагменти логіки першого порядку ми обираємо.
На практиці одним з найвідоміших втілень дескриптивної логіки є онтологія - формалізація деякої області знань у вигляді безлічі понять і зв`язків між ними. Онтології знайшли широке застосування в інформатиці, зокрема в задачах накопичення та обробки даних з урахуванням їх семантики, при побудові «порталів знань», моделюванні, а також в якості посередника між користувачем і інформаційною системою або іншими користувачами.
Окремо варто відзначити, що онтологіям виділена центральна роль в планах розвитку Всесвітньої павутини. Сучасні методи автоматичної обробки даних, доступних в Інтернеті, як правило, засновані на частотному і лексичному аналізі текстового вмісту, який, насамперед, призначений для сприйняття людиною. Застосування ж метаданих і онтологій дозволило б здійснювати машинну обробку цих колосальних обсягів інформації, що призвело б до революції в цій області. Консорціум Всесвітньої павутини (W3C) затвердив і активно розвиває мову опису онтологій OWL, навколо якого сьогодні сконцентрована значна частина всіх досліджень в області подання знань, онтологічного інжинерингу та практичного застосування дескриптивної логіки.
Однак надзвичайно висока обчислювальна складність алгоритмів логічного аналізу в таких системах перешкоджає масовому впровадженню онтологій та використанню інтелектуальних систем. Початок дослідженню обчислювальної складності дескриптивної логіки поклала стаття [2], в якій була порушена ця проблема, а саме розглядалася оцінка обчислювальної складності логічного аналізу та ті фактори, які на неї впливають. Виявилося, що різні комбінації дозволених конструкцій мови породжували мови опису з абсолютно різними обчислювальними властивостями. Авторами була досліджена одна з таких мов – FL-, для якої алгоритм логічного аналізу зберігав поліноміальну складність. Згодом були вивчені ще дві мови - EL [3] і EL++ [4], які зберігали розв`язок за поліноміальний час і були при цьому більш практичними.
У процесі розробки семантичної інформаційної системи Грід, в якій центральну роль відіграють онтології, виявилася неприпустимо низька продуктивність логічного аналізу над базою знань. Після розгляду різних алгоритмів і методів оптимізації був зроблений висновок, що табличний алгоритм, який лежить в основі майже всіх логічних процесорів, не може впоратися з онтологіями великого розміру, оскільки спочатку був розрахований на мови з великою експресивністю і виконує процес класифікації онтології шляхом ітеративної побудови моделі для кожної пари концептів і пошук протиріч в ній. Згідно роботі [1] таке завдання відноситься до класу NExpTime, що в комбінації з дуже великим розміром онтології в нашому випадку виключає цей підхід.
За рішенням проблеми ми звернулися до інтелектуальних систем на основі одних з найбільших онтологій на сьогоднішній день - SNOMED CT, GALEN і Gene Ontology. Щоб забезпечити прийнятну швидкість класифікації і масштабованість, згадані онтології були побудовані з застосуванням дескриптивної логіки EL++.
Розширена підтримка типізованих виразів
Згідно специфікації мови OWL 2 профіль OWL 2 EL передбачає використання 19 типів даних [5], більшість з яких визначені у рамках специфікації XSD - мови опису структури XML-документів. На рис. 1 резюмовані всі підтримувані в рамках профілю типи даних, встановлено їх спадковість і дозволені обмежувальні аспекти.
Повний текст статті за посиланням