2
$\begingroup$

I'm new to the AI Stackexchange and wasn't certain if this should go here or to Maths instead but thought the context with ML may be useful to understand my problem. I hope posting this question here could help another student learning about Support Vector Machines some day.

I'm currently learning about Support Vector Machines at university and came across a weird step I could not understand. We were talking about basic SVMs and formulated the optimisation problem $\max_{w,b} \{ \frac{1}{||w||} \min_n(y^{(n)}f(x^{(n)}))\}$ which we then simplified down to $\max_{w,b} \{ \frac{1}{||w||}\}$ by introducing $\kappa$ as a scaling factor for $w$ and $b$ according to the margin of the SVM. Now our lecturer converted it without explanation into a quadratic optimisation problem as $\min_{w,b}\{\frac{1}{2} ||w||^2\}$ which I could not explain myself. I hope someone with context can help me how this is possible and what math or trick is behind this approach?


Notation information:

  • $w$ - weight matrix
  • $b$ - bias (sometimes denoted $w_0$ I believe?)
  • $x^{(n)}$ - Independent variable (vector)
  • $y^{(n)}$ - Dependent variable (scalar classifying the input in a binary classifcation as $y=1$ or $y=-1$)

Thank you very much!

$\endgroup$
2
  • $\begingroup$ Welcome to SE:AI! I'm glad you asked here as this involves supervised learning. $\endgroup$ – DukeZhou Oct 27 '20 at 1:33
  • $\begingroup$ This actually involves convincing yourself that this is true. It gets more complex to convince yourself when you introduce slack varaibles. Try to think it in terms of what happnes if there is a single data point, will the SVM margin be infinity? What happnes if 2 datapoints of 2 classes? What role does b play? One side note is that the first formulation is not convex, but the second is, so that is the sole motivation. Also note the formulation of SVM you presented is super vague, try Understanding ML by Shai David for a better formulation of SVM. $\endgroup$ – user9947 Oct 28 '20 at 10:54
1
$\begingroup$

So actually I managed to get hold of my lecturer to explain the argmax to argmin conversion.

Generally speaking maximising $\frac{1}{||w||}$ is identical to minimising $||w||$. As $||w||$ in $\frac{1}{||w||}$ decreases, the overall value increases, i.e. we maximise it. The reason for choosing $\frac{1}{2}||w||^2$ turns out to be a less mathematic and more practical one as our optimisation algorithms used perform better on quadratic functions and the $\frac{1}{2}$ seems to be a rather arbitrary scaling choice.

If anyone has something to add, I'd love to hear any details though!

$\endgroup$

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.