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

ВВЕДЕНИЕ.

ГЛАВА 1. НЕОДНОРОДНЫЕ СЕМАНТИЧЕСКИЕ СЕТИ.

1.1. Основные понятия.

1.2. Рассуждения в неоднородной семантической сети.

1.2.1. Признаки.

1.2.2. Процедуры пополнения и редукции множества гипотез.

ГЛАВА 2. ДЕСКРИПТИВНАЯ ЛОГИКА.

2.1. Основные понятия.

2.2. База знаний.

2.3. Рассуждения в дескриптивной логике.

2.4. Семейство языков дескриптивных логик, их классификация и вычислимость.

2.5. Способы отображения дескриптивной логики во фрагменты логики первого порядка.

2.6. Дескриптивная логика с конкретным доменом.

2.5.1. Правила вывода.

ГЛАВА 3. ЯЗЫК СЕМЕЙСТВА ЯЗЫКОВ ДЕСКРИПТИВНЫХ ЛОГИК HSN-ALCEN.

3.1. Синтаксис и семантика HSN-ALCEN.

3.2. Алгоритм вычисления предикатной зависимости по структуре концептов.

3.3. Правила вывода.

3.4. Алгоритмы поиска вывода.

ГЛАВА 4. ИНТЕРПРЕТАЦИЯ.

4.1. Сложность алгоритмов поиска вывода.

4.2. Вычислимость и выразительность HSN-ALCEN.

4.3. Корректность и полнота HSN-ALCEN.

4.4. Пример.

ГЛАВА 5. ПЛАНИРОВАНИЕ В HSN-ALCEN.

5.1. Функциональные отношения на событиях в неоднородной семантической сети.

5.2. Планирование в дескриптивной логике.

5.3. Функциональные символы в HSN-ALCEN.

5.4. Предикатные символы, порожденные функциями на конкретном домене.

5.5. Алгоритмы планирования в HSN-ALCEN.

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

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

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

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

Цель и задачи работы

Целью работы является исследование семейства языков дескриптивных логик. Для этой цели в диссертации решаются следующие задачи: построение расширения дескриптивных логик средствами, достаточными для описания неоднородных семантических сетей. Исследование свойств этого расширения; построение полиномиальных алгоритмов поиска вывода для задач моделирования рассуждений типа аргументации в дескриптивной логике; поиск полиномиального алгоритма планирования поведения для задачи классического AI планирования в дескриптивной логике.

Предмет исследования

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

Научная новизна работы

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

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

Реализация результатов работы

Результаты работы были применены в ходе выполнения проектов:

Планирование поведения в динамических системах, основанных на знаниях, № 00-01-00595, РФФИ;

Интеллектуальные интегрированные системы для моделирования поведения сложных систем, № 37.011.11.0020, федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники" на 2002-2006 годы Министерства промышленности, науки и технологий РФ.

Апробация работы

Основные результаты работы докладывались и обсуждались на следующих научных конференциях:

• Второй международный семинар по прикладной семиотике в рамках международной конференции AIICSR'97, Словакия, Смоленица, 15 сентября 1997 г.;

• XXXY всероссийской научной конференции по проблемам физики, химии, математики, информатики и методики преподавания (Москва, 1999);

• Третья международная летняя школа-семинар по искусственному интеллекту для студентов и аспирантов (Браславская школа-99);

• Седьмая национальная научная конференция по искусственному интеллекту (КИИ-2000, Переславль-Залесский, 2000);

• Международная научно-техническая конференция "Интеллектуальные САПР-99". Таганрог: ТРТУ, г. Геленджик 2-7 сентября 1999 г.;

• Областная научно-практическая конференция студентов, аспирантов и молодых ученых ВУЗов Ярославской области "Ярославский край - наше общество в 3-ем тысячелетии" 20 - 22 апреля 1999 года, г. Ярославль;

• Развернутая публикация по теме диссертации приведена в трудах международного семинара по дескриптивной логике, DL'99,

Линкепинг, Швеция, 30 июля - 1 августа 1999 г.;

• Работа обсуждалась на научных семинарах Исследовательского центра искусственного интеллекта ИПС РАН (Переславль

Залесский).

Публикации

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

Структура и объем работы

Диссертация состоит из введения, пяти глав, заключения и списка литературы, содержащего 105 наименований. Общий объём работы 96 страниц и содержит 15 таблиц и 1 диаграмму.

Основные результаты работы:

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

2. Построено функциональное расширение языка HSN-ALCEN, позволяющее моделировать рассуждения в функциональных неоднородных семантических сетях.

3. Показано, что неоднородные семантические сети являются моделью дескриптивной логики HSN-ALCEN.

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

5. Построен полиномиальный алгоритм планирования поведения для задачи классического AI планирования.

Заключение

1. Анохин М.И., Варновский В.М., Сидельников В.М., Ященко В.В. Курс лекций по теории кодирования. // www.creptography.ru

2. Аншаков О.М. Исчисление с обобщенными кванторами, связанное с формализацией правдоподобных рассуждений // КИИ'2000. Труды конференции. М.: Физматлит, 2000.

3. Ашиньянц Р.А., Богданов К.С. Представление знаний и логический вывод в сети фреймов. // КИИ'2000. Труды конференции. М.: Физматлит, 2000.

4. Беляев А.Б., Годовников М.Н., Голубев С.А., Загоровский И.М., Комаров С.И., Куршев Е.П., Осипов Г.С., Сазонова Л.И. Технология создания распределённых интеллектуальных сетей, // Переславль-Залесский, УГП, 1997.

5. Вагин В.Н. Параллельная дедукция на семантических сетях, К Известия АН СССР. Техническая кибернетика, 1986. №5. С 51-61.

6. Вагин В.Н., Загорянская А.А. Аргументация в правдоподобном выводе. // КИИ'2000. Труды конференции. М.: Физматлит, 2000.

7. Верещагин Н.К. Шень А. Вычислимые функции, Москва, МЦНМО,1999.

8. Виноградов Д.В. Выразимость фигур правдоподобных рассуждений в логике предикатов первого порядка. // КИИ'2000. Труды конференции. -М.: Физматлит, 2000.

9. Виноградов Д.В. Корректные формализации правдоподобных рассуждений. // КИИ'2000. Труды конференции. М.: Физматлит,2000.

10. Ю.Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. СПб: Питер, 2000.11 .Дорофеева А. Моделирование абдуктивных рассуждений / Университет города Переславля, фак. прикл. математика и информатика, 1997.

11. Дорофеева А.Г. Описание и исследование неоднородной семантической сети средствами дескриптивной логики. Международная научно- техническая конференция "Интеллектуальные САПР'99". Таганрог: ТРТУ, место проведения г. Геленжик 2-7 сентября 1999 г.

12. Жилякова Л.Ю. Исследование алгебраических и топологических свойств неоднородных семантических сетей, Дисс. к-та физ.-мат. наук. Переславль-Залеский., 2001. - 165 с.

13. Кейслер Г. Чэн Ч. Теория моделей.-М.: Мир, 1977.

14. Кнут Д. Искусство программирования. Том 1-3.- М.: Мир, 1999.

15. Комаров С.И., Куршев Е.П., Осипов Г.С., Построение моделей предметных областей. 4.2. Прямое приобретение знаний в системе SIMER. // Изв. АН СССР. Техническая кибернетика. 1991. - № 3. -с. 192-197

16. Кон П. Универсальная алгебра. М.: Мир. - 1968.

17. Лебедева Т.Г., Осипов Г.С. Архитектура и управляемость дискретных динамических систем, основанных на знаниях. // Известия АН. Теория и системы управления. М: Наука, 2000, №5, 703 709.

18. Лисица А.П., Сазонов В.Ю. Д-язык для гипермножеств и базы данных типа WEB. // КИИ'98. Труды конференции. М.: Физматлит, 1998.

19. Лорьер Ж.-Л. Системы искусственного интеллекта. -М.: Мир, 1990.

20. Майкевич Н.В. От информационного пространства к пространству знаний. // КИИ'98. Труды конференции. -М.: Физматлит, 1998.

21. Мендельсон Э. Введение в математическую логику. М.: Наука, 1984.

22. Минский М. Фреймы для представления знаний. М.: Энергия, 1979.29.0комин И. Теория сложности и ее использование в криптографии. // Курс лекций, http://se.math.spbu.ru/

23. Осипов Г.С. Выявление «грубой» модели предметной области. // Всесоюзная конференция по искусственному интеллекту. Тезисы докладов. Т. I.-M., 1988.-е. 512-513.

24. Осипов Г.С. Динамика в системах, основанных на знаниях. // Изв. РАН. ТиСУ. 1998. №5.

25. Осипов Г.С. Инструментарий для экспертных систем. Теория SIMER+MIR // Программные продукты и системы 1990, №3. -с.23 -32.

26. Осипов Г.С. Метод формирования и структурирования модели знаний одного типа предметных областей // Изв. АН СССР. Техническая кибернетика. 1988, №2 - с. 3 - 12.

27. Осипов Г.С. О формировании модели для плохо структурированной предметной области // Изв. АН СССР. Техн. кибернетика 1987, №5, с. 198-200.

28. Осипов Г.С. Построение моделей предметных областей. Неоднородные семантические сети. // Известия РАН СССР. Техн. кибернетика 1990, №5 - с. 32 - 45.

29. Осипов Г.С. Приобретение знаний интеллектуальными системами // М: Наука Физматлит, 1997.

30. Осипов Г.С. Специальные знания и синтез механизма рассуждений в задачах концептуального анализа // Изв. РАН Техническая кибернетика. 1992 -№5, с. 22 - 27.

31. Падучева Е.В. О семантике синтаксиса. М.: Наука, 1974

32. Попов Э.В. Общение с ЭВМ на естественном языке. М.: Наука, 1982.

33. Попов Э.В. Экспертные системы: решение неформальных задач в диалоге с ЭВМ. М.: Мир, 1987.

34. Поспелов Д.А. Ситуационное управление. Теория и практика. М.: Наука, 1986.

35. Построение экспертных систем / под ред. Ф. Хейс-Рот, Д. Уотерман, Д. Ленат. М.: Мир, 1987.

36. Приобретение знаний. / под ред. С. Осуги, Ю. Саэки. М.: Мир, 1990.

37. Сазонова Л.И. Разработка методов создания прикладных интеллектуальных систем с использованием технологии SIMER+MIR. Автореферат. Переславль-Залесский, - 1998.

38. Сазонова Л.И., Годовников М.Н., Куршев Е.П., Осипов Г.С. Создание интегрированных распределенных систем прогнозирования запасов рыбных объектов с использованием методов искусственного интеллекта. // Сб. трудов АзНИИРХ -Ростов-на-Дону: БКИ, 1998.

39. Сердюк Ю.П. К оцениванию интеллекта систем ИИ. // ICIT'99. Труды международной конференции интеллектуальное управление: новые интеллектуальные технологии в задачах управления. М.: Физматлит, 1999.

40. Тарский А. О обосновании научной семантики. // www.philisiphy.ru

41. Тейз А. Грибомомн П., Луи Ж. И др. Логический подход к искусственному интеллекту. М.: Мир, 1990.

42. Финн В.К. Правдоподобные выводы и правдоподобные рассуждения // Итоги науки и техники. Сер. теория вероятности, математическая статистика, теоретическая кибернетика. Т. 28. М.: ВИНИТИ, 1988.

43. Шушакова А.Г. Решение задач представления и обработки знаний средствами дескриптивной логики. // Программные продукты и системы №3, 2002 М: НТП «Фактор» - с. 14 - 19

44. Экспертные системы. Под. Ред. Р. Форсайта. М.: Радио и связь, 1987.

45. Artale A. Lunz С. A Corespondence betwyen Temporal Description Logics // In Proceeding of the 1998 International Workschop on Description Logics (DL-98), Povo-Treno. Italy, pp.-21-29, 1998.

46. Baader F., Borgida A., McGuines D.L. Matching in Description Logics: Preliminary results. // In Proceeding of the Sixth International Conference of Conceptual Structuries (ICCS' 98), Lecture Notes in Artificial Intelligence. Springer-Vertag, 1998.

47. Baader F., Hanschke P., "A scheme for integrating concrete domain into concept languages" , Technical report, DFKI Research Report RR-91-10, 1991.

48. Badea Liviu, Planning in Description Logics: Deduction versus Satisfiability Testing. // In Proceeding of the 1998 International Workschop on Description Logics (DL-98), Povo-Treno. Italy, pp.-21 -29, 1998.

49. Berrnudez J., Illarramendi A. A description logic with concrete domain for a metaclass level of an interoperable data system. // In Proceedings of DL'2000, International Workshop of Description Logics, 2000, Aachen, Germany.

50. Blanco J.M., Goni A. Illaramedi A. Mapping among Knowledge Base and Databases: Precise definition of is syntax and semantics. // Information Systems, 24(4). pp: 275-301, 1999.

51. Borgida A. On the relative expressiveness of description logics and pordicate logics // Artificial Intelligence, 1982 (996) pp.: 353-367.

52. Borgida A., McGuiness D. Asking Queries about Frames. // In Procidings of the First International Conference on Knowledge Representation and Reasoning. (KR-96) Cambrige. Mass., pp.-340-349, 1996.

53. Borgida Alexander, Ronald J. Brachman, Deborah L.McGuinness, Lori Alperin Resnick. CLASSIC: A Structural Data Model for Objects. In Proc. of the ACM SIGMOD // Int. Conf. On Management of Data, 1989, pp.: 59-67.

54. Brachman, Ronald J., Hector J. Levensque The Tractability of Subsumption in Frame-Based Description Languages. // In Proc. of the 4th Nat. Conf. On Artificial Intelligence (AAAI-84), 1984, pp.: 34 37.

55. Brachman, Ronald J., James G. Schmolze An Overview of the KL-ONE // Knowledge Representations System: Cognitive Science 9 (2), 1985 pp.: 171-216.

56. Calvanese D., Giacomo G. Lenzerini M., Nardi D., Infornation Integration: Conceptual Modeling and Reasoning Support. // In Proceeding of the 6 th International Conference on Cooperative Information Systems (CoopIS'98), pp.- 280-291, 1998.

57. Calvanese D., Lenzerini M., Nardi D., Description Logics for conceptual data modeling. In J. Chomicki and G.Saake editors // Logics for Databases and Information Systems, pp.- 229-264., Kluwer Academic Publisher, 1998.

58. Calvanese D., Lenzerini M., Nardi D., Unifying Class-Based representation formalisms. // J. of Artificial Intelligence Research, 11 : 199-240, 1999.

59. Chomichi Jan, Saake Gunter, Logics for Databases and Information Systems.// The Kluwer International series in engineering and computer science, v.436, 1998.

60. Donini F.M., Lenzerini M. Nardi D. Schaerf A. Reasoning in Description Logics // In. Principles of Artificial Intelligence. Ed: G. Brewska, Springer Verlag, 1995.

61. Donini F.M., Lenzerini M., Nardi D., Nutt W., Reasoning in Description Logics // In Procedings of the Second International Conference on

62. Principles of Knowledge Representation and Reasoning. (KR-91), pp. -151 162, 1991.

63. Donini F.M., Lenzerini M., Nardi D., Nutt W., The complexity of concept languages//Inform.and Сотр. 134, 1997. pp: 1-58.

64. Donini, Francesco M., Maurizio Lenzerini, Daniele Nardi, Werner Nutt. The Complexity of Concept Language. // In Proc. of the 2nd Int. Conf. On the Principles of Knowledge Representation and Reasoning (KR-91), 1991.

65. Dorofeyeva A. Analysis of Semantic Networks By Means of Description Logics// In Proceedings of the 1999 International Workshop on Description Logics(DL'99) Linku;ping, Sweden July 30 August 1, 1999. pp.167 - 168.

66. Dorofeyeva A. G., Lisitsa A.P., Labelled deductive systems for semantic network based reasoning: A semantic view. // In Proc. of Second Workshop on Applied Semiotics, September 15, AIICSR'97, Smolenice Castle, Slovakia, 1997. pp.97 105

67. Dr. Diego Calvanese Dr. Giuseppe De Giacomo, Dr. Maurizio Lenzerini, Identification Constraints and Functional Dependencies in Description Logics // In Proceedings of DL'2001, International Workshop of Description Logics, august 2001, USA.

68. Dr. Diego Calvanese, Dr. Giuseppe De Giacomo, Dr. Maurizio Lenzerini. Keys for Free in Description logics II In Proceedings of DL'2000, International Workshop of Description Logics, 2000, Aachen, Germany.

69. Elhaik Q., Rousset M., Making an Abox Persistent // In Proceeding of the 1998 International Workschop on Description Logics (DL-98), Povo-Treno. Italy, 1998.

70. Gabbay Dov M. Labelled Deductive System; priciples and applicatopns 11 Volume 1: Basic Principles, Oxford University Press, 1996.

71. Giunchiglia E., Giunchiglia F., Tacchella A. SAT, KSATC, DLP and ТА: a comparative analisis // In Proceeding of the 1998 International Workschop on Description Logics (DL-98), Povo-Treno. Italy, 1998.

72. Horrocks I., Sattler U. A. Description Logic with Transitive and Inverse Roles and Role hierarchies. // Technical Report 98-05, LuFg Theoretical Computer Science, RWTH Aachen, 1998.

73. Hustadt U., Schmidt R.A., On the Relation and Resolution and Tableaux Proof Systems for Description Logics.// Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI'99), 31 july- 6 august, 1999, Stockholm, Sweden.

74. Kaczmarek, Thomas S., Raymond Bates, Gabriel Robins. 1986 Recent Developments in NIKL. // In Proc.of the 5th Nat. Conf. on Artificial Intellegence, (AAAI-86), pp.: 978 985.

75. Kambhampati S. Refinement Planning as a Unifying Framework for Plan Synthesis // AI Magazine, 18(2): Summer 1997, pp.: 67 97

76. Kurtonona N., Rijke M., Expressivenes of concept espressions in first-order description logics // Artificial Intelligence, v.107, 1999.

77. Lambrix P., Larocchia P. Learning Composite Objects. // In Proceedings of the 1998 International Workschop on Description Logics (DL-98). Povo-Trento. Italy, pp. 147 - 152, 1998.

78. Lambrix P., Maleki J. Learning Composite Concepts in Description Logics: A First Step. // Proceedings of the 9 th International Symposium of Methodologies for Intelligent Systems ISMIS 96, LNAI 1079, pp: 68-77, 1996.

79. Lambrix P., Part-Whole Reasoning in Description Logics, Ph.D. Thesis, Department of Computer and Information Scince, Linkopring University, Sweden, 1996.

80. Larocchia P. Learning Composite Concepts in Description Logics: A First Step. // M.Sc. Thesis, Department of Computer and Information Scince, Linkopring University, Sweden, LiTH-IDA-Ex-9657.

81. Levesque, Hector J., and Ron J. Brachman, 1987, Expressiveness and Tractability in Knowledge Representation and Reasoning. Computational Intellegence 3. pp: 78-93.

82. Lisitsa Alexei P., Osipov Gennady S. Evolving algebras and labeled deductive systems for the semantic network based reasoning // In Proceedings of Workshop on Applied Semiotics, held in conjunction with ECАГ96, Budapest, Aug 1996,pp: 5-12.

83. Logics for Databases and Information System, edited by Jan Comicki, Gunter Saake, Monmouth University/ University of Magdeburg, Kluwer Academic Publishers, Boston/ Dordercht/ London, 2000.

84. Lutz C., Reasoning with Concrete Domains // Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI'99), 31 july 6 august, 1999, Stockholm, Sweden.

85. MacGregor, Robert, R.Bates, 1987. The Loom Knowledge Representations Language. Technical Reports ISI/RS-87 pp. 188.

86. Mayer M., Pirri F., A Study on the Logic of Abduction. // Proc. of 12 th European Conference on Artificial Itelligence (ECAI'96), 1996.

87. Patel-Schneider, P.F., and Bill Swatou. Working version: Description Logic Specification from the KRSS Effort, June 1993.

88. Scherf A. On the complexity of the instance checking problem in concept languages with existential quantification. // Journal of Intelligent Information Systems, 1993. №2: pp: 265 278,

89. Scherf A. Reasoning with individuals in concept languages. // Data and Knowledge Engieneering, 13: pp: 141 176, 1994.

90. Scherf A., Query Answering in Concept- Based Knowledge Representations System: Algorithms, Complexity, and Semanic Issues. Docoral dissertation, Departimento di Informaticd Sistemisica, Universita di Roma "La Sapienza", 1994.

91. Schmidt-Schauss, Manfred, Gert Smolka, 1991. Attributive Concept Description with Complements, // Artificial Intelligence Journal 48(1): 1 -26.

92. Tobies Stephan, On the Complexity in Description Logics // In Proceeding of the 1998 International Workschop on Description Logics (DL-98), Povo-Treno. Italy, 1998.

93. Wolter F., Zakharyaschev, Multi- dimensional description logics // Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAF99), 31 july 6 august, 1999, Stockholm, Sweden.

94. Woods, William A. 1975 What's in a Link. Foundations for Semantic Networks / In Representation and Understanding: Studies in Cognitive Science, ed. D.G. Bobrow and A.M. Collins.35-82. Academic Press. Republished in Brachman and Levesque 1985.