article

Free access

Adaptive Exact Inference in Graphical Models

Authors:

Özgür Sümer,

Alexander T. Ihler,

Ramgopal R. MettuAuthors Info & Claims

The Journal of Machine Learning Research, Volume 12

Pages 3147 - 3186

Published: 01 November 2011 Publication History

Abstract

Many algorithms and applications involve repeatedly solving variations of the same inference problem, for example to introduce new evidence to the model or to change conditional dependencies. As the model is updated, the goal of adaptive inference is to take advantage of previously computed quantities to perform inference more rapidly than from scratch. In this paper, we present algorithms for adaptive exact inference on general graphs that can be used to efficiently compute marginals and update MAP configurations under arbitrary changes to the input factor graph and its associated elimination tree. After a linear time preprocessing step, our approach enables updates to the model and the computation of any marginal in time that is logarithmic in the size of the input model. Moreover, in contrast to max-product our approach can also be used to update MAP configurations in time that is roughly proportional to the number of updated entries, rather than the size of the input model. To evaluate the practical effectiveness of our algorithms, we implement and test them using synthetic data as well as for two real-world computational biology applications. Our experiments show that adaptive inference can achieve substantial speedups over performing complete inference as the model undergoes small changes over time.

References

[1]

U. Acar, A. T. Ihler, R. R. Mettu, and Ö. Sümer. Adaptive Bayesian inference in general graphs. In Proceedings of the 24th Annual Conference on Uncertainty in Artificial Intelligence, pages 1-8, 2008.

[2]

U. A. Acar. Self-Adjusting Computation. PhD thesis, Department of Computer Science, Carnegie Mellon University, May 2005.

[3]

U. A. Acar, G. Blelloch, R. Harper, J. Vittes, and M. Woo. Dynamizing static algorithms with applications to dynamic trees and history independence. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004.

[4]

U. A. Acar, G. Blelloch, and J. Vittes. An experimental analysis of change propagation in dynamic trees. In Proc. 7th ACM-SIAM W. on Algorithm Eng. and Exp'ts, 2005.

[5]

U. A. Acar, Guy E. Blelloch, and Robert Harper. Adaptive functional programming. ACM Trans. Prog. Lang. Sys., 28(6):990-1034, 2006.

[6]

U. A. Acar, A. T. Ihler, R. R. Mettu, and Ö Sümer. Adaptive Bayesian inference. In Advances in Neural Information Processing Systems 20. MIT Press, 2007.

[7]

U. A. Acar, Guy E. Blelloch, Matthias Blume, Robert Harper, and Kanat Tangwongsan. An experimental analysis of self-adjusting computation. ACM Trans. Prog. Lang. Sys., 32(1):3:1-3:53, 2009a.

[8]

U. A. Acar, A. T. Ihler, R. R. Mettu, and ö. Sümer. Adaptive updates for maintaining MAP configurations with applications to bioinformatics. In Proceedings of the IEEE Workshop on Statistical Signal Processing, pages 413-416, 2009b.

[9]

A. A. Canutescu, A. A. Shelenkov, and R. L. Dunbrack Jr. A graph-theory algorithm for rapid protein side-chain prediction. Protein Sci, 12(9):2001-2014, Sep 2003.

[10]

W. Chu, Z. Ghahramani, and D.Wild. A graphical model for protein secondary structure prediction. In Proc. 21st International Conference on Machine Learning, 2004.

[11]

A. Darwiche. Modeling and Reasoning with Bayesian Networks. Cambridge, 1st edition, 2009.

[12]

A. Darwiche and M. Hopkins. Using recursive decomposition to construct elimination orders, jointrees, and dtrees. In Trends in Artificial Intelligence, Lecture Notes in AI, pages 180-191. Springer-Verlag, 2001.

[13]

R. Dechter. Bucket elimination: A unifying framework for probabilistic inference. In M. I. Jordan, editor, Learning in Graphical Models, pages 75-104. MIT Press, 1998.

[14]

A. L. Delcher, A. J. Grove, S. Kasif, and J. Pearl. Logarithmic-time updates and queries in probabilistic networks. J. Artificial Intelligence Research, 4:37-59, 1995.

[15]

R. L. Dunbrack Jr. Rotamer libraries in the 21st century. Curr Opin Struct Biol, 12(4):431-440, 2002.

[16]

D. Frishman and P. Argos. Knowledge-based protein secondary structure assignment. Proteins: Structure, Function and Genetics, 23:566-579, 1995.

[17]

M. A. Hammer, U. A. Acar, and Y. Chen. CEAL: a C-based language for self-adjusting computation. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2009.

[18]

W. Kabsch and C. Sander. Dictionary of protein secondary structure: pattern recognition of hydrogen-bonded and geometrical features. Biopolymers, 22(12):2577-2637, 1983.

[19]

H. Kamisetty, E. P. Xing, and C. J. Langmead. Free energy estimates of all-atom protein structures using generalized belief propagation. In Proc. 11th Ann. Int'l Conf. Research in Computational Molecular Biology, pages 366-380, 2007.

[20]

K. Kask, R. Dechter, J. Larrosa, and A. Dechter. Unifying cluster-tree decompositions for reasoning in graphical models. Artificial Intelligence, 166:165-193, 2005.

[21]

S. Koenig, M. Likhachev, Y. Liu, and David Furcy. Incremental heuristic search in artificial intelligence. Artificial Intelligence Magazine, 25:99-112, 2004.

[22]

P. Kohli and P. H. S. Torr. Dynamic graph cuts for efficient inference in markov random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29:2079-2088, 2007.

[23]

N. Komodakis, G. Tziritas, and N. Paragios. Performance vs computational efficiency for optimizing single and dynamic mrfs: Setting the state of the art with primal-dual strategies. Comput. Vis. Image Underst., 112:14-29, October 2008.

[24]

F. Kschischang, B. Frey, and H.-A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Trans. Inform. Theory, 47(2):498-519, February 2001.

[25]

S. Lauritzen and D. Spiegelhalter. Local computations with probabilities on graphical structures and their applications to expert systems. J. Royal Stat. Society, Ser. B, 50:157-224, 1988.

[26]

J.Martin, J.-F. Gibrat, and F. Rodolphe. Choosing the optimal hiddenMarkov model for secondarystructure prediction. IEEE Intelligent Systems, 20(6):19-25, 2005.

[27]

G. L. Miller and J. H. Reif. Parallel tree contraction and its application. In Proc. 26th IEEE Symp. Found. of Comp. Sci., pages 487-489, 1985.

[28]

V. Namasivayam, A. Pathak, and V. Prasanna. Scalable parallel implementation of bayesian network to junction tree conversion for exact inference. In Information Retrieval: Data Structures and Algorithms, pages 167-176. Prentice-Hall PTR, 2006.

[29]

J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufman, San Mateo, 1988.

[30]

D. M. Pennock. Logarithmic time parallel Bayesian inference. In Proc. 14th Annual Conf. on Uncertainty in Artificial Intelligence, pages 431-438, 1998.

[31]

D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362-391, 1983.

[32]

M. Wainwright, T. Jaakkola, and A. Willsky. MAP estimation via agreement on (hyper)trees: message-passing and linear programming approaches. IEEE Trans Info Theory, 51(11):3697- 3717, 2005a.

[33]

M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky. A new class of upper bounds on the log partition function. IEEE Trans Info Theory, 51(7):2313-2335, July 2005b.

[34]

S. J. Weiner, P.A. Kollman, D.A. Case, U.C. Singh, G. Alagona, S. Profeta Jr., and P. Weiner. A new force field for the molecular mechanical simulation of nucleic acids and proteins. J. Am. Chem. Soc., 106:765-784, 1984.

[35]

Y. Xia and V. K. Prasanna. Junction tree decomposition for parallel exact inference. In IEEE International Parallel and Distributed Preocessing Symposium, pages 1-12, 2008.

[36]

C. Yanover and Y. Weiss. Approximate inference and protein folding. In Proc. NIPS, pages 84-86, 2002.

[37]

J. S. Yedidia, W. T. Freeman, and Y. Weiss. Constructing free energy approximations and generalized belief propagation algorithms. Technical Report 2004-040, MERL, May 2004.

Cited By

Li KZhou XWang DGrant CDobra ADudley C(2017)In-database batch and query-time inference over probabilistic graphical models using UDA---GISTThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-016-0446-126:2(177-201)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s00778-016-0446-1
Papachristoudis GFisher J(2015)Adaptive belief propagationProceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 3710.5555/3045118.3045215(899-907)Online publication date: 6-Jul-2015
https://dl.acm.org/doi/10.5555/3045118.3045215
Pujara JLondon BGetoor L(2015)Budgeted online collective inferenceProceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence10.5555/3020847.3020921(712-721)Online publication date: 12-Jul-2015
https://dl.acm.org/doi/10.5555/3020847.3020921

Adaptive Exact Inference in Graphical Models
1. Computing methodologies

Recommendations

Adaptive inference for graphical models
Approximate inference in collective graphical models
ICML'13: Proceedings of the 30th International Conference on International Conference on Machine Learning - Volume 28

We study the problem of approximate inference in collective graphical models (CGMs), which were recently introduced to model the problem of learning and inference with noisy aggregate observations. We first analyze the complexity of inference in CGMs: ...
Scalable exact MAP inference in graphical models
ECAI'16: Proceedings of the Twenty-second European Conference on Artificial Intelligence

This paper presents parallel dovetailing in a distributed-memory environment for exact MAP inference in graphical models. Parallel dovetailing is a simple procedure which performs multiple searches in parallel with different parameter configurations. We ...

Comments

Information & Contributors

Information

Published In

cover image The Journal of Machine Learning Research

The Journal of Machine Learning Research Volume 12, Issue

2/1/2011

3426 pages

ISSN:1532-4435

EISSN:1533-7928

Issue’s Table of Contents

Publisher

JMLR.org

Publication History

Published: 01 November 2011

Published in JMLR Volume 12

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
124
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)13

Reflects downloads up to 27 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li KZhou XWang DGrant CDobra ADudley C(2017)In-database batch and query-time inference over probabilistic graphical models using UDA---GISTThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-016-0446-126:2(177-201)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s00778-016-0446-1
Papachristoudis GFisher J(2015)Adaptive belief propagationProceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 3710.5555/3045118.3045215(899-907)Online publication date: 6-Jul-2015
https://dl.acm.org/doi/10.5555/3045118.3045215
Pujara JLondon BGetoor L(2015)Budgeted online collective inferenceProceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence10.5555/3020847.3020921(712-721)Online publication date: 12-Jul-2015
https://dl.acm.org/doi/10.5555/3020847.3020921

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents