jmlr jmlr2008 jmlr2008-88 jmlr2008-88-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Zongming Ma, Xianchao Xie, Zhi Geng
Abstract: Chain graphs present a broad class of graphical models for description of conditional independence structures, including both Markov networks and Bayesian networks as special cases. In this paper, we propose a computationally feasible method for the structural learning of chain graphs based on the idea of decomposing the learning problem into a set of smaller scale problems on its decomposed subgraphs. The decomposition requires conditional independencies but does not require the separators to be complete subgraphs. Algorithms for both skeleton recovery and complex arrow orientation are presented. Simulations under a variety of settings demonstrate the competitive performance of our method, especially when the underlying graph is sparse. Keywords: chain graph, conditional independence, decomposition, graphical model, structural learning
A. Agresti. Categorical Data Analysis. John Wiley & Sons, Hoboken, NJ., 2nd edition, 2002. T. W. Anderson. An Introduction to Multivariate Statistical Analysis. John Wiley & Sons, Hoboken, NJ., 3rd edition, 2003. S. A. Andersson, D. Madigan, and M. D. Perlman. Alternative Markov properties fror chain graphs. Scand. J. Statist., 28:33–85, 2001. I. Beinlich, H. Suermondt, R. Chevaz, and G. Cooper. The alarm monitoring system: A case study with two probabilistic inference techniques for belief networks. In Proceedings of the 2nd European Conference on Artificail Intelligence in Medicine, pages 247–256. Springer-Verlag, Berlin, 1989. S. Carroll and V. Pavlovic. Protein calassification using probabilistic chain graphs and the gene ontology structure. Bioinformatics, 22(15):1871–1878, 2006. D. M. Chickering. Learning equivalence classes of bayesian-network structures. J. Mach. Learn. Res., 2:445–498, 2002. R. G. Cowell, A. P. Dawid, S. L. Lauritzen, and D. J. Spiegelhalter. Probabilistic Networks and Expert Systems. Springer-Verlag, New York, 1999. D. R. Cox and N. Wermuth. Multivariate Dependencies: Models, Analysis and Interpretation. Chapman and Hall, London, 1996. M. Drton and M. Perlman. A sinful approach to gaussian graphical model selection. J. Stat. Plan. Infer., 138:1179–1200, 2008. D. Edwards. Introduction to Graphical Modelling. Springer-Verlag, New York, 2nd edition, 2000. 2878 S TRUCTURAL L EARNING OF C HAIN G RAPHS VIA D ECOMPOSITION B. Ellis and W. H. Wong. Learning bayesian network structures from experimental data. URL http://www.stanford.edu/group/wonglab/doc/EllisWong-061025.pdf. 2006. J. Friedman, T. Hastie, and R. Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 2007. doi: doi:10.1093/biostatistics/kxm045. N. Friedman and D. Koller. Being bayesian about network structure: a bayesian approach to structure discovery in bayesian networks. Mach. Learn., 50:95–126, 2003. N. Friedman, I. Nachmana, and D. Pe’er. Learning bayesian network structure from massive datasets: The ”sparse candidate” algorithm. In Proceedings of the Fifteenth Conference on Uncertainty in Artificail Intelligence, pages 206–215, Stockholm, Sweden, 1999. M. Frydenberg. The chain graph markov property. Scand. J. Statist., 17:333–353, 1990. M. Kalisch and P. B¨ hlmann. Estimating high-dimensional directed acyclic graphs with the pcu algorithm. J. Mach. Learn. Res., 8:616–636, 2007. S. L. Lauritzen. Graphical Models. Claredon Press, Oxford, 1996. S. L. Lauritzen and T. S. Richardson. Chain graph models and their causal interpretations (with discussion). J. R. Statist. Soc. B, 64:321–361, 2002. Y. Liu, Xing E. P., and J. Carbonell. Predicting protein folds with structural repeats using a chain graph model. In Proceedings of the 22nd International Conference on Machine Learning, 2005. N. Meinshausen and P. B¨ hlmann. High-dimensional graphs and variable selection with the lasso. u Ann. Statist., 34:1436–1462, 2006. J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco, CA, 1988. P. Ravikumar, M. J. Wainwright, and J. Lafferty. High-dimensional graphical model selection using 1 -regularized logistic regression. Technical Report 750, Department of Statistics, University of California, Berkeley., 2008. URL http://www.stat.berkeley.edu/tech-reports/750.pdf. A. Roverato and L. La Rocca. On block ordering of variables in graphical modelling. Scand. J. Statist., 33:65–81, 2006. P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction and Search. MIT Press, Cambridge, MA, 2nd edition, 2000. E. Stanghellini, K. J. McConway, and D. J. Hand. A discrete variable chain graph for applicants for credit. J. R. Statist. Soc. C, 48:239–251, 1999. M. Studen´ . A recovery algorithm for chain graphs. Int. J. Approx. Reasoning, 17:265–293, 1997. y M. Studen´ and R. R. Bouckaert. On chain graph models for description of conditional indepeny dence structures. Ann. Statist., 26:1434–1495, 2001. 2879 M A , X IE AND G ENG I. Tsamardinos, L. E. Brown, and C. F. Aliferis. The max-min hill-climbing bayesian network structure learning algorithm. Mach. Learn., 65:31–78, 2006. N. Wermuth. On block-recursive linear regression equations. Revista Brasileira de Probabilidade e Estatistica, 6:1–56, 1992. N. Wermuth and S. L. Lauritzen. Biometrika, 72:537–552, 1983. Graphical and recursive models for contingency tables. N. Wermuth and S. L. Lauritzen. On substantive research hypotheses, conditional independence graphs and graphical chain models. J. R. Statist. Soc. B, 52:21–50, 1990. J. Whittaker. Graphical Models in Applied Multivariate Statistics. John Wiley & Sons, 1990. S. Wilks. The large-sample distribution of the likelihood ratio for testing composite hypotheses. Ann. Math. Stat., 20:595–601, 1938. X. Xie and Z. Geng. A recursive method for structural learning of directed acyclic graphs. J. Mach. Learn. Res., 9:459–483, 2008. X. Xie, Z. Geng, and Q. Zhao. Decomposition of structural learning about directed acyclic graphs. Artif. Intell., 170:442–439, 2006. 2880