Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An Idiot’s guide to Support vector machines (2003) [pdf]

web.mit.edu

Post reply on HN
Print view View original

31–40 of 64 posts

Re: An Idiot’s guide to Support vector machines (2003) [pdf]

#31

Post by nightski »

dplavery92 wrote: post #29
yters wrote: post #9

Earlier quoted context omitted.

If 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/SlidesLect2...

Significantly, 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.

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

Re: An Idiot’s guide to Support vector machines (2003) [pdf]

#32

Post by slashcom »

nightski wrote: post #31
dplavery92 wrote: post #29

Earlier quoted context omitted.

Significantly, 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.

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

An infinitely sized 2 layer NN is universal in the same way a Turing machine is universal — sure you can write any program; God help you if you try.

Re: An Idiot’s guide to Support vector machines (2003) [pdf]

#33

Post by iamwil »

I 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?

Re: An Idiot’s guide to Support vector machines (2003) [pdf]

#34

Post by dplavery92 »

nightski wrote: post #31
dplavery92 wrote: post #29

Earlier quoted context omitted.

Significantly, 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.

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

This is something of an academic factoid that has nothing to do with the practice of training and using neural networks, or with the merits of deep networks that I was describing above.

Shallow feed-forward networks are "universal function approximators" [0] when the number of hidden neurons is finite but unbounded. Of course, the width of that layer grows exponentially in the depth of the deep network that you might wish to approximate [1].

The statement that "[i]t's just that deep neural networks are a lot more practical to train" (emphasis mine) sounds somewhat reductive; it's not only that depth is a nice trick or hack for training speed, but that depth makes the success of deep networks in the past decade at all possible. We live in a world with bounded computing resources and bounded training data. You cannot subsume all deep networks into shallow networks, and shallow networks into SVMs in the real world. So I am pretty sure of how important that distinction is.

And what's more, depth extracts a hierarchy of interpret-able features at multiple scales[2], and a decision surface embedded within that feature space, rather than a brittle decision surface in an extremely high dimensional space with little semantic meaning. One of these approaches generalizes better than the other to unseen data.

[0] https://en.wikipedia.org/wiki/Universal_approximation_theore... [1] https://pdfs.semanticscholar.org/f594/f693903e1507c33670b896... [2] https://distill.pub/2017/feature-visualization/

Re: An Idiot’s guide to Support vector machines (2003) [pdf]

#35

Post by yters »

dplavery92 wrote: post #34
nightski wrote: post #31

Earlier quoted context omitted.

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

This is something of an academic factoid that has nothing to do with the practice of training and using neural networks, or with the merits of deep networks that I was describing above. Shallow feed-forward networks are "universal function approximators" [0] when the number of hidden neurons is finite but unbounded. Of course, the width of that layer grows exponentially in the depth of the deep network that you might…

If an SVM kernel can replicate a 2 layer NN, why couldn't there be a kernel for a X layer NN, and then autoderive the architecture just like SVMs can autoderive the correct number of neurons? Then there'd also be a more robust theoretical understanding of what's happening.

Re: An Idiot’s guide to Support vector machines (2003) [pdf]

#36

Post by rpedela »

abhgh wrote: post #12

If you need closer to a ELI5 version I recommend this - [1]. Disclaimer: written by me. [1] https://blog.statsbot.co/support-vector-machines-tutorial-c1...

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

Re: An Idiot’s guide to Support vector machines (2003) [pdf]

#37

Post by quantombone »

iamwil wrote: post #33

I 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, b…

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

Re: An Idiot’s guide to Support vector machines (2003) [pdf]

#38

Post by salty_biscuits »

iamwil wrote: post #33

I 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, b…

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

Re: An Idiot’s guide to Support vector machines (2003) [pdf]

#39

Post by rwilson4 »

iamwil wrote: post #33

I 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, b…

SVMs are a convex optimization problem, which means any local optimum is also globally optimal. In practice that leads to fast, provably optimal solutions.

With deep learning, the problem is non-convex, so the results are locally optimal but not necessarily globally optimal. We get around this with different techniques such as randomized initial weights, but with few exceptions, non-convex problems are NP-complete. Therefore there is no polynomial-time algorithm for finding the global optimum in deep learning unless P==NP.

I occasionally hear people claim deep learning finds the globally optimal solution, but that’s just not correct (or they mean they are doing an exhaustive search e.g. branch and bound, which has exponential worst case run time and isn’t practical).

That said, locally optimal solutions are often “good enough” for practical problems.

Re: An Idiot’s guide to Support vector machines (2003) [pdf]

#40

Post by jameslk »

abhgh wrote: post #12

If you need closer to a ELI5 version I recommend this - [1]. Disclaimer: written by me. [1] https://blog.statsbot.co/support-vector-machines-tutorial-c1...

Great 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/ is really cool.
Post reply on HN