Pattern recognition

Pattern recognition is generally categorized according to the type of learning procedure used to generate the output value. Supervised learning assumes that a set of training data (the training set) has been provided, consisting of a set of instances that have been properly labeled by hand with the correct output. A learning procedure then generates a model that attempts to meet two sometimes conflicting objectives: Perform as well as possible on the training data, and generalize as well as possible to new data (usually, this means being as simple as possible, for some technical definition of "simple", in accordance with Occam's Razor, discussed below). Unsupervised learning, on the other hand, assumes training data that has not been hand-labeled, and attempts to find inherent patterns in the data that can then be used to determine the correct output value for new data instances.[5] A combination of the two that has recently been explored is semi-supervised learning, which uses a combination of labeled and unlabeled data (typically a small set of labeled data combined with a large amount of unlabeled data). Note that in cases of unsupervised learning, there may be no training data at all to speak of; in other words, the data to be labeled is the training data.

Note that sometimes different terms are used to describe the corresponding supervised and unsupervised learning procedures for the same type of output. For example, the unsupervised equivalent of classification is normally known as clustering, based on the common perception of the task as involving no training data to speak of, and of grouping the input data into clusters based on some inherent similarity measure (e.g. the distance between instances, considered as vectors in a multi-dimensional vector space), rather than assigning each input instance into one of a set of pre-defined classes. In some fields, the terminology is different: For example, in community ecology, the term "classification" is used to refer to what is commonly known as "clustering".

The piece of input data for which an output value is generated is formally termed an instance. The instance is formally described by a vector of features, which together constitute a description of all known characteristics of the instance. (These feature vectors can be seen as defining points in an appropriate multidimensional space, and methods for manipulating vectors in vector spaces can be correspondingly applied to them, such as computing the dot product or the angle between two vectors.) Typically, features are either categorical (also known as nominal, i.e., consisting of one of a set of unordered items, such as a gender of "male" or "female", or a blood type of "A", "B", "AB" or "O"), ordinal (consisting of one of a set of ordered items, e.g., "large", "medium" or "small"), integer-valued (e.g., a count of the number of occurrences of a particular word in an email) or real-valued (e.g., a measurement of blood pressure). Often, categorical and ordinal data are grouped together; likewise for integer-valued and real-valued data. Furthermore, many algorithms work only in terms of categorical data and require that real-valued or integer-valued data be discretized into groups (e.g., less than 5, between 5 and 10, or greater than 10).

Formally, the problem of pattern recognition can be stated as follows: Given an unknown function ${\displaystyle g:{\mathcal {X}}\rightarrow {\mathcal {Y}}}$ (the ground truth) that maps input instances ${\displaystyle {\boldsymbol {x}}\in {\mathcal {X}}}$ to output labels ${\displaystyle y\in {\mathcal {Y}}}$, along with training data ${\displaystyle \mathbf {D} =\{({\boldsymbol {x}}_{1},y_{1}),\dots ,({\boldsymbol {x}}_{n},y_{n})\}}$ assumed to represent accurate examples of the mapping, produce a function ${\displaystyle h:{\mathcal {X}}\rightarrow {\mathcal {Y}}}$ that approximates as closely as possible the correct mapping ${\displaystyle g}$. (For example, if the problem is filtering spam, then ${\displaystyle {\boldsymbol {x}}_{i}}$ is some representation of an email and ${\displaystyle y}$ is either "spam" or "non-spam"). In order for this to be a well-defined problem, "approximates as closely as possible" needs to be defined rigorously. In decision theory, this is defined by specifying a loss function or cost function that assigns a specific value to "loss" resulting from producing an incorrect label. The goal then is to minimize the expected loss, with the expectation taken over the probability distribution of ${\displaystyle {\mathcal {X}}}$. In practice, neither the distribution of ${\displaystyle {\mathcal {X}}}$ nor the ground truth function ${\displaystyle g:{\mathcal {X}}\rightarrow {\mathcal {Y}}}$ are known exactly, but can be computed only empirically by collecting a large number of samples of ${\displaystyle {\mathcal {X}}}$ and hand-labeling them using the correct value of ${\displaystyle {\mathcal {Y}}}$ (a time-consuming process, which is typically the limiting factor in the amount of data of this sort that can be collected). The particular loss function depends on the type of label being predicted. For example, in the case of classification, the simple zero-one loss function is often sufficient. This corresponds simply to assigning a loss of 1 to any incorrect labeling and implies that the optimal classifier minimizes the error rate on independent test data (i.e. counting up the fraction of instances that the learned function ${\displaystyle h:{\mathcal {X}}\rightarrow {\mathcal {Y}}}$ labels wrongly, which is equivalent to maximizing the number of correctly classified instances). The goal of the learning procedure is then to minimize the error rate (maximize the correctness) on a "typical" test set.

For a probabilistic pattern recognizer, the problem is instead to estimate the probability of each possible output label given a particular input instance, i.e., to estimate a function of the form

${\displaystyle p({\rm {label}}|{\boldsymbol {x}},{\boldsymbol {\theta }})=f\left({\boldsymbol {x}};{\boldsymbol {\theta }}\right)}$

where the feature vector input is ${\displaystyle {\boldsymbol {x}}}$, and the function f is typically parameterized by some parameters ${\displaystyle {\boldsymbol {\theta }}}$.[9] In a discriminative approach to the problem, f is estimated directly. In a generative approach, however, the inverse probability ${\displaystyle p({{\boldsymbol {x}}|{\rm {label}}})}$ is instead estimated and combined with the prior probability ${\displaystyle p({\rm {label}}|{\boldsymbol {\theta }})}$ using Bayes' rule, as follows:

${\displaystyle p({\rm {label}}|{\boldsymbol {x}},{\boldsymbol {\theta }})={\frac {p({{\boldsymbol {x}}|{\rm {label,{\boldsymbol {\theta }}}}})p({\rm {label|{\boldsymbol {\theta }}}})}{\sum _{L\in {\text{all labels}}}p({\boldsymbol {x}}|L)p(L|{\boldsymbol {\theta }})}}.}$

When the labels are continuously distributed (e.g., in regression analysis), the denominator involves integration rather than summation:

${\displaystyle p({\rm {label}}|{\boldsymbol {x}},{\boldsymbol {\theta }})={\frac {p({{\boldsymbol {x}}|{\rm {label,{\boldsymbol {\theta }}}}})p({\rm {label|{\boldsymbol {\theta }}}})}{\int _{L\in {\text{all labels}}}p({\boldsymbol {x}}|L)p(L|{\boldsymbol {\theta }})\operatorname {d} L}}.}$

The value of ${\displaystyle {\boldsymbol {\theta }}}$ is typically learned using maximum a posteriori (MAP) estimation. This finds the best value that simultaneously meets two conflicting objects: To perform as well as possible on the training data (smallest error-rate) and to find the simplest possible model. Essentially, this combines maximum likelihood estimation with a regularization procedure that favors simpler models over more complex models. In a Bayesian context, the regularization procedure can be viewed as placing a prior probability ${\displaystyle p({\boldsymbol {\theta }})}$ on different values of ${\displaystyle {\boldsymbol {\theta }}}$. Mathematically:

${\displaystyle {\boldsymbol {\theta }}^{*}=\arg \max _{\boldsymbol {\theta }}p({\boldsymbol {\theta }}|\mathbf {D} )}$

where ${\displaystyle {\boldsymbol {\theta }}^{*}}$ is the value used for ${\displaystyle {\boldsymbol {\theta }}}$ in the subsequent evaluation procedure, and ${\displaystyle p({\boldsymbol {\theta }}|\mathbf {D} )}$, the posterior probability of ${\displaystyle {\boldsymbol {\theta }}}$, is given by

${\displaystyle p({\boldsymbol {\theta }}|\mathbf {D} )=\left[\prod _{i=1}^{n}p(y_{i}|{\boldsymbol {x}}_{i},{\boldsymbol {\theta }})\right]p({\boldsymbol {\theta }}).}$

In the Bayesian approach to this problem, instead of choosing a single parameter vector ${\displaystyle {\boldsymbol {\theta }}^{*}}$, the probability of a given label for a new instance ${\displaystyle {\boldsymbol {x}}}$ is computed by integrating over all possible values of ${\displaystyle {\boldsymbol {\theta }}}$, weighted according to the posterior probability:

${\displaystyle p({\rm {label}}|{\boldsymbol {x}})=\int p({\rm {label}}|{\boldsymbol {x}},{\boldsymbol {\theta }})p({\boldsymbol {\theta }}|\mathbf {D} )\operatorname {d} {\boldsymbol {\theta }}.}$

The face was automatically detected by special software.

Within medical science, pattern recognition is the basis for computer-aided diagnosis (CAD) systems. CAD describes a procedure that supports the doctor's interpretations and findings. Other typical applications of pattern recognition techniques are automatic speech recognition, speaker identification, classification of text into several categories (e.g., spam/non-spam email messages), the automatic recognition of handwriting on postal envelopes, automatic recognition of images of human faces, or handwriting image extraction from medical forms.[10][11] The last two examples form the subtopic image analysis of pattern recognition that deals with digital images as input to pattern recognition systems.[12][13]

Optical character recognition is a classic example of the application of a pattern classifier, see OCR-example. The method of signing one's name was captured with stylus and overlay starting in 1990. The strokes, speed, relative min, relative max, acceleration and pressure is used to uniquely identify and confirm identity. Banks were first offered this technology, but were content to collect from the FDIC for any bank fraud and did not want to inconvenience customers.

Pattern recognition has many real-world applications in image processing, some examples include:

• identification and authentication: e.g., license plate recognition,[14] fingerprint analysis, face detection/verification;,[15] and voice-based authentication.[16]
• medical diagnosis: e.g., screening for cervical cancer (Papnet),[17] breast tumors or heart sounds;
• defence: various navigation and guidance systems, target recognition systems, shape recognition technology etc.
• mobility: advanced driver assistance systems, autonomous vehicle technology, etc.[18][19][20][21][22]

In psychology, pattern recognition (making sense of and identifying objects) is closely related to perception, which explains how the sensory inputs humans receive are made meaningful. Pattern recognition can be thought of in two different ways: the first being template matching and the second being feature detection. A template is a pattern used to produce items of the same proportions. The template-matching hypothesis suggests that incoming stimuli are compared with templates in the long-term memory. If there is a match, the stimulus is identified. Feature detection models, such as the Pandemonium system for classifying letters (Selfridge, 1959), suggest that the stimuli are broken down into their component parts for identification. For example, a capital E has three horizontal lines and one vertical line.[23]

Algorithms for pattern recognition depend on the type of label output, on whether learning is supervised or unsupervised, and on whether the algorithm is statistical or non-statistical in nature. Statistical algorithms can further be categorized as generative or discriminative.

This article is based on material taken from the Free On-line Dictionary of Computing prior to 1 November 2008 and incorporated under the "relicensing" terms of the GFDL, version 1.3 or later.

• Fukunaga, Keinosuke (1990). Introduction to Statistical Pattern Recognition (2nd ed.). Boston: Academic Press. ISBN 978-0-12-269851-4.
• Hornegger, Joachim; Paulus, Dietrich W. R. (1999). Applied Pattern Recognition: A Practical Introduction to Image and Speech Processing in C++ (2nd ed.). San Francisco: Morgan Kaufmann Publishers. ISBN 978-3-528-15558-2.
• Schuermann, Juergen (1996). Pattern Classification: A Unified View of Statistical and Neural Approaches. New York: Wiley. ISBN 978-0-471-13534-0.
• Godfried T. Toussaint, ed. (1988). Computational Morphology. Amsterdam: North-Holland Publishing Company. ISBN 9781483296722.
• Kulikowski, Casimir A.; Weiss, Sholom M. (1991). Computer Systems That Learn: Classification and Prediction Methods from Statistics, Neural Nets, Machine Learning, and Expert Systems. Machine Learning. San Francisco: Morgan Kaufmann Publishers. ISBN 978-1-55860-065-2.
• Duda, Richard O.; Hart, Peter E.; Stork, David G. (2000). Pattern Classification (2nd ed.). Wiley-Interscience. ISBN 978-0471056690.
• Jain, Anil.K.; Duin, Robert.P.W.; Mao, Jianchang (2000). "Statistical pattern recognition: a review". IEEE Transactions on Pattern Analysis and Machine Intelligence. 22 (1): 4–37. CiteSeerX 10.1.1.123.8151. doi:10.1109/34.824819.
• An introductory tutorial to classifiers (introducing the basic terms, with numeric example)

• The International Association for Pattern Recognition
• List of Pattern Recognition web sites
• Journal of Pattern Recognition Research
• Pattern Recognition Info
• Pattern Recognition (Journal of the Pattern Recognition Society)
• International Journal of Pattern Recognition and Artificial Intelligence
• International Journal of Applied Pattern Recognition
• Open Pattern Recognition Project, intended to be an open source platform for sharing algorithms of pattern recognition
• Improved Fast Pattern Matching Improved Fast Pattern Matching