Publishing house Radiotekhnika

"Publishing house Radiotekhnika":
scientific and technical literature.
Books and journals of publishing houses: IPRZHR, RS-PRESS, SCIENCE-PRESS

Тел.: +7 (495) 625-9241


Stochastic search of preimages based on the clustering of knowledge in the fuzzy LP-inference


A. N. Shmarin – Post-graduate Student, Voronezh State University

The increase in the volumes and complexity of processed information makes the use of artificial intelligence systems more and more actual. In such systems, one of the most widespread knowledge representation models is the production model and search algorithms are based on the inference engine. In practice, the values measurement of the features of the classified objects from some data domain is time-consuming operation for many problems. These tasks appear, for example, when the robot explores the surface of another planet. If the goal of the robot is to get to some rock, but the future route is observed only partially, then the robot should try to make the best decision on how to achieve the goal, taking into account limitation of the resources available to additional exploration of terrain. Another example, in which the cost of obtaining new information may be high, is the commercial medicine. To minimize costs, it is necessary to find the acceptable treatment method using the minimum number of analyses performed in minimal time. The delay in providing treatment, caused by the additional analyses, leads to increased costs. Moreover, the patient's condition, which was not provided timely assistance, can significantly deteriorate. Also, the cost of additional research is essential in the field of mineral exploration. It can turn out that more cost-effective solution is to begin drilling, if confidence of the success is 95%, than to spend the considerable resources to achieve the 98% confidence.
The complexity of the operations of data acquisition necessary for decision-making, leads to the problem of minimizing the number of requests for information about values of the features of the classified object during inference. This problem is NP-hard. To achieve global minimization there is the general method of LP-inference with exponential computational complexity relative to the number of atomic facts in the knowledge base. However, some of its heuristic modifications have polynomial complexity. The goal of the provided research is development of the approximating method to better minimize the number of feature values requests performed in the inference.
Earlier, the questions of implementation of computing approximate estimates of the number of layers without cycles in the fuzzy LP-inference task were considered. This paper presents the mathematical statement of the fuzzy LP-inference task, researches the fuzzy knowledge clustering method, and presents the implementation of the stochastic initial preimages search. This algorithm is designed for the iterative analysis of such subsets of productions, which most significantly influence to the relevancy. Presented approach can be applied to accelerate the reverse inference in production type systems of artificial intelli-gence.

  1. Dzharratano D., Rajli G. E'kspertny'e sistemy': princzipy' razrabotki i programmirovanie: Per. s angl. M.: Vil'yams. 2007. 1152 s.
  2. Maxortov S.D., Shmarin A.N. Optimizacziya metoda LP-vy'voda // Nejrokomp'yutery'. Razrabotka, primenenie. 2013. № 9. S. 59–63.
  3. Maxortov S.D. Osnovanny'j na reshetkax podxod k issledovaniyu i optimizaczii mnozhestva pravil uslovnoj sistemy' perepisy'vaniya termov // Intellektual'ny'e sistemy'. Teoriya i prilozheniya. 2009. T. 13. S. 51–68.
  4. Maxortov S.D. Integrirovannaya sreda logicheskogo programmirovaniya LPExpert // Informaczionny'e texnologii. 2009. № 12. C. 65–66.
  5. Bolotova S.Ju., Maxortov S.D. Algoritmy' relevantnogo obratnogo vy'voda, osnovanny'e na reshenii produkczionno-logicheskix uravnenij // Iskusstvenny'j intellekt i prinyatie reshenij. 2011. № 2. S. 40–50.
  6. Shmarin A.N., Maxortov S.D. O priblizhenny'x oczenkax kolichestva sloev bez cziklov v zadache nechetkogo LP-vy'voda // Nejrokomp'yutery'. Razrabotka, primenenie. 2015. № 12. S. 44–51.
  7. Salij V.N., Bogomolov V.A. Algebraicheskie osnovy' teorii diskretny'x sistem. M.: Fizmatlit. 1997. 368 s.
  8. Pegat A. Nechetkoe modelirovanie i upravlenie. M.: Binom. Laboratoriya znanij. 2013. 798 s.
  9. Maxortov S.D. LP-struktury' dlya obosnovaniya i avtomatizaczii refaktoringa v ob''ektno-orientirovannom programmirovanii // Programmnaya inzheneriya. 2010. № 2. S. 15–21.
  10. Shmarin A.N. O realizaczii priblizheniya chisla sloev bez cziklov v zadache nechetkogo LP-vy'voda // Programmnaya inzheneriya. 2016. № 7. S. 330–336.
  11. Svidetel'stvo o gosudarstvennoj registraczii programmy' dlya E'VM № 2017613295 / A.N. Shmarin. Fuzzy LPExpert; № 2017610737; zayavl. 24.01.2017; zaregistr. 14.03.2017, Byul. № 3.
  12. Peixoto T.P. Nonparametric Bayesian inference of the microcanonical stochastic block model // Phys. Rev., 2017. № E 95. P. 24. doi:10.1103/PhysRevE.95.012317
  13. Ore O. Teoriya grafov: Per. s angl. M.: LIBROKOM. 2009. 354 s.
  14. Schaeffer S.E. Graph clustering // Computer Science Review. 2007. V. I. P. 27–64.
  15. Ermakov S.M. Metod Monte-Karlo v vy'chislitel'noj matematike. SPb.: Nevskij Dialekt. 2009. 192 s.
  16. Kanunfo T., Mount D.M., Netanyahu N.S. An Efficient k-Means Clustering Algorithm: Analysis and Implementation // IEEE Transactions on pattern analysis and machine intelligence, 2002. V. 24. № 7. P. 881–892.
  17. Flax P. Mashinnoe obuchenie: Nauka i iskusstvo postroeniya algoritmov, kotory'e izvlekayut znaniya iz danny'x: Per. s angl. M.: DMK. 2015. 400 s.
  18. Abraham A., Pedregosa F., Eickenberg M. Machine Learning for Neuroimaging with Scikit-Learn. // Frontiers in Neuroinformatics. 2014. № 8. P. 11. doi:10.3389/fninf.2014.00014
  19. Patwary M.M., Palsetia D.A., New Scalable Parallel DBSCAN Algorithm Using the Disjoint-Set Data Structure // IEEE. 2012. V. 12. P. 10–16.
  20. Bressert E., SciPy and NumPy. USA Sebastopol: O’Reilly. 2013. 57 pp.
  21. Chechkin A.V. Nejrokomp'yuternaya paradigma informatiki // Nejrokomp'yutery': razrabotka, primenenie. 2011. № 7. S. 3–9.

© Издательство «РАДИОТЕХНИКА», 2004-2017            Тел.: (495) 625-9241                   Designed by [SWAP]Studio