Kernel method

Kernel Methods (KMs) are a class of algorithms for pattern analysis, whose best known element 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 general types of data (such as sequences, text documents, sets of points, vectors, images, etc).

KMs approach the problem by mapping the data into a high dimensional feature space, where each co-ordinate corresponds to one feature of the data items, transforming the data into a set of points in a Euclidean space. In that space, a variety of methods can be used to find relations in the data. Since the mapping can be quite general (not necessarily linear, for example), the relations found in this way are accordingly very general. This approach is called the kernel trick.

KMs owe their name to the use of kernel functions, that enable them to operate in the 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. Kernel functions have been introduced for sequence data, graphs, text, images, as well as vectors.

Algorithms capable of operating with kernels include SVM, Fisher's linear discriminant analysis (LDA), principal components analysis (PCA), canonical correlation analysis, ridge regression, spectral clustering, and many others.

Because of the particular culture of the research community that has been developing this approach since the mid-1990s, most kernel algorithms are based on convex optimization or eigenproblems, are computationally efficient and statistically well-founded. Typically, their statistical properties are analyzed using statistical learning theory (for example, using Rademacher complexity).

Applications

At the moment, the main application areas are in geostatistics, kriging, Inverse distance weighting, bioinformatics, chemoinformatics, text categorization, and handwriting recognition.

Since any kernel can be used with any kernel-algorithm, it is possible to construct exotic combinations such as: regression over biosequences; classification of documents; clustering of images; and so on.

References

• Kernel-Machines Org -- community website
• www.support-vector-machines.org (Literature, Review, Software, Links related to Support Vector Machines - Academic Site)
• J. Shawe-Taylor and N. Cristianini. Kernel Methods for Pattern Analysis. Cambridge University Press, 2004.