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

• Липовченко, Владимир Андреевич
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Липовченко, Владимир Андреевич

Введение

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].

Список литературы диссертационного исследования кандидат физико-математических наук Липовченко, Владимир Андреевич, 2007 год

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/.