0
$\begingroup$

The theory behind Linear Support Vector Machines with tolerance of misclassifications states that we are trying to minimise in the primal weight space the following function:

$$\min\limits_{w,b,\xi} J_{P}(w,\xi) = \frac{1}{2}w^{T}w + c\sum\limits_{k=1}^{N}\xi_{k}$$

Subject to the following constraints defined for all data points $k$ where $\xi_{k}$ are slack variables, $x_{k}$ are input points, $(w^{T}x_{k}+b)$ are outputs of trained classifier for weights $w$ and $b$ and $y_{k}$ are classes (either $-1$ or $+1$): $$\forall_{k\in1...N} \ \ \xi_{k} \geq 0$$ $$\forall_{k\in1...N} \ \ y_{k}(w^{T}x_{k}+b) \geq 1 - \xi_{k}$$

These sets are used of inequality constraints are - as far as I understand - mandatory to satisfy. The slack variables $\xi_{k}$ provide wiggle room for some datapoints that would not satisfy a regular $y_{k}(w^{T}x_{k}+b) \geq 1$ condition.

However, if for some datapoint $l$ we have misclassification - thus the slack variable is greater than $1$: $\xi_{l} > 1$ then obviously this condition cannot be satisfied:

$$y_{l}(w^{T}x_{l}+b) \geq 1 - \xi_{l}$$

Because of the following example values ($y_{l} \neq (w^{T}x_{k}+b)$ because we have a misclassification): $$\xi_{l} = 1.5$$ $$y_{l} = +1$$ $$(w^{T}x_{l}+b) = -1$$ then

$$1\cdot -1 \ngeq 1 - 1.5$$ $$ -1 \ngeq -0.5 $$

So, as far as I understand this makes it impossible to find any solutions to this problem. Yet if I input such data to a SVM classifier using SMO Quadratic Programming algorithm it outputs some results with the offending point being on the "wrong" side of classification.

My question is: How is this possible? Aren't those conditions mandatory to satisfy? If not, what regulates how many of them won't be satisfied, since slack variables $\xi$ can't?

$\endgroup$
  • $\begingroup$ Do you know the concept of feasible set? $\endgroup$ – TenaliRaman May 22 '16 at 3:14
2
$\begingroup$

Your mistake is that you did not choose $\xi_l$ to be large enough for your example. Note that it is not bounded from above, so it will grow to be as large as necessary to make the constraint valid. In you example above, you could have chose $\xi_l$ to be 2. This would satisfy the constraint.

You also assume that $(w^{T}x_{l}+b) = -1$ in the case of a misclassification. This is not true. A misclassification happens when $y_l(w^{T}x_{l}+b) \lt 1$. The value $(w^{T}x_{l}+b)$ could be positive and still be misclassified.

$\endgroup$
  • $\begingroup$ Okay, I think I get it! My confusion arose frm the fact that in the book I am reading about it I have found the sentence "When slack variable XI > 1 the inequality becomes violated in comparison with the corresponding inequality from the linearly separable case.". Could you explain what the author meant? It would seem to me that all slack variables greater than 0 are there because the inequality would be otherwise violated... $\endgroup$ – Jeremiah May 22 '16 at 12:25
  • $\begingroup$ @Jeremiah, It is difficult to tell what the author meant. I often find it helpful to learn a new topic from a number of different sources (authors can make mistakes). Given the form of the equations above, your sense is correct. A slack variable $\xi_l \neq 0$ implies a constraint violation. If you consider the form of the hard-margin classifier, which does not have slack variables $\xi$, it is almost self-evident that non-zero slack variables imply a constraint violation. BTW, what author are you reading? $\endgroup$ – Tpofofn May 22 '16 at 18:00

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.