Addressing one of the core problems in statistics and machine learning, Microsoft researchers have developed a new, more efficient algorithm that enables exact sampling.
 |
| Daniel Tarlow and Tom Minka |
Researchers Daniel Tarlow, Tom Minka, and former Microsoft intern Chris Maddison introduced the algorithm in their paper, A* Sampling, one of only two of the 1,700 submitted that received an Outstanding Paper Award at NIPS 2014, the renowned machine learning conference of the Neural Information Processing Systems Foundation.
“This research makes a very significant advance in the efficiency of sampling, which is a core component of probabilistic modelling and reasoning systems,” said Andrew Blake, Distinguished Scientist and Laboratory Director of Microsoft Research Cambridge.
In their paper, the authors present a new construction of the Gumbel process and A* sampling -- an algorithm that searches for the maximum of a Gumbel process using A* search -- and explain how their approach, from a different perspective, enables exact sampling, whereas previous solutions were forced to resort to approximate sampling.
Citing inspiration from an algorithm for sampling from a discrete distribution known as the “Gumbel-Max trick,” the authors note how an exact sample results by adding independent Gumbel perturbations to each configuration of a discrete negative energy function and returning the argmax configuration of the perturbed negative energy function.
“Our first key observation,” the authors write, “is that we can apply the Gumbel-Max trick without instantiating all of the (possibly exponentially many) Gumbel perturbations.
The same basic idea then allows us to extend the Gumbel-Max trick to continuous spaces where there will be infinitely many independent perturbations.
“Intuitively, for any given random energy function, there are many perturbation values that are irrelevant to determining the argmax so long as we have an upper bound on their values. We will show how to instantiate the relevant ones and bound the irrelevant ones, allowing us to find the argmax -- and thus an exact sample.”
Tarlow’s hope for the future is these findings will lead to probabilistic reasoning systems that are more powerful and easier to use than current systems. “When we can provide stronger guarantees about the quality of outputs from our inference algorithms, it becomes easier to use these algorithms inside larger systems and to build tools that can be used reliably by non-experts,” he said.
Machine learning is a key focus of Microsoft Research (@MSFTResearch) and has led to numerous product contributions that include Microsoft Office, SQL Server, Xbox One, Cortana speech recognition, and Skype Translator.
The Neural Information Processing Systems Foundation is a non-profit corporation whose purpose is to foster the exchange of research on neural information processing systems in their biological, technological, mathematical, and theoretical aspects.
Microsoft Research
