1
$\begingroup$

I'm asked to find the maximum margin decision surface separating positive from negative samples by inspection. The positive examples are (1,1) and (-1,-1), the negative ones are (1,-1) and (-1,1). The feature transformation is $\phi(x)=[1,x_1,x_2,x_1x_2]$. The solution should be $w=(0,0,0,1)^T$.

On Alex Smola's slides, there are two weight perceptron algorithms, the weight update of the first one (slide 36/56):

if $y_i(w\cdot\phi(x_i)+b)\leq0$ then

$w'=w+y_i\phi(x_i)$

the second one instead (slide 43/56):

if $y_if(x_i)\leq0$ then

$f(\cdot)\leftarrow f(\cdot)+y_ik(x_i,\cdot)+y_i$

My understanding is that the first algorithm is simply the perceptron algorithm after applying some mapping function on the features while the second one is the updated perceptron algorithm after the kernel trick. Which one should I apply for the above exercise?

Considering the second algorithm, since the classifier is linear combination of inner products $f(x)=\sum\limits_{i \in I} y_ik(x_i,x)+b$ what is being updated after each step if the weights are no longer in the equation?

$\endgroup$
1
$\begingroup$

The slides are about Perceptron algorithm not SVM (although it's quoted maybe mistakenly). First equation is about normal perceptron, and the second is about the kernel version of it. They're equivalent. However, perceptron algorithm only give you a solution, not necessarily the max-margin solution.

For having max-margin solution, you need to look at the SVM slides, and solve it using the Lagrangian and KKT conditions (slides after 15).

$\endgroup$
1
  • $\begingroup$ Thanks for the clarification. Can you answer to my second question more precisely? $\endgroup$ – TonyRomero Feb 16 '20 at 1:12

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.