Kernel Perceptron

machine-learning algorithms kernel-methods

Definition

Kernel Perceptron

The kernel perceptron is a non-linear extension of the perceptron algorithm that utilises the kernel trick to identify decision boundaries in a high-dimensional Hilbert space. Formally, the classifier is represented in its dual form:

$f(\mathbf{x})=\text{sign}\left({\sum }_{i=1}^n{\alpha }_i{y}_{i}k({\mathbf{x}}_i,\mathbf{x})\right)$

where ${\alpha }_i$ is the number of times the $i$-th training example was misclassified during training.

Algorithmic Update

For each training example $({\mathbf{x}}_t,y_t)$, the model performs an update if the prediction is incorrect:
If $y_t\left({\sum }_{i=1}^{t-1}{\alpha }_i{y}_{i}k({\mathbf{x}}_i,{\mathbf{x}}_t)\right)\le 0$:
${\alpha }_t\leftarrow {\alpha }_{t-1}+1$

This allows the perceptron to solve non-linearly separable problems, such as the XOR function, by implicitly mapping the data into a space where a linear hyperplane exists.