7
$\begingroup$

Typical support vector classifier uses the following optimization procedure:

$$\min ||w||^2 + C\sum_{i=1}^N \zeta_i$$ $$y_i(w^Tx_i+b) \geq 1 - \zeta_i$$ $$\zeta_i \geq 0$$

This hinge loss setup slightly penalizes the correctly classified data points within the margin. Now if we gently modify the constraint the result will be a learning machinery with a regularized perceptron loss and it will only penalize misclassified data points.

$$y_i(w^Tx_i+b) \geq - \zeta_i$$

enter image description here

I understand there are historical reasons things are the way they are (maximizing margin rhetoric, etc.) But is there a particular theoretical reason for not implementing a support vector classifier in this manner? What will be the pros and cons?

$\endgroup$
2
+50
$\begingroup$

Maximizing the margin is not just "rhetoric". It is the essential feature of support vector machines and ensures that the trained classifier has the optimal generalization properties. More precisely, making the margin large maximizes the probability that the classification error on new data will be small. The theory behind it is called the Vapnik-Chervonenkis (VC) Theory.

In your question you consider a soft-margin classifier, but the reasoning is equally valid for hard-margin classifiers, which work only on linearly separable datasets. In that case, all your $\zeta_i$'s would simply turn out $0$, thus minimizing the sum in your objective function. Therefore, for simplicity, I'll reformulate your argument for linearly separable data.

Training a support vector machine amounts to optimizing:

$$\min ~ \lVert w \rVert ^2 \\ \text{s.t.} ~ ~ ~ y_i (w^T x_i + b) \ge 1$$

We want to minimize $\lVert w \rVert ^2$ because that maximizes the margin $\gamma$:

$$\gamma = \frac{1}{\lVert w \rVert ^2}$$

The constraints ensure not only that all points from the training set are correctly classified, but also that the margin is maximized. As long as there are points for which $y_i (w^T x_i + b) \lt 1$, the training continues by adjusting $w$ and $b$.

Now, you suggest that we can use different constraints:

$$\min ~ \lVert w \rVert ^2 \\ \text{s.t.} ~ ~ ~ y_i (w^T x_i + b) \ge 0$$

The solution to this problem is trivial: Simply set $w=0$ and $b=0$, and $\lVert w \rVert ^2$ will be zero, too. However, this doesn't give you any information about the class boundary: $w$, being now a null vector, doesn't define any hyperplane at all!

Or, to have a look from a different perspective:

Imagine having performed the training using some different learning algorithm, let's say, the perceptron algorithm. You have found some $w$ and $b$ which result in perfect classification on your training set. In other words, your constraint $y_i (w^T x_i + b) \ge 0$ is satisfied for every $i$. But, is this class boundary realistic?

Take the following example: The class boundary separates the blue from the red points, but almost touches one in each class (i.e. the "perceptron" condition is satisfied, but not the SVM condition):

suboptimal separation

In contrast, the one below has a "large margin", satisfying the SVM condition:

large margin separation

It is intuitively clear that this classifier, having the boundary as far as possible from the training points, has a better chance of good generalization.

$\endgroup$
  • $\begingroup$ Your reasoning about the optimization is valid. Having max margin vs another boundary is in my mind dubious, no matter how visually pleasing or intuitive it is. Can you provide a reference showing that max margin is actually a minimax boundary under all probability distributions for two class scenario? $\endgroup$ – Cagdas Ozgenc Jan 27 at 18:45
  • $\begingroup$ See for example Nello Cristianini & John Shawe-Taylor: "Support Vector Machines", Cambridge University Press, 2000, p. 63 (quote of the theorem, originally, I believe, by Vapnik). $\endgroup$ – Igor F. Jan 27 at 19:30
  • $\begingroup$ Also, if you take a look at the figures, maybe you can recognize that both lines (and infinitely many more) satisfy the "perceptron" condition: They correctly classify all points. But, are they all equally good class boundaries? $\endgroup$ – Igor F. Jan 27 at 19:47
  • 1
    $\begingroup$ I am under the impression that you are "moving the goalposts". Originally, you wanted to know whether there is a theoretical reason for not using the "perceptron" loss function. I answered that. For everything else, I suggest you post a new, separate question. $\endgroup$ – Igor F. Jan 27 at 20:29
  • $\begingroup$ You answered the original question I am not challenging your answer. Since you evangelized the max margin, I thought maybe you know a proof for minimax bound. For example two gaussians with equal diagonal covariances placed far apart from each other will be estimated quite poorly by max margin compared to simply taking the mid point of the means. For this reason I wanted to understand at least if there is a minimax defense for it. $\endgroup$ – Cagdas Ozgenc Jan 27 at 20:34

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.