Логический вывод и обработка знаний в информационных средах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

г-

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

Липовченко Владимир Андреевич

ЛОГИЧЕСКИЙ ВЫВОД И ОБРАБОТКА ЗНАНИЙ В ИНФОРМАЦИОННЫХ СРЕДАХ

01 01 09 - Дискретная математика и математическая кибернетика

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

ииз161575

Иркутск - 2007

003161575

Работа выполнена в Иркутском государственном университете

Научный руководитель доктор физико-математических наук,

профессор Манцивода Андрей Валерьевич

Официальные оппоненты доктор физико-математических наук,

профессор Перязев Николай Алексеевич

кандидат технических наук,

доцент Черкашин Евгений Александрович

Ведущая организация Институт математики

им С Л Соболева СО РАН

Защита состоится 9 ноября 2007 г в 13 00 на заседании диссертационного совета Д 212 074 01 при Иркутском государственном университете по адресу 664003, г Иркутск, ул К Маркса, 1, ИМЭИ ИГУ Институт математики, экономики и информатики

С диссертацией можно ознакомиться в библиотеке Иркутского государственного университета (г Иркутск, бульвар Гагарина, 24)

Автореферат разослан 9 октября 2007 г

Ученый секретарь диссертационного совета

кандфиз-мат наук л Аргучинцева М А

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

Актуальность проблемы В настоящее время ведется большое количество исследований, связанных с представлением и обработкой знаний, основную потребность в которых диктует развитие глобальной информационной среды Интернет С развитием Интернета стало очевидно, что данная распределенная среда является мощным независимо-наполняемым банком знаний человечества Проблемой сегодняшнего Интернета является неэффективная система поиска и обработки информации, которая функционирует на основе контекстного поиска данных В сегодняшнем Интернете компьютер играет роль хранителя и передатчика информации, который предоставляет лишь достаточно примитивные средства поиска, оставляя интеллектуальную, системную и классификационную работу пользователю-человеку При том объеме данных, которые сегодня накопились в мировой информационной среде, эта проблема становится ключевой Для ее решения во главе с создателем мировой информационной паутины Т Бернерсом Ли развивается концепция Интернета нового поколения — Semantic Web, где представление знаний должно реализоваться на основе логического формализма На роль такого рода формализмов выбраны дескриптивные логики, обеспечивающие компромисс между выразительностью и эффективностью работы Это означает, что с теоретической точки зрения дескриптивные логики являются весьма простыми формализмами, поскольку они должны успешно работать в распределенной среде в реальном времени Поэтому на них нельзя возлагать задачи сложного манипулирования системами знаний, например, реализацию таких метазадач, как развитие баз знаний, взаимодействие с внешним миром и тд Для таких внешних задач нужны иные формализмы Ряд ведущих специалистов в области представления и обработки знаний (Я Хоррокс, А Сатлер, А Леви, X Боли и другие) в качестве основного претендента на эту роль рассматривают логическое программирование С появлением еще одного формализма возникает и проблема взаимодействия «базового» формализма дескриптивных логик и «внешнего» формализма логического программирования Поэтому задача создания действительно эффективного механизма представления и обработки знаний, в основе которого лежит интеграция данных подходов, является актуальной

Еще одной актуальной задачей является развитие систем выводов для дескриптивных логик В настоящее время для этой

цели используются табличные алгоритмы (М Шмидт-Шауб, Г Смолка, 1991 г), имеющие переборную природу, что приводит к неэффективности в случае больших баз знаний (например, больших онтологий в области медицины или биологии), хотя здесь имеется ряд существенных достижений (Хоррокс, 1998, Харслев и Меллер, 1999) Весьма интересным представляется подход, связанный с использованием большого опыта, накопленного в сфере автоматического доказательства теорем, в первую очередь, резолюционного типа Ряд вычислительных экспериментов показывает, что даже универсальные системы автоматического доказательства резолюционного типа, в частности, система Vampire, разработанная А Воронковым, демонстрируют результаты, близкие узкоспециализированным решателям, основанным на табличных алгоритмах (Царьков и др , 2004) Поэтому разработка специализированных систем вывода, основанных на принципе резолюций, также имеет значительный потенциал

Цели и задачи исследования. Диссертационная работа посвящена разработке логических основ работы со знаниями в распределенных информационных средах на основе интеграции дескриптивных логик и системы логического программирования

Цель работы — создание интегрального логического формализма, реализующего эффективные механизмы представления и обработки знаний В работе развивается формализм, который в качестве ядра содержит способ представления знаний, семантически подобный дескриптивной логике ALC, использует логический вывод резолюционного типа, и который обладает ключевыми свойствами корректности и полноты Данный формализм объединяет преимущества дескриптивной логики и логического программирования С практической точки зрения формализм ориентирован на использование в различных Web-сервисах, имеющих отношение к обработке знаний в контексте развития Интернета нового поколения — Semantic Web

Для достижения этой цели решались задачи

• Разработка способа представления знаний на основе дескриптивных термов

• Разработка системы вывода дескриптивных термов на основе метода резолюций

• Обоснование корректности и полноты системы вывода

• Исследование свойств разработанного исчисления

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

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

Научная новизна. В диссертационной работе рассмотрен новый подход к объединению средств логического программирования и дескриптивной логики, основной идеей которого является разделение этих двух уровней за счет перевода дескриптивного формализма на уровень термов Данный интеграционный подход базируется на исчислении именующих ограничений, разработка которого выполнена в работе В этом обобщении дескриптивной логики заключается основное отличие от других гибридных подходов к обработке знаний (напр , Б Грософ и др , 2003, X Боли и др , 2004, А Леви, 1998, Р Фольтц, 2003 и др ) Основными элементами исчисления именующих ограничений являются дескриптивные термы Понятие дескриптивного терма вводится впервые, оно основано на идеях, заложенных в теории информационных ресурсов (А В Манцивода, А А Малых, 2005) и семантическом программировании (Ю Л Ершов, С С Гончаров , 1986)

В работе впервые вводится резолюционная система вывода для дескриптивных логик и термов

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

1 Исчисление именующих ограничений техника представления знаний на основе дескриптивных термов и резолюционная система вывода

2 Доказательство полноты и корректности системы вывода исчисления именующих ограничений

3 Построение модели языка, реализующего комбинированный подход к обработке знаний

4 Теоретическое обоснование обобщенного подхода к логическому программированию

Научная и практическая значимость работы

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

Из-за бурного и неконтролируемого наполнения информационными ресурсами глобальная информационная среда постепенно превращается в собрание разрозненной и неупорядоченной информации, а контекстный поиск информации часто не позволяет получить доступ к действительно нужным данным

Поэтому проблемы представления и обработки знаний находятся в фокусе внимания многих исследовательских групп, в частности, консорциума \¥ЗС На данный момент устоявшихся технологий нет

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

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

Также является востребованной разработка новых систем вывода для дескриптивных логик, тк табличные алгоритмы являются недостаточно эффективными в больших предметных областях Система вывода, которая разработана г, рамках работы, позволяет внедрить в дескриптивные

логики резолюционную систему вывода, обладающую свойством полноты Принцип резолюции хорошо изучен, и существует целый спектр разнообразных стратегий и оптимизаций, которые могут быть использованы и в дескриптивном случае

Личный вклад автора состоит 1) в совместной с научным руководителем разработке исчисления именующих ограничений, 2) в самостоятельном обосновании полноты и корректности исчисления именующих ограничений, 3) в совместной с научным руководителем разработке модели языка, реализующего комбинированный подход к обработке знаний, 4) в самостоятельной разработке обобщенного подхода к логическому программированию с выполнением обоснования корректности

Апробация работы. Основные результаты работы представлялись на Международной конференции по логическому программированию (Сиэтл, США, 2006), Всероссийской научно-практической конференции «Телематика» (Санкт-Петербург, 2006), VII школе-семинаре «Математическое моделирование и информационные технологии» (Иркутск, 2005), Молодежной научно-практической конференции в рамках недели информационных технологий в г Иркутске (Иркутск, 2006), семинарах кафедры информационных систем Иркутского государственного университета (2003 -2007гг)

Публикации По теме диссертации опубликовано 6 работ Основное содержание диссертационной работы опубликовано в работал; [1-6] В число указанных работ входят 1 статья [1] из "Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2001-2006 гг", 1 статья в зарубежном издании [2], 1 статья в рецензируемом журнале [3], 3 полных текстов докладов [4-6] в материалах международных и всероссийских конференций Публикации [1,5] выполнены в нераздельном соавторстве с научным руководителем проф А В Манциводой Из совместных публикаций [2,3] в диссертационную работу включены результаты, полученные лично соискателем и не затрагивающие права других соавторов

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

Основное содержание работы

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

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

В параграфе 12 вводятся основы построения семейства дескриптивных языков базовая логика AL и структура ее расширения Вводится понятие базы знаний в дескриптивных логиках, которая состоит из двух компонентов блока терминологии и блока утверждений

В параграфе 13 рассматривается структура терминологических описаний в базе знаний

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

В параграфе 1 4 рассматривается структура утверждающих описаний в базе знаний

Блоком утверждений называется конечное множество утверждений концептов вида С(а) и утверждения ролей вида R(a, b), где С - описание концепта, R - роль и а, Ъ - индивидуальные имена

В параграфе 1 5 рассматривается известная система вывода для дескриптивных логик, которая называется табличным алгоритмом Данная система вывода обладает свойством полноты В диссертационной работе это свойство табличного алгоритма используется в обосновании полноты исчисления NCC

Во второй главе описывается основной результат диссертационной работы — исчисление именующих ограничений (NCC — Naming Constraints Calculus), являющееся специализацией резолюционного подхода

В параграфе 2 1 описывается общая схема подхода, основой которого является понятие дескриптивного терма

Пусть А — домен знаний (предметная область) Введем специальный тип термов - дескриптивные термы Дескриптивный

терм t интерпретируется как множество объектов <1 <= А, которые он описывает, что означает (' С Д или, более точно, £7 = {(= й, й е Д} Здесь / — интерпретация, £ = й обозначает, что й описывается термом £ Так как данные в термах могут быть неполными, то полезно иметь возможность сравнивать, а также уточнять информацию объединением термов Для этого на множестве дескриптивных термов вводятся операции аппроксимации и амальгамы, соответственно

Именующее ограничение имеет вид г<1 где гс1 - имя

(идентификатор) объекта в Д и I - описание Именующее ограничение означает, что объект <1 из Д с именем гс1 описывается дескриптивным термом £

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

В параграфе 2 2 формально определяется язык дескриптивных термов, вводится понятие именующего ограничения и аксиомы

Пусть К = (Мх, - модель типов данных, где М, - виды

(типы данных) и - сигнатура Пусть все элементы 3? различны, и для каждого элемента модели введем отдельную константу Множество всех таких констант обозначим через М = М\ и и М^

Язык дескриптивных термов имеет следующие основные составляющие

1 Множество констант М,

2 Множество имен типов 5 = {вх, модели 5? ,

3 «Верхняя» и «нижняя» константы Т, ± ,

4 Счетное множество уникальных имен Ю = {гй\,гй2, } ,

5 Счетное множество временных имен ИХ = {¿х\, <1x2, }■!

6 Множество имен атрибутов (ролей) АЫг = {рг,р2, ,

7 Множество атомарных концептов (имен классов) и отрицаний концептов СИ = {сь с2, , ст, ~ си ~ с2, , ~ ст}

Обозначим IX = Ю и БХ и будем использовать гх (возможно с индексами) для обозначения имен из IX

Далее определяется множество дескриптивных термов

Определение 2 2.1 1 Если £ е С N и IX и {Т, ±} , тогда £ есть атомарный дескриптивный терм

2 Если р £ АНг иг 6 Ми IX и 5 и Т^ , тогда р г и р * г есть атомарные дескриптивные термы

3 Если < 1, ¿25 , ¿п являются атомарными дескриптивными термами, тогда (¿1, ¿2, п) есть дескриптивный терм Если п = 0, тогда ¿2, , ¿п) = -I-

^ .Бели ¿1, ¿2, являются дескриптивными термами, тогда

(¿1,^2, , ¿п) есть дескриптивный терм Если п = О, тогда

(¿1,^2, ,£п) = Т

Дескриптивные термы обладают свойствами ассоциативности и коммутативности Заметим, что, по определению, термы не могут иметь вид («1, £2), ¿з

Далее определяется семантика дескриптивных термов — аналогично семантике концептов в дескриптивных логиках

Пусть .¿„еТя, я» е 5, т€М, р € АИг

и га; € IX Покажем семантику дескриптивных термов ()г с помощью табл 1

Таблица 1

_Семантика дескриптивных термов_

Термы Интерпретация термов

с с1 С A

~ с Д\с<

)tn fjn .ГК.

¿1, , tn «iu Uf„

st < = мг

v t {x\ x € A,3y e t1 (x,y)epJ}

p*t {x\xeA,4yeA (x,y) ep1 ->y et1}

P St {x\ x e A,3y € Mt (x,y)ep1}

p* s, {x\xeA,Vy (x,y) epJ -*ye M,}

p m {x\ x e A, (x, m) Gp1}

p*m {x| x e A,Vy (x,у) € P1 -* у = m}

гх гх1 € A

T T1 — A

-L ±J = 0

Далее вводятся понятия именующего ограничения и аксиомы

Определение 2 2 2 Именующил1 ограничением называется выражение вида гх где гх е IX и £ £

и

Определение 2.2 3 Аксиомой будем называть дескриптивный терм I такой, что для любой интерпретации I выполняется Ь1 = А

На следующем этапе вводятся понятия ключевых операций, действующих на дескриптивных термах, — аппроксимации и амальгамы

Определение 2.2.4 Аппроксимация обозначается символом и определяется следующим образом

1 / » /, для любого / е СДГ и IX,

2 р / р д и р* / » р* д, если выполняется одно из условий

(a) /,9€Ми5 и! = д,

(b) д = йг £ 5 и / 6 М„

(c) /,д еТши/^д,

3 и, ,¿„»¿1, еслиУг е {1 т},3^е{1 п} ^ »

4 ¿1, , г„ » , ?т, если V; е {1 п}, Эг е {1 т} . ^ »

5 Т » Ь для любого Ь 6 Т^,

6 4 Л. Лгя любого £ € Тдг,

7 если гх ¿1 € С5 и » I,

8 Если при проверке выполнения аппроксимации гх I, в некотором направлении возникнет необходимость повторно проверитьгх

то проверку в данном направлении останавливаем

Последние два пункта в определении касаются выполнения аппроксимации относительно контекста и снабжены дополнительными пояснениями

Определение 2.2 5 Амальгама дескриптивных термов ¿1 и ¿2 обозначается П ¿2, и ее результат — дескриптивный терм

Приводится утверждение, которое подтверждает, что определение операции амальгамы корректно относительно аппроксимации

Утверждение 2.2.3 Амальгама ¿1 П ¿2 является наименьшей верхней гранью и ¿2 относительно частичного порядка <<Э>»

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

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

посылки

логическое следствие В правилах используются следующие обозначения с, ~ с € СЛГ, € Тя, р е АНг, йх € ПХ, гх,гх\,гх2 € IX, ге^г^г 6

Ю, Ахгот(£) - условие, что Ь является аксиомой Логическое следствие является результатом применения правила

1 Правило (Res)

2 Правило (Any)

3 Правило (Ах)

4 Правило (Ama)

5 Правило (Ех)

6 Правило (Subst)

7 Правило (False)

8 Правило (Perm)

гх {с, ti), c,t2),t гх ti, ¿2

гх (р t,ti),(j>*t',t2),h

гх р (t,t'),ti,t2

Axwm(ti, ,tk) гх ti, , tk

гх ti гх • Í2 гх ti, ¿2

гх (p Ml), ¿2 гх (p dx,ti),t2 dx t

гх\ _L гх2 t[ix i] ixi. t[±]

гх t

гх _L

, г/ t » -L

гхi гх2 ,t гх г ixi,t

Словарь, состоящий из именующих ограничений, и система вывода, базирующаяся на приведенных правилах, называются исчислением именующих ограничений или NCC (Naming Constraints Calculus)

Далее показывается, что основные правила вывода Res и Any являются специализированными вариантами принципа резолюций В процесс вывода аксиомы вводятся с помощью правила Ах Данное правило может быть применимо для любого гх G А и любой аксиомы, определенной над Д Правило Ama применяется к паре именующих ограничений гх ti и гх í2 и позволяет объединять в одном именующем ограничении информацию о некотором объекте гх, заданную в конечном множестве именующих ограничений Основным назначением данного правила является формирование именующих ограничений, к которым на следующем шаге применяются правила Res или Any Правило Ех применяется для вынесения значения атрибутов на внешний уровень с целью выполнения дальнейших манипуляций с ними Правило Subst обрабатывает ситуацию, когда некоторый объект гх\ не существует Тогда вхождения этого объекта в других ограничениях могут быть заменены на -L Правило False обрабатывает противоречие в дескриптивных термах Правило Perm позволяет выполнять обработку синонимов

Данные правила являются базовыми, в практических задачах иногда удобнее использовать определенные комбинации и упрощения правил Например, удобно использовать упрощение правила Ех

гх (р (ixi,t),ti),t2 гх (р ixi,ti),t2 гх i t

Далее дается ряд определении и утверждений, на которых базируется процедура вывода

Определение 2.3.1 Множеством ограничений СS называется конечное множество именующих ограничений и аксиом

В нашей системе множества ограничений играют роль баз знаний

Определение 2.3.2 I - есть интерпретация множества ограничений CS в предметной области Д, если для любой аксиомы t выполняется t1 = Д и для любого именующего ограничения ix t £ CS выполняется ix1 е t1

Определение 2.3.3 Множество ограничений СS непротиворечиво, если существует интерпретация CS, и противоречиво в обратном случае

Определение 2.3.4 NCC-последовательностью называется последовательность мноснсеств ограничении С Si, , CSn таких, что С Si - исходное множество ограничений и CSt+\ = CSt U С, где С получено из элементов CSt применением некоторого NCC-правила

Определение 2.3.5 Будем говорить, что именующее ограничение гх t выводимо из множества ограничений CS\ и обозначать CS\ Ь гх t, если существует NCC-последователъность CS\, ,CSn такая, что гх t е CSn

Определение 2.3.6 Имя гх & IX является начальным в NCC-последовательности CSi, ,CSn, если гх t 6 CS\ для некоторого t

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

Теорема 2.3.1 Множество ограничений CS противоречиво тогда, и только тогда, когда CS b гх ± для некоторого начального гх

Далее рассматривается аспект терминальности системы вывода вводятся условия на применение правил вывода для формирования конечной NCC-последовательности

В параграфе 2 4 показано, что для любого дескриптивного терма существует эквивалентный концепт дескриптивной логики (DL-концепт) и наоборот

В параграфе 2 5 выполняется обоснование корректности правил вывода и доказывается полнота исчисления NCC

Обоснование корректности основных правил вывода выполняется с помощью метода резолюций

Обоснование полноты выполняется путем универсальной перестройки вывода, выполненного с помощью табличного алгоритма (ТА), в вывод исчисления именующих ограничений Известно, что ТА обладает свойством полноты Заметим, что возможность сведения к ТА не означает, что всегда осуществимо прямое алгоритмичное транслирование правил вывода NCC в последовательности правил вывода ТА, те вывод NCC не является частным случаем ТА Системы выводов имеют различные структуры, совпадение наблюдается только в переходах между индивидуальными именами в структурах выводов

Свойство полноты системы вывода NCC подтверждает следующая теорема

Теорема 2.5 2 Пусть дано множество ограничений CS\ NCC-последователъностъ CS\, ,CSn такая, что гх ± G CSn для некоторого начального гх, существует тогда и только тогда, когда существует вывод противоречивости для DL{CS\) способом ТА

Для доказательства теоремы определяется понятие канонического вида для вывода, выполненного с помощью табличного алгоритма, доказывается ряд лемм

Лемма 2 Ъ \ К каноническому виду можно свести любой, выполненный с помощью табличного алгоритма, вывод

Лемма 2.5.2 Структуру вывода канонического вида можно разделить на конечное число блоков (срезов) по индивидуальным именами

Далее доказывается лемма, в которой устанавливаются связи между срезами и соответствующими блоками в NCC На основе данной леммы выполняется доказательство теоремы

В параграфе 2 6 выполняется расширение исчисления именующих ограничений Расширение дескриптивной логики необходимо для построения обобщенного подхода к логическому программированию

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

На практике, дескриптивная логика ALCN хотя и является достаточно выразительной, в задачах повышенной сложности является неэффективной, тк может приводить к большому перебору

Для построения обобщенного подхода к логическому программированию необходимо расширение NCC только конструкцией р < 1, имеющей следующую семантику

(Р < I)7 = {а е Д'НМа, Ь)€/}|<1}

В параграфе 2 7 показано, как резолюционная система вывода исчисления NCC может быть перенесена в дескриптивную логику ALC

Для этого необходимо ввести в дескриптивную логику понятие аппроксимации и амальгамы, сформировать соответствующие правила вывода для обработки DL-концептов

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

В параграфе 3 1 выполняется построение концептуальной модели языка, в котором реализована комбинация методов дескриптивной логики и логического программирования Данный комбинированный язык базируется на парадигме программирования в ограничениях и обозначается CLP(K) (Constraint Logic Programming for Knowledge Domains) На основе языка приводятся примеры, иллюстрирующие аспекты взаимодействия различных логических стилей и работу резолюционной системы вывода Некоторые выдержки из примеров relatives -

axiom({~grandparent, hasChild.parent}), axiom({grandparent; hasChild*~parent>), axiom({~ancient, parent; hasChild ancient», axiom({~parent; ancient}), axiom({ancient, hasChild*~ancient})

grandparent({hasChild hasChild Z},Z) ancient({hasChild Z},Z) ancient({hasChild Y},Z) - ancient(Y,Z) В параграфе 3 2 рассматриваются дескриптивные термы как обобщение эрбрановых термов классического логического программирования

Обобщение эрбрановых термов до дескриптивных осуществляется на основе следующих положений, позволяющих интерпретировать эрбрановы термы как единицы описания знаний

• Эрбрановы термы могут содержать частичную и неполную информацию — за счет существования свободных переменных

• Во время вычисления количество информации в термах становится больше, и она становится более точной — за счет подстановок термов вместо переменных

• Если даны два терма эрбранова универсума t\ и í2, то можно сравнивать и объединять информацию, содержащуюся в них Пусть MGU(t\ ¿2) — наиболее общий унификатор термов t\ и £2, тогда

¿2 » ¿1, если ¿2 = ьмсиц 1,г2),

г = ¿х п ¿з, если 4 = г1мви{и,г2) = 12ма1(ььг2)

Далее вводится правило преобразования эрбрановых термов к дескриптивному виду

Пусть /Щг) — дескриптивное представление эрбранова терма

тогда

1 если 4 - константа в виде атома вида /(), то ЮТ^) = /, где / е СДГ,

2 если í - константа отличная от атома, то 1)Т(£) = где { £ М,

3 если I - переменная, то ОТ({) = ¿хг, где с1хг € ОХ,

4 если некоторый терм вида/(¿1, где /- функтор, -произвольные термы, то БТ(Ь) =/, агд\ БТ^), ,агдп ОТ(1п), где / € (Ж, аг^, , аг<7п € Лйг

В параграфе 3 3 рассматривается операция амальгамы дескриптивных термов с дополнительными ограничениями (называется ЬР-амальгамой и обозначается «ГТ») как обобщенный механизм унификации

В параграфе 3 4 приводится обоснование корректности обобщенного подхода к логическому программированию Корректность обобщенного подхода подтверждают следующие теорема и утверждение

Теорема 3.4.1

Если термы р\ и р2 унифицируемы, тогда выполняется ОТ{р{) ГТ ОТ(р2) ^ БТ{р\и) = ВТ{р2а), где а - наиболее общий унификатор для термов р\ и р2

Утверждение 3.4 1 Для дескриптивных термов БТ{р\) и БТ(р2) операция ЬР-амалъгамы выполняется тогда, и только тогда, когда термы рг и р2 унифицируемы

Данная теорема позволяет интерпретировать дескриптивные термы как обобщение эрбрановых термов, а амальгаму как обобщение унификации

4. Заключение

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

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

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

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

Публикации по теме диссертации

1 Манцивода А В, Липовченко В А Применение логического программирования к обработке знаний // Вестник Бурятского университета Серия 13 Математика и информатика - Улан-Удэ Изд-во Бурят ун-та, 2006 - Вып 2, - С 50-57

2 Mantsivoda А , Lipovchenko V , Malykh A Logic Programming in Knowledge Domains // Lecture Notes in Computer Science - Berlin Springer, 2006 - P. 451-452

3 Mantsivoda A, Lipovchenko V, Malykh A Logic Programming in Knowledge Domains (Full version) // Известия ИГУ Серия математика Т1 - Иркутск Издательство Иркутского ун-та, 2007

- С 188-204

4 Липовченко В А Обобщенный подход к логическому программированию // Материалы VII школы-семинара «Мат моделирование и информационные технологии» - Иркутск Изд-во ИДСТУ СО РАН, 2005 - С 20-21

5 Липовченко В А, Манцивода А В Комбинированный подход к обработке знаний // Труды всероссийской конф «Телематика-2006»

- С -Пб , 2006. - С 59-61

6 Липовченко В А Полнота исчисления именующих ограничений // Материалы Молодежной научно-практической конференции «Информационные технологии» - Иркутск, 2006 - С 12-14

Подписано в печать 08 10 07 Формат 60x84 1/16 Печать трафаретная. Усл. печ. л 1,4 Уч-изд л 1,2 Тираж 150 экз. Заказ 81.

Издательство Иркутского государственного университета 664003, Иркутск, бульвар Гагарина, 36, тел (3952) 24-14-36

Введение

1 Дескриптивные логики и табличный алгоритм вывода

1.1 Современные подходы к обработке знаний

1.2 Структура дескриптивных языков.

1.3 Блок терминологии.

1.4 Блок утверждений.

1.5 Табличный алгоритм.

2 Исчисление именующих ограничений

2.1 Общая схема.

2.2 Основные определения.

2.3 Система логического вывода.

2.4 Корреляция с дескриптивной логикой.

2.5 Корректность и полнота исчисления.

2.6 Расширение исчисления.

2.7 Революционный вывод в дескриптивной логике.

3 Язык CLP и обобщенный подход к логическому программированию

3.1 Язык CLP(K).

3.2 Дескриптивные термы, как обобщение эрбрановых термов

3.3 Амальгама, как обобщение унификации.

3.4 Корректность обобщенного подхода.

Актуальность проблемы

В настоящее время ведется большое количество исследований, связанных с представлением и обработкой знаний, основную потребность в которых диктует развитие глобальной информационной среды Интернет. С развитием Интернета стало очевидно, что данная распределенная среда является мощным независимо-наполняемым банком знаний человечества. Проблемой сегодняшнего Интернета является неэффективная система поиска и обработки информации, которая функционирует на основе контекстного поиска данных. В сегодняшнем Интернете компьютер играет роль хранителя и передатчика информации, который предоставляет лишь достаточно примитивные средства поиска, оставляя интеллектуальную, системную и классификационную работу пользователю-человеку. При том объеме данных, которые сегодня накопились в мировой информационной среде, эта проблема становится ключевой. Для ее решения во главе с создателем мировой информационной паутины Т. Бернерсом Ли развивается концепция Интернета нового поколения — Semantic Web [19], где представление знаний должно реализоваться на основе логического формализма. На роль такого рода формализмов выбраны дескриптивные логики [17][32], обеспечивающие компромисс между выразительностью и эффективностью работы. Это означает, что с теоретической точки зрения дескриптивные логики являются весьма простыми формализмами, поскольку они должны успешно работать в распределенной среде в реальном времени. Поэтому на них нельзя возлагать задачи сложного манипулирования системами знаний, например, реализацию таких метазадач, как развитие баз знаний, взаимодействие с внешним миром и т.д. Для таких внешних задач нужны иные формализмы. Ряд ведущих специалистов в области представления и обработки знаний (Я. Хоррокс, А. Сатлер, А. Леви, X. Боли и другие) в качестве основного претендента на эту роль рассматривают логическое программирование. С появлением еще одного формализма возникает и проблема взаимодействия «базового» формализма дескриптивных логик и «внешнего» формализма логического программирования [47]. Поэтому задача создания действительно эффективного механизма представления и обработки знаний, в основе которого лежит интеграция данных подходов, является актуальной.

Еще одной актуальной задачей является развитие систем выводов для дескриптивных логик. В настоящее время для этой цели используются табличные алгоритмы [48], имеющие переборную природу, что приводит к неэффективности в случае больших баз знаний (например, больших онтологий в области медицины или биологии), хотя здесь имеется ряд существенных достижений, например — системы Fact [27] и Racer [26]. Весьма интересным представляется подход, связанный с использованием большого опыта, накопленного в сфере автоматического доказательства теорем, в первую очередь, революционного типа. Ряд вычислительных экспериментов показывает, что даже универсальные системы автоматического доказательства революционного типа, в частности, система Vampire [46], разработанная А. Воронковым, демонстрируют результаты, близкие узкоспециализированным решателям, основанным на табличных алгоритмах [49]. Поэтому разработка специализированных систем вывода, основанных на принципе резолюций, также имеет значительный потенциал.

Цели и задачи исследования

Диссертационная работа посвящена разработке логических основ работы со знаниями в распределенных информационных средах на основе интеграции дескриптивных логик и системы логического программирования.

Цель работы — создание интегрального логического формализма, реализующего эффективные механизмы представления и обработки знаний. В работе развивается формализм, который в качестве ядра содержит способ представления знаний, семантически подобный дескриптивной логике ALC, использует логический вывод резолюционного типа, и который обладает ключевыми свойствами корректности и полноты. Данный формализм объединяет преимущества дескриптивной логики и логического программирования. С практической точки зрения формализм ориентирован на использование в различных Web-сервисах, имеющих отношение к обработке знаний в контексте развития Интернета нового поколения — Semantic Web.

Для достижения этой цели решались задачи:

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

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

3. Обоснование корректности и полноты системы вывода.

4. Исследование свойств разработанного исчисления.

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

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

Научная новизна

В диссертационной работе рассмотрен новый подход [11] [39] к объединению средств логического программирования и дескриптивной логики, основной идеей которого является разделение этих двух уровней за счет перевода дескриптивного формализма на уровень термов. Данный интеграционный подход базируется на исчислении именующих ограничений, разработка которого выполнена в работе. В этом обобщении дескриптивной логики заключается основное отличие от других гибридных подходов к обработке знаний (например, языков DLP [25], Carin [35], Dat-alogDL [40], AL-log [23]). Основными элементами исчисления именующих ограничений являются дескриптивные термы. Понятие дескриптивного терма вводится впервые, оно основано па идеях, заложенных в теории информационных ресурсов [12][Т] и семантическом программировании [24[[37].

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

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

Научная и практическая значимость работы

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

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

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

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

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

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

На защиту выносятся:

1. Исчисление именующих ограничений: техника представления знаний на основе дескриптивных термов и резолюционная система вывода.

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

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

4. Теоретическое обоснование обобщенного подхода к логическому программированию.

Структура и объем диссертации

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

Заключение

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

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

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

Дальнейшее исследование и развитие резолюционной системы вывода должно выполняться в следующих направлениях:

1. Оценка сложности алгоритма вывода и сравнение его эффективности с другими системами вывода в дескриптивных логиках.

2. Исследование возможности оптимизаций системы вывода.

3. Реализация системы-решателя для дескриптивных логик на базе резолюционной системы вывода

Отметим, работа по реализации системы-решателя для онтологий выполняется на кафедре информационных систем ИГУ с целью его внедрения в систему создания и редактирования онтологий Meta-2 [8][6].

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

Будущие исследования в данных направлениях представляются достаточно обширными и дожны выполнятся с учетом наработок [51][36]. В перспективе необходимо: изучение всех возможных взаимодействий между слоями логических подходов, реализация универсальной системы вывода.

Также, интересным направлением является изучение обобщенного подхода к логическому программированию, как более гибкого метода для описания задач искусственного интеллекта и обработки научно-технических текстов [10].

1. Братко И. Программирование на языке Пролог для искусственного интеллекта. - М.: Мир, 1990. - 560с.

2. Загоруйко Н.Г., Гусев В.Д., Завергайлов А.В. и др. Система ONTOGRID для автоматизации процессов построения онтологий предметных областей // Автометрия. Новосибирск, 2005. - Том. 41, №5. - С.13-25.

3. Липовченко В.А. Обобщенный подход к логическому программированию // Материалы VII школы-семинара «Мат. моделирование и информационные технологии» Иркутск: Изд-во ИДСТУ СО РАН, 2005. - С.20-21.

4. Липовченко В.А. Полнота исчисления именующих ограничений // Материалы Молодежной научно-практической конференции «Информационные технологии». Иркутск, 2006. - С. 12-14.

5. Липовченко В.А., Манцивода А.В. Комбинированный подход к обработке знаний // Труды всероссийской конф. «Телематика-2006». С.-Пб., 2006. - С.59-61.

6. Маковецкий P.O., Малых А.А. Язык запросов к онтологической системе // Труды всероссийской конф. «Телематика'2007». С.-Пб., 2007.

7. Малых А.А. Представление знаний и семантическое программирование.: дис. на соискание ученой степени канд. ф.-м. наук: 01.01.09 // Иркутский гос. ун-т. Иркутск, 2005. - 144с.

8. Малых А.А., Манцивода А.В. МЕТА-2: Модульная система для представления знаний // Труды Всероссийской конф. «Телематика'2006». С.-Пб., 2006. - С.64-65.

9. Малых А.А., Манцивода А.В. МЕТА-2: поддержка онтологий и образовательные системы // Труды всероссийской конф. «Телематика'2005». С.-Пб., 2005. - С.232-233.

10. Манцивода А.В., Липовченко В.А. Канонический текстовый формат и математические формулы // Вычислительные системы. Математические модели и вычислительные структуры. Новосибирск, 2004. - Вып. 173. - С.8Т-98.

11. Манцивода А.В., Липовченко В.А. Применение логического программирования к обработке знаний // Вестник Бурятского университета. Серия 13. Математика и информатика. Улан-Удэ: Изд-во Бурят, ун-та, 2006. - Вып. 2. - С.50-57.

12. Манцивода А.В., Малых А.А. Представление и обработка знаний в Интернете: Информационные системы и логика. Иркутск: Издательство Иркутского ун-та, 2005. - Вып. 2. - 111с.

13. Хоггер К. Введение в логическое программирование. М.:Мир, 1988. - 348с.

14. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. - 360 с.

15. Чери С., Готлоб Г., Танка JI. Логическое программирование и базы данных. — М.: Мир, 1992. 352с.

16. Baader F., Calvanese D., McGuinness D. L., Nardi D., Patel-Schneider P. F. The Description Logic Handbook: Theory, Implementation, Applications. Cambridge, 2003. - 574p.

17. Baader F., Sattler U. Number restrictions on complex roles in description logics //In Proceedings of KR-96. 1996. -P. 328-339.

18. Berners-Lee Т., Hendler J., Lassila O. The Semantic Web // Scientific American. 2001. - №5. - P.34-43.

19. Borgida A. On the relative expressiveness of description logics and predicate logics // Artificial Intelligence. 1996. - Vol. 82. - P.353-367.

20. Brachman R. A Structural Paradigm for Representing Knowledge // BBN Report No.3605. Cambridge,1978

21. Brachman R., Schmolze J. An Overview of the KL-ONE Knowledge Representation System // Cognitive Sci. 1985. - Vol.9.

22. Donini F., Lenzerini M., Nardi D., Schaerf A. AL-log: integrating Data-log and description logics // J. of Intelligent and Cooperative Information Systems. 1998. - Vol.10. - P.227-252.

23. Goncharov S., Ershov Yu., Sviridenko D. Semantic programming // 10th World Congress Information Processing'86. Dublin, 1986. - P. 1093-1100.

24. Grosof В., Horrocks I., Volz R., Decker S. Description Logic Programs: Combining Logic Programs with Description Logics // Proc. of WWW 2003. Budapest, 2003. - P.48-57.

25. Haarslev V., Moller R. Racer: An OWL Reasoning Agent for the Semantic Web //In Proc. Products and Services of Web-based Support Systems, in conjunction with the 2003 IEEE/WIC International Conference on Web Intelligence. Canada, 2003. - P.91-95.

26. Horrocks I. Using an expressive description logic: FaCT or fiction? // Proceedings of the Sixth International Conference «Principles of Knowledge Representation and Reasoning». San Francisco:Morgan Kaufmann, 1998.- P.636-647.

27. Horrocks I., Parsia В., Patel-Schneider P., Hendler J. Semantic web architecture: Stack or two towers? // Principles and Practice of Semantic Web Reasoning. Berlin:Springer, 2005. - Lecture Notes in Computer Science.- Vol.3703. P.37-41.

28. Horrocks I., Patel-Schneider P. Reducing OWL entailment to description logic satisfiability. J. of Web Semantics, l(4):345-357, 2004.

29. Kim Marriott, Peter Stuckey. Programming with Constraints: An Introduction. MIT Press, 1998.

30. Kowalski R. The early years of logic programming // Communications of the ACM. 1988. - Vol 31. - P.38-43.

31. Krysztof R. Apt. Principles of Constraint Programming. Cambridge University Press, 2003.

32. Levy A. Rousset M. Combining horn rules and description logics in CARIN // Artificial Intelligence. 1998. - Vol.104. - P.165-209.

33. Mantsivoda A. Flang: A Functional-Logic Language // Lecture Notes in Computer Science. Berlin: Springer, 1992. - Vol. 567. - P.257-270.

34. Mantsivoda, A. Semantic Programming for Semantic Web // Invited Talk. Proceedings of the 9th International Asian Logic Conference. Novosibirsk, 2005. - P.17-21.

35. Mantsivoda A., Lipovchenko V., Malykh A. Logic Programming in Knowledge Domains // Lecture Notes in Computer Science. Berlin: Springer,2006. P.451-452.

36. Mantsivoda A., Lipovchenko V., Malykh A. Logic Programming in Knowledge Domains (Full version) // Известия ИГУ. Серия математика. T.l. Иркутск: Издательство Иркутского ун-та, 2007. - С. 188-204.

37. Mei J., Boley Н., Li J., Bhavsar V., Lin Z. DatalogDL: Datalog Rules Parameterized by Description Logics. // Canadian Semantic Web. Springer Series: Semantic Web and Beyond. Canada, 2006. - Vol. 2. - P.171-188.

38. Minsky M. A Framework for Representing Knowledge // The Psychology of Computer Vision. New York,1975. P.211-277.

39. D. Parchunov. GABEK for Ontology Generation// Zelger, Josef; Herdi-na, Philip; Oberprantacher, Andreas (Hrsg.): Lernen und Entwicklung in Organisationen, Wien: LIT-publishing Company, 2006, p. 87-107.

40. D.E.Palchunov. Lattices of relatively axiomatizable classes// S.O.Kuznetsov and S. Schmidt (Eds.), ICFCA 2007, Lecture Notes in Artificial Intelligence No. 4390, Springer-Verlag, Berlin Heidelberg,2007, pp. 221-239

41. Proc. of the First International Conference «Rules and Rule Markup Languages for the Semantic Web». Berlin:Springer, 2005.

42. Proc. of the Second International Conference «Rules and Rule Markup Languages for the Semantic Web». Berlin:Springer, 2006.

43. Riazanov A., Voronkov A. The Design and Implementation of Vampire // AI Communications. -2002. Vol.15. - P.91-110.

44. Rosati R. The limits and possibilities of combining Description Logics and Datalog // Proc. RuleML 2006. Athens, 2006.

45. Schmidt-Schauss M., Smolka G. Attributive concept descriptions with complements // Artificial Intelligence. 1991. - Vol.48. - P.l-26.

46. Tsarkov D., Riazanov A., Bechhofer S., Horrocks I. Using Vampire to reason with OWL. // Proc. of ISWC 2004. Lecture Notes in Computer Science. Berlin: Springer, 2004. - Vol.3298. - P.471-485.

47. Volz, R., Decker, S., Oberle, D. Bubo Implementing OWL in Rule-Based Systems // Proc. of WWW 2003. - Budapest, 2003.

48. Флэнг-проект: web-страница. 2002-2004. - http://teacode.com/flang.

49. OWL Web Ontology Language: Overview. http://www.w3.org/TR/2004/REC-owl-features-20040210/.

50. Protege: open source ontology editor and knowledge-base framework. -http://protege.stanford.edu/.

51. Semantic Web activity. http://www.w3.org/2001/sw/.

52. SWRL: A Semantic Web Rule Language Combining OWL and RuleML. -http://www.w3.org/Submission / SWRL/.

53. The Rule Markup Initiative. http://ruleml.org/.

54. W3C: About the World Wide Web Consortium, http: / / www.w3.org/Consortium/.