Background

A pattern recognition problem amounts to learning how to discriminate between data points belonging to two classes, defined by class labels , when given only a set of examples from each class. These problems are found in various applications, from automated handwriting recognition to medical expert systems, and pattern recognition or machine learning algorithms are routinely applied to solve them.

It may be helpful for newcomers to relate this to a more familiar problem: standard statistical hypothesis testing for one-dimensional , such as Student's t-test [1, ch. 8], can be viewed as a very simple kind of pattern recognition problem. Here, the hypotheses and correspond to classes , and the familiar

where is the mean of within-class means,

and , is called the decision rule or sometimes simply the classifier. We say that the decision rule is induced from data , in this case determined by computing .

However, real pattern recognition problems usually involve high-dimensional data (such as image data) and unknown underlying distributions. In this situation, it is nearly impossible to develop statistical tests like the preceding one. These problems are typically attacked with algorithms, such as artificial neural networks [2], decisions trees [3, ch. 18], Bayesian models [4], and recently SVMs [5], to which we will devote the rest of this article. Here we will only consider data that can be represented as vectors ; other kinds of information can usually be changed to this form in some appropriate manner.