The optimization problem of soft margin Support Vector Machine: How to interpret?

Question

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 margin 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?

Answer 1

I will start off with a non geometric way of thinking of this. Specifically, $w^Tx + b$ is the classification value of $x$. We ideally want this value to be $\geq 1$ for points classified as $+1$ and to be $\leq -1$ for points classified as $-1$, thus, we want $y_i(w^Tx_i + b) \geq 1$ (where I'm using subscripts for convenience). In this context $\epsilon_i$ is the amount by which we are misclassifying. If it is $0$ then we are correct in our classification. As it increases, we are getting closer and closer to classifying it as the wrong class and the size of our mistake grows.

Note that this is a "logical" approach and less a geometric one. Indeed, the value $1$ enforces a scaling for the problem. For a geometric perspective, consider two hyper-planes $w_1$ and $w_2$ such that $w_2 = D w_1$ for some positive constant $D$. Clearly, $w_2$ makes the exact same +/- decisions as $w_1$, however evaluating $w_2$ vs $w_1$ would require factoring in that $D$ scaling. Thus, there needs to be some way in which we "lock down" the scaling, we could have similarly required that $||w|| = 1$ and then have $\gamma - \epsilon_i$ and seek to minimize -$\gamma + C \sum \epsilon_i$.