Интеллектуальная система программирования FramIX для представления знаний в системах принятия решений тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Богданов, Кирилл Сергеевич

• Богданов, Кирилл Сергеевич
• кандидат технических наук
• 2001

Оглавление диссертации кандидат технических наук Богданов, Кирилл Сергеевич

Введение

1. Методы и системы представления знаний.

1.1. Методы представления знаний.

1.1.1. Продукционная модель.

1.1.2. Логические модели.

1.1.3. Семантические сети.

1.1.4. Фреймы.

1.1.5. Преимущества гибридной модели представления знаний.

1.2. Системы представления знаний.

1.2.1. Rhet.

1.2.2. Babylon.

1.2.3. Parmenides.

1.2.4. Frobs, Frolic.

1.2.5. Florid

1.2.6. FramerD.

1.2.7. SNePS.

1.3. Постановка задачи.

1.4. Выводы.

2. Гибридная модель представления знаний, основанная на сети фреймов. Логический вывод на сети фреймов.

2.1. Гибридная модель представления знаний.

2.1.1. Фрейм.

2.1.2. Связи между фреймами. Типы связей.

2.2. Демоны.

2.3. Сообщения - единый метод доступа и манипуляции данными в сети.

2.4. Логический вывод на сети фреймов.

2.4.1. Понятие Процессора Логического Вывода (ПЛВ).

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

2.4.3. Формальное представление знаний. Синтаксис языка запросов

2.4.4. Семантика языка запросов. Метод резолюций на сети фреймов.

2.4.5. Пример логического вывода.

2.5. Архитектура фреймовой системы представления знаний Рлам1Х

2.6. Выводы.

3. Реализация гибридной фреймово-сетевой модели. Ядро системы П1АМ1Х. Алгоритмы и методы реализиции.

3.1. Архитектура системы Р11АМ1Х.

3.2. Объектная модель ядра.

3.2.1. Базовые классы манипулирования данными.

3.2.2. Подсистема управления демонами.

3.2.3. Слот.

3.2.4. Фрейм.

3.2.5. Подсистема управления связями.

3.3. АР1 системы РкамГХ.

3.3.1. Структура АР1 системы РЯАМ1Х.

3.3.2. Функции управления структурой сети.

3.3.3. Функции манипулирования данными.

3.3.4. Функция SendMessage.

3.4. Механизмы фиксации состояний сети фреймов.

3.5. Пользовательский модуль. Структура типичного

Введение диссертации (часть автореферата) на тему «Интеллектуальная система программирования FramIX для представления знаний в системах принятия решений»

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

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

Таким образом, естественно формируется триада: приобретение знаний (data mining), представление знаний (модель) и обработка знаний (прикладная система) - и эта триада представляет содержание направления искусственный интеллект.

Настоящая диссертационная работа посвящена разработке методов и средств, реализующих все три этапа: представление знаний (2-я глава), извлечение знаний (4-я глава), прикладная система, основанная на знаниях (3-я,

4-я главы).

Если в системах, основанных на знаниях, на этапе моделирования невозможно непосредственное использование аналитических, статистических методов, то первый этап наоборот широко и активно их использует. Направление data mining - это по существу совокупность различных, хорошо апробированных методов: регрессионного, дискриминантного, факторного, кластерного анализов и др., - приобретающих новое смысловое назначение - извлечение знаний. Объектами этих методов становятся пассивные хранилища данных -суть результат жизнедеятельности некоторой предметной области. Заметим, что здесь проблема представительности выборки теряет свою остроту.

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

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

Принято различать следующие основные подходы к представлению знаний:

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

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

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

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

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

Таким образом, актуальность темы диссертации может быть сформулирована следующими положениями:

1) Необходимость разработки методов и средств формализации предметной области;

2) Разработка форм отображения знаний, инвариантных к предметной области;

3) Построение программных систем, основанных на предложенных моделях, для решения задач поддержки принятия решений.

Цель работы - Решение задачи отображения в гибридной системе достоинств логический систем. Известно, что при всех недостатках логических систем, это единственный подход, который в любом случае приводит к положительному результату, что не всегда достижимо в других системах. Поэтому, если теорию фреймов и соответствующее представление объектов в форме связанных друг с другом отношениями подчиненности, причинности и т.д., что представляет собой сеть фреймов, трансформировать в теорию предикатов 1-го порядка, расширив, тем самым, саму теорию предикатов 1-го порядка, то все её достоинства будут обращены и в теорию сетей фреймов.

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

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

1) Предложена новая гибридная модель представления знаний, основанная на формализмах фреймов и семантических сетей.

2) Разработана активная фреймовая структура, сочетающая внутренние процедуры обработки и передачи информации внутри сети фреймов.

3) Разработан механизм реализации множества различных методов логического вывода на единой базе знаний, представленной в виде сети фреймов.

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

Результаты исследований обсуждены на 7-й национальной конференции по искусственному интеллекту "КИИ-2000М[5].

Результаты исследований внедрены в ЗАО "БМ-СопвиШ^".

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Богданов, Кирилл Сергеевич

4.4. Выводы.

1) Проведен анализ хранилища ретроспективных данных, содержащих исходные данные об изменении котировок.

2) Применение метода регрессионного и корреляциооного анализа позволило установить функциональную зависимость между прогнозируемыми величинами в текущий момент времени от факторов котировок в прошлом. Сформулированы две задачи: прогноза и принятия решения.

3) На базе системы программирования Ри.Ам1Х построена оболочка экспертной системы РВСБ, позволяющей формировать обобщенные прогнозные гипотезы из множества первичных.

4) Система внедрена в ЗАО "СМ-Консалтинг" и используется для анализа фьючерсных рынков.

5) Особенности архитектуры РЯАМ1Х позволяют разработать на её основе реализацию других форм ПЛВ и соответствующих им модификаций базы знаний.

Заключение

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

В настоящей диссертатионной работе:

1) Обоснована необходимость разработки гибридных систем представления знаний, аккумулирующих достоинства известных форм представления знаний. Такие гибридные системы должны обладать несколькими ПЛВ, работающими на единой базе знаний.

2) Разработано математическое обеспечение фреймово-сетевого представления знаний.

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

4) В качестве механизма логического вывода использован метод резолюций.

5) Разработана архитектура ядра системы FramIX.

6) Разработана объектная модель ядра, структура классов для представления модулей ядра, методы классов и API системы.

7) Показано, что система FramIX может быть использована как средство описания фреймово-сетевых моделей.

8) Функционирование модулей системы FramIX на тестовых задачах обеспечивает высокую производительность и эффективность по сравнению с другими системами.

9) Проведен анализ хранилища ретроспективных данных содержащих исходные данные об изменении котировок.

10) Применение метода регрессионного и корреляциооного анализа позволило установить функциональную зависимость между прогнозируемыми величинами в текущий момент времени от факторов котировок в прошлом. Сформулированы две задачи: прогноза и принятия решения.

11) На базе системы программирования FramIX построена оболочка экспертной системы FBCS, позволяющей формировать обобщенные прогнозные гипотезы из множества первичных.

12) Система внедрена в ЗАО "СМ-Консалтинг"и используется для анализа фьючерсных рынков.

13) Особенности архитектуры FramIX позволяют разработать на её основе реализацию других форм ПЛВ и соответствующих им модификаций базы знаний.

Список литературы диссертационного исследования кандидат технических наук Богданов, Кирилл Сергеевич, 2001 год

1. Ашинянц М.Р., Ашинянц P.A., "Аналитическое, ассоциативное, генетическое обучение - новейшие стратегии" // Информационные технологии в проектировании и производстве. - М.: ВИМИ, N2, 1997, сс.49-58

2. Ашинянц P.A., "Логические методы в искусственном интеллекте" М.: МГАПИ, 2001 - 223с.

3. Ашинянц P.A., "Логический язык программирования ПРОЛОГ" М.: МГАПИ, 2001 - 303с

4. Ашинянц P.A., "Стратегии логических методов обучения и концептуальной классификации" // Информационные технологии в проектировании и производстве М.: ВИМИ, N3, сс.22-40, 1997

5. P.A. Ашинянц, К.С. Богданов, "Представление знаний и логический вывод в сети фреймов", Труды 7-й национальной конференции по искусственному интеллекту "КИИ-2000", Москва.: Наука, изд. Физ.-мат. Литература, 2000. - 150 - 158сс.

6. Ашинянц P.A. Нечипай A.M., "Модифицируемые рассуждения в задачах медицинской диагностики." Информационные технологии, ВИМИ, №2, 1999

7. К. С. Богданов, А.Д. Куприйчук, "Учебная система фреймового представления знаний на языке Пролог", Научно-техническая конференция студентов, аспирантов и молодых специалистов МГИЭМ, тезисы докладов. М.: МГИЭМ, 1997. - 233с.

8. К. С. Богданов, А Д. Куприйчук, "Фреймово-сетевая модель представления знаний системы FRAMIX. Ядро системы", '"Новые информационные технологии". Тезисы докладов VI международной студенческой школы-семинара М.: МГИЭМ , 1998. - 49-50ес.

9. М. Даконта, А. Саганич, "XML и Java2" С.-Пб.: Питер, 2001, - 384с

10. И. Доил Дж., "Система поддержки истинности" М.: Мир, Кибернетический сборник, новая серия, вып. 20, сс. 159-214, 1983.

11. Дюк В., Самойленко А., "Data mining" С.-Пб.: Питер, 2001, - 368с.

12. Загоруйко Н.Г., "Прикладные методы анализа данных и знаний." Новосибирск. Ин-т математики РАН, 1999. - 270с.

13. Клини С., "Математическая логика" М.: Мир, 1973 - 480с.

14. АД. Куприйчук, К.С. Богданов, "Модели представления знаний. Сети фреймов", Международная научно-техническая конференция "Пятьдесят лет развития кибернетики", труды конференции Санкт-Петербург: Издательство "НЕСТОР", 1999. - 179с.

15. АД. Куприйчук, К. С. Богданов, "Система FRAMIX. Фреймово-сетевой язык программирования", Тезисы докладов научно-технической конференции студентов, аспирантов и молодых специалистов МГИЭМ М.: МГИЭМ , 1998. - 317с.

16. А.Д. Куприйчук, К.С. Богданов, "Фреймово-сетевая система представления знаний. Язык программирования FRAMIX", "Новые информационные технологии". Тезисы докладов VI международной студенческой школы-семинара- М.: МГИЭМ, 1998. 51с.

17. Д. Мартин, М. Бирбек и др., "XML для профессионалов" М.: Издательство "Лори", 2001, - 900с.

18. Минский М., "Фреймовая структура представление знаний." //В сб. Психология машинного зрения.-М.:Мир,1978, с.249-338.

19. Осипов Г. С., "Приобретение знаний интеллектуальными системами" М.: Наука-Физматлит, 1997. - 112с.21. под ред. С. Осуги, Ю. Сажи'"Приобретение знаний" М.: Мир, 1990 -304 с.

20. Под ред. Д. А. Поспелова, "Искусственный интеллект" В 3-х кн. Кн.2. Модели и методы: Справочник - М.: Радио и связь, 1990. - 304 е.: ил.

21. Роберт Колби, Томас Мейерс, "Энциклопедия технических индикаторов рынка" Москва: Издательский Дом "Альпина", 1998 - 581с.

22. Стерлинг Л., Шапиро Э., "Искусство программирования на языке Пролог" М.: Мир, 1990. - 235с.

23. Тейз А., Грибомон П., Луи Ж. и др., "Логический подход к искусственному интеллекту: от классической логики к логическому программированию." М.: Мир, т. 1, 1990. - 432с.

24. Тейз А. и др., "Логический подход к искусственному интеллекту." -М.: Мир,т.2. 1998.

25. Ю.Н. Тюрин, A.A. Макаров, "Статистический анализ данных на компьютере", под ред. В.Э. Фигурнова М: ИНФРА-М, 1998 - 528с.

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

27. А.Н. Ширяев, "Основы стохастической финансовой математики. Том 1. Факты. Модели." Москва: ФАЗИС, 1998 - 512с.

28. Bradford W. Miller, "Rhet Programmer's Guide" Technical Report 363 -University of Rochester, Computer Science Department, 1990.

29. Bradford W. Miller, "The RHET Plan Recognition System" Technical Report 298 - University of Rochester, Computer Science Department, 1990.

30. Davis R., King «/., "An overview of production systems", Machine Intelligence, vol. 8, Ellis Horwood Limited, Chichester, pp. 300-333, 1985.

31. Eric Muehle, "FROBS User Guide" Utah PASS Project OpNote 87-05 -University of Utah, Computer Science Department, 1993

32. Etherington D., "Formalizing nonmonotonic system.", J. Artificial Intelligence., vol.31, №1, 1987 pp. 41-85.

33. James F. Allen, Bradford W. Miller, "The Rhetorical Knoweledge Representation System: A Tutorial Introduction" Technical Report 325 -University of Rochester, Computer Science Department, 1991.

34. James F.Allen, Bradford W. Miller, "The Rhetorical Knoweledge Representation System: A User's Guide" Technical Report 238 (rerevised) - University of Rochester, Computer Science Department, 1989.

35. Jed Krohnfeldt, Craig Steury, "Frolic: Logic Programming with Frobs" -Utah PASS Project OpNote 86-08 University of Utah, Computer Science Department, 1993

36. Johannes A.G.M., Koomen, "The TIMELOGIC Temporal Reasoning System" Technical Report 231 (revised) - University of Rochester, Computer Science Department, 1988.

37. Jürgen Frohn, Rainer Himmeröder, Paul-Th. Kandzia, Christian Schlepphorst, "FLORID: User Manual, Version 2.0" Institut für Informatik, Universität Freiburg, Germany, 1997

38. K. Haase, "FramerD: Representing knowledge in large" IBM Systems Journal, vol 35, nos 3&4, 1996, 381-397

39. Thomas Hellstrom and Kenneth Holmstrom, "Predicting the Stock Market", Center of Mathematical Modelling Department of Mathemaics and Physics Malardalen University, Vasteras, Sweden, 1998.

40. Michael Kifer, Georg Launsen, James Wu, "Logical Foundations of Object-Oriented and Frame-Based Languages" Technical Report 93/06 - Stony Brook, Department of Computer Science, NY 11794, 1994

41. De Kleer J., "An assumption based TMS", J. of Artificial Intelligence, vol. 28, pp. 127-224, 1986.

42. McCarthy J., "Applications of circumscription to formalizing common-sense knowledge." A.I., vol. 28. 1986, pp. 89-116.

43. Quinlan J.R., "A formal deductive problem Solving Systems" - J. Assoc. Comp. Mach, 1968, v.15, N4, pp 625-646.

44. Quinlan J.R., "Induction of decision trees" Machine Learning, v.l, N1, pp 81-106, 1968.

45. Reiter R., "A theory of diagnosis principals", A.I., vol. 33,№ 1, 1987.

46. Peter Shell, Jaime Carbonell, "PARMENIDES: A Class-Based Frame System" Carnegie Mellon University, 1991

47. Peter Shell, Jaime Carbonell, "FRulekit: A Frame based production system, User's manual" Carnegie Mellon University, 1993

48. Stuart C. Shapiro and The SNePS Implementation Group, "SNePS 2.1 User's manual" State University of New York at Buffalo, Department of Computer Science, Buffalo, NY 14260, 1993

49. Touretzky D., "The Mathematics of Inheritance Systems", Research Notes in A.I., London,1986.

50. УТВЕРЖДАЮ Генеральный директор ЗАО "СМ-Консалтинг'1. Консалтинг"1. М.В.СмирновУ1. АКТо внедрении результатов научно-исследовательской работы "Экспертная система ГВС8 для анализа и классификации результатов первичного прогнозирования биржевых котировок"

51. Комиссия в составе: Генерального директора Смирнова Михаила Валерьевича, Начальника аналитического отдела Гнеденко Бориса Дмитриевича, Проф. Ашинянца Роберта Арамовича, Богданова Кирилла Сергеевича

52. Конкретные результаты внедрения состоят в следующем:

53. Разработана оболочка экспертной системы БВСЗ, построенной на базе системы программирования Ргат1Х.

54. Система РВС8 позволяет формировать обобщенные прогнозные гипотезы из множества первичных.

55. Система значительно облегчает задачу анализа фьючерсного рынка.

56. Испытания показали, что порождаемые системой обобщенные прогнозные гипотезы соответствуют ожидаемым.1. Смирнов М.В./1. Ашинянц Р.А./1. Богданов К.С./