1
$\begingroup$

I try to understand what exactly we are trying to optimize in the case of Support Vector Machine problem, which supports soft margins. The original problem is posed first as, without soft margins (assuming linear separability):

\begin{equation*} \begin{aligned} & \underset{\gamma}{\text{maximize}} & & \dfrac{\gamma}{||w||} \\ & \text{subject to} & & y^{(i)}(w^Tx^{(i)} +b) \geq \gamma, \; i = 1, \ldots, m. \end{aligned} \end{equation*}

$\gamma$ is the so called functional margin of the closest sample to the hyperplane, related to the actual geometric margin $\gamma' = \dfrac{\gamma}{||w||}$. Then in order to make this a convex problem, the closest functional margin is equated to $1$. Given a hyperplane $(w,b)$ where $w$ is a unit vector; all $(\alpha w,\alpha b)$ pairs are equivalent where $\alpha > 0$. By equating $\gamma$ to $1$, we favor the $(\alpha' w,\alpha' b)$ pair where $\alpha' = \dfrac {1}{\gamma'}$ over all $(\alpha w,\alpha b)$ pairs. The objective turns to $\dfrac{1}{||w||}$ whose minimization is equivalent to the maximization of $||w||^2$. The final problem is then:

\begin{equation*} \begin{aligned} & \underset{w}{\text{minimize}} & & \ ||w||^2 \\ & \text{subject to} & & y^{(i)}(w^Tx^{(i)} +b) \geq 1, \; i = 1, \ldots, m. \end{aligned} \end{equation*}

If we allow points which violate the margin conditions, by penalizing them, we obtain the soft margin support vector machine problem, which is then: \begin{equation*} \begin{aligned} & \underset{w}{\text{minimize}} & & \ ||w||^2 + C \sum_{1}^{m} \epsilon_i\\ & \text{subject to} & & y^{(i)}(w^Tx^{(i)} +b) \geq 1 - \epsilon_i, \; i = 1, \ldots, m. & & \epsilon_i \geq 0, \; i = 1, \ldots, m. \end{aligned} \end{equation*}

Here is something which I not clearly understand: How the penalty values, $\epsilon_i$, should be interpreted? We again consider the smallest positive functional margin to be equal to $1$ such that $\alpha' = \dfrac{1}{\gamma'}$ where is $\gamma'$ is the smallest positive geometric margin with respect to the hyperplane. Then the penalty $\epsilon_i$ which we pay to shift a data point to its closest admissible location becomes dependent on $\gamma'$. For example if we pick a hyperplane where $\gamma'$ is large, then $\alpha'$ becomes small and for the same amount of actual geometric distance, $\epsilon_i$ becomes smaller to compared a hyperplane where $\gamma'$ is small. In the end, different hyperplanes pay different costs for moving inadmissible data points at the same distances; hyperplanes with large nearest geometric margins are favoured.

How is this behavior justified? Shouldn't we design a method which assigns the same cost for the same distance among all hyperplanes?

$\endgroup$
  • $\begingroup$ Do you have a particular alternate objective in mind? I suspect the objective that has the property you seek would be non-convex. $\endgroup$ – Michael Grant Dec 20 '14 at 15:22
  • $\begingroup$ I just thought that the cost for moving points which violate the condition must be directly equal to the actual geometric distance which they move. I think that this would a more natural interpretation of the optimal hyperplane problem. In the actual case, a data point which is actually very close to the hyperplane but is on the wrong side, introduces a very high cost if $\gamma'$ is very small or introduces very little cost if $\gamma'$ is very large. I want to know whether this specific scheme has a geometric justification as well. $\endgroup$ – Ufuk Can Bicici Dec 20 '14 at 16:13
  • $\begingroup$ I understand, but you still have to translate that idea into an objective function. That is, you need a mathematical description of it, not a bunch of words ;-) If you cannot come up with one---that is an answer to your question. If you can, but it renders the model intractable---that is also an answer. It's quite possible that the standard model just happens to be the one we can easily solve. $\endgroup$ – Michael Grant Dec 20 '14 at 16:33
  • $\begingroup$ So basically, we use that model since it is convex and we are able to efficiently solve it,using a Quadratic program solver for example, rather than having a precise geometric intuition, is that right? $\endgroup$ – Ufuk Can Bicici Dec 20 '14 at 17:54
  • $\begingroup$ That's my guess, yes. But I have not attempted to construct an objective function that supports your preferred geometric interpretation. If you want a definitive answer, you'll have to derive that one yourself. (That's why I'm posting in the comments, not as an answer :-)) $\endgroup$ – Michael Grant Dec 20 '14 at 17:56

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.