Reconfigurable computing for learning Bayesian networks

ABSTRACT

Learning the structure of Bayesian networks(BNs) is known to be NP-complete and most of the recent work in the field is based on heuristics. Many recent approaches to the problem trade correctness and exactness for faster computation and are still computationally infeasible, except for networks with few variables. In this paper we present a software/hardware co-design approach to learning Bayesian networks from experimental data that is scalable to very large networks. Our implementation improves the performance of algorithms that are traditionally developed based on the Von Neumann computing paradigm by more than four orders of magnitude. Through parallel implementation and exploitation of the reconfigurability of Field Programmable Gate Array (FPGA) systems our design enables scientists to apply BN learning techniques to large problems such as studies in molecular biology where the number of variables in the system overwhelms any state of the art software implementations. We describe how we combine Markov Chain Monte Carlo (MCMC) sampling with Bayesian network learning techniques as well as supervised learning methods in a parallel and scalable design. We also present how our design is mapped and customized to run on the Berkeley Emulation Engine 2 (BEE2) multi-FPGA system. Experimental results are presented on synthetic data sets generated from standard Bayesian networks as well as a real life problem in the context of systems biology

REFERENCES

• 1: Bayesian Networks Repository: http://compbio.cs.huji.ac.il/Repository/.
• 2: BEE2 Website: http://bee2.eecs.berkeley.edu/.
• 3: L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth and Brooks, Monterey, CA, 1984.
• 4: Wray Buntine, Theory refinement on Bayesian networks, Proceedings of the seventh conference (1991) on Uncertainty in artificial intelligence, p.52-60, June 1994, Los Angeles, California, United States
• 5: Chen Chang , John Wawrzynek , Robert W. Brodersen, BEE2: A High-End Reconfigurable Computing System, IEEE Design & Test, v.22 n.2, p.114-125, March 2005 [doi>10.1109/MDT.2005.30]
• 6: D.M. Chickering. Learning bayesian networks is np-complete. In Learning from Data: Artificial Intelligence and Statistics. V. Springer Verlag, 1996.
• 7: Gregory F. Cooper , Edward Herskovits, A Bayesian Method for the Induction of Probabilistic Networks from Data, Machine Learning, v.9 n.4, p.309-347, Oct. 1992 [doi>10.1023/A:1022649401552]
• 8: G.F. Cooper and C. Yoo. Causal discovery from a mixture of experimental and observational data. In UAI, pages 116--125, 1999.
• 9: B. Ellis and W. Wong. Sampling bayesian network quickly. In Interface, 2006.
• 10: J. Friedman. Greedy function approximation: a gradient boosting machine, 1999.
• 11: Jerome H. Friedman, Stochastic gradient boosting, Computational Statistics & Data Analysis, v.38 n.4, p.367-378, 28 February 2002 [doi>10.1016/S0167-9473(01)00065-2]
• 12: N. Friedman and D. Koller. Being Bayesian about Bayesian network structure: A Bayesian approach to structure discovery in Bayesian networks. Machine Learning, 50(1-2):95--125, 2003. Full version of UAI 2000 paper.
• 13: N. Friedman, I. Nachman, and D. Pe'er. Learning bayesian network structure from massive datasets: The "sparse candidate" algorithm. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, pages 206--215.
• 14: D. Geiger and D. Heckerman. Learning gaussian networks. Technical Report MSR-TR-94-10, Redmond, WA, 1994.
• 15: C.J. Geyer. Markov chain monte carlo maximum likelihood. In Computing Science and Statistics: Proceedings of 23rd Symposium on the Interface Foundation, pages 156--163. Fairfax Station, 1991.
• 16: W.K. Hastings. Monte carlo sampling methods using markov chains and their applications. 1970.
• 17: David Heckerman , Dan Geiger , David M. Chickering, Learning Bayesian Networks: The Combination of Knowledge and Statistical Data, Machine Learning, v.20 n.3, p.197-243, Sept. 1995 [doi>10.1023/A:1022623210503]
• 18: A. Moore and W.K. Wong. Optimal reinsertion: A new search operator for accelerated and more accurate bayesian network structure learning. In T. Fawcett and N. Mishra, editors, Proceedings of the 20th International Conference on Machine Learning (ICML'03), pages 552--559, Menlo Park, California, August 2003. AAAI Press.
• 19: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 20: I. Pournara, C.S. Bouganis, and G.A. Constantinides. Fpga-accelerated bayesian learning for reconstruction of gene regulatory networks. pages 323--328, 2005.
• 21: K. Sachs, O. Perez, D. Pe'er, D.A. Lauffenburger, and G.P. Nolan. Causal protein-signaling networks derived from multiparameter single-cell data. Science, 308(5721):523--529, 2005.
• 22: H.K.H. So. Borph: An operating system for fpga-based reconfigurable computers. PhD dissertaion, University of California, Berkeley.
• 23: M. Teyssier and D. Koller. Ordering-based search: A simple and effective algorithm for learning bayesian networks. In Proceedings of the Twenty-first Conference on Uncertainty in AI (UAI), pages 584--590, Edinburgh, Scottland, UK, July 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Algorithms, Design, Performance

Keywords:
Bayesian networks, Markov chain Monte Carlo, reconfigurable computing