Suppose that we have a set of linearly separable data and this pseudocode of Perceptron:

Input: (xi, yi), i=1,...,n, w = 0, k = 0
  k = (k + 1) mod n
  if(sign(yi) != sign(traspose(w)*xi) then
      w = w + yi*xi
  end if
until(every point is not misclasified)

Is there a way to modify this code to get a separator hyperplane as optimal as possible? In other words, is there a way to modify this code to obtain a new algorithm that learns an hyperplane as similar as possible to the hyperplane that SVM algorithm obtains? Maybe iterating first on the most misclassified data, or changing the if condition to be more restrictive?

  • 1
    $\begingroup$ (Although this question asks about modifying code, it is about pseudocode, i.e., an algorithm. This is software-neutral, & should be considered on topic here. I'm voting to leave open.) $\endgroup$ – gung May 28 '17 at 17:13

If you want to get a similar solution to SVM (max margin) then you will similarly need some sort of regularizer term for what you're solving - e.g. $\frac{\lambda}{2}||w||^2_2$. If you wish to consider $\lambda = 0$ you could do that as well, although convergence would be smaller, and I'm less sure about whether it will indeed be max margin.

In any case, to keep your format similar to what you have, you could solve using various stochastic schemes (e.g. SGD would apply for $\lambda = 0$ or not, and if you do have $\lambda > 0$, you could also consider Pegasos). Those aren't the latest results, but their algorithms are simple; in both cases, you'd only update $w$ when you encounter loss (not misclassification but loss according to e.g. the hinge loss), and the step-sizes are not constant. If you want constant step sizes, consider SAGA, although I do believe that requires your loss function to be Lipschitz smooth with constant $L$ which it isn't for the hinge loss (but you could use the Huber loss as a good substitute)


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.