Estimating the partition function of graphical models using Langevin importance sampling

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.