nips nips2007 nips2007-75 nips2007-75-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ozgur Sumer, Umut Acar, Alexander T. Ihler, Ramgopal R. Mettu
Abstract: Motivated by stochastic systems in which observed evidence and conditional dependencies between states of the network change over time, and certain quantities of interest (marginal distributions, likelihood estimates etc.) must be updated, we study the problem of adaptive inference in tree-structured Bayesian networks. We describe an algorithm for adaptive inference that handles a broad range of changes to the network and is able to maintain marginal distributions, MAP estimates, and data likelihoods in all expected logarithmic time. We give an implementation of our algorithm and provide experiments that show that the algorithm can yield up to two orders of magnitude speedups on answering queries and responding to dynamic changes over the sum-product algorithm. 1
[1] Umut A. Acar, Guy E. Blelloch, Matthias Blume, and Kanat Tangwongsan. An experimental analysis of self-adjusting computation. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2006.
[2] Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes, and Maverick Woo. Dynamizing static algorithms with applications to dynamic trees and history independence. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004.
[3] Umut A. Acar, Guy E. Blelloch, and Jorge L. Vittes. An experimental analysis of change propagation in dynamic trees. In Workshop on Algorithm Engineering and Experimentation (ALENEX), 2005.
[4] H. M. Berman, J. Westbrook, Z. Feng, G. Gilliland, T. N. Bhat, H. Weissig, I. N. Shindyalov, and P. E. Bourne. The protein data bank. Nucl. Acids Res., 28:235–242, 2000.
[5] P. Clifford. Markov random fields in statistics. In G. R. Grimmett and D. J. A. Welsh, editors, Disorder in Physical Systems, pages 19–32. Oxford University Press, Oxford, 1990.
[6] A. L. Delcher, A. J. Grove, S. Kasif, and J. Pearl. Logarithmic-time updates and queries in probabilistic networks. Journal of Artificial Intelligence Research, 4:37–59, 1995.
[7] R. L. Dunbrack Jr. Rotamer libraries in the 21st century. Curr Opin Struct Biol, 12(4):431–440, 2002.
[8] M. I. Jordan. Graphical models. Statistical Science, 19:140–155, 2004.
[9] H. Kamisetty, E. P Xing, and C. J. Langmead. Free energy estimates of all-atom protein structures using generalized belief propagation. In Proceedings of the 11th Annual International Conference on Research in Computational Molecular Biology, 2007. To appear.
[10] F. Kschischang, B. Frey, and H.-A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47:498–519, 2001.
[11] R. McEliece and S. M. Aji. The generalized distributive law. IEEE Transactions on Information Theory, 46(2):325–343, March 2000.
[12] Marina Meil˘ and Michael I. Jordan. Learning with mixtures of trees. Journal of Machine Learning a Research, 1(1):1–48, October 2000.
[13] Gary L. Miller and John H. Reif. Parallel tree contraction and its application. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, pages 487–489, 1985.
[14] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco, 1988.
[15] M. J. Wainwright, T. Jaakkola, and A. S. Willsky. Tree consistency and bounds on the performance of the max-product algorithm and its generalizations. Statistics and Computing, 14:143–166, April 2004.
[16] 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.
[17] C. Yanover and Y. Weiss. Approximate inference and protein folding. In Proceedings of Neural Information Processing Systems Conference, pages 84–86, 2002. 8