Pattern recognition

The piece of input data for which an output value is generated is formally termed an instance. The instance is formally described by a

• They output a confidence value associated with their choice. (Note that some other algorithms may also output confidence values, but in general, only for probabilistic algorithms is this value mathematically grounded in probability theory. Non-probabilistic confidence values can in general not be given any specific meaning, and only used to compare against other confidence values output by the same algorithm.)
• Correspondingly, they can abstain when the confidence of choosing any particular output is too low.
• Because of the probabilities output, probabilistic pattern-recognition algorithms can be more effectively incorporated into larger machine-learning tasks, in a way that partially or completely avoids the problem of error propagation.

Number of important feature variables

Feature selection algorithms attempt to directly prune out redundant or irrelevant features. A general introduction to feature selection which summarizes approaches and challenges, has been given.^[6] The complexity of feature-selection is, because of its non-monotonous character, an optimization problem where given a total of ${\displaystyle n}$ features the

${\displaystyle 2^{n}-1}$

${\displaystyle n}$

Techniques to transform the raw feature vectors (feature extraction) are sometimes used prior to application of the pattern-matching algorithm.

Problem statement

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

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

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

${\displaystyle {\boldsymbol {x}}}$

${\displaystyle {\boldsymbol {\theta }}}$

${\displaystyle p({{\boldsymbol {x}}|{\rm {label}}})}$

${\displaystyle p({\rm {label}}|{\boldsymbol {\theta }})}$

${\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

${\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 }}.}$

Frequentist or Bayesian approach to pattern recognition

The first pattern classifier – the linear discriminant presented by

. Also the probability of each class ${\displaystyle p({\rm {label}}|{\boldsymbol {\theta }})}$ is estimated from the collected dataset. Note that the usage of '

Bayes rule

' in a pattern classifier does not make the classification approach Bayesian.

Bayesian statistics has its origin in Greek philosophy where a distinction was already made between the 'a priori' and the 'a posteriori' knowledge. Later Kant defined his distinction between what is a priori known – before observation – and the empirical knowledge gained from observations. In a Bayesian pattern classifier, the class probabilities ${\displaystyle p({\rm {label}}|{\boldsymbol {\theta }})}$ can be chosen by the user, which are then a priori. Moreover, experience quantified as a priori parameter values can be weighted with empirical observations – using e.g., the

Optical character recognition is an example of the application of a pattern classifier. The method of signing one's name was captured with stylus and overlay starting in 1990.^[citation needed] 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.^{[citation needed]}

Pattern recognition has many real-world applications in image processing. Some examples include:

• identification and authentication: e.g.,
  voice-based authentication.^[15]
• medical diagnosis: e.g., screening for cervical cancer (Papnet),[16] breast tumors or heart sounds;
• defense: various navigation and guidance systems, target recognition systems, shape recognition technology etc.
• mobility:
  advanced driver assistance systems, autonomous vehicle technology, etc.^{[17][18][19][20][21]}

In psychology, pattern recognition is used to make sense of and identify objects, and is closely related to perception. This explains how the sensory inputs humans receive are made meaningful. Pattern recognition can be thought of in two different ways. The first concerns template matching and the second concerns 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. One observation is a capital E having three horizontal lines and one vertical line.^[22]

Algorithms

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 may contain embedded lists. Please help clean up the lists by removing items or incorporating them into the text of the article. (May 2014)

Classification methods (methods predicting categorical labels)

Parametric:^[23]

• Linear discriminant analysis
• Quadratic discriminant analysis
• Maximum entropy classifier (aka logistic regression, multinomial logistic regression
  ): Note that logistic regression is an algorithm for classification, despite its name. (The name comes from the fact that logistic regression uses an extension of a linear regression model to model the probability of an input being in a particular class.)

Nonparametric:[24]

• Decision trees, decision lists
• K-nearest-neighbor
  algorithms
• Naive Bayes classifier
• Neural networks
  (multi-layer perceptrons)
• Perceptrons
• Support vector machines
• Gene expression programming

Clustering methods (methods for classifying and predicting categorical labels)

• Categorical mixture models
• Hierarchical clustering (agglomerative or divisive)
• K-means clustering
• Correlation clustering
• Kernel principal component analysis (Kernel PCA)

Ensemble learning algorithms (supervised meta-algorithms for combining multiple learning algorithms together)

• Boosting (meta-algorithm)
• Bootstrap aggregating ("bagging")
• Ensemble averaging
• hierarchical mixture of experts

General methods for predicting arbitrarily-structured (sets of) labels

• Bayesian networks
• Markov random fields

Multilinear subspace learning algorithms (predicting labels of multidimensional data using tensor representations)

Unsupervised:

• Multilinear principal component analysis (MPCA)

Real-valued sequence labeling methods (predicting sequences of real-valued labels)

• Kalman filters
• Particle filters

Regression methods (predicting real-valued labels)

• Gaussian process regression
  (kriging)
• Linear regression and extensions
• Independent component analysis (ICA)
• Principal components analysis
  (PCA)

Sequence labeling methods (predicting sequences of categorical labels)

• Conditional random fields (CRFs)
• Hidden Markov models (HMMs)
• Maximum entropy Markov models
  (MEMMs)
• Recurrent neural networks
  (RNNs)
• Dynamic time warping (DTW)

See also

References