jmlr jmlr2011 jmlr2011-7 jmlr2011-7-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Özgür Sümer, Umut A. Acar, Alexander T. Ihler, Ramgopal R. Mettu
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. Keywords: exact inference, factor graphs, factor elimination, marginalization, dynamic programming, MAP computation, model updates, parallel tree contraction ¨ u u c 2011 Ozg¨ r S¨ mer, Umut A. Acar, Alexander T. Ihler and Ramgopal R. Mettu. ¨ S UMER , ACAR , I HLER AND M ETTU
¨ u U. Acar, A. T. Ihler, R. R. Mettu, and O. S¨ mer. Adaptive Bayesian inference in general graphs. In Proceedings of the 24th Annual Conference on Uncertainty in Artificial Intelligence, pages 1–8, 2008. 3183 ¨ S UMER , ACAR , I HLER AND M ETTU U. A. Acar. Self-Adjusting Computation. PhD thesis, Department of Computer Science, Carnegie Mellon University, May 2005. 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. 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. U. A. Acar, Guy E. Blelloch, and Robert Harper. Adaptive functional programming. ACM Trans. Prog. Lang. Sys., 28(6):990–1034, 2006. ¨ u U. A. Acar, A. T. Ihler, R. R. Mettu, and O S¨ mer. Adaptive Bayesian inference. In Advances in Neural Information Processing Systems 20. MIT Press, 2007. 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. ¨ u U. A. Acar, A. T. Ihler, R. R. Mettu, and O. 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. 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. W. Chu, Z. Ghahramani, and D. Wild. A graphical model for protein secondary structure prediction. In Proc. 21st International Conference on Machine Learning, 2004. A. Darwiche. Modeling and Reasoning with Bayesian Networks. Cambridge, 1st edition, 2009. 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. 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. 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. R. L. Dunbrack Jr. Rotamer libraries in the 21st century. Curr Opin Struct Biol, 12(4):431–440, 2002. D. Frishman and P. Argos. Knowledge-based protein secondary structure assignment. Proteins: Structure, Function and Genetics, 23:566–579, 1995. 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. 3184 A DAPTIVE E XACT I NFERENCE IN G RAPHICAL M ODELS W. Kabsch and C. Sander. Dictionary of protein secondary structure: pattern recognition of hydrogen-bonded and geometrical features. Biopolymers, 22(12):2577–2637, 1983. 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. K. Kask, R. Dechter, J. Larrosa, and A. Dechter. Unifying cluster-tree decompositions for reasoning in graphical models. Artificial Intelligence, 166:165–193, 2005. S. Koenig, M. Likhachev, Y. Liu, and David Furcy. Incremental heuristic search in artificial intelligence. Artificial Intelligence Magazine, 25:99–112, 2004. 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. 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. 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. 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. J. Martin, J.-F. Gibrat, and F. Rodolphe. Choosing the optimal hidden Markov model for secondarystructure prediction. IEEE Intelligent Systems, 20(6):19–25, 2005. 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. 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. J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufman, San Mateo, 1988. D. M. Pennock. Logarithmic time parallel Bayesian inference. In Proc. 14th Annual Conf. on Uncertainty in Artificial Intelligence, pages 431–438, 1998. D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362–391, 1983. 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. 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. 3185 ¨ S UMER , ACAR , I HLER AND M ETTU 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. 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. C. Yanover and Y. Weiss. Approximate inference and protein folding. In Proc. NIPS, pages 84–86, 2002. 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. 3186