# Incorporating regularization for the kernel perceptron

To my understanding, the following is how the kernel perceptron works.

Kernel perceptron algorithm

The parameters to be calculated are $$\alpha = \begin{pmatrix} \alpha_1 &\ldots &\alpha_d \end{pmatrix}$$ —a $$d$$-dimensional vector, where $$d$$         is the dimensionality of the instance space— and $$\theta_0$$ —a real number, oftentimes called the             offset —.

1. Initialize the value of $$\alpha$$ and $$\theta_0$$ —usually, $$\alpha^{(0)}$$ is set to be the $$d$$-dimensional zero vector and $$\theta_0^{(0)}$$ is set to be the real number zero—.

2. Begin the first iteration of the current epoch. Pick some labeled instance $$(X_j, y_j)$$ from the training set and check whether or not $$sign \big(\theta_0 + \sum_{i = 1}^n \alpha_i y_i K(X_i, X_j) \big) = y_j$$. In case this is not satisfied then the $$(k + 1)$$-th mistake is said to have been made, and consequently an update has to be made on the parameters according to the following rules:

\begin{align} \alpha_j^{(k + 1)} &= \alpha_j^{(k)} + 1 \\ \theta_0^{(k + 1)} &= \theta_0^{(k)} + y_j \end{align}

Otherwise, the equation is satisfied. Hence, no update is made and we just move on to the next        iteration.

1. Notice that step 2 dealt with $$j = 1$$. Now, repeat step 2 for $$j = 2, 3, \ldots, n$$. With that, a whole epoch —i.e. a sweep across all training instances— will have been fulfilled.

2. Repeat steps 2 and 3 until $$T$$ epochs have been fulfilled. Then stop. Return, at last, the following function \begin{align} h: \mathcal{X} &\to \{-1, 1\} \\ Z &\mapsto sign \Big(\theta_0 + \sum_{i = 1}^n \alpha_i y_i K(X_i, Z) \Big) \end{align}

where $$\mathcal{X}$$ is the instance space.

Now, my question is what exactly should we add to this scheme in order to regularize the kernel perceptron. Linear, not-kernelized perceptron can be made to behave as if it was minimizing a hinge loss. Can the same be done with the kernel perceptron? How exactly?

• I don't think it is possible to regularize the update of the weights in this particular algorithm since the update is done iteratively wrt a single data point without considering the entire dataset/batch. Take a look at this answer for more information. The only regularization I can think of is some sort of adjustable learning rate that depends on the value of the update. Jun 17 at 14:48