Kernel-based Learning Algorithm

A Kernel-based Learning Algorithm is a supervised learning algorithm that uses a kernel function (that maps into a high-dimension space and whose instance similarity score in the original space has low computational complexity - typically through inner product operations).

• AKA: Large-Margin Method.
• Context:
  • input: a Kernel Function (that maps into a high-dimension space and whose instance similarity score in the original space has low computational complexity - typically through inner product operations).
  • output: a kernel-based predictive function).
  • It can exploit information about a Kernel Function's output.
  • It can be implemented by a Kernel-based Learning System (to solve a kernel-based learning task).
• Example(s):
  • a Support Vector Machine Learning Algorithm.
  • a Kernel-based Gaussian Process Algorithm (Gaussian processes).
  • a Kernel-based Principal Components Algorithm (PCA).
  • a Kernel-based Canonical Correlation Algorithm (canonical correlation analysis).
  • a Kernel-based Ridge Regression Algorithm (ridge regression)
  • a Kernel-based Spectral Clustering (spectral clustering).
  • a Kernel-based Linear Adaptive Filter Algorithm (adaptive filters)
  • a Gaussian Process Algorithm.
  • …
• Counter-Example(s):
  • a k-Nearest Neighbor Learning Algorithm.
  • a Maximum Entropy-based Learning Algorithm, such as logistic regression.
• See: Kernel Matrix, Positive-Definite Kernel, Inner Product, Graph Kernel, Sparse Kernel Machine, Rademacher Complexity, Principal Components, Positive-Definite Kernel.

---

---

References

2017

• (Wikipedia, 2017) ⇒ https://en.wikipedia.org/wiki/Kernel_method Retrieved:2017-1-19.
  • 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 algorithms that solve these tasks, the data in raw representation have to be explicitly transformed into feature vector representations via a user-specified feature map: in contrast, kernel methods require only a user-specified kernel, i.e., a similarity function over pairs of data points in raw representation.

    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).

2016

• http://www.quora.com/What-are-the-major-factors-that-motivate-us-to-use-Neural-networks-over-Kernel-methods-for-large-datasets-in-layman-terms
  • QUOTE: … Kernel methods, by contrast, work by comparing pairs of data points. This means that the matrix of comparisons (aka the kernel matrix) needs lots of memory … On the other hand, deep networks are rather compact function classes, hence you can get away with compact storage, at the expense of a lot more computation to train them. …

2011

• (Zhang, 2011d) ⇒ Xinhua Zhang. (2011). “Kernel Methods.” In: (Sammut & Webb, 2011) p.566
  • QUOTE: Kernel methods refer to a class of techniques that employ positive definite kernels. At an algorithmic level, its basic idea is quite intuitive: implicitly map objects to high-dimensional feature spaces, and then directly specify the inner product there. As a more principled interpretation, it formulates learning and estimation problems in a reproducing kernel Hilbert space, which is advantageous in a number of ways:
    • It induces a rich feature space and admits a large class of (nonlinear) functions.
    • It can be flexibly applied to a wide range of domains including both Euclidean and non-Euclidean spaces.
    • Searching in this infinite-dimensional space of functions can be performed efficiently, and one only needs to consider the finite subspace expanded by the data.
    • Working in the linear spaces of function lends significant convenience to the construction and analysis of learning algorithms.

2006

• (Bishop, 2006) ⇒ Christopher M. Bishop. (2006). “Pattern Recognition and Machine Learning. Springer, Information Science and Statistics.

2004

• (Lanckriet et al., 2004a) ⇒ Gert R. G. Lanckriet, Nello Cristianini, Peter Bartlett, Laurent El Ghaoui, and Michael I. Jordan. (2004). “Learning the Kernel Matrix with Semidefinite Programming.” In: The Journal of Machine Learning Research, 5.
  • QUOTE: Kernel-based learning algorithms (see, for example, Cristianini and Shawe-Taylor, 2000; Scholkopf and Smola, 2002; Shawe-Taylor and Cristianini, 2004) work by embedding the data into a Hilbert space, and searching for linear relations in such a space. The embedding is performed implicitly, by specifying the inner product between each pair of points rather than by giving their coordinates explicitly. This approach has several advantages, the most important deriving from the fact that the inner product in the embedding space can often be computed much more easily than the coordinates of the points themselves.

---