10
$\begingroup$

I was wondering if it was possible to train an SVM (say a linear one, to make things easy) using backpropagation?

Currently, I'm at a road block, because I can only think about writing the classifier's output as

$$ f(\mathbf{x};\theta,b) = \text{sgn}(\theta\cdot\mathbf{x} - (b+1)) = \text{sgn}(g(\mathbf{x};\theta,b)) $$

Hence, when we try and calculate the "backwards pass" (propagated error) we get $$ \begin{align} \frac{\partial E}{\partial \mathbf{x}} &= \frac{\partial E}{\partial f(\mathbf{x};\theta,b)} \frac{\partial f(\mathbf{x};\theta,b)}{\mathbf{x}} \\ &= \frac{\partial E}{\partial f(\mathbf{x};\theta,b)} \frac{\partial \text{sgn}(g(\mathbf{x};\theta,b))}{\partial g(\mathbf{x};\theta,b)} \frac{\partial g(\mathbf{x};\theta,b)}{\partial \mathbf{x}} \\ &= \delta \, \frac{d \text{sgn}(z)}{dz} \, \theta \\ &= \delta \cdot 0 \cdot \theta \\ &= \mathbf{0} \end{align} $$ since the derivative of $\text{sgn}(x)$ is $$ \frac{d\text{sgn}(x)}{dx} = \begin{cases} 0 &\text{if $x \neq 0$}\\ 2\delta(x) &\text{if $x=0$} \end{cases} $$

Similarly, we find that $\partial E/\partial \theta = \partial E /\partial b = 0$, which means we cannot pass back any information, or perform gradient updates!

What gives?

$\endgroup$
14
$\begingroup$

You are correct that if you try to directly optimize the SVM's accuracy on training cases, also called the 0-1 loss, the gradient vanishes. This is why people don't do that. :)

What you're trying to do, though, isn't really an SVM yet; it's rather just a general linear classifier. An SVM in particular arises when you replace the 0-1 loss function with a convex surrogate known as hinge loss; this amounts to the idea of margin maximimization which is core to the idea of an SVM. This loss function is (almost) differentiable; the only issue is if any outputs are exactly at the hinge point, which (a) happens with probability zero under most reasonable assumptions and (b) then you can just use either 0 or 1 as the derivative (or anything in between), in which case you're technically doing subgradient descent.

Since you're talking about backpropagation, I'll assume you're at least a little familiar with optimizing neural networks. The same problem occurs with neural network classifiers as well; this is why people use other loss functions there too.

$\endgroup$
  • $\begingroup$ So if I understand you correctly, you're really saying that a linear SVM can be thought of a 1-layer NN -- the single layer is just a linear transformation, $A \mathbf{x} + b$ -- with the hinge loss function? $\endgroup$ – StevieP Jun 26 '15 at 22:00
  • 1
    $\begingroup$ Yes, a linear SVM is basically equivalent to a 1-layer NN with linear activation on the output node and trained via hinge loss. $\endgroup$ – Dougal Jun 28 '15 at 0:00
5
$\begingroup$

If you are interested in only the linear case then logistic regression (LR) is a better choice, as it is both convex and analytic(you may want to ridge it if you are interested in the regularization). But when you go for non-linear that's where the tricky part comes into picture. For non linear cases there is no reasonable way to keep things both convex and analytic you will need to sacrifice one of the two.In neural nets you sacrifice convexity and in svms you sacrifice holomorphism.

strictly speaking there is no difference between LR and SVM ,svms just predict on which side of the line a point lies, LRs take also into consideration how far they lie from the boundary(on the boundary-margin line the sigmoid gives you the probability 0.5 in case of LR) . SVMs are forced to make this compromise because for non linear kernels the intuition of distance from a curved-hyperplane(algebraic variety is a better term) is not the same as in linear case , in fact the problem of solving shortest distance from a hyper surface to a specific point is very hard(harder than the SVM itself), but on the other hand Vapnik realized to just predict on which side of boundary a point lies is very easy as in O(1) time. This is the true insight behind SVM, making it the only available convex optimization alternative in statistical learning theory.But my feeling is you sacrifice a little too much, both holomorphism and probabilistic nature are lost. But for specific cases like ground-truthing SVMs are very reliable and are also fully falsifiable scientific models unlike its non convex alternatives.

Tldr: yes, the mean value theorem comes to rescue for non analytic functions.In convex-non analytic cases the mean value thorem turns into an inequality setting some boundary conditions on the sub-gradients use that to do a sub gradient decent

$\endgroup$
  • 1
    $\begingroup$ What does LR mean to you? $\endgroup$ – Reinstate Monica Aug 3 '16 at 21:06
  • $\begingroup$ @Sycorax logistic regression $\endgroup$ – Franck Dernoncourt Jan 10 '17 at 16:04

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.