Pattern recognition

A branch of mathematical cybernetics devising principles and methods for the classification and identification of objects, phenomena, processes, signals, and situations, i.e. of all those objects that can be described by a finite set of features or properties characterizing the object.

A description of an object (a sample) is an $n$-dimensional vector, where $n$ is the number of features used to characterize the object and the $i$-th coordinate of the vector is equal to the value of the $i$-th feature, $i=1,\ldots,n$. It is permissible for a description to contain no information about the values of some of the features. If it is necessary to classify given objects into several classes (patterns) solely on the basis of their descriptions, where the number of classes need not be specified, then the problem of recognition is called a taxonomy problem (cluster analysis, learning without a teacher, self-education). For the proper problems of pattern recognition (learning with a teacher), apart from the descriptions of the objects additional information is needed about the inclusion of some of these objects into one class (pattern) or another. The number of classes is finite and specified. They may overlap.

A set of descriptions of objects for which the patterns to which they belong are known constitutes a so-called training sequence (design set). The fundamental problem of pattern recognition is to determine, on the basis of a training sequence, the class which the sample to be classified or identified belongs to. Any problem of decision making can be reduced to such a scheme as long as the process of decision making is based mainly on the analysis of previously-gained experience.

The applied problems that can be solved by methods of pattern recognition arise in the identification of typed- and handwritten texts, the identification of photographic images, in automatic speech recognition, in medical diagnostics, in geological prediction, in the prediction of properties of chemical compounds, in the evaluation of situations in economics, politics and commercial production, in the classification of sociological data, etc. For solving such problems a great number of so-called heuristic recognition algorithms have been accumulated, each oriented to specific properties of a problem. Moreover, models of recognition algorithms have been constructed, based on certain intuitive principles, i.e. families of algorithms for solving classification problems. The most widely used are: models based on the potential principle; models based on the partition principle, specifying a class of surfaces discriminating the patterns; models for calculating estimates (voting models); as well as structural and statistical models.

At the model level the problem consists of finding a recognition algorithm (a model for calculating estimates) of extremal quality. The quality of a recognition algorithm is generally judged by the results it produces on a certain test set of objects (a test sequence) for which the true classification is a priori known. In developing the general theory of recognition algorithms the most complete results have been obtained within an algebraic framework. A recognition algorithm is represented by a composition of a recognition operator and a decision rule. Introducing operations of addition, multiplication and multiplication by a scalar for recognition operators allows one to prove that a recognition algorithm of extremal quality on any test sequence exists within some algebraic extension of the initial set of recognition operators.

The problems of pattern recognition also include problems of data reduction in the descriptions of the initial objects and the selection of relevant informative features.

References

[1]	Yu.I. Zhuravlev, "An algebraic approach to the solution of pattern recognition and identification problems" Probl. Kibernet. , 33 (1978) pp. 5–68; 232 (In Russian)
[2]	M.A. Aizerman, E.M. Braverman, L.I. Rozonoer, "The method of potential functions in the theory of computer learning" , Moscow (1970) (In Russian)
[3]	V.N. Vapnik, A.Ya. Chervonenkis, "The theory of pattern recognition" , Moscow (1974) (In Russian)
[4]	K.S. Fu, "Sequential methods in pattern recognition and learning" , Acad. Press (1968)

Comments

One usually finds the terms supervised and unsupervised learning in the English literature, instead of learning with and without a teacher. For a comparative discussion, see [a12].

The research area as described in the main article above includes the domain of inductive inference and machine learning. Both subjects deal with the theory and programming of the process of collecting structural and algorithmic information about concepts from positive and/or negative examples for these concepts. The term "pattern recognition" in the West is restricted to the investigation of structures with a clear geometrical or sequential structure. Pattern recognition represents an inherent task in applied areas like computer vision, signal analysis, speech understanding, natural language analysis, and various applications in artificial intelligence. A specific form of pattern recognition is the process of pattern matching, where some given input pattern must be compared to another input stream of data and all occurrences of the pattern in the data must be discovered. For this problem efficient linear-time algorithms have been proposed in [a1] and [a2].

References

[a1]	R.S. Boyer, J.S. Moore, "A fast string searching algorithm" Comm. Assoc. Comput. Mach. , 20 (1977) pp. 762–772
[a2]	D.E. Knuth, J.H. Morris, V.R. Pratt, "Fast pattern matching in strings" SIAM J. Comput. , 6 (1977) pp. 240–267
[a3]	D. Angluin, C. Smith, "Inductive inference: theory and methods" Computing Surveys , 15 (1983) pp. 237–269
[a4]	E.M. Gold, "Language identification in the limit" Inform. and Control , 10 (1967) pp. 447–474
[a5]	L.G. Valiant, "A theory of the learnable" Comm. Assoc. Comput. Mach. , 27 (1984) pp. 1134–1142
[a6]	H.L. Andrews, "Introduction to mathematical techniques in pattern recognition" , Wiley (Interscience) (1972)
[a7]	O. Duda, P.E. Hart, "Pattern classification and scene analysis" , Wiley (1973)
[a8]	K.S. Fu, A.C. Kak, "Syntactic methods in pattern rcognition" , Acad. Press (1974)
[a9]	U. Grenander, "Lectures in pattern theory" , 1–3 , Springer (1976–1979)
[a10]	J. Sklansky, "Pattern recognition: introduction and foundations" , Dowden, Hutchinson & Ross (1973)
[a11]	J.T. Tou, R.C. Gonzales, "Pattern recognition principles" , Addison-Wesley (1974)
[a12]	Ya.Z. Tsypkin, "Foundations of the theory of learning systems" , Acad. Press (1973) (Translated from Russian)
[a13]	J.R. Ullmann, "Pattern recognition techniques" , Crane, Russak & Co. (1973)