26
$\begingroup$

I am a bit confused with the difference between an SVM and a perceptron. Let me try to summarize my understanding here, and please feel free to correct where I am wrong and fill in what I have missed.

  1. The Perceptron does not try to optimize the separation "distance". As long as it finds a hyperplane that separates the two sets, it is good. SVM on the other hand tries to maximize the "support vector", i.e., the distance between two closest opposite sample points.

  2. The SVM typically tries to use a "kernel function" to project the sample points to high dimension space to make them linearly separable, while the perceptron assumes the sample points are linearly separable.

$\endgroup$
17
$\begingroup$

It sounds right to me. People sometimes also use the word "Perceptron" to refer to the training algorithm together with the classifier. For example, someone explained this to me in the answer to this question. Also, there is nothing to stop you from using a kernel with the perceptron, and this is often a better classifier. See here for some slides (pdf) on how to implement the kernel perceptron.

The major practical difference between a (kernel) perceptron and SVM is that perceptrons can be trained online (i.e. their weights can be updated as new examples arrive one at a time) whereas SVMs cannot be. See this question for information on whether SVMs can be trained online. So, even though a SVM is usually a better classifier, perceptrons can still be useful because they are cheap and easy to re-train in a situation in which fresh training data is constantly arriving.

$\endgroup$
  • 2
    $\begingroup$ SVMs can be trained online. From a dual solution you can obtain the corresponding primal and from this one you update weights in stochastic fashion. $\endgroup$ – Firebug Feb 6 '17 at 13:02
  • 1
    $\begingroup$ jmlr.org/papers/volume6/bordes05a/bordes05a.pdf $\endgroup$ – sinθ Mar 24 '17 at 16:56
0
$\begingroup$

SVM: $$\min \|w\|_2 + C\sum_{i = 1}^{n}(1 - y_i(wx_i + w_0))_+ $$ Perceptron $$\min \sum_{i = 1}^{n}(- y_i(wx_i + w_0))_+ $$

We can see that SVM has almost the same goal as L2-regularized perceptron.

Since the objective is different, we also have different optimization schemes for these two algorithms, from the $\|w\|_2$, we see that it is the key reason for using quadratic programming for optimizing SVM.

Why does perceptron allow online update? If you see the gradient descent update rule for the hinge loss (hinge loss is used by both SVM and perceptron),

$$w^t = w^{t-1} + \eta\frac{1}{N}\sum_{i = 1}^{N}y^ix^i\mathbb{I}(y^iw^tx^i \leq 0)$$

Since all machine learning algorithms can be seen as the combination of loss function and optimization algorithm.

Perceptron is no more than hinge loss (loss function) + stochastic gradient descent (optimization)

$$w^t = w^{t-1} + y^{y+1}x^{t+1}\mathbb{I}(y^{t+1}w^{t}x^{t+1} \leq 0)$$

And SVM can be seen as hinge loss + l2 regularization (loss + regularization) + quadratic programming or other fancier optimization algorithms like SMO (optimization).

$\endgroup$
-1
$\begingroup$

Perceptron is the generalization of SVM where SVM is the perceptron with optimal stability. So you are correct when you say perceptron does not try to optimize the separation distance.

$\endgroup$

protected by kjetil b halvorsen Feb 15 '18 at 9:17

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.