ВИЗНАЧЕННЯ ЕФЕКТИВНОСТІ МЕХАНІЗМІВ ЛОГІЧНОГО ВИВЕДЕННЯ
DOI:
https://doi.org/10.26906/SUNZ.2020.4.081Ключові слова:
продукційні системи, співставлення зі зразком, бенчмарки, ReteАнотація
Предметом дослідження в статті є алгоритми співставлення зі зразком, які використовуються в програмному інструментарії розробки систем, що базуються на правилах. Мета роботи - представлення особливостей вибору або генерації бенчмарків алгоритмів співставлення зі зразком в залежності від специфіки вирішуваних задач. В статті вирішуються наступні завдання: визначити проблематику тестових задач; провести аналіз концепцій базових алгоритмів співставлення зі зразком; провести аналіз існуючих бенчмарків алгоритмів співставлення зі зразком; виокремити основні підходи та методи формування бенчмарків. Методами, що аналізуються, є Rete, Treat та їх модифікації, а також методи та підходи до формування бенчмарків для аналізу продуктивності алгоритмів співставлення та систем, заснованих на правилах. Отримані наступні результати: для порівняльного аналізу представлено концепції базових алгоритмів співставлення зі зразком, що дозволило виокремити значимі характеристики, які впливають на продуктивність співставлення в термінах часу виконання та структури бази знань. Виокремлення характеристик відбувалося за двома підходами, які стосуються логічного виведення в системах, що базуються на правилах (rule-base) та для систем Semantic Web. Визначено базові тестові задачі, які використовуються в якості бенчмарків. Представлено основні бенчмарки алгоритмів співставлення зі зразком з відповідним визначенням специфіки області їх використання. Висновки: визначено проблеми аналізу ефективності механізмів логічного виведення для прикладних систем різного типу. Проведено аналіз та представлено концептуальні відмінності базових алгоритмів співставлення зі зразком, які впливають на вимоги до формування або вибору бенчмарків. На основі проведеного аналізу представлено основні характеристики бенчмарків для продукційних систем та систем Semantic Web. Визначено основні підходи та методи формування бенчмарків. Перспективним напрямком подальших досліджень вбачається вбачається створення нових тестових задач, які дозволять застосовувати представлення в термінах логіки першого порядку
Завантаження
Посилання
Riley G. Rearchitecting CLIPS. Business Rules Knowledge Base. October Rulefest 2008. available at: http://bizrules.info/conference/ORF2008DFW/GaryRiley_RearchitectingCLIPS_ORF2008.pdf (last accessed 20.10.20).
Miranker D. P. Treat: A better match algorithm for AI production systems. ArtificialIntelligence: SixthNationalConference AAAI-87. 1987. P.42—47.
Riley G. The CLIPS Implementation of the Rete Pattern Matching Algorithm. 2009. Corpus ID: 33742322
Bobek, S., Misiak, P. (2017), "Framework for Benchmarking Rule-Based Inference Engines", Artificial Intelligence and Soft Computing, ICAISC 2017, Lecture Notes in Computer Science, vol. 10246, Springer, Cham. P. 399-410. DOI:https://doi.org/10.1007/978-3-319-59060-8_36
S. Liang, P. Fodor, H. Wan, and M. Kifer, (2009), "OpenRuleBench: An analysis of the performance of rule engines", Proc.18th International Conference on World Wide Web, P.601–610. DOI: https://doi.org/10.1145/1526709.1526790.
Rattanasawad, T., Buranarach, M., Saikaew, K.R., Supnithi, T. (2018), "A Comparative Study of Rule-Based Inference Engines for the Semantic Web", IEICE Transactions on Information and Systems, January 2018, P. 82-89. DOI:https://doi.org/10.1587/transinf.2017SWP0004
Шаповалова С.І., Мажара О.О. Вибір оптимального алгоритму співставлення зі зразком при проектуванні продукційної системи. Східно-Європейський журнал передових технологій. 2014, Вип.2/2(68). С. 43-49.
Forgy C. On the Efficient Implementation of Production System. Ph.D. Dissertation. Carnegie Mellon University. 1979.210 p.
H. Cirstea C. Kirchner M. M., Moreau P. Production Systems and Rete Algorithm Formalisation. Research Report: ILOG,INRIA, 2004. URL: https://hal.inria.fr/inria-00280938/file/rete.formalisation.pdf.
Шаповалова С.І., Мажара О.О. Формалізація базових алгоритмів співставлення зі зразком в продукційних системах.Східно-Європейський журнал передових технологій. 2015. Вип.4/3(76). С. 22-27. DOI: 10.15587/1729-4061.2015.46571
Ligeza A. Logical Foundations for Rule-Based Systems. Studies in Computational Intelligence (SCI). 2006. 11.P.191-198.
Wright I. Marshall J. The execution kernel of RC++: RETE*, a faster RETE with TREAT as a special case. Int. J. Intell.Games & Simulation 2 (1). 2003. P.36-48.URL: https://books.google.com.ua/books?id=R5EHCAAAQBAJ
Hicks R.C., Wright K. (2009), "Performance Testing of Propositional Logic Inference Engines", Journal of ComputerInformation Systems, Published online. Vol. 49, P. 122-126.
Doorenbos R. Production Matching for Large Learning Systems. Ph.D. Dissertation. Carnegie Mellon University. 1995.208 p.
Hanson E.N., Hasan M.S. Gator: Anoptimized discrimination network for active database rule condition testing. Tech. Rep.93-036, CIS Department University of Florida. 1993. 27 p.
Kim M., Lee K., Kim Y., T. Kim, Lee Y, Cho S., Lee C. RETE-ADH: An Improvement to RETE forCompositeContextAware Service. International Journal of Distributed Sensor Networks. 2014 —11p. 69.DOI: 10.1155/2014/507160
Bouaud J., Zweigenbaum P. A reconstruction of conceptual graphs on top of a production system. Conceptual Structures:Theory and Implementation Ed. by H. Pfeiffer, T. Nagle. 1993. Vol. 754. P.125–136.
Shapovalova S. Generation of test bases of rules for the analysis of productivity of logical inference engine. InnovativeTechnologies and Scientific Solutions for Industries. 2020. No. 3(13). P. 88–96. DOI: https://doi.org/10.30837/ITSSI.2020.13.088.
