3
$\begingroup$

Consider the soft-margin SVM formulation. $$ \begin{align} \mbox{min}_{\mathbf{w},b,\boldsymbol{\xi}} & & \frac{1}{2}\|\mathbf{w}\|_2^2 + C\sum_i \xi_i \\ \mbox{s.t.} & & y_i(\mathbf{w}^Tx_i+b) \geq1-\xi_i \\ & & \xi_i\geq0 \end{align} $$ If $C$ is sufficiently small, the $\xi_i$'s can grow large, and therefore the constraints can be honored by a plethora of grossly misclassified points. Therefore, the minimization of $\|\mathbf{w}\|^2_2$ no longer seems that helpful in the pursuit of a separating hyperplane.

I have done a quick test with scikit-learn's SVC and a toy (and admittedly a bit pathological) dataset.

C=1 C=0.1 C=0.001

So in this case I think we can say it breaks down badly (unless it is due to the implementation).

The SVM objective (minimize $\|\mathbf{w}\|$) arises from the consideration of the constraints in the original, natural objective (maximize the margin to the closest point). Doesn't it cease to be a natural formulation once we introduce the slack variables? Is there something intrinsic to the minimization of $\|\mathbf{w}\|$ that provides better separating hyperplanes in less extreme cases, or will this pathology happen in general?

EDIT: The corresponding slack variables for each of the above cases are:

y  point     xi
1  [ 0.  1.] 0.000276941610509
1  [ 1.  1.] 9.22304236668e-05
1  [ 2.  1.] 9.24807631741e-05
1  [ 3.  1.] 0.000277191950016
-1 [ 0. -1.] 0.000461843532213
-1 [ 1. -1.] 0.000277132345372
-1 [ 2. -1.] 9.24211585298e-05
-1 [ 3. -1.] 9.22900283107e-05
1  [ 1.5 -0.9] 1.90017553166

1  [ 0.  1.] 2.38418573772e-09
1  [ 1.  1.] 3.57627882863e-09
1  [ 2.  1.] 9.53674317294e-09
1  [ 3.  1.] 1.54972079613e-08
-1 [ 0. -1.] 0.779999997616
-1 [ 1. -1.] 0.780000003576
-1 [ 2. -1.] 0.780000009537
-1 [ 3. -1.] 0.780000015497
1  [ 1.5 -0.9] 1.15899999344

1  [ 0.  1.] 2.38418618181e-10
1  [ 1.  1.] 1.5894552341e-10
1  [ 2.  1.] 5.56309887045e-10
1  [ 3.  1.] 9.53674250681e-10
-1 [ 0. -1.] 1.87799999976
-1 [ 1. -1.] 1.87800000016
-1 [ 2. -1.] 1.87800000056
-1 [ 3. -1.] 1.87800000095
1  [ 1.5 -0.9] 0.115899999642
$\endgroup$
  • $\begingroup$ For reference, what are the $\xi_i$ produced for each plot? $\endgroup$ – Alex R. Sep 19 '17 at 20:04
  • $\begingroup$ @AlexR. Good point. I added them. $\endgroup$ – cangrejo Sep 19 '17 at 20:19
1
$\begingroup$

As $C \rightarrow 0$, $w \rightarrow 0$ (independent of the data, of course the precise results for specific values of $C$ will be data dependent). Note that your implementation though will generally be $\epsilon$-accurate for some expression (this may be the objective, or it may be on something related, like a bound on the duality-gap), and it might be sensitive to how it started the optimization.

$\endgroup$
  • $\begingroup$ This answer certainly introduces interesting elements. However, can we expect data-independent $\epsilon$-accuracy considering the $\xi$'s can grow arbitrarily? $\endgroup$ – cangrejo Jan 24 '18 at 14:44
  • $\begingroup$ This depends on the optimization approach. For example, some algorithms explicitly take $\epsilon$ as a parameter and thus guarantee this bound - i.e, its guaranteed that the objective is within $\epsilon$ of optimal - however the precise value that you exceed the objective by is definitely data dependent; if the algorithm is stochastic it would even be dependent on the randomization there $\endgroup$ – MotiN Jan 25 '18 at 15:29

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.