Skip to yearly menu bar Skip to main content


Poster

Embed and Project: Discrete Sampling with Universal Hashing

Stefano Ermon · Carla Gomes · Ashish Sabharwal · Bart Selman

Harrah's Special Events Center, 2nd Floor

Abstract:

We consider the problem of sampling from a probability distribution defined over a high-dimensional discrete set, specified for instance by a graphical model. We propose a sampling algorithm, called PAWS, based on embedding the set into a higher-dimensional space which is then randomly projected using universal hash functions to a lower-dimensional subspace and explored using combinatorial search methods. Our scheme can leverage fast combinatorial optimization tools as a blackbox and, unlike MCMC methods, samples produced are guaranteed to be within an (arbitrarily small) constant factor of the true probability distribution. We demonstrate that by using state-of-the-art combinatorial search tools, PAWS can efficiently sample from Ising grids with strong interactions and from software verification instances, while MCMC and variational methods fail in both cases.

Live content is unavailable. Log in and register to view live content