zbMATH — the first resource for mathematics

Decomposition of structural learning about directed acyclic graphs. (English) Zbl 1131.68510
Summary: In this paper, we propose that structural learning of a directed acyclic graph can be decomposed into problems related to its decomposed subgraphs. The decomposition of structural learning requires conditional independencies, but it does not require that separators are complete undirected subgraphs. Domain or prior knowledge of conditional independencies can be utilized to facilitate the decomposition of structural learning. By decomposition, search for d-separators in a large network is localized to small subnetworks. Thus both the efficiency of structural learning and the power of conditional independence tests can be improved.

68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI
[1] Beinlich, I.; Suermondt, H.; Chavez, R.; Cooper, G., The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks, (), 247-256
[2] Becker, A.; Geiger, D., A sufficiently fast algorithm for finding close to optimal clique trees, Artificial intelligence, 125, 3-17, (2001) · Zbl 0972.68152
[3] Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database schemes, J. ACM, 30, 479-513, (1983) · Zbl 0624.68087
[4] Berge, C., Graphs and hypergraphs, (1976), North-Holland Amsterdam · Zbl 0483.05029
[5] Cowell, R.G.; David, A.P.; Lauritzen, S.L.; Spiegelhalter, D.J., Probabilistic networks and expert systems, (1999), Springer Publications New York · Zbl 0937.68121
[6] Cox, D.R.; Wermuth, N., Multivariate dependencies: models, analysis, and interpretation, (1993), Chapman and Hall London · Zbl 0783.62102
[7] Danks, D., Learning the causal structures of overlapping variable sets, (), 178-191 · Zbl 1024.68547
[8] Edwards, D., Introduction to graphical modelling, (1995), Springer-Verlag New York · Zbl 0856.62004
[9] Fung, R.; Crawford, S., CONSTRUCTOR—a system for the induction of probabilistic models, (), 762-779
[10] Geng, Z., Decomposability and collapsibility for log-linear models, Appl. stat., 38, 1, 189-197, (1989)
[11] Z. Geng, C. Wang, Q. Zhao, Decomposition of search for v-structures in DAGs, J. Multivariate Anal. (2005), submitted for publication · Zbl 1137.62420
[12] Heckerman, D., A tutorial on learning with Bayesian networks, (), 301-354 · Zbl 0921.62029
[13] Jensen, F.V.; Jensen, F., Optimal junction trees, (), 360-366
[14] D. Koller, M. Sahami, Toward optimal feature selection, in: Proceedings of the 13th International Conference on Machine Learning, Bari, Italy (1996) pp. 284-292
[15] Lauritzen, S.L., Graphical models, (1996), Clarendon Press Oxford · Zbl 0907.62001
[16] Little, R.J.A.; Rubin, D.B., Statistical analysis with missing data, (2002), Wiley New York
[17] Meek, C., Causal inference and causal explanation with background knowledge, (), 403-410
[18] Pearl, J., Probabilistic reasoning in intelligent systems, (1988), Morgan Kaufmann San Mateo, CA
[19] Pearl, J., Causality, (2000), Cambridge University Press Cambridge · Zbl 0959.68116
[20] Rassler, S., Statistical matching, Lecture notes in statistics, vol. 168, (2002), Springer New York · Zbl 1008.62002
[21] Roberston, N.; Seymour, P.D., Graph minors XIII. the disjoint paths problems, J. combin. theory B, 53, 65-100, (1995) · Zbl 0823.05038
[22] Rose, D.; Tarjan, R.; Lueker, G., Algorithmic aspects of vertex elimination on graphs, SIAM J. comput., 5, 266-283, (1976) · Zbl 0353.65019
[23] Spirtes, P.; Glymour, C., An algorithm for fast recovery of sparse causal graphs, Social sci. comput. rev., 9, 62-72, (1991)
[24] Spirtes, P.; Glymour, C.; Scheines, R., Causation, prediction and search, (2000), MIT Press Cambridge, MA · Zbl 0806.62001
[25] Tarjan, R.E.; Yannakakis, M., Simple linear-time algorithm to test chordality of graphs, test acyclicity of hypergraphs, and selective reduce acyclic hypergraphs, SIAM J. comput., 13, 566-579, (1984) · Zbl 0545.68062
[26] I. Tsamardinos, C. Aliferis, A. Statnikov, Time and sample efficient discovery of Markov blankets and direct causal relations, in: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, 2003, pp. 673-678
[27] Verma, T.; Pearl, J., Equivalence and synthesis of causal models, (), 255-268
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.