{"id":578,"date":"2014-12-23T12:59:49","date_gmt":"2014-12-23T12:59:49","guid":{"rendered":"https:\/\/blogs.technet.microsoft.com\/inside_microsoft_research\/2014\/12\/23\/new-research-brings-precision-to-sampling-methods-used-in-statistics-and-machine-learning\/"},"modified":"2016-07-20T07:29:34","modified_gmt":"2016-07-20T14:29:34","slug":"new-research-brings-precision-to-sampling-methods-used-in-statistics-and-machine-learning","status":"publish","type":"post","link":"https:\/\/www.microsoft.com\/en-us\/research\/blog\/new-research-brings-precision-to-sampling-methods-used-in-statistics-and-machine-learning\/","title":{"rendered":"New Research Brings Precision to Sampling Methods Used in Statistics and Machine Learning"},"content":{"rendered":"

Posted by George Thomas Jr.<\/span><\/p>\n

Addressing one of the core problems in statistics and machine learning (opens in new tab)<\/span><\/a>, Microsoft researchers have developed a new, more efficient algorithm that enables exact sampling.<\/p>\n<\/p>\n\n\n\n\n
\"Daniel<\/td>\n<\/tr>\n
Daniel Tarlow and Tom Minka<\/strong><\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Researchers Daniel Tarlow (opens in new tab)<\/span><\/a>, Tom Minka (opens in new tab)<\/span><\/a>, and former Microsoft intern Chris Maddison (opens in new tab)<\/span><\/a> introduced the algorithm in their paper, A* Sampling (opens in new tab)<\/span><\/a><\/em>, one of only two of the 1,700 submitted that received an Outstanding Paper Award at NIPS 2014 (opens in new tab)<\/span><\/a>, the renowned machine learning conference of the Neural Information Processing Systems Foundation.<\/p>\n

“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 (opens in new tab)<\/span><\/a>, Distinguished Scientist and Laboratory Director of Microsoft Research Cambridge (opens in new tab)<\/span><\/a>.<\/p>\n

In their paper, the authors present a new construction of the Gumbel (opens in new tab)<\/span><\/a> 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 (opens in new tab)<\/span><\/a>, whereas previous solutions were forced to resort to approximate sampling.<\/p>\n

\"Illustration<\/p>\n

Illustration of A* sampling<\/b><\/span><\/p>\n

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.<\/p>\n

“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.<\/p>\n

“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.”<\/p>\n

Tarlow’s hope for the future is these findings will lead to probabilistic reasoning (opens in new tab)<\/span><\/a> 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.<\/p>\n

Machine learning is a key focus of Microsoft Research (@MSFTResearch (opens in new tab)<\/span><\/a>) and has led to numerous product contributions (opens in new tab)<\/span><\/a> that include Microsoft Office (opens in new tab)<\/span><\/a>, SQL Server<\/a>, Xbox One<\/a>, Cortana speech recognition<\/a>, and Skype Translator (opens in new tab)<\/span><\/a>.<\/p>\n

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.<\/p><\/p>\n","protected":false},"excerpt":{"rendered":"

Posted by George Thomas Jr. 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 […]<\/p>\n","protected":false},"author":0,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":[],"msr_hide_image_in_river":0,"footnotes":""},"categories":[1],"tags":[200195,200897,201195,201781,186418,196435,203063,203387,204297],"research-area":[],"msr-region":[],"msr-event-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-impact-theme":[],"msr-promo-type":[],"msr-podcast-series":[],"class_list":["post-578","post","type-post","status-publish","format-standard","hentry","category-research-blog","tag-a-sampling","tag-chris-maddison","tag-daniel-tarlow","tag-gumbel-max-trick","tag-machine-learning","tag-microsoft-research-cambridge","tag-nips-2014","tag-probabilistic-reasoning","tag-tom-minka","msr-locale-en_us"],"msr_event_details":{"start":"","end":"","location":""},"podcast_url":"","podcast_episode":"","msr_research_lab":[],"msr_impact_theme":[],"related-publications":[],"related-downloads":[],"related-videos":[],"related-academic-programs":[],"related-groups":[],"related-projects":[],"related-events":[],"related-researchers":[],"msr_type":"Post","byline":"","formattedDate":"December 23, 2014","formattedExcerpt":"Posted by George Thomas Jr. 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…","locale":{"slug":"en_us","name":"English","native":"","english":"English"},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/578","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/post"}],"replies":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/comments?post=578"}],"version-history":[{"count":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/578\/revisions"}],"predecessor-version":[{"id":260883,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/578\/revisions\/260883"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=578"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/categories?post=578"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/tags?post=578"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=578"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=578"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=578"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=578"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=578"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=578"},{"taxonomy":"msr-promo-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-promo-type?post=578"},{"taxonomy":"msr-podcast-series","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-podcast-series?post=578"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}