Estimating the partition function of graphical models using Langevin importance sampling

Jianzhu Ma, Jian Peng, Sheng Wang, Jinbo Xu

Research output: Contribution to journalConference article

Abstract

Graphical models are powerful in modeling a variety of real-world applications. Com- puting the partition function of a graphical model is known as an NP-hard problem for a general graph. A few sampling algorithm- s like Markov chain Monte Carlo (MCMC), Simulated Annealing Sampling (SAS), An- nealed Importance Sampling (AIS) are de- veloped to approximate the partition func- tion. This paper presents a new Langevin Importance Sampling (LIS) algorithm to ad- dress this challenge. LIS performs a ran- dom walk in the configuration-temperature space guided by the Langevin equation and estimates the partition function using all the samples generated during the random walk at all the temperatures, as opposed to the other configuration-temperature sampling method- s, which use only the samples at a specific temperature. Experimental results on sev- eral benchmark graphical models show that LIS can obtain much more accurate partition function than the others. LIS performs espe- cially well on relatively large graphical mod- els or those with a large number of local op- tima.

Original languageEnglish (US)
Pages (from-to)433-441
Number of pages9
JournalJournal of Machine Learning Research
Volume31
StatePublished - Jan 1 2013
Externally publishedYes
Event16th International Conference on Artificial Intelligence and Statistics, AISTATS 2013 - Scottsdale, United States
Duration: Apr 29 2013May 1 2013

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Estimating the partition function of graphical models using Langevin importance sampling'. Together they form a unique fingerprint.

  • Cite this