Software & Systems

Системы искусственного интеллекта находят все более широкое применение в производственных и научных областях в силу гибкости настроек, способности к обобщению, выявлению зависимостей, противоречий и возможности постоянной адаптации своих параметров к изменяющейся внешней среде. В сфере исследований искусственного интеллекта [1] сформировалось самостоятельное направление, получившее название технологии экспертных систем (ЭС) [2]. Достоинство ЭС – обобщение эмпирического опыта специалистов для построения адекватного представления о внутреннем устройстве изучаемой области без привлечения специальных математических аппаратов для выявления этих структурных зависимостей [3].

На первоначальном этапе разработки ЭС особое внимание уделяется выбору механизма хранения данных, способам организации полученных сведений в базе знаний (БЗ) и инструментам логического вывода. Чаще всего в ЭС применяется модель знаний в виде правил, получившая название продукционной модели Поста, такая модель базируется на понятии формальной теории и представляет знания в виде предложений типа «ЕСЛИ – посылка, ТО – следствие» [4].

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

При увеличении объема правил в БЗ логический вывод выполняется за недопустимо большой промежуток времени, что снижает возможность получения оперативного решения. Алгоритм сопоставления с образцом (сеть Rete) частично решает эту задачу, но в силу особенности преобразования исходных правил в альфа- и бета-сеть может затормозить этот процесс по причине наличия этапа обработки всей базы правил в Rete-сети и выделения дополнительной динамической памяти вычислительного устройства для хранения преобразованного исходного набора правил.

Авторами статьи предложен подход к ускорению преобразования исходных правил в Rete-сеть путем подключения реляционной БД, в которой будут храниться как исходные правила для каждой предметной области, так и связи между альфа- и бета-сетями. Процесс построения и обработки Rete-сети реализован в виде периодического запуска в фоновом режиме (параллельном потоке) в отдельном вычислительном узле (сервере), который при большом количестве правил в БЗ сделает этап преобразования правил в Rete-сеть для пользователя практически незаметным.

Для демонстрации возможного применения излагаемого подхода использована идея преобразования когнитивных моделей в продукционные правила ЭС для автоматизации вывода на когнитивных моделях [5]. Выполнено преобразование одной из когнитивных моделей, построенной для исследований проблем энергетической безопасности [6], – «Уровень инвестиций в отраслях топливно-энергетического комплекса» [7], в продукционную модель с размещением рабочей памяти решателя (системы логического вывода) в реляционной БД; также показано сравнение времени выполнения механизма логического вывода при использовании алгоритма наивного поиска и алгоритма сопоставления с образцом (Rete-сеть) в разработанной авторами системе.

Хранение данных и знаний

Представим основные компоненты архитек- туры хранилища данных и знаний (ХДЗ) и их взаимодействие (рис. 1).

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

Рассмотрим ЭС как конкретизацию архитектуры, показанной на рисунке 1 [8]. В состав ЭС входят компонент анализа знаний, интерфейс взаимодействия, БЗ, решатель (механизм вывода) и компонент объяснения.

Математическое описание продукционных правил (знаний) имеет вид:  g1, g2, g3, …, gn ® s, где  g1, g2, g3, …, gn – посылки (антецеденты), то есть исходный факт, по которому осуществляется поиск в базе знаний; s – следствие (консеквенты), то есть факты и/или действие, полученное/выполненное при успешном исходе поиска [9].

Когнитивное моделирование

Когнитивные модели графически можно представить в виде когнитивных карт. Концепция когнитивных карт предложена в 1948 году психологом Э. Толменом [10]. В 1976 г. в работе [11] предложено использовать когнитивные карты и методологию когнитивного моделирования для анализа проблемных ситуаций и принятия решений в слабоформализованных системах. В настоящее время когнитивное моделирование широко применяется для анализа слабоструктурированных систем, таких как экономические, социальные, экологические и т.п. Известные зарубежные ученые в своих работах исследуют возможности конструирования нечетких когнитивных моделей на основе набора данных [12], а также использование таких моделей, например в [13], для исследования сложных динамических систем. Отечественные специалисты решают задачи применения когнитивных моделей для исследования качества жизни населения [14]. Так, в работе [15] предлагается использовать когнитивные карты совместно с семиотическим подходом для  уточнения исследуемой предметной области, что может быть полезно в области принятия управленческих решений. В [16, 17] когнитивное моделирование предполагается применять для исследования энергетической безопасности вместе с другими семантическими моделями для оценки угроз и рисков.

Когнитивное моделирование используется для выявления характера причинно-следствен- ных зависимостей между основными составляющими исследуемой угрозы энергетической безопасности [16]. Вывод на когнитивной карте до последнего времени выполнялся экспертом-исследователем вручную. Учитывая, что когнитивная карта может иметь большое количество концептов или несколько уровней вложенности согласно фрактальному подхо- ду [18], либо же из-за ошибок, свойственных человеку, результат анализа может содержать ошибки. Также может случиться, что время, затраченное на анализ, может сделать нецелесообразным использование когнитивного подхода. Поэтому предлагается для увеличения скорости анализа когнитивной карты использовать преобразование отношений когнитивной модели в продукционные правила экспертной системы и логический вывод, основанный на применении Rete-сетей. Когнитивную карту довольно просто представить в продукционном виде: «Если {концепт_1}, то {концепт_2}», где концепт_1 является антецедентом, а концепт_2 – консеквентом. Одной из основных угроз, исследуемых с точки зрения энергетической безопасности, является недостаток инвестиций в энергетике. С использованием опыта экспертов-энергетиков построена когнитивная карта, содержащая основные концепты, которые могут влиять на исследуемую угрозу. На ее примере проиллюстрировано возможное применение предлагаемого авторами подхода. Фрагмент когнитивной карты приведен на рисунке 2.

Механизм логического вывода. Rete-сеть

Ядром функционирования ЭС служит механизм логического вывода. Скорость получения вывода в системе зачастую является ключевым фактором при выборе инструмента реализации [19].

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

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

1) A ® B,

2) A ® C,

3) C&D ® E,

4) B&E ® F, где A – уровень доходности предприятий, которая увеличивается; B – внутренние инвестиционные ресурсы, которые уменьшаются; С – инвестиционная привлекательность ТЭК – уменьшается; D – неблагоприятный инвестиционный климат в стране – уменьшается; E – внешние инвестиционные ресурсы – уменьшаются; F – необходимость привлечения инвестиций в энергетику.

Пусть пользователем на начальном этапе ввода введены факты A и D. При первом обходе активируются правила № 1 и № 2, из которых будут получены факты B и C. На втором этапе будет применено правило № 3, в нем в стек добавляется новый факт – E, и только после получения этого факта на следующей итерации активируется правило № 4, в котором будет получен последний факт – F, далее вывод завершится, так как больше не останется правил, которые сможет применить механизм логического вывода.

Наивный поиск имеет недостатки, основной из которых – низкая скорость вывода при многократном обходе правил: чем больше правил в БЗ, тем медленнее выполняется поиск конечного решения. Оптимальным с точки зрения скорости логического вывода считается алгоритм сопоставления с образцом Чарльза Форги, другое название – Rete-сеть.

Rete-сеть – алгоритм логического вывода для продукционных систем, ЭС и БЗ, предложенный Чарльзом Форги из Университета Карнеги–Меллона. Впервые описан в рабочем документе 1974 года, затем в докторской диссертации 1979 года [20]. Алгоритм Rete стал основой многих популярных ЭС, включая CLIPS, Jess, Drools, BizTalk Rules Engine и Soar [21].

Основная идея работы алгоритма Rete-сети состоит в создании образцов (расширенного набора антецедентов) для каждого правила в БЗ.

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

Рассмотрим правило № 4 из рисунка 3: в наборе антецедентов содержится факт E, который одновременно является антецедентом для получения факта F и консеквентом при выполнении условий в фактах D и C.

В таком случае, применяя алгоритм Rete, получим следующий набор антецедентов правила № 4: без изменений останется старая группа фактов – E, B, добавится новый набор, полученный при разворачивании факта Е. В результате такого преобразования будут получены несколько групп антецедентов правила № 4 (точнее, группы образцов для сопоставления). Полученная группа образцов для сопоставления представлена на рисунке 4.

Алгоритм Rete не завершен, так как имеются еще правила № 1 и № 2 (A ® B, A ® C), объединив которые, получим: A ® B/C. В таком случае, применив правила № 1 и № 2 к преобразованной группе антецедентов, получим расширение группы образцов для вывода факта F следующими антецедентами: E&A, D&A&B, D&C&B, D&A&A (по правилам логики A&A ® A, сократив до D&A), итоговый набор образцов для вывода фактов F представлен на рисунке 5.

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

Проектирование и реализация ЭС

Структура ЭС изображена на рисунке 6.

Учитывая особенности реализации ЭС, опишем основные модули разработанной системы (рис. 6): модуль разрешения конфликтов (разрешение зацикливания выводов в случае наличия замкнутых цепочек между правилами в продукционном графе), блок объяснения вывода (показывает ход выполненных рассуждений), механизм вывода, БЗ (взаимосвязь между посылками и следствиями в правилах).

Механизм вывода, реализующий алгоритм сопоставления с образцом, использует рабочую память, выделенную в БД (rete-algorithm), схема которой показана на рисунке 7.

Основные таблицы: rete-pattern – содержит все наборы антецедентов для сопоставления и вывода новых фактов; rete-scheme – настройка решателя, в которой указывается стратегия вывода, идентификатор предметной области, для которой сформирована рабочая память.

По завершении разработки ЭС был выполнен сравнительный анализ, результаты которого приведены в таблице и проиллюстрированы на рисунке 8. В ходе анализа выяснилось, что алгоритм сопоставления с образцом при получении решения выигрывает в скорости выполнения при большом объеме правил в БЗ по сравнению с методом наивного поиска.

Средняя скорость выполнения разных алгоритмов вывода

Average execution speed of different output algorithms

Анализ таблицы позволяет сделать следующий вывод: скорость выполнения наивного по- иска высока при малом количестве фактов в БЗ, но алгоритм Rete-сети в любом случае быстрее выполняет вывод. Однако при возрастании количества фактов (от 1 500 правил и выше) скорость вывода при использовании для рабочей памяти реляционной БД значительно выше, чем при расположении памяти в динамическом стеке ЭВМ.

Заключение

В статье предложено выполнять формирование и хранение рабочей памяти механизма логического вывода продукционных ЭС с применением технологии Rete-сеть. Для демонстрации преимуществ предлагаемого подхода использована идея преобразования когнитив- ных моделей в продукционные правила ЭС для автоматизации вывода на когнитивных моделях. Рассмотрены основные понятия когнитивного моделирования и обобщенная структура ХДЗ и ЭС. На примере когнитивной карты «Недостаток инвестиций в энергетике» проиллюстрирован логический вывод с использованием Rete-сети. Рассмотрены проектирование и реализация авторской ЭС, с помощью которой выполнено сравнение двух алгоритмов: наивного поиска и с применением Rete-сети. Показано, что предлагаемое технологическое решение по переносу рабочей памяти алгоритма Rete в реляционную БД позволяет сократить время выполнения логического вывода при большом объеме правил в БЗ.

Результаты получены в рамах выполнения проекта по госзаданию ИСЭМ СО РАН АААА-А17-117030310444-2 (проект № 349-2016-0005) и при частичной финансовой поддержке грантов РФФИ №№ 19-07-00351, 19-57-04003, 18-07-00714.

Литература

1.    Рассел С., Норвиг П. Искусственный интеллект. Современный подход; [пер. с англ.]. М.: Вильямс, 2007. 1410 с.

2.    Башмаков А.И., Башмаков И.А. Интеллектуальные информационные технологии. М.: Изд-во МГТУ им. Н.Э. Баумана, 2005. 304 с.

3.    Матвеев М.Г., Свиридов А.С., Алейникова Н.А. Модели и методы искусственного интеллекта. М.: Инфра-М-Финансы и статистика, 2014. 448 с.

4.    Ездаков А.Л. Экспертные системы САПР. М.: Форум, 2019. 160 с.

5.    Пестерев Д.В. Использование продукционных экспертных систем для анализа когнитивных моделей // Информационные и математические технологии в науке и управлении. 2018. № 1. С. 46–55.

6.    Сендеров С.М., Рабчук В.И., Пяткова Н.И., Воробьев С.В. Обеспечение энергетической безопасности России: выбор приоритетов. Новосибирск: Наука, 2017. 116 с.

7.     Пяткова Н.И., Массель Л.В., Массель А.Г. Методы ситуационного управления в исследованиях проблем энергетической безопасности // Изв. РАН. Энергетика. 2016. № 4. С. 156–163.

8.    Ручкин В.Н., Фулин В.А. Универсальный искусственный интеллект и экспертные системы. СПб: БХВ-Петербург, 2009. 240 с.

9.    Лоскутов А.Ю., Михайлов А.С. Основы теории сложных систем. Ижевск: Изд-во ИКИ, 2007. 620 с.

10. Tolman E.C. Cognitive maps in rats and men. Psychological Review, 1948, no. 55, pp. 189–208.

11. Axelrod R. Structure of Decision: The Cognitive Maps of Political Elites. Princeton, Princeton Univ. Press Publ., 1976, 395 p.

12. Groumpos P.P., Stylios C.D. Modelling supervisory control systems using fuzzy cognitive maps. Chaos, Solitons and Fractals, 2000, vol. 11, pp. 329–336.

13. Papageorgiou E.I., Stylios C.D., Groumpos P.P. An integrated two-level hierarchical system for decision making in radiation therapy based on fuzzy cognitive maps. IEEE Transactions on Biomedical Engineering, 2003, vol. 50, no. 12, pp. 1326–1339. DOI: 10.1109/TBME.2003.819845.

14. Авдеева З.К., Коврига С.В., Макаренко Д.И. Когнитивное моделирование для решения задач управления слабоструктурированными системами (ситуациями) // УБС. 2007. № 16. С. 26–39.

15. Кузнецов О.П., Кулинич А.А., Марковский А.В. Анализ влияний при управлении слабоструктурированными ситуациями на основе когнитивных карт. В кн.: Человеческий фактор в управлении. М.: КомКнига, 2006. С. 313–344.

16. Массель А.Г. Когнитивное моделирование в исследованиях проблем энергетической безопасности: применения и перспективы развития // Междунар. конгресс IS&IT’14: сб. тр. М.: Физматлит, 2014. Т. 2. С. 153–158.

17. Массель Л.В. Применение онтологического, когнитивного и событийного моделирования для анализа развития и последствий чрезвычайных ситуаций в энергетике // Проблемы безопасности и чрезвычайных ситуаций. 2010. № 2. С. 34–43.

18. Массель Л.В. Фрактальный подход к структурированию знаний и примеры его применения // Онтология проектирования. 2016. Т. 6. № 2. С. 149–161.

19. Сидоркина И.Г. Системы инженерии знаний. URL: http://csd.faculty.ifmo.ru/files/sidorkina_i_g_internet_lecture.pdf (дата обращения: 15.04.2020).

20. Forgy Ch. On the efficient implementation of production systems. Ph.D. Thes., Carnegie-Mellon Univ. Publ., 1979. 210 p.

21. Джексон П. Введение в экспертные системы; [пер. с англ.]. М.: Вильямс, 2001. 624 с.

References

1. Russel S., Norvig P. Artificial Intelligence. A Modern Approach. Prentice Hall Publ., 2003, 1136 p. (Rus. ed.: Moscow, 2007, 1410 p.).
2. Bashmakov A.I., Bashmakov I.A. Intelligent Information Technologies. Moscow, 2005, 304 p.
   (in Russ.).
3. Matveev M.G., Sviridov A.S., Aleynikova N.A. Models and Methods of Artificial Intelligence. Мoscow, 2014, 448 p. (in Russ.).
4. Ezdakov A.L. Expert CAD Systems. Мoscow, 2019, 160 p. (in Russ.).
5. Pesterev D.V. Using production expert systems for the analysis of cognitive models. Information and Mathematical Technologies in Science and Management, 2018, no. 1, pp. 46–55 (in Russ.).
6. Senderov S.M., Rabchuk V.I., Pyatkova N.I., Vorobyov S.V. Ensuring Russia's Energy Security: A Choice of Priorities. Novosibirsk, 2017, 116 p. (in Russ.).
7. Pyatkova N.I., Massel L.V., Massel A.G. Methods of situational management in studies of energy security problems. Bull. of the Russian Academy of Science: Energetics, 2016, no. 4. pp. 156–163 (in Russ.).
8. Ruchkin V.N., Fulin V.A. Universal Artificial Intelligence and Expert Systems. St. Peterburg, 2009, 240 p. (in Russ.).
9. Loskutov A.Yu., Mikhaylov A.S. Fundamentals of the Theory of Complex Systems. Izhevsk, 2007,
   620 p. (in Russ.).
10. Tolman E.C. Cognitive maps in rats and men. Psychological Review, 1948, no. 55, pp. 189–208.
11. Axelrod R. Structure of Decision: The Cognitive Maps of Political Elites. Princeton, Princeton Univ. Press, 1976, 422 p.
12. Groumpos P., Stylios C. Modelling supervisory control systems using fuzzy cognitive maps. Chaos, Solitons and Fractals, 2000, vol. 11, pp. 329–336.
13. Papageorgiou E.I., Stylios C.D., Groumpos P.P. An Integrated Two-level hierarchical system for decision making in radiation therapy based on fuzzy cognitive maps. IEEE Transactions on Biomedical Engineering, 2003, vol. 50, no. 12, pp. 1326–1339. DOI: 10.1109/TBME.2003.819845.
14. Avdeeva Z.K., Kovriga S.V., Makarenko D.I. Cognitive modeling for solving problems of managing poorly structured systems (situations). Large-Scale Systems Control, 2007, no. 16, pp. 26–39 (in Russ.).
15. Kuznetsov O.P., Kulinich A.A., Markovskiy A.V. Impact analysis for managing poorly structured cognitive map-based situations. In: The Human Factor in Management, Мoscow, 2006, pp. 313–344 (in Russ.).
16. Massel A.G. Cognitive modeling in studies of energy security problems: applications and development prospects. Proc. IS&IT’14, 2014, vol. 2, pp. 153–158 (in Russ.).
17. Massel L.V. The use of ontological, cognitive and event modeling to analyze the development and consequences of emergency situations in the energy sector. Safety and Emergencies Problems, 2010, no. 2,
    pp. 34–43 (in Russ.).
18. Massel L.V. Fractal approach to structuring knowledge and examples of its application. Ontology of Designing, 2016, vol. 6, no. 2, pp. 149–161 (in Russ.).
19. Sidorkina I.G. Knowledge Engineering Systems. Available at: http://csd.faculty.ifmo.ru/files/sidorkina_
    i_g_internet_lecture.pdf (accessed: April 15, 2020) (in Russ.).
20. Forgy Ch. On the Efficient Implementation of Production Systems. Ph.D. Thes., Carnegie-Mellon Univ. Publ., 1979, 210 p.
21. Jackson Jr., Philip C. Introduction to Artificial Intelligence. Dover Publ., 1985, 513 p. (Russ. ed.: Moscow, 2001, 624 p.).