Efficient Sampling from Combinatorial Space via Bridging

Dahua Lin, John Fisher
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:694-702, 2012.

Abstract

MCMC sampling has been extensively studied and used in probabilistic inference. Many algorithms rely on local updates to explore the space, often resulting in slow convergence or failure to mix when there is no path from one set of states to another via local changes. We propose an efficient method for sampling from combinatorial spaces that addresses these issues via “bridging states” that facilitate the communication between different parts of the space. Such states can be created dynamically, providing more flexibility than methods relying on specific space structures to design jump proposals. Theoretical analysis of the approach yields bounds on mixing times. Empirical analysis demonstrates the practical utility on two problems: constrained map labeling and inferring partial order of object layers in a video.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-lin12, title = {Efficient Sampling from Combinatorial Space via Bridging}, author = {Lin, Dahua and Fisher, John}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {694--702}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/lin12/lin12.pdf}, url = {https://proceedings.mlr.press/v22/lin12.html}, abstract = {MCMC sampling has been extensively studied and used in probabilistic inference. Many algorithms rely on local updates to explore the space, often resulting in slow convergence or failure to mix when there is no path from one set of states to another via local changes. We propose an efficient method for sampling from combinatorial spaces that addresses these issues via “bridging states” that facilitate the communication between different parts of the space. Such states can be created dynamically, providing more flexibility than methods relying on specific space structures to design jump proposals. Theoretical analysis of the approach yields bounds on mixing times. Empirical analysis demonstrates the practical utility on two problems: constrained map labeling and inferring partial order of object layers in a video.} }
Endnote
%0 Conference Paper %T Efficient Sampling from Combinatorial Space via Bridging %A Dahua Lin %A John Fisher %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-lin12 %I PMLR %P 694--702 %U https://proceedings.mlr.press/v22/lin12.html %V 22 %X MCMC sampling has been extensively studied and used in probabilistic inference. Many algorithms rely on local updates to explore the space, often resulting in slow convergence or failure to mix when there is no path from one set of states to another via local changes. We propose an efficient method for sampling from combinatorial spaces that addresses these issues via “bridging states” that facilitate the communication between different parts of the space. Such states can be created dynamically, providing more flexibility than methods relying on specific space structures to design jump proposals. Theoretical analysis of the approach yields bounds on mixing times. Empirical analysis demonstrates the practical utility on two problems: constrained map labeling and inferring partial order of object layers in a video.
RIS
TY - CPAPER TI - Efficient Sampling from Combinatorial Space via Bridging AU - Dahua Lin AU - John Fisher BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-lin12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 694 EP - 702 L1 - http://proceedings.mlr.press/v22/lin12/lin12.pdf UR - https://proceedings.mlr.press/v22/lin12.html AB - MCMC sampling has been extensively studied and used in probabilistic inference. Many algorithms rely on local updates to explore the space, often resulting in slow convergence or failure to mix when there is no path from one set of states to another via local changes. We propose an efficient method for sampling from combinatorial spaces that addresses these issues via “bridging states” that facilitate the communication between different parts of the space. Such states can be created dynamically, providing more flexibility than methods relying on specific space structures to design jump proposals. Theoretical analysis of the approach yields bounds on mixing times. Empirical analysis demonstrates the practical utility on two problems: constrained map labeling and inferring partial order of object layers in a video. ER -
APA
Lin, D. & Fisher, J.. (2012). Efficient Sampling from Combinatorial Space via Bridging. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:694-702 Available from https://proceedings.mlr.press/v22/lin12.html.

Related Material