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?

  • $\begingroup$ 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. $\endgroup$ Jun 17 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.