nips nips2011 nips2011-229 nips2011-229-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Michael L. Wick, Andrew McCallum
Abstract: Traditional approaches to probabilistic inference such as loopy belief propagation and Gibbs sampling typically compute marginals for all the unobserved variables in a graphical model. However, in many real-world applications the user’s interests are focused on a subset of the variables, specified by a query. In this case it would be wasteful to uniformly sample, say, one million variables when the query concerns only ten. In this paper we propose a query-specific approach to MCMC that accounts for the query variables and their generalized mutual information with neighboring variables in order to achieve higher computational efficiency. Surprisingly there has been almost no previous work on query-aware MCMC. We demonstrate the success of our approach with positive experimental results on a wide range of graphical models. 1
[1] Yucheng Low, Joseph Gonzalez, Aapo Kyrola, Danny Bickson, Carlos Guestrin, and Joseph M. Hellerstein. Graphlab: A new parallel framework for machine learning. In Conference on Uncertainty in Artificial Intelligence (UAI), Catalina Island, California, July 2010.
[2] Sameer Singh, Amarnag Subramanya, Fernando Pereira, and Andrew McCallum. Large-scale cross-document coreference using distributed inference and hierarchical models. In Association for Computational Linguistics: Human Language Technologies (ACL HLT), 2011.
[3] Arthur Choi and Adnan Darwiche. Focusing generalizations of belief propagation on targeted queries. In Association for the Advancement of Artificial Intelligence (AAAI), 2008.
[4] Anton Chechetka and Carlos Guestrin. Focused belief propagation for query-specific inference. In International Conference on Artificial Intelligence and Statistics (AI STATS), 2010.
[5] Nilesh Dalvi and Dan Suciu. The dichotomy of conjunctive queries on probabilistic structures. Technical Report 0612102, University of Washington, 2007.
[6] Prithviraj Sen, Amol Deshpande, and Lise Getoor. Exploiting shared correlations in probabilistic databases. In Very Large Data Bases (VLDB), 2008.
[7] Daisy Zhe Wang, Eirlinaios Michelakis, Minos Garofalakis, and Joseph M. Hellerstein. BayesStore: Managing large, uncertain data repositories with probabilistic graphical models. In Very Large Data Bases (VLDB), 2008.
[8] Hoifung Poon and Pedro Domingos. Joint inference in information extraction. In Association for the Advancement of Artificial Intelligence, pages 913–918, Vancouver, Canada, 2007.
[9] Aron Culotta, Michael Wick, Robert Hall, and Andrew McCallum. First-order probabilistic models for coreference resolution. In Human Language Technology Conf. of the North American Chapter of the Assoc. of Computational Linguistics (HLT/NAACL), pages 81–88, 2007.
[10] Adrian Barbu and Song Chun Zhu. Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities. IEEE Trans. Pattern Anal. Mach. Intell., 27(8):1239–1253, 2005.
[11] Ruslan Salakhutdinov and Geoffrey Hinton. Deep Boltzmann machines. In International Conference on Artificial Intelligence and Statistics (AI STATS), 2009.
[12] Bhaskara Marthi, Hanna Pasula, Stuart Russell, and Yuval Peres. Decayed MCMC filtering. In Conference on Uncertainty in Artificial Intelligence (UAI), pages 319–326, 2002.
[13] Michael Wick, Andrew McCallum, and Gerome Miklau. Scalable probabilistic databases with factor graphs and MCMC. In Very Large Data Bases (VLDB), pages 794–804, 2010.
[14] Michael Wick, Andrew McCallum, and Gerome Miklau. Representing uncertainty in probabilistic databases with scalable factor graphs. Master’s thesis, University of Massachusetts, proposed September 2008 and submitted April 2009.
[15] Daisy Zhe Wang, Michael J. Franklin, Minos Garofalakis, Joseph M. Hellerstein, and Michael L. Wick. Hybrid in-database inference for declarative information extraction. In Proceedings of the 2011 international conference on Management of data, SIGMOD ’11, pages 517–528, New York, NY, USA, 2011. ACM.
[16] R.H. Swendsen and J.S. Wang. Nonuniversal critical dynamics in MC simulations. Phys. Rev. Lett., 58(2):68–88, 1987.
[17] Radford Neal. Slice sampling. Annals of Statistics, 31:705–767, 2000. 9