Library Subscription: Guest
Journal of Automation and Information Sciences

Published 12 issues per year

ISSN Print: 1064-2315

ISSN Online: 2163-9337

SJR: 0.173 SNIP: 0.588 CiteScore™:: 2

Indexed in

More
Purchase $100.00(open in a new tab) Check subscription Download MARC record(open in a new tab) Get Permissions(open in a new tab)

Interrelation of Pattern Recognition, Machine Thinking and Learning Problems

Volume 52, Issue 5, 2020, pp. 51-78
DOI: 10.1615/JAutomatInfScien.v52.i5.50
Get accessGet access
Vladimir I. Gritsenko
International Research and Training Center of Information Technologies and Systems of National Academy of Sciences of Ukraine and Ministry of Education and Science of Ukraine, Kiev
Mikhail I. Schlesinger
International Research and Training Center of Information Technologies and Systems of National Academy of Sciences of Ukraine and Ministry of Education and Science of Ukraine, Kiev

ABSTRACT

The paper reviews the state of the art in structural recognition − one of the areas of modern pattern recognition. It is shown that the main problems of structural recognition go beyond the problems of machine learning, and thereby slightly moderates the revived idea that the pattern recognition problem is completely exhausted by the machine learning problem. At the same time, it is shown that the basic concepts and problems of structural recognition form the base for formalizing a certain class of thought processes that differ from the learning processes and are called imaginative thinking. The mathematical base of the works included in the review is the classical theory of Constraint Satisfaction Problem − one of the acknowledged paradigms of machine thinking. It is shown how the application of this theory to real recognition problems necessitates its further generalizations, which in turn expand the concept of machine thinking, the formalization of which this theory was originally oriented to. The generalized problem of structural recognition and imaginative thinking is formulated, a particular case of which is the classical Constraint Satisfaction Problem. For the Gibbs statistical model of recognizable objects, it is shown that the recognition of these objects is reduced to one or another particular case of a generalized structural recognition problem. For more general statistical models, not necessarily Gibbs ones, the analysis of the known learning procedures is carried out when they are used with learning information of a limited volume. The flaw of these procedures, known as the effect of short samples, is studied, its causes and ways of overcoming are shown.

KEY WORDS: pattern recognition, machine learning, constraint satisfaction problem, Gibbs fields, submodular minimization
REFERENCES

  1. Shannon C., The Bandwagon, Trans. IRE, 1956, 3, IT-2, No. 1. Works on information theory and cybernetics [Russian translation], Izdatelstvo inostrannaya literatura, Moscow, 1963.

  2. Vintsyuk T.K., Speech recognition by dynamic programming methods, Kibernetika, 1968, No. 1, 81-88.

  3. Vintsyuk T.K., Analysis, recognition and interpretation of speech signals [in Russian], Naukova dumka, Kiev, 1987.

  4. Kovalevskiy V.A., Optimal recognition algorithm for some pattern sequences, Kibernetika, 1967, No. 4, 75-80.

  5. Kovalevskiy V.A., Methods of optimal solutions in pattern recognition [in Russian], Nauka, Moscow, 1976.

  6. Nariniani A.S., Uncertainty in knowledge presentation and processing systems, Izvestiya AN SSSR, Tekhn. Kibernetika, 1986, No. 5, 3-38.

  7. Nariniani A.S., Telerman V.V., UshakovD.M., Shvetsov I.E., Constrained programming and underdetermined models, Informatsionnyye tekhnologii, 1998, No. 5.

  8. Gritsenko V.I., SchlesingerM.I., Formal models, problems and algorithms of imaginative thinking. AUTOMATICS-2011. Materialy 18-oi Mizhnarodnoi konferentsii z avtomatychnogo upravlinnya (Lviv, 28-30 veresnya, 2011), 110-113.

  9. Rossi F., van BeekP., Walsh T., Handbook of constraint programming, Foundations of Artificial Intelligence, Elsevier.

  10. Shcherbina O.A., Constrains satisfaction and constrained programming, Intellektualnyye sistemy, 2011, 15, No. 1-4, 53-170.

  11. Pelillo M., Hancock E., Energy minimization methods in computer vision and pattern recognition, 11th International Conference. EMMCVPR 2017, Venice, Italy, October 30 - November 1, 2017, Lecture Notes in Computer Science, 10746, Springer 2018.

  12. Ruttkay Zs., Fuzzy constraint satisfaction, In Proc. 3rd IEEE International Conference on Fuzzy Systems, 1994, 1263-1268.

  13. Cooper M.C., Reduction operations in fuzzy or valued constraint satisfaction, Fuzzy Sets and Systems, 2003,134, 311-342, www.elsevier.com/locate/fss.

  14. VodolazskiyE.V., FlakhB., SchlesingerM.I., Minimax discrete optimization problems invariant with respect to majority operators, ZhVMMF, 2014, 54, No. 8, 1368-1378.

  15. Cohen D.A., Cooper M.C., JeavonsP.G., KrokhinA.A., The complexity of soft constraint satisfaction, Artificial Intelligence, 2006,170, 983-1016, www.elsevier.com/locate/artint.

  16. JeavonsP.G., Krokhin A.A., Zivny S., The complexity of valued constraint satisfaction, Bulletin of EATCS, 2014.

  17. Bistarelli S, MontanariU., Rossi F., SchiexT., Verfaillie G., FargierH., Semiring-Based CSPs and Valued CSPs, Frameworks, Properties, and Comparison, Constraints, 1999, 4, No. 3, 199-240.

  18. Schlesinger M.I., Mathematical means of images processing [in Russian], Naukova dumka, Kiev, 1989.

  19. Rollon E., Flerova N., Dechter R., Inference schemes for m best solutions for soft CSPs, Proceedings of Workshop on Preferences and Soft Constraints, 2011.

  20. Flerova N., MarinescuR., Dechter R., Searching for the M best solutions in graphical models, Journal of Artificial Intelligence Research, 2016, 55, 889-952.

  21. SchlesingerM.I., FlakhB., VodolazskiyE.V., Search for given number of solutions of fuzzy constraints system, Kibernetika i sistemnyi analiz, 2018, No. 1, 67-83.

  22. Schlesinger M.I., Pattern recognition as implementation of certain subclass of thinking processes, Upravlyayushchie sistemy i mashiny, 2017, No. 2, 20-37.

  23. JeavonsP., CohenM., CooperM., Constrarints, consistency and closure, Artificial Intelligence, 1998, 101(1-2), 251-265.

  24. Bulatov A., Mal'tsev constraints are tractable. Technical report PRG-RR-02-05, Oxford University, 2002.

  25. Bulatov A., Tractable conservative constraint satisfaction problems, LICS, 2003.

  26. Cohen D.A., JeavonsP.G., The complexity of constraint languages, Handbook of Constraint Programming, Elsevier, 2006, 245-280.

  27. Ishikawa H., Geiger D., Segmentation by grouping junctions, IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1998, 125-131.

  28. Lovasz L., Submodular functions and convexity. Ed. by A. Bachem, M. Grotschel, B. Korte, Mathematical programming - the state of the art, Springer-Verlag, New York, 1983, 235-257.

  29. BoykovY., Kolmogorov V., An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision, PAMI, 2004, 26(9).

  30. Boykov Y., Veksler O., Zabih R., Fast approximate energy minimization via graph cuts, IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), 2001, 23(11), 1222-1239.

  31. Kolmogorov V., Zabih R., What energy functions can be minimized via graph cuts? Eur. Conf. on Comp. Vision (ECCV), Springer-Verlag, 2002, 65-81. See also PAMI, 26(2):147159, February 2004.

  32. Osokin A., VetrovD., Submodular relaxation for Inference in Markov random fields, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37, No. 7, 1347-1359.

  33. Osokin A., VetrovD., KolmogorovV., Submodular decomposition framework for inference in associative Markov networks with global constraints, IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2011, 1889-1896.

  34. Schlesinger M.I., Syntactic analysis of two-dimensional visual signals under interference, Kibernetika, 1976, No. 4, 113-130.

  35. KovalV.K., SchlesingerM.I., Two-dimensional programming in problems of image analysis, Avtomatika i telemekhanika, 1976, No. 8, 149-168.

  36. SchlesingerM.I., FlachB., Some solvable subclasses of structural recognition problems, Czech Pattern Recognition Workshop, 2000, 55-62.

  37. WainwrightM.J., Jaakkola T.S., Willsky A.S., MAP estimation via agreement on (hyper)trees: Message-passing and linear-programming approaches, IEEE Transactions on Information Theory, 2005, 51(11), 3697-3717.

  38. Kolmogorov V., Convergent Tree-reweighted message passing for energy minimization, IEEE Transactions on Pattern Analysis and Machine Intelligence, 28, No. 10, 1568-1583.

  39. SchlesingerM.I., GiginyakV.V., Solution of (MAX,+)-problems of structural recognition via their equivalent transformations, Upravlyayushchie sistemy i mashiny, 2007, Ch. 1, No. 1, 3-15, Ch. 2, No. 2, 5-17.

  40. Werner T., A linear programming approach to max-sum problem: A Review, IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI), 2007, 29(7), 1165-1179.

  41. Werner T., Revisiting the linear programming relaxation approach to Gibbs energy minimization and weighted constraint satisfaction, IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI), 2010, 32(8), 1474-1488.

  42. Komodakis N., Paragios N., Tziritas G., Mrf energy minimization and beyond via dual decomposition, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(3), 531-552.

  43. 43. Bulatov A., GroheM., The complexity of partition functions, Elsevier, Theoretical Computer Science, 2005, 348, No. 2-3, 148-186.

  44. 44. Lynch S., Introduction to applied Bayesian statistics and estimation for social scientists, Berlin ... Tokyo, Springer, 2007.

  45. 45. WainwrightM., Jordan M., Graphical models, exponential families, and variational inference, Foundations and Trends in Machine Learning, 2008,1, No. 1-2, 1-305.

  46. 46. Schlesinger M., Vodolazskiy E., Minimax deviation strategies for machine learning and recognition with short learning samples, An Article, 2017 (arXiv preprint arXiv:1707.04849).

CITED BY

  1. Gritsenko Volodymyr I., The State of Art and Prospects Development for the Intelligent Information Technologies. To the 25th Anniversary of the International Research and Training Centre for Information Technologies and Systems, Control Systems and Computers, 1 (297), 2022. Crossref

826 Article views 14 Article downloads Metrics
826 VIEWS 14 DOWNLOADS 1 Crossref CITATIONS Google
Scholar CITATIONS

Articles with similar content:

Structural Recognition of the Nonlinear Discrete Dynamic Objects Based on the Generalized Probabilistic Criteria Journal of Automation and Information Sciences, Vol.46, 2014, issue 1
Sergey V. Sokolov, Pavel A. Kucherenko
Simulation of Quantum Control Systems. Part I. System Analysis of Physical Constraints Journal of Automation and Information Sciences, Vol.30, 1998, issue 2-3
Sergey A. Smirnov
The Transportation Problem under Uncertainty Journal of Automation and Information Sciences, Vol.52, 2020, issue 4
Alexander A. Pavlov , Elena G. Zhdanova
GEOMETRIC ASPECTS OF THE THEORY OF INCOMPATIBLE DEFORMATIONS. PART II. STRAIN AND STRESS MEASURES Nanoscience and Technology: An International Journal, Vol.10, 2019, issue 2
S. A. Lychev, K. G. Koifman
Algorithms for Solving the Systems of Linear Constraints with Integer Coefficients in the Set {0, 1} Journal of Automation and Information Sciences, Vol.51, 2019, issue 7
Vasiliy T. Antonyuk , Sergey L. Kryvyi

Latest Issue

Modeling of Configurations Formed when Using Microneedle Systems Gennadiy V. Sandrakov , Sergey I. Lyashko, Elena S. Bondar , Nataliya I. Lyashko , Vladimir V. Semenov Properties of Large Deviations of Empirical Estimates in a Stochastic Optimization Problem for a Homogeneous Random Field Pavel S. Knopov, Evgeniya J. Kasitskaya The Dynamics of One Arms Race Mathematical Model with a Delay Andrey V. Shatyrko, Denis Ya. Khusainov, Bedrik Puzha , Veronika Novotna Some Ways to Modeling Input Data for Information Search in the Library of Standards when Solving Semantics Problems Nadezhda K. Tymofijeva Method for Constructing Primitive Polynomials for Cryptographic Subsystems of Dependable Automated Systems Gennadiy N. Gulak Complete Asymptotics of Approximations by Certain Singular Integrals in Mathematical Modeling Konstantin N. Zhyhallo Index, Volume 52, 2020
Begell Digital Portal Begell Digital Library eBooks Journals References & Proceedings Research Collections Prices and Subscription Policies Begell House Contact Us Language English 中文 Русский Português German French Spain