Why Deep Learning Works at All: Yoshua Bengio on Composition, Saddle Points and the Case for Unsupervised Learning

Bengio opens with a high-level talk and no new algorithm, listing the ingredients a machine needs to reach human-level performance. It must acquire a huge amount of knowledge about the world through data, so it needs models far bigger than the ones available at the time. That means flexible function classes, enough computing power to train them, and efficient ways to use them, which rules out models where inference is intractable.

The ingredient he wants to focus on is defeating the curse of dimensionality. If you assume little about the world, learning is impossible, because the number of configurations of the observed variables is exponentially large. A million binary pixels give two to the power of a million possible images.

His answer is that the only way to beat an exponential is to use another one. Models have to be compositional, representing complicated functions through a reasonably small number of parameters by composing small pieces. Deep learning does this in two ways: parallel composition within a layer, which is the idea of distributed representations, and sequential composition across levels, which is depth.

Bengio stresses that deep learning is not magic. Over the set of all possible distributions it is no better than any other method, which is what the no free lunch theorem says. It works so well because we live in a world that can be described by composition.

He contrasts this with classical non-distributed methods such as clustering, n-grams, nearest neighbors, SVMs with Gaussian kernels, and decision trees. They carve the data space into regions and use separate parameters for each one, so the number of parameters grows linearly with the number of regions. They can model any function, but they fail when asked to extrapolate to a new example outside the cases they have seen.

A neural net's first layer instead intersects half-planes, so a few binary units define an exponential number of regions while the parameters grow only linearly. Bengio's example is a person detector with features such as glasses, gender and child, where a hundred such features could cover two to the 100 combinations. Because each feature can be learned independently, a model can learn about glasses without seeing every combination of other traits. He notes that bagged trees and forests work better than single trees partly because they are one level deeper, though they are not trained jointly.

He adds evidence that nets really find such features: a 2012 MIT experiment trained a convolutional net to recognize places and found that many hidden units had obvious human interpretations, such as people, animals, buildings and lighting. Generative models like GANs and VAEs benefit from the same idea, he says, because composing independent factors is much easier than working in pixel space.

Bengio summarizes some of the mathematical support. For a single-layer network with rectifier units, the function is piecewise linear, and the number of pieces grows exponentially with the number of inputs, with the number of units as the base. This is a way of quantifying the richness of what the network can compute.

Earlier theory says one hidden layer can represent any function, but it does not say how many units that takes. Several results show some functions can be represented efficiently by a deep network with few parameters, but would need an exponential number of parameters in a shallow one. These functions are a tiny fraction of all possible ones, and we are lucky that the ones we want to learn tend to have this property.

He points out that this is not surprising, since we use compositionality everywhere, such as writing programs with many functions instead of a single main. For deep rectifier networks, the number of linear pieces grows exponentially with depth, on top of the exponential growth already present in a single layer.

Turning to training, Bengio recalls that in the 1990s many researchers left neural nets because results suggested an exponentially large number of local minima. That drove a wave of research into convex methods, which have a single global minimum. In low dimensions a random function does look full of ups and downs, but he says high dimensions behave very differently.

In a space with millions or billions of parameters, what a training run meets instead are saddle points, where the surface curves up in some directions and down in others. Experiments from an NYU group showed that as the network grows, the lowest points reached by training concentrate around a similar cost, and the bad local minima vanish. A real local minimum needs upward curvature in every direction, and the probability of that becomes exponentially small.

Bengio's group tested this by plotting training error against the fraction of downward-curving directions at critical points. As training progressed it approached saddle points but never local minima until it reached the lowest cost it could. He also cites theory suggesting that any local minima lie in a thin band just above the global minimum.

He does not claim optimization is solved. Gradients near these points are not close to zero, ill-conditioning may be to blame, and tasks like machine translation or reasoning with Turing-machine-like problems remain hard and rely on tricks such as curriculum learning. The problem is simply much less worrying than people thought in the 1990s.

Deep learning is moving beyond pattern recognition to reasoning, planning and combining with reinforcement learning, Bengio says. Attention is one of its most useful tools, which he describes as internal attention over the representations the network has built, not only attention in visual space. It has been very successful in machine translation.

Long-term dependencies in recurrent nets are a challenge he has worked on since he was a PhD student, and he says it is still not fully cracked. Ideas include skip connections over time and multiple time scales. He also suggests viewing attention and memory as part of the network's state, so that memory cells that are written once and not overwritten let gradients pass back through them almost unhampered, avoiding the vanishing gradient problem.

Bengio calls unsupervised learning the biggest challenge ahead. It is not yet obvious in industrial products, although it already helps in less visible ways: word embeddings and pretrained language models used in translation and other NLP tasks. He says its potential and importance are usually underrated.

His illustration is a two- or three-year-old who understands physics, such as what happens when a ball is dropped or how liquids behave, with nobody ever teaching her the equations. That learning is purely unsupervised, and computers in 2016 could not match it. Beyond that, supervised learning only models one output given the input, while unsupervised learning captures the joint distribution and so can answer any question about the data.

He lists several practical benefits. It works as a regularizer, since the target is one of the factors that explain the input. It underlies why transfer and multi-task learning and domain adaptation work, because tasks share underlying factors. It can make training deep nets easier, since much of the learning can be done locally, and it helps with structured outputs like sentences, where the output has a complicated joint distribution.

Bengio uses self-driving cars to make the case for model-based reinforcement learning. A human learns not to steer into a wall without ever experiencing a crash, so traditional policy learning or actor-critic methods cannot work, since they would need data from states that would be fatal. He adds an anecdote about nuclear plant data where the number of explosions was zero.

His only solution is to learn enough about the world to predict how things unfold, then run a mental simulation. That needs a generative model of the world given actions, and unsupervised learning is the natural way to build it, though training models that capture so many aspects of the world will be hard.

He also argues that deep learning researchers can do more than provide a black box to RL. In supervised backpropagation, credit assignment uses the observed correct answer, whereas RL typically learns a critic that predicts expected future reward. He mentions a paper on sequence prediction that tries to bring the supervised view into RL, and says RL's older habit of enumerating discrete states looks very different from the neural-net approach.

Bengio says current nets often cheat by using the wrong cues, and the remedy is for models to understand how the world works. He contrasts invariance, the old idea of computing features that ignore position or orientation, with disentangling factors of variation. In speech, that means not only extracting phonemes but also learning the speaker, the recording conditions and the microphone, so the model can generalize to new tasks like identifying the speaker.

He pairs this with multiple levels of abstraction, from pixels and strokes up to words and the meaning of a paragraph. Higher levels make it much easier to act on information, since many sentences can express the same meaning and questions about intent can't be answered at the level of words.

His last topic is the link between machine and biological intelligence. Backpropagation works very well, but it is unclear how brains could implement it. He describes his own work on target propagation and on gradient estimation in recurrent networks that resembles spike-timing-dependent plasticity, and says the field has largely forgotten neuroscience because everyone is busy building self-driving cars.

Asked why the hub-like connectivity seen in brain networks does not show up in deep nets, Bengio says connectivity is not the heart of it. The central question is how the brain learns complicated things, which it does better than current machines, and we do not know a simple way to train brain-like networks that fits the biology.

On whether the curse of dimensionality still bites, he says it does whenever generalization fails. More data and compute work for some problems, but sometimes the amount of data needed is too large, so research on algorithms and architectures that capture how the world is organized is also needed. He notes that speech and language models use far more data than any human sees in a lifetime, which suggests we are doing something wrong.

He expects video to be mainly a computational bottleneck and not a fundamental problem. He is also sure humans would beat machines at learning unfamiliar tasks from a few examples, because we bring common sense learned earlier from a lot of data. On local minima, a 2009 experiment found that different initializations end up in different places, so the number of minima is vastly larger than the trajectories tried, yet they all have similar cost in large networks.