jmlr jmlr2009 jmlr2009-11 jmlr2009-11-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Raanan Yehezkel, Boaz Lerner
Abstract: We propose the recursive autonomy identification (RAI) algorithm for constraint-based (CB) Bayesian network structure learning. The RAI algorithm learns the structure by sequential application of conditional independence (CI) tests, edge direction and structure decomposition into autonomous sub-structures. The sequence of operations is performed recursively for each autonomous substructure while simultaneously increasing the order of the CI test. While other CB algorithms d-separate structures and then direct the resulted undirected graph, the RAI algorithm combines the two processes from the outset and along the procedure. By this means and due to structure decomposition, learning a structure using RAI requires a smaller number of CI tests of high orders. This reduces the complexity and run-time of the algorithm and increases the accuracy by diminishing the curse-of-dimensionality. When the RAI algorithm learned structures from databases representing synthetic problems, known networks and natural problems, it demonstrated superiority with respect to computational complexity, run-time, structural correctness and classification accuracy over the PC, Three Phase Dependency Analysis, Optimal Reinsertion, greedy search, Greedy Equivalence Search, Sparse Candidate, and Max-Min Hill-Climbing algorithms. Keywords: Bayesian networks, constraint-based structure learning
C. F. Aliferis, I. Tsamardinos, A. Statnikov, and L. E. Brown. Causal Explorer: A causal probabilistic network learning toolkit for biomedical discovery. In Proceedings of the International Conference on Mathematics and Engineering Techniques in Medicine and Biological Sciences, pages 371–376, 2003. S. Andreassen, F. V. Jensen, S. K. Andersen, B. Falck, U. Kjærulff, M. Woldbye, A. R. Sørensen, A. Rosenfalck, and F. Jensen. MUNIN—an expert EMG assistant. In John E. Desmedt, editor, Computer-Aided Electromyography and Expert Systems, chapter 21, pages 255–277. Elsevier Science Publishers, 1989. I. A. Beinlich, H. J. Suermondt, R. M. Chavez, and G. F. Cooper. The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks. In Proceedings of the Second European Conference on Artificial Intelligence in Medicine, pages 246–256, 1989. J. Binder, D. Koller, S. Russell, and K. Kanazawa. Adaptive probabilistic networks with hidden variables. Machine Learning, 29:213–244, 1997. J. Cheng. PowerConstructor system. http://www.cs.ualberta.ca/∼jcheng/bnpc.htm, 1998. J. Cheng and R. Greiner. Comparing Bayesian network classifiers. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, pages 101–107, 1999. J. Cheng, D. Bell, and W. Liu. Learning Bayesian networks from data: An efficient approach based on information theory. In Proceedings of the Sixth ACM International Conference on Information and Knowledge Management, pages 325–331, 1997. J. Cheng, C. Hatzis, H. Hayashi, M. Krogel, S. Morishita, D. Page, and J. Sese. KDD cup 2001 report. ACM SIGKDD Explorations Newsletter, 3:47–64, 2002. D. M. Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3:507–554, 2002. D. M. Chickering, D. Heckerman, and C. Meek. Large-sample learning of Bayesian networks is NP-hard. Journal of Machine Learning Research, 5:1287–1330, 2004. G. F. Cooper and E. A. Herskovits. Bayesian method for the induction of probabilistic networks from data. Machine Learning, 9:309–347, 1992. R. G. Cowell. Conditions under which conditional independence and scoring methods lead to identical selection of Bayesian network models. In Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence, pages 91–97, 2001. R. G. Cowell, A. P. Dawid, S. L. Lauritzen, and D. J. Spiegelhalter. Probabilistic Networks and Expert Systems. Springer, 1999. D. Dash and M. Druzdzel. A hybrid anytime algorithm for the construction of causal models from sparse sata. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, pages 142–149, 1999. 1567 Y EHEZKEL AND L ERNER D. Dash and M. Druzdzel. Robust independence testing for constraint-based learning of causal structure. In Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence, pages 167–174, 2003. J. Demˇar. Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learns ing Research, 7:1–30, 2006. T. G. Dietterich. Approximate statistical tests for comparing supervised classification learning algorithms. Neural Computation, 10:1895–1923, 1998. D. Dor and M. Tarsi. A simple algorithm to construct a consistent extension of a partially oriented graph. Technical Report R-185, Cognitive Systems Laboratory, UCLA Computer Science Department, 1992. M. Friedman. A comparison of alternative tests of significance for the problem of m rankings. Annals of Mathematical Statistics, 11:86–92, 1940. N. Friedman, D. Geiger, and M. Goldszmidt. Bayesian network classifiers. Machine Learning, 29: 131–161, 1997. 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, 1999. D. Grossman and P. Domingos. Learning Bayesian network classifiers by maximizing conditional likelihood. In Proceedings of the Twenty-First International Conference on Machine Learning, pages 361–368, 2004. D. Heckerman. A tutorial on learning with Bayesian networks. Technical Report TR-95-06, Microsoft Research, 1995. D. Heckerman, D. Geiger, and D. M. Chickering. Learning Bayesian networks: The combination of knowledge and statistical data. Machine Learning, 20:197–243, 1995. D. Heckerman, C. Meek, and G. F. Cooper. A Bayesian approach to causal discovery. In G. Glymour and G. Cooper, editors, Computation, Causation and Discovery, pages 141–165. AAAI Press, 1999. A. Jensen and F. Jensen. MIDAS—an influence diagram for management of mildew in winter wheat. In Proceedings of the Twelfth Conference on Uncertainty in Artificial Intelligence, pages 349–356, 1996. R. J. Kennett, K. Korb, and A. E. Nicholson. Seebreeze prediction using Bayesian networks. In Proceedings of the Fifth Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, pages 148–153, 2001. R. Kohavi and G. H. John. Wrappers for feature subset selection. Artificial Intelligence, 97:273– 324, 1997. 1568 BAYESIAN N ETWORK S TRUCTURE L EARNING BY R ECURSIVE AUTONOMY I DENTIFICATION R. Kohavi, G. H. John, R. Long, D. Manley, and K. Pfleger. MLC++: A machine learning library in C++. In Proceedings of the Sixth International Conference on Tools with AI, pages 740–743, 1994. P. Kontkanen, P. Myllymaki, T. Sliander, and H. Tirri. On supervised selection of Bayesian networks. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, pages 334–342, 1999. K. Kristensen and I. A. Rasmussen. The use of a Bayesian network in the design of a decision support system for growing malting barley without use of pesticides. Computers and Electronics in Agriculture, 33:197–217, 2002. S. Kullback and R. A. Leibler. On information and sufficiency. Annals of Mathematical Statistics, 22:79–86, 1951. P. Leray and O. Francois. BNT structure learning package: Documentation and experiments. Tech¸ nical Report FRE CNRS 2645, Laboratoire PSI, Universit` et INSA de Rouen, 2004. e M. Marengoni, C. Jaynes, A. Hanson, and E. Riseman. Ascender II, a visual framework for 3D reconstruction. In Proceedings of the First International Conference on Computer Vision Systems, pages 469–488, 1999. C. Meek. Causal inference and causal explanation with background knowledge. In Proceedings of the Fifth Conference on Uncertainty in Artificial Intelligence, pages 403–410, 1995. C. Meek. Graphical Models: Selecting Causal and Statistical Models. PhD thesis, Carnegie Mellon University, 1997. A. Moore and W. Wong. Optimal reinsertion: A new search operator for accelerated and more accurate Bayesian network structure learning. In Twentieth International Conference on Machine Learning, pages 552–559, 2003. K. Murphy. The Bayes net toolbox for Matlab. Computing Science and Statistics, 33:331–350, 2001. D. J. Newman, S. Hettich, C. L. Blake, and C. J. Merz. UCI repository of machine learning databases, 1998. URL http://www.ics.uci.edu/∼mlearn/MLRepository.html. J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan– Kaufmann, 1988. J. Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2000. F. Pernkopf and J. Bilmes. Discriminative versus generative parameter and structure learning of Bayesian network classifiers. In Proceedings of the Twenty-Second International Conference on Machine Learning, pages 657–664, 2005. T. Roos, H. Wettig, P. Grunwald, P. Myllymaki, and H. Tirri. On discriminative Bayesian network classifiers and logistic regression. Machine Learning, 59:267–296, 2005. 1569 Y EHEZKEL AND L ERNER M. Singh and M. Valtorta. Construction of Bayesian network structures from data: A brief survey and an efficient algorithm. International Journal of Approximate Reasoning, 12:111–131, 1995. P. Spirtes. An anytime algorithm for casual inference. In Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics, pages 213–221, 2001. P. Spirtes and C. Meek. Learning Bayesian networks with discrete variables from data. In Proceedings of the First International Conference on Knowledge Discovery and Data Mining, pages 294–299, 1995. P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction and Search. MIT Press, 2nd edition, 2000. I. Tsamardinos, L. E. Brown, and C. F. Aliferis. The max-min hill-climbing Bayesian network structure learning algorithm. Machine Learning, 65:31–78, 2006a. I. Tsamardinos, A. Statnikov, L. E. Brown, and C. F. Aliferis. Generating realistic large Bayesian networks by tiling. In Proceedings of the Nineteenth International Florida Artificial Intelligence Research Society Conference, 2006b. T. Verma and J. Pearl. Equivalence and synthesis of causal models. In Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence, pages 220–227, 1990. S. Yang and K. C. Chang. Comparison of score metrics for Bayesian network learning. IEEE Transactions on Systems, Man and Cybernetics A, 32:419–428, 2002. R. Yehezkel and B. Lerner. Recursive autonomy identification for Bayesian network structure learning. In Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, pages 429–436, 2005. 1570