Timezone: »
The problem of drawing samples from a discrete distribution can be converted into a discrete optimization problem. In this work, we show how sampling from a continuous distribution can be converted into an optimization problem over continuous space. Central to the method is a stochastic process recently described in mathematical statistics that we call the Gumbel process. We present a new construction of the Gumbel process and A* sampling, a practical generic sampling algorithm that searches for the maximum of a Gumbel process using A* search. We analyze the correctness and convergence time of A* sampling and demonstrate empirically that it makes more efficient use of bound and likelihood evaluations than the most closely related adaptive rejection sampling-based algorithms.
Author Information
Chris Maddison (University of Oxford / DeepMind)
Daniel Tarlow (Google Brain)
Tom Minka (MSR)
Related Events (a corresponding poster, oral, or spotlight)
-
2014 Oral: A* Sampling »
Wed Dec 10th 09:20 -- 09:40 PM Room Level 2, room 210
More from the Same Authors
-
2014 Workshop: Perturbations, Optimization, and Statistics »
Tamir Hazan · George Papandreou · Daniel Tarlow -
2014 Poster: Just-In-Time Learning for Fast and Flexible Inference »
S. M. Ali Eslami · Daniel Tarlow · Pushmeet Kohli · John Winn -
2013 Workshop: Perturbations, Optimization, and Statistics »
Tamir Hazan · George Papandreou · Sasha Rakhlin · Daniel Tarlow -
2013 Poster: Annealing between distributions by averaging moments »
Roger Grosse · Chris Maddison · Russ Salakhutdinov -
2013 Poster: Learning to Pass Expectation Propagation Messages »
Nicolas Heess · Daniel Tarlow · John Winn -
2013 Oral: Annealing between distributions by averaging moments »
Roger Grosse · Chris Maddison · Russ Salakhutdinov -
2012 Workshop: Perturbations, Optimization, and Statistics »
Tamir Hazan · George Papandreou · Daniel Tarlow -
2012 Poster: Bayesian n-Choose-k Models for Classification and Ranking »
Kevin Swersky · Daniel Tarlow · Richard Zemel · Ryan Adams · Brendan J Frey -
2012 Poster: Cardinality Restricted Boltzmann Machines »
Kevin Swersky · Daniel Tarlow · Ilya Sutskever · Richard Zemel · Russ Salakhutdinov · Ryan Adams -
2011 Poster: Non-conjugate Variational Message Passing for Multinomial and Binary Regression »
David A Knowles · Tom Minka -
2008 Demonstration: Infer.NET: Software for Graphical Models »
Tom Minka · John Winn · John P Guiver · Anitha Kannan -
2008 Poster: Gates »
Tom Minka · John Winn -
2008 Spotlight: Gates »
Tom Minka · John Winn -
2007 Poster: TrueSkill Through Time: Revisiting the History of Chess »
Pierre Dangauthier · Ralf Herbrich · Tom Minka · Thore K Graepel -
2007 Spotlight: TrueSkill Through Time: Revisiting the History of Chess »
Pierre Dangauthier · Ralf Herbrich · Tom Minka · Thore K Graepel -
2006 Poster: TrueSkill: A Bayesian Skill Rating System »
Ralf Herbrich · Tom Minka · Thore K Graepel -
2006 Poster: Using Combinatorial Optimization within Max-Product Belief Propagation »
John Duchi · Daniel Tarlow · Gal Elidan · Daphne Koller -
2006 Spotlight: Using Combinatorial Optimization within Max-Product Belief Propagation »
John Duchi · Daniel Tarlow · Gal Elidan · Daphne Koller -
2006 Talk: TrueSkill: A Bayesian Skill Rating System »
Ralf Herbrich · Tom Minka · Thore K Graepel