Difference between a SVM and a perceptron

Question

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.

Answer 1

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.

Answer 2

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).

Answer 3

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.