Kernel method

From Wikipedia, the free encyclopedia
  (Redirected from Kernel machines)
Jump to: navigation, search

In machine learning, kernel methods are a class of algorithms for pattern analysis, whose best known member is the support vector machine (SVM). The general task of pattern analysis is to find and study general types of relations (for example clusters, rankings, principal components, correlations, classifications) in datasets. For many of these tasks, data have to be represented as feature vectors, but kernel methods replace this representation by similarities to other data points.

Kernel methods owe their name to the use of kernel functions, which enable them to operate in a high-dimensional, implicit feature space without ever computing the coordinates of the data in that space, but rather by simply computing the inner products between the images of all pairs of data in the feature space. This operation is often computationally cheaper than the explicit computation of the coordinates. This approach is called the kernel trick. Kernel functions have been introduced for sequence data, graphs, text, images, as well as vectors.

Algorithms capable of operating with kernels include the kernel perceptron, support vector machines (SVM), Gaussian processes, principal components analysis (PCA), canonical correlation analysis, ridge regression, spectral clustering, linear adaptive filters and many others. Any linear model can be turned into a non-linear model by applying the "kernel trick" to the model: replacing its features (predictors) by a kernel function.

Most kernel algorithms are based on convex optimization or eigenproblems and are statistically well-founded. Typically, their statistical properties are analyzed using statistical learning theory (for example, using Rademacher complexity).

Motivation and informal explanation[edit]

Kernel methods can be thought of as instance-based learners: rather than learning some fixed set of parameters corresponding to the features of their inputs, they instead remember their training examples and learn weights for these. Unseen examples (not in the training set) are treated by the application of a similarity function, called a kernel, between the new example and each of the training examples. For instance, a kernelized binary classifier typically computes a weighted sum of similarities,

\sgn \sum_i \alpha_i y_i K(\mathbf{x}_i, \mathbf{x'})

where x is the unseen example, xi are the examples in classifier's training set, and αi are their weights. The sign function determines whether the classification comes out positive or negative.

Kernel classifiers were described as early as the 1960s, with the invention of the kernel perceptron.[1] They rose to great prominence with the popularity of the support vector machine (SVM) in the 1990s, when the SVM was found to be competitive with neural networks on tasks such as handwriting recognition.

Mathematics[edit]

The kernel trick avoids the explicit mapping that is needed to get linear learning algorithms to learn non-linear function or decision boundaries. For x, y on S, certain functions  K(x,y) can be expressed as an inner product (usually in a different space). K is often referred to as a kernel or a kernel function. The word kernel is used in different ways throughout mathematics.

If one is insightful regarding a particular machine learning problem, one may manually construct  \varphi: S \to V such that

K(x,y) = \langle \varphi(x), \varphi(y) \rangle_V

and verify that  \langle \cdot, \cdot \rangle_V is indeed an inner product.

Furthermore, an explicit representation for \varphi is not required: it suffices to know that V is an inner product space. Conveniently, based on Mercer's theorem, it suffices to equip S with one's choice of measure and verify that in fact,  K : S \times S \to \mathbb{R} satisfies Mercer's condition.

Mercer's theorem is stated in a general mathematical setting with implications in the theory of integral equations. However, the general statement is more than what is required for understanding the kernel trick. Given a finite observation set S, one can select the counting measure  \mu(T) = |T| for all  T \subset S . Then the integral in Mercer's theorem reduces to a simple summation

 \sum_{i=1}^n\sum_{j=1}^n K(x_i, x_j) c_i c_j \geq 0

for all finite sequences of points x1, ..., xn of S and all choices of real numbers c1, ..., cn (cf. positive definite kernel).

Some algorithms that depend on arbitrary relationships in the native space would, in fact, have a linear interpretation in a different setting: the range space of \varphi. The linear interpretation gives us insight about the algorithm. Furthermore, there is often no need to compute \varphi directly during computation, as is the case with support vector machines. Some cite this running time shortcut as the primary benefit. Researchers also use it to justify the meanings and properties of existing algorithms.

Theoretically, a kernel matrix K must be positive semi-definite (PSD).[2] Empirically, for machine learning heuristics, choices of K that do not satisfy Mercer's condition may still perform reasonably if K at least approximates the intuitive idea of similarity.[3] Regardless of whether K is a Mercer kernel, K can still be referred to a "kernel". Suppose K is any square matrix, then K^\mathrm{T}K is a PSD matrix.

Applications[edit]

Application areas of kernel methods are diverse and include geostatistics,[4] kriging, inverse distance weighting, 3D reconstruction, bioinformatics, chemoinformatics, information extraction and handwriting recognition.

Popular kernels[edit]

See also[edit]

Notes[edit]

  1. ^ Aizerman, M. A.; Emmanuel M. Braverman; L. I. Rozoner (1964). "Theoretical foundations of the potential function method in pattern recognition learning". Automation and Remote Control 25: 821–837.  Cited in Guyon, Isabelle; B. Boser; Vladimir Vapnik (1993). "Automatic capacity tuning of very large VC-dimension classifiers". Advances in neural information processing systems. 
  2. ^ Mehryar Mohri, Afshin Rostamizadeh, Ameet Talwalkar (2012) Foundations of Machine Learning, The MIT Press ISBN 9780262018258.
  3. ^ http://www.svms.org/mercer/
  4. ^ Honarkhah, M and Caers, J, 2010, Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling, Mathematical Geosciences, 42: 487 - 517

References[edit]

  • J. Shawe-Taylor and N. Cristianini. Kernel Methods for Pattern Analysis. Cambridge University Press, 2004.
  • W. Liu, J. Principe and S. Haykin. Kernel Adaptive Filtering: A Comprehensive Introduction. Wiley, 2010.

External links[edit]