2
$\begingroup$

Im studying about support vector machines; on the dual formulation of SVM and I couldnt understand why the objective function is concave wrt $\alpha$. I know I can use the definition on concavity but I was hoping someone could give me an intuitive explanation on why it would be concave.

An example of an explanation for w would be: the objective function in convex in w because you can visualize points from 2 classes that scattered in a 2D plane and are linearly separable. From there, it is easy to see that there is only one configuration of the separating line that gives the lowest error. If you rotate this line around you will get larger errors.

https://github.com/epfml/ML_course/blob/master/lectures/07/lecture07a_svm.pdf

enter image description here

$\endgroup$
  • 1
    $\begingroup$ This seems linear in $\alpha$, therefore it is concave (and convex) in $\alpha$ $\endgroup$ – RUser4512 Nov 3 '17 at 10:07
1
$\begingroup$

For a fixed $\mathbf w$, you are seeking the value of $\boldsymbol \alpha$ that maximizes the expression.

Let's break it down.

We have that

\begin{cases} 1-y_n\mathbf x_n \mathbf w \leq 0 & \mbox{if} ~ y_n\mathbf x_n^T \mathbf w \geq 1 \\ 1-y_n\mathbf x_n^T \mathbf w > 0 & \mbox{otherwise} \end{cases}

That is, the only cases that will contribute positively to that sum are those in which the classification is either wrong or not very confident (in terms of distance from the separating hyperplane). For those cases, the $\alpha_i$'s will want to push up the value of the sum as much as possible, so they'll take 1. When $y_i\mathbf x_i^T \mathbf w > 1$, they'll take 0, as they would contribute negatively to the sum otherwise. Finally, when $y_i\mathbf x_i^T \mathbf w = 1$, the value of $\alpha_i$ does not make any difference.

From there, once all the $\alpha_i$'s are correct, it is easy to see that any meaningful change in the value of $\boldsymbol \alpha$ that moves away from the optimum will always decrease the value of the sum, and any change back towards the optimum will increase it. Changes in the values that are annihilated are inconsequential, so if those exist there will be a plateau.

$\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.