Estimating the Partition Function of Graphical Models Using Langevin Importance Sampling

Jianzhu Ma, Jian Peng, Sheng Wang, Jinbo Xu
Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, PMLR 31:433-441, 2013.

Abstract

Graphical models are powerful in modeling a variety of applications. Computing the partition function of a graphical model is a typical inference problem and known as an NP-hard problem for general graphs. A few sampling algorithms like MCMC, Simulated Annealing Sampling (SAS), Annealed Importance Sampling (AIS) are developed to address this challenging problem. This paper describes a Langevin Importance Sampling (LIS) algorithm to compute the partition function of a graphical model. LIS first performs a random walk in the configuration-temperature space guided by the Langevin equation and then estimates the partition function using all the samples generated during the random walk, as opposed to the other configuration-temperature sampling methods, which uses only the samples at a specific temperature. Experimental results show that LIS can obtain much more accurate partition function than the others tested on several different types of graphical models. LIS performs especially well on relatively large graph models or those with a large number of local optima.

Cite this Paper

BibTeX
@InProceedings{pmlr-v31-ma13a, title = {Estimating the Partition Function of Graphical Models Using Langevin Importance Sampling }, author = {Ma, Jianzhu and Peng, Jian and Wang, Sheng and Xu, Jinbo}, booktitle = {Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics}, pages = {433--441}, year = {2013}, editor = {Carvalho, Carlos M. and Ravikumar, Pradeep}, volume = {31}, series = {Proceedings of Machine Learning Research}, address = {Scottsdale, Arizona, USA}, month = {29 Apr--01 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v31/ma13a.pdf}, url = {https://proceedings.mlr.press/v31/ma13a.html}, abstract = {Graphical models are powerful in modeling a variety of applications. Computing the partition function of a graphical model is a typical inference problem and known as an NP-hard problem for general graphs. A few sampling algorithms like MCMC, Simulated Annealing Sampling (SAS), Annealed Importance Sampling (AIS) are developed to address this challenging problem. This paper describes a Langevin Importance Sampling (LIS) algorithm to compute the partition function of a graphical model. LIS first performs a random walk in the configuration-temperature space guided by the Langevin equation and then estimates the partition function using all the samples generated during the random walk, as opposed to the other configuration-temperature sampling methods, which uses only the samples at a specific temperature. Experimental results show that LIS can obtain much more accurate partition function than the others tested on several different types of graphical models. LIS performs especially well on relatively large graph models or those with a large number of local optima.} }
Endnote
%0 Conference Paper %T Estimating the Partition Function of Graphical Models Using Langevin Importance Sampling %A Jianzhu Ma %A Jian Peng %A Sheng Wang %A Jinbo Xu %B Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2013 %E Carlos M. Carvalho %E Pradeep Ravikumar %F pmlr-v31-ma13a %I PMLR %P 433--441 %U https://proceedings.mlr.press/v31/ma13a.html %V 31 %X Graphical models are powerful in modeling a variety of applications. Computing the partition function of a graphical model is a typical inference problem and known as an NP-hard problem for general graphs. A few sampling algorithms like MCMC, Simulated Annealing Sampling (SAS), Annealed Importance Sampling (AIS) are developed to address this challenging problem. This paper describes a Langevin Importance Sampling (LIS) algorithm to compute the partition function of a graphical model. LIS first performs a random walk in the configuration-temperature space guided by the Langevin equation and then estimates the partition function using all the samples generated during the random walk, as opposed to the other configuration-temperature sampling methods, which uses only the samples at a specific temperature. Experimental results show that LIS can obtain much more accurate partition function than the others tested on several different types of graphical models. LIS performs especially well on relatively large graph models or those with a large number of local optima.
RIS
TY - CPAPER TI - Estimating the Partition Function of Graphical Models Using Langevin Importance Sampling AU - Jianzhu Ma AU - Jian Peng AU - Sheng Wang AU - Jinbo Xu BT - Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics DA - 2013/04/29 ED - Carlos M. Carvalho ED - Pradeep Ravikumar ID - pmlr-v31-ma13a PB - PMLR DP - Proceedings of Machine Learning Research VL - 31 SP - 433 EP - 441 L1 - http://proceedings.mlr.press/v31/ma13a.pdf UR - https://proceedings.mlr.press/v31/ma13a.html AB - Graphical models are powerful in modeling a variety of applications. Computing the partition function of a graphical model is a typical inference problem and known as an NP-hard problem for general graphs. A few sampling algorithms like MCMC, Simulated Annealing Sampling (SAS), Annealed Importance Sampling (AIS) are developed to address this challenging problem. This paper describes a Langevin Importance Sampling (LIS) algorithm to compute the partition function of a graphical model. LIS first performs a random walk in the configuration-temperature space guided by the Langevin equation and then estimates the partition function using all the samples generated during the random walk, as opposed to the other configuration-temperature sampling methods, which uses only the samples at a specific temperature. Experimental results show that LIS can obtain much more accurate partition function than the others tested on several different types of graphical models. LIS performs especially well on relatively large graph models or those with a large number of local optima. ER -
APA
Ma, J., Peng, J., Wang, S. & Xu, J.. (2013). Estimating the Partition Function of Graphical Models Using Langevin Importance Sampling . Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 31:433-441 Available from https://proceedings.mlr.press/v31/ma13a.html.

Related Material