STA 4273 / CSC 2547 Spring 2018:

# Learning Discrete Latent Structure

## Overview

New inference methods allow us to train learn generative latent-variable models. These models can generate novel images and text, find meaningful latent representations of data, take advantage of large unlabeled datasets, and even let us do analogical reasoning automatically. However, most generative models such as GANs and variational autoencoders currently have pre-specified model structure, and represent data using fixed-dimensional continuous vectors. This seminar course will develop extensions to these approaches to learn model structure, and represent data using mixed discrete and continuous data structures such as lists of vectors, graphs, or even programs. The class will have a major project component, and will be run in a similar manner to Differentiable Inference and Generative Models

## Prerequisites:

This course is designed to bring students to the current state of the art, so that ideally, their course projects can make a novel contribution. A previous course in machine learning such as CSC321, CSC411, CSC412, STA414, or ECE521 is strongly recommended. However, the only hard requirements are linear algebra, basic multivariate calculus, basics of working with probability, and basic programming skills.

To check if you have the background for this course, try taking this Quiz. If more than half the questions are too difficult, you might want to put some extra work into preparation.

### Where and When

- Spring term, 2018
- Instructor: David Duvenaud
- Email: duvenaud@cs.toronto.edu (put “STA4273” in the subject)
- Location: Galbraith 119
- Time: Fridays, 2-4pm
- Office hours: Mondays, 3:30-4:30pm, in 384 Pratt

## What is discrete latent structure?

Loosely speaking, it referes to any discrete quantity that we wish to estimate or optimize. Concretely, in this course we’ll consider using gradient-based stochastic optimization to train models like:

- Variational autoencoders with latent binary vectors, mixture models, or lists of vectors
- Differentiable versions of stacks, deques, and Turing machines
- Generative models of text, graphs, and programs
- Tree-structured recursive neural networks

## Why discrete latent struture?

**Computational efficency**- Making models fully differentiable sometimes requires us to sum over all possiblities to compute gradients, for instance in soft attention models. Making hard choices about which computation to perform breaks differentiability, but is faster and requires less memory.**Reinforcement learning**- In many domains, the set of possible actions is discrete. Planning and learning in these domains requires integrating over possible future actions.**Interpretability and Communication**- Models with millions of continuous parameters, or vector-valued latent states, are usually hard to interpret. Discrete structure is easier to communicate using language. Conversely, communicating using words is an example of learning and planning in a discrete domain.

## Why not discrete latent struture?

**It’s hard to compute gradients**- It’s hard to estimate gradients through functions of discrete random variables. It is so difficult that much of this course will be dedicated to investigating different techniques for doing so. Developing these techniques are an active research area, with several large developments in the last few years.

## Course Structure

Aside from the first two and last two lectures, each week a different group of students will present on a set of related papers covering an aspect of these methods. I’ll provide guidance to each group about the content of these presentations.

In-class discussion will center around understanding the strengths and weaknesses of these methods, their relationships, possible extensions, and experiments that might better illuminate their properties.

The hope is that these discussions will lead to actual research papers, or resources that will help others understand these approaches.

Grades will be based on:

- [15%] One assignment, designed to help you become familiar with unbiased gradient estimators, such as REINFORCE (also known as the score-function estimator) and REBAR
- [15%] Class presentations
- [15%] Project proposal
- [15%] Project presentation
- [40%] Project report and code

### Project

Students can work on projects individually,in pairs, or even in triplets. The grade will depend on the ideas, how well you present them in the report, how clearly you position your work relative to existing literature, how illuminating your experiments are, and well-supported your conclusions are. Full marks will require a novel contribution.

Each group of students will write a short (around 2 pages) research project proposal, which ideally will be structured similarly to a standard paper.
It should include a description of a minimum viable project, some nice-to-haves if time allows, and a short review of related work.
You don’t have to do what your project proposal says - the point of the proposal is mainly to have *a* plan and to make it easy for me to give you feedback.

Towards the end of the course everyone will present their project in a short, roughly 5 minute, presentation.

At the end of the class you’ll hand in a project report (around 4 to 8 pages), ideally in the format of a machine learning conference paper such as NIPS.

Projects will be graded according to an updated version of Last year’s project report grading rubric

## Tentative Schedule

### Week 1 - Jan 12th - Optimization, integration, and the reparameterization trick

This lecture will set the scope of the course, the different settings where discrete structure must be estimated or chosen, and the main existing approaches. As a warm-up, we’ll look at the REINFORCE and reparameterization gradient estimators.

### Week 2 - Jan 19th - Gradient estimators for non-differentiable computation graphs

Discrete variables makes gradient estimation hard, but there has been a lot of recent progress on developing unbiased gradient estimators.

Recommended reading:

- Gradient Estimation Using Stochastic Computation Graphs
- Backpropagation through the Void: Optimizing control variates for black-box gradient estimation

Material that will be covered:

- The original REINFORCE paper.
- REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models
- Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation
- MuProp: Unbiased Backpropagation for Stochastic Neural Networks
- Neural Variational Inference and Learning in Belief Networks
- Variational inference for Monte Carlo objectives
- Categorical Reparameterization with Gumbel-Softmax
- The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables
- Stochastic Backpropagation and Approximate Inference in Deep Generative Models
- The Generalized Reparameterization Gradient

### Week 3 - Jan 26th - Differentiable Data Structures

Attempts learn programs using gradient-based methods, and program induction in general.

- Neural Turing Machines
- Neural Networks, Types, and Functional Programming
- Pointer Networks
- Solomonoff Induction
- Probabilistic programming - Automatic inference in arbitary models specified by a program.
- Sampling for Bayesian Program Learning
- Programming with a Differentiable Forth Interpreter
- Neural Sketch Learning for Conditional Program Generation
- Adaptive Computation Time for Recurrent Neural Networks

### Week 4 - Feb 2nd - Discrete latent structures

Variational autoencoders and GANs typically use continuous latent variables, but there is recent work on getting them to use discrete random variables.

- The Helmholtz Machine - The forerunner of VAEs used binary latent variables.
- Attend, Infer, Repeat: Fast Scene Understanding with Generative Models - The latent variables can be a list or set of vectors.
- Composing graphical models with neural networks for structured representations and fast inference - the prior on latent variables can be any tractable graphical model, and we can use this inference as part of the recognition step.
- Learning Hard Alignments with Variational Inference
- Neural Discrete Representation Learning

### Week 5 - Feb 9th - Reinforcement learning

- Connecting Generative Adversarial Networks and Actor-Critic Methods
- Emergence of Grounded Compositional Language in Multi-Agent Populations
- Model-Based Planning in Discrete Action Spaces - “it is in fact possible to effectively perform planning via backprop in discrete action spaces”
- Reinforcement Learning Neural Turing Machines
- Qprop

### Week 6 - Feb 16th - Adversarial training and text models

It’s not obvious how to train GANs to produce discrete structures, because this cuts off the gradient to the discriminator.

- Adversarial Autoencoders - One surprisingly effective hack for training discrete random variables is to let them be continuous, and have a discriminator check if they’re discrete.
- Adversarially Regularized Autoencoders for Generating Discrete Structures
- GANS for Sequences of Discrete Elements with the Gumbel-softmax Distribution
- Breaking Sticks and Ambiguities with Adaptive Skip-gram - word2vec with multiple meanings for each word.
- Program Synthesis for Character-Level Language Modeling
- Hierarchical Multiscale Recurrent Neural Networks
- Generating and designing DNA with deep generative models
- Learning to Compose Words into Sentences with Reinforcement Learning

### Week 7 - Feb 23rd - Bayesian nonparametrics

Models of infinitely-large discrete objects.

- Slides on Bayesian nonparametrics
- Lecture notes on Bayesian nonparametrics
- Warped Mixtures for Nonparametric Cluster Shapes
- Structure Discovery in Nonparametric Regression through Compositional Kernel Search
- Learning the Structure of Deep Sparse Graphical Models

### Week 8 - March 2nd - Learning model structure

- The discovery of structural form - put a grammar on model structures and built a different model for each dataset automatically.
- Exploiting compositionality to explore a large space of model structures - another systematic search through model structure using a grammar.
- Bayesian Compression for Deep Learning - putting a sparse prior on a neural network’s weights is a principled way to learn its structure.

### Week 9 - March 9th - Variational optimization and evolutionary strategies

- Evolution Strategies as a Scalable Alternative to Reinforcement Learning
- Optimization by Variational Bounding
- Natural Evolution Strategies
- Parallel Gaussian Perturbation