Kernel perceptron

In machine learning, the kernel perceptron is a variant of the popular perceptron learning algorithm that can learn kernel machines, i.e. non-linear classifiers that employ a kernel function to compute the similarity of unseen samples to training samples. The history of the algorithm can be traced to the 1960s.

Preliminaries

The perceptron algorithm

Main article: Perceptron

The perceptron algorithm is an old but popular online learning algorithm that operates by a principle called "error-driven learning": it iteratively improves a model by running it on training samples, then updating the model whenever it finds it has made an incorrect classification wrt. a supervised signal. The model learned by the standard perceptron algorithm is a linear binary classifier: a vector of weights w (and optionally an intercept term b) that is used to classify a sample vector x as class "one" or class "minus one" according to

${\hat {y}}=\operatorname {sgn}(\mathbf {w} ^{\top }\mathbf {x} )$

where a zero is arbitrarily mapped to one or minus one.

In pseudocode, the perceptron algorithm is given by:

Initialize w to an all-zero vector of length p, the number of predictors (features).

For each training example xᵢ with ground truth label yᵢ ∈ {-1, 1}:

Let ŷ = sgn(w^T xᵢ).

If ŷ ≠ yᵢ, update w := w + yᵢ xᵢ.

Repeat this procedure until convergence, or for a set amount of iterations ("epochs").

Kernel machines

Main article: Kernel methods

By contrast with the linear models learned by the perceptron, a kernel machine is a classifier that stores a subset of its training examples xᵢ, associates with each a weight αᵢ, and makes decisions for new samples x' by evaluating

$\operatorname {sgn} \sum _{i}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x'} )$

Here, K is some kernel function. Formally, a kernel function is a non-negative semidefinite kernel (see Mercer's condition); intuitively, it can be thought of as a similarity function between samples. Each function x' ↦ K(xᵢ, x') serves as a basis function in the classification.

Algorithm

To derive a kernelized version of the perceptron algorithm, we must first formulate it in dual form, starting from the observation that the weight vector w can be expressed as a linear combination of the n training samples:

$\mathbf {w} =\sum _{i}^{n}\alpha _{i}y_{i}\mathbf {x} _{i}$

where αᵢ is the number of times xᵢ was misclassified, forcing an update. The dual algorithm thus loops through the samples as before, making predictions. But instead of explicitly updating the per-feature weight vector w, it updates the per-sample "mistake counter" vector α. We can also rewrite the prediction formula as

${\begin{aligned}{\hat {y}}&=\operatorname {sgn}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} )\\&=\operatorname {sgn} \left(\sum _{i}^{n}\alpha _{i}y_{i}\mathbf {x} _{i}\right)^{\mathsf {T}}\mathbf {x} \\&=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}(\mathbf {x} _{i}\cdot \mathbf {x} )\end{aligned}}$

Finally, we can replace the dot product (linear kernel) in the dual version of the perceptron algorithm by a different kernel function. Doing this yields the kernel perceptron algorithm:

Initialize α to an all-zeros vector of length n, the number of training samples.

For some fixed number of iterations, or until the model makes no mistakes on the training set:

For each training example x, y:

Let ${\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} )$

If ŷ ≠ y, perform an update:

αᵢ := αᵢ + 1

Forgetron

A problem with the kernel perceptron, as presented above, is that it does not learn sparse kernel machines. Initially, all the αᵢ are zero so that evaluating the decision function to get ŷ requires no kernel evaluations at all, but each update increments a single αᵢ, making the evaluation increasingly more costly. Moreover, when the kernel perceptron is used in an online setting, the number of non-zero αᵢ and thus the evaluation cost grow linearly in the number of examples presented to the algorithm.

The forgetron variant of the kernel perceptron was suggested to deal with this problem. It maintains an active set of examples with non-zero αᵢ, removing ("forgetting") examples from the active set when it exceeds a pre-determined budget and "shrinking" (lowering the weight of) old examples as new ones are promoted to non-zero αᵢ.

See also

• Support vector machine