5 ms·
An Idiot’s guide to Support vector machines (2003) [pdf]
- strikelaserclaw 8y agoimplementing a svm was my senior project in college. Brings back nightmares.
- rusbus 8y agoIt's interesting how quickly support vector machines went from the hot new thing to classify images to an afterthought after deep learning started having great results.
- rdtsc 8y agoNoticed that too. It feels it was just a few years and all of the sudden everything is "deep" now. The same thing happened with data storage. As soon as big data appeared everyone stopped doing just data and started doing "big data". Now the term is kind of a joke even. I predict in a few years "deep learning" term will become mostly used in an ironic sense as well.
- username223 8y ago> I predict in a few years "deep learning" term will become mostly used in an ironic sense as well. I may be a bit behind the times, but I'm also mystified by "deep learning's" popularity. Both giant neural nets and kernel methods have overfitting problems: torture a billion-parameter model long enough, and it will tell you what you want to hear. SVMs address this by finding a large margin for error, which will hopefully improve generalization. DNNs (I think) do this by throwing more ("big") data at the problem and hoping that the training set covers all possible inputs. Work on adversarial learning suggests that DNNs go completely off the rails when presented with anything slightly unexpected.
- side_up_down 8y agoEmpericially, CNNs generalize better on image recognition tasks than hand built features. This comment doesn't make much sense and is needlessly obtuse in the face of progress, tbh.
- soraki_soladead 8y agoMy other comment addresses some of this but you're overstating things a bit. Throwing more data at the model is one solution. Its just not the only, or even best, approach. Properly measured performance on good holdouts and the application of regularization avoids the worst of overfitting. This is standard practice is most of machine learning, not just deep learning. Deep learning gets a lot of hype because for many applications they perform better and scale better without a lot of tricks and extensions which are now possible with SVMs. You can even use a large margin loss with deep models to get some of the benefits of SVMs. Adversarial examples are way overblown. First, SVMs are not immune to them either. Second, very few applications are threatened by things like adversarial examples.
- soraki_soladead 8y agoThat outcome doesn't seem terribly likely. It's true that, like big data, deep learning is often misused. This is largely because it works well enough in the off-the-shelf case and it's "easier" due to tooling, transfer learning, and free educational materials for beginners. However, deep learning also obtains state-of-the-art in a number of tasks and domains when you know what you're doing. I don't think your scenario is likely to occur unless something else starts outperforming deep learning (in the broadest sense) _and_ there's an approachable alternative to solve the same problems at least as well.
- autokad 8y agothey were also all the rage in pretty much everything else as well. In the problems not pushed out by DNN, gradient boosting has pretty much replaced SVMs as GBMs are faster training and better accuracy.
- srean 8y agoHot new ?! For whom ? SVMs have been in active use since the early nineties and have been formulated much before that
- usgroup 8y agoClearly idiots are not what they use to be in my day ...
- commandlinefan 8y agoI had trouble following it myself, and then it struck me - that must be because I’m not an idiot!
- mekicha 8y agoI think the idiot there refers to the author, not the readers. On the first page, he calls himself 'village idiot'.
- quantombone 8y agoBack in around 2008, SVMs were all the rage in computer vision. We would use hand designed visual features and then a linear SVM on top. That was how object detectors were built (remember DPM?) Funny how SVMs are just max-margin loss functions and we just took for granted that you needed domain expertise to craft features like HOG/SIFT by hand. By 2018, we use ConvNets to learn BOTH the features and the classifier. In fact, it’s hard to separate where the features end and the classifier begins (in a modern CNN).
- etrain 8y agoIt’s also hard to separate the design of the neural architecture from the definition of the feature extractor.
- yters 8y agoIf you use the right sort of kernel for an SVM it becomes a neural network with automatic architecture derivation. See slide 7: http://www.cs.rpi.edu/~magdon/courses/LFD-Slides/SlidesLect26.pdf http://www.cs.rpi.edu/~magdon/courses/LFD-Slides/SlidesLect2...
- dplavery92 8y agoSignificantly, it becomes a simple, 2-layer neural network. The power of the advances of neural networks in the past decade have largely relied on "deep" architectures with many layers. Very deep networks effectively learn the features from the data, rather than learn a decision surface over a set of hand-crafted features, as in learning with SVMs or shallow neural networks.
- nightski 8y agoI thought it had been proven that a two layer neural network has the same power as a deep one (obviously with a much greater width). It's just that deep neural networks are a lot more practical to train in practice. So I'm not sure how important that distinction is.
- abhgh 8y agoIf you need closer to a ELI5 version I recommend this - [1]. Disclaimer: written by me. [1] https://blog.statsbot.co/support-vector-machines-tutorial-c1618e635e93 https://blog.statsbot.co/support-vector-machines-tutorial-c1...
- rpedela 8y agoDefinitely a better fit for idiots like me. BTW that is a compliment. It is very hard to make something complicated easy to understand. You succeeded.
- abhgh 8y agoThanks!
- jameslk 8y agoGreat article! I did not understand the part with kernels before, so I appreciate the simplified explanation. The interactive demo on https://www.csie.ntu.edu.tw/~cjlin/libsvm/ https://www.csie.ntu.edu.tw/~cjlin/libsvm/ is really cool.
- abhgh 8y agoThanks! Yes its a pretty good demo, it should be more popular IMO.
- cultus 8y agoThere's been some work on variational Bayesian formulations of SVMs in the last few years. These can give actual uncertainty estimates and do automatic hyperparameter tuning. This one in particular is very cool: https://arxiv.org/pdf/1707.05532.pdf https://arxiv.org/pdf/1707.05532.pdf
- cultus 8y agoI notice this doesn't mention hinge loss, which is by far the simpler way of arriving at the SVM. Hinge loss is just max(0, 1- t*y), where y is the output of the linear model and t = +-1 is the label. Thus, it takes the common-sense approach of not penalizing losses that are far enough away from the decision boundary, and penalizing linearly after that. An SVM is literally just a linear model with hinge loss instead of log loss (logistic regression) or squared loss (ordinary linear regression) in primal form. For apparently historical reasons, it is usually derived from the "hard-margin" SVM in dual form, motivating with trying to maximize the margin. This is complicated and not very intuitive. This also causes people to conflate the kernel trick and the dual form, while in fact they have nothing to do with each other. You can use the kernel trick in primal svm just fine. Stochastic gradient descent can also be used for primal methods, while it doesn't work in the dual. That makes it much faster for large problems than the dual.
- quantombone 8y agoThe hinge-loss and the primal form of the SVM objective is really easy to understand. Every ML 101 class would jump into the dual formulation, talk about kernels, RKHS, and all the fancy stuff. Once you realize that a linear SVM isn’t very different from logistic regression, it starts to all make sense (at least it did for me). Key insight of the hinge-loss: once something is classified correctly beyond the margin, it incurs a loss of zero. Now, Something fun to think about. Draw the hinge loss. Now draw the ReLU (which is found all over the place in CNNs). Now thing about L1-regularization (which was used to induce sparsity in compressed sensing). They are more similar in form than you would think.
- cultus 8y agoIt's funny how close everything is connected. It turns out you can even derive the hinge loss using a mixture of normal distributions, so it is also connected closely to OLS. Some people have had good luck with hinge or multi-hinge loss for neural networks instead of the almost universal log loss, since of course the hinge loss can be used in things other than linear models. It doesn't care how you get the y output.
- 8y ago
- mistrial9 8y agocompare to Tzotsos 2006 "A SUPPORT VECTOR MACHINE APPROACH FOR OBJECT BASED IMAGE ANALYSIS"
- simonw 8y agoBullet point on page 2: "Optimal hyperplane for linearly separable patterns" I think the author may be working from a very different definition of the word "idiot".
- simonw 8y agoSeconding the recommendation for https://blog.statsbot.co/support-vector-machines-tutorial-c1618e635e93 https://blog.statsbot.co/support-vector-machines-tutorial-c1... - after reading that, "Optimal hyperplane for linearly separable patterns" actually made sense to me.
- iamwil 8y agoI have a question! In the pdf, it said that the optimization problem in SVMs have a nice property in that it was quadratic, which means that there's a nice global minimum to go towards, and not lots of local minimum like in NN. That means, it seems SVMs won't get stuck at a suboptimal solution. Is that not a problem in DNNs now? Or is it that it's such high dimensionality that local minima don't stop the optimizer, because there's always another way around the local minimum?
- quantombone 8y agoSVMs have convex objective functions, but when people use SVMs, they are using some kind of features + SVMs on top. The success of the approach is both good features, and waiting long enough for the optimizer to converge. With DNNs, people learn everything (features + decision boundary), and this problem is not convex. Surprisingly DNNs work quite well in practice even though we were taught to be afraid of non-convex problems in grad school around 2005. If back in early 2000s, we stopped worrying about theoretical issues and explored more approaches like ConvNets, we might have had the deep learning revolution 10 years earlier.
- salty_biscuits 8y agoStill a problem, but not a problem at the same time. Downhill in the loss function is always better, so you may not be at the global minima but you might be at a good enough spot anyway. Using SGD gives you a bit of local minima hopping ability as well. Interesting question to think about what the loss surface looks like, as it is so high dimensional that it might just be saddles everywhere. The difference between a local minima and the global might be practically nothing in terms of classifier performance. The convexity of the loss function for SVMs is a mixed blessing, you are guaranteed to be at the global min but the optimization problem doesn't scale with large training data or big feature vectors. Hence the historical feature engineering efforts or sacrificing this property to a more scalable optimization method. So in short the ability to use high dimensional features in a NN means you don't get any guarantee about if the minima you get will be the best, but you lose less by not having to cut down the size of the input vector by hand (i.e. working directly with an image rather than some embedding with keypoint descriptors etc).
- 8y ago
- deleted 8y ago[deleted]