From Sparse Coding to GANs: A Tour of Unsupervised Deep Learning in 2016

Salakhutdinov opens by saying that unsupervised learning has had a lot of research but, compared with the supervised methods covered earlier in the day, it is not there yet. His motivation is that the data we have, whether images, speech, social network or scientific data, is mostly unlabeled. He wants statistical models that can discover structure in an unsupervised or semi-supervised way and that apply across domains.

He frames the field as a map of model families. Non-probabilistic models include sparse coding, autoencoders and clustering methods, while probabilistic models split into tractable ones, such as fully observed belief networks and neural autoregressive density estimators, and intractable ones, such as Boltzmann machines, variational autoencoders and Helmholtz machines. A newer family, generative adversarial networks and moment matching networks, only needs to be able to sample from the model.

The core idea is representation learning. Classifying raw pixels is hard, and for years people used hand-designed features in vision and audio. The hope of deep learning is to learn those representations automatically, ideally from unlabeled data alone, and he warns the audience that he wants to lower their expectations because the field is not there yet.

Sparse coding, which he traces to 1996 and to explaining early visual processing in the brain, learns a dictionary of bases so that each data point is a linear combination of them with mostly zero coefficients. Applied to image patches, the learned bases look like edge detectors. The objective combines a reconstruction error with a sparsity penalty.

Fitting alternates between two convex problems. With the dictionary fixed, finding the coefficients is a standard lasso problem, and with the coefficients fixed, finding the bases is a quadratic program. At test time you solve a lasso problem for the new input. Salakhutdinov notes that this is all done without labels.

He cites 2006 work from Stanford on Caltech 101, where features from sparse coding beat logistic regression on raw input and PCA followed by logistic regression. Sparse coding also shows up in medical imaging and neuroscience because it is easy to fit. He frames it as an implicit nonlinear encoder with an explicit linear decoder, which leads naturally into autoencoders.

An autoencoder pairs a bottom-up encoder with a top-down decoder that reconstructs the input. Without constraints, it could trivially copy the input, so you need bottlenecks or other restrictions. In its basic form it is a one-hidden-layer neural network trained with backpropagation on reconstruction error.

If the encoder and decoder share parameters and the hidden layer is linear, the model discovers the same space as PCA. That makes autoencoders nonlinear extensions of PCA. He also covers variants with sparsity constraints, such as predictive sparse decomposition, and the stacking of layers for greedy layer-wise learning, which helps when you have lots of unlabeled data and little labeled data.

In a 2006 example, a deep autoencoder compresses faces to a 30-dimensional code and reconstructs sharper faces than PCA. The model sometimes removes glasses or mustaches, treating rare features as noise. On roughly 800,000 Reuters stories compressed to two dimensions, he jokes that the model puts European economic policy next to disasters and accidents.

Semantic hashing compresses data into binary codes. A 20-bit code gives about 2 to the 20 addresses, so you can store everything in memory and do lookups without searching, and he says retrieval from millions of images takes a fraction of a millisecond. He says it is still an active research area.

Salakhutdinov shows a model trained on about 25,000 characters from 50 alphabets, with around two million parameters, generating what it believes Sanskrit looks like. He notes that convincing samples could mean generalization or overfitting. The difficulty is that a 28 by 28 binary image has 2 to the 784 configurations, and real images occupy a tiny corner of that space.

Fully observed models factor an image into conditional probabilities, one pixel at a time, which makes likelihood tractable. He mentions the neural autoregressive density estimator developed by Hugo Larochelle and DeepMind's pixel recurrent models that year, including a PixelCNN producing elephants. The drawback is that it is unclear how good the representations are for other tasks.

Restricted Boltzmann machines have visible variables, like pixels, and hidden variables that act as feature detectors, with a bipartite structure. Given an input, inferring the features is quick, unlike in sparse coding. Maximum likelihood gives a learning rule that matches data-driven correlations to model-driven ones, but the model term sums over all possible images and is intractable.

The standard answer is Markov chain Monte Carlo, but it would have to run forever to be exact. Hinton's 2002 contrastive divergence runs the chain for just one step, and he says it takes about 10 lines of MATLAB. He jokes that he would like to see an RBM in TensorFlow.

Swapping the conditional distributions lets RBMs handle real-valued data with Gaussians or word counts with a softmax. Trained on documents, hidden units pick up topics, such as Russia, the US and computers. A one-step reconstruction of "chocolate cake" returns words like dessert, sugar and cupcake, and a flower-and-Japan query returns Sakura, blossom and Tokyo.

On the Netflix collaborative filtering data, the hidden units capture preferences such as movie genres, and he says one unit was dedicated to Michael Moore's movies. He then explains that these models act as products of experts: each hidden variable defines a distribution over words, and the intersection makes the model precise. This tends to beat mixture-based topic models.

He contrasts local representations, such as clustering, where the number of regions grows only linearly with parameters, with distributed representations, where each neuron affects many regions. The number of regions grows roughly exponentially with the number of parameters. That is the advantage of factor models, RBMs and deep models.

Stacking layers gives the Deep Boltzmann Machine, where each unit depends on both what comes from below and what comes from above, so the model needs a consensus between the data and its beliefs. Hidden variables become dependent even given the data, which makes learning and inference harder. The same learning rule applies, matching data statistics to model statistics, using variational inference or stochastic approximation.

To test how good the model is, he shows two panels of handwritten characters, one real and one simulated, and the audience splits roughly half and half. The real ones are crisper and more diverse. In other samples, the model generates a "car with wings" and rarely generates donkeys or elephants, but people with guns more often.

For multimodal data, images are dense and text is sparse, and the tags are noisy, so a hierarchical model that builds up each modality first and then joins them works better. He admits some outputs are wrong, such as a mix-up with Barack Obama signs, and says they lacked modern convnet features. Pre-training on a million unlabeled images helped compared with using only 25,000 labeled ones, and he shows image arithmetic like kittens minus ball plus box.

Helmholtz machines, from 1995 work by Hinton, Peter Dayan, Brendan Frey and Radford Neal, pair a stochastic generative network with a recognition model that approximately infers latent states. The wake-sleep algorithm never really worked, and Salakhutdinov says people moved to Boltzmann machines. Two years earlier, people figured out how to make them work. A variational autoencoder is a Helmholtz machine whose conditional distributions can be deep nonlinear networks.

Since the data likelihood cannot be optimized directly, you maximize a variational lower bound, which Jensen's inequality makes workable. It equals the log likelihood minus a KL divergence between the recognition model and the true posterior. The 1995 algorithm was not really optimizing anything, just alternating steps.

The 2014 trick, from Kingma and Welling and independently others, writes a Gaussian sample as mean plus standard deviation times noise drawn from a standard normal. This makes the recognition path a deterministic mapping and collapses the model into an autoencoder with an external noise source. Taking gradients inside the expectation, instead of gradients of averages, hugely reduces variance and allows backpropagation.

To explain why noise is needed, he describes a student's project to generate images from captions. Given "a stop sign is flying in blue skies," a deterministic system would give one image, while the stochastic model samples different stop signs and skies. It also draws a yellow, red, green and blue school bus, even though blue buses were not in the data, and a toilet seat in a grass field.

He jokes that after the paper went on arXiv, a student pointed out you could simply ask Google for the toilet seat query. Because people click on the model's image, he says Google ranked it above the real result. He also shows a model trained on about 7,000 romance novels, hooked up to a captioning system. He says it is syntactically reasonable but semantically nowhere near, though.

In one-shot learning of characters, a generative model draws a new character from a single example, and people could barely tell human from machine drawings, with results at almost 50/50 in the work of Brendan Lake. Salakhutdinov notes this is a small, carved-out domain.

Generative adversarial networks avoid explicit densities, maximum likelihood and Markov chains, and only require sampling. A generator turns noise into samples, and a discriminator, typically a convolutional network, tries to tell real data from fake. The generator tries to fool the discriminator, which is a minimax objective.

The optimal discriminator outputs the data probability divided by the sum of the data and model probabilities. If the generative model is good, that ratio becomes one half and the discriminator is always confused. He shows a deconvolutional GAN producing LSUN bedrooms, plus CIFAR and ImageNet samples, and says he even wondered whether the bedroom model was memorizing.

Open questions remain, since it is unclear whether the model learns the space of all images or just blurs training data. He would like to know whether a new test image of a horse would be judged likely. He concludes that GANs step away from maximum likelihood into a game-theoretic framework, and unsupervised learning has made progress but has far to go.

Asked why GANs produce clearer images than variational autoencoders, Salakhutdinov points to the Gaussian loss. With L2 loss, putting an edge in the wrong place is penalized heavily, so the model avoids crisp edges and produces diffuse images. GANs only need to look realistic to the classifier, which gives sharper results but sometimes artifacts. He mentions work using VAEs for global coherence and GANs for sharpening.

On PCA pre-processing for variational autoencoders, he says he does not know why people do it and has not seen much pre-processing, although ZCA whitening sometimes helps. Asked about partition function estimation, he says Ising models with special structure allow exact sampling or polynomial-time approximations, but RBMs do not meet those assumptions, so the problem is NP-hard and sampling-based methods like contrastive divergence beat variational ones in practice.

For semantic hashing on text, he says you can feed in any differentiable representation, from bag of words to word2vec sums or GloVe. He thinks bidirectional GRUs, then the method of choice, would probably work better than adding word vectors, and then you can learn a hashing function into binary space.