{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:24:45Z","timestamp":1750307085683,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,10,1]],"date-time":"2012-10-01T00:00:00Z","timestamp":1349049600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2012,10]]},"abstract":"<jats:p>Dependency analysis is a typical approach for Bayesian network learning, which infers the structures of Bayesian networks by the results of a series of conditional independence (CI) tests. In practice, testing independence conditioning on large sets hampers the performance of dependency analysis algorithms in terms of accuracy and running time for the following reasons. First, testing independence on large sets of variables with limited samples is not stable. Second, for most dependency analysis algorithms, the number of CI tests grows at an exponential rate with the sizes of conditioning sets, and the running time grows of the same rate. Therefore, determining how to reduce the number of CI tests and the sizes of conditioning sets becomes a critical step in dependency analysis algorithms. In this article, we address a two-phase algorithm based on the observation that the structures of Markov random fields are similar to those of Bayesian networks. The first phase of the algorithm constructs a Markov random field from data, which provides a close approximation to the structure of the true Bayesian network; the second phase of the algorithm removes redundant edges according to CI tests to get the true Bayesian network. Both phases use Markov blanket information to reduce the sizes of conditioning sets and the number of CI tests without sacrificing accuracy. An empirical study shows that the two-phase algorithm performs well in terms of accuracy and efficiency.<\/jats:p>","DOI":"10.1145\/2362383.2362384","type":"journal-article","created":{"date-parts":[[2012,10,26]],"date-time":"2012-10-26T18:34:02Z","timestamp":1351276442000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Learning bayesian networks from Markov random fields"],"prefix":"10.1145","volume":"6","author":[{"given":"Zhenxing","family":"Wang","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laiwan","family":"Chan","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,10,29]]},"reference":[{"volume-title":"Proceedings of UAI. 346--353","year":"2001","key":"e_1_2_1_1_1","unstructured":"(a), D. M. 2001 . A Bayesian multiresolution independence test for continuous variables . In Proceedings of UAI. 346--353 . (a), D. M. 2001. A Bayesian multiresolution independence test for continuous variables. In Proceedings of UAI. 346--353."},{"key":"e_1_2_1_2_1","volume-title":"I: Algorithms and empirical evaluation. J. Machince Learn. Res. 11.","author":"Aliferis C. F.","year":"2010","unstructured":"Aliferis , C. F. , Statnikov , A. , Tsamardinos , I. , Mani , S. , and Koutsoukos , X. D . 2010 . Local causal and Markov blanket induction for causal discovery and feature selection for classification part I: Algorithms and empirical evaluation. J. Machince Learn. Res. 11. Aliferis, C. F., Statnikov, A., Tsamardinos, I., Mani, S., and Koutsoukos, X. D. 2010. Local causal and Markov blanket induction for causal discovery and feature selection for classification part I: Algorithms and empirical evaluation. J. Machince Learn. Res. 11."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0924-980X(95)00252-G"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281203"},{"volume-title":"Proceedings of AAAI. 825--830","year":"2005","key":"e_1_2_1_5_1","unstructured":"(b), D. M. 2005 . Distribution-free learning of Bayesian network structure in continuous domains . In Proceedings of AAAI. 825--830 . (b), D. M. 2005. Distribution-free learning of Bayesian network structure in continuous domains. In Proceedings of AAAI. 825--830."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 2nd European Conference on Artificial Intelligence in Medicine.","volume":"38","author":"Beinlich I. A.","unstructured":"Beinlich , I. A. , Suermondt , H. J. , Chavez , R. M. , and Cooper , G. F . 1989. The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks . In Proceedings of the 2nd European Conference on Artificial Intelligence in Medicine. Vol. 38 , 247--256. Beinlich, I. A., Suermondt, H. J., Chavez, R. M., and Cooper, G. F. 1989. The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks. In Proceedings of the 2nd European Conference on Artificial Intelligence in Medicine. Vol. 38, 247--256."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007421730016"},{"volume-title":"Structural Equations with Latent Variables","author":"Bollen K. A.","key":"e_1_2_1_8_1","unstructured":"Bollen , K. A. 1989. Structural Equations with Latent Variables . Wiley . Bollen, K. A. 1989. Structural Equations with Latent Variables. Wiley."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00191-1"},{"volume-title":"Learning from Data","author":"Chickering D. M.","key":"e_1_2_1_10_1","unstructured":"Chickering , D. M. 1996. Learning Bayesian networks is NP-Complete . In Learning from Data : Artificial Intelligence and Statistics V. Springer-Verlag , 121--130. Chickering, D. M. 1996. Learning Bayesian networks is NP-Complete. In Learning from Data: Artificial Intelligence and Statistics V. Springer-Verlag, 121--130."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1005332.1044703"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022649401552"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of UAI 11","author":"Cussens J.","year":"2011","unstructured":"Cussens , J. 2011 . Bayesian network learning with cutting planes . In Proceedings of UAI 11 . AUAI Press, 153--160. Cussens, J. 2011. Bayesian network learning with cutting planes. In Proceedings of UAI 11. AUAI Press, 153--160."},{"volume-title":"Introduction to Structural Equation Models","author":"Duncan O.","key":"e_1_2_1_14_1","unstructured":"Duncan , O. 1975. Introduction to Structural Equation Models . Academic Press . Duncan, O. 1975. Introduction to Structural Equation Models. Academic Press."},{"key":"e_1_2_1_15_1","series-title":"Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics","volume-title":"Linear Statistical Models and Related Methods: With Applications to Social Research","author":"Fox J.","unstructured":"Fox , J. 1984. Linear Statistical Models and Related Methods: With Applications to Social Research . Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics . Wiley . Fox, J. 1984. Linear Statistical Models and Related Methods: With Applications to Social Research. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. Wiley."},{"key":"e_1_2_1_16_1","unstructured":"Glymour C. and Cooper G. 1999. Computation Causation and Discovery. AAAI Press.  Glymour C. and Cooper G. 1999. Computation Causation and Discovery. AAAI Press."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022623210503"},{"volume-title":"Proceedings of UAI. 282--289","author":"Hoyer P.","key":"e_1_2_1_18_1","unstructured":"Hoyer , P. , Hyvrinen , A. , Scheines , R. , Spirtes , P. , Ramsey , J. , Lacerda , G. , and Shimizu , S . 2008. Causal discovery of linear acyclic models with arbitrary distributions . In Proceedings of UAI. 282--289 . Hoyer, P., Hyvrinen, A., Scheines, R., Spirtes, P., Ramsey, J., Lacerda, G., and Shimizu, S. 2008. Causal discovery of linear acyclic models with arbitrary distributions. In Proceedings of UAI. 282--289."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390210"},{"volume-title":"Proceedings of UAI. 349--356","author":"Jensen A. L.","key":"e_1_2_1_20_1","unstructured":"Jensen , A. L. and Jensen , F. V . 1996. Midas: An influence diagram for management of mildew in winter wheat . In Proceedings of UAI. 349--356 . Jensen, A. L. and Jensen, F. V. 1996. Midas: An influence diagram for management of mildew in winter wheat. In Proceedings of UAI. 349--356."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of UAI. 241--248","author":"Koivisto M.","year":"2006","unstructured":"Koivisto , M. 2006 . Advances in exact Bayesian structure discovery in Bayesian networks . In Proceedings of UAI. 241--248 . Koivisto, M. 2006. Advances in exact Bayesian structure discovery in Bayesian networks. In Proceedings of UAI. 241--248."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1005332.1005352"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-1699(02)00007-8"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230200503"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 20th National Conference on Artificial Intelligence. Morgan Kaufmann.","author":"Margaritis D.","year":"2005","unstructured":"Margaritis , D. 2005 . Distribution-free learning of Bayesian network structure in continuous domains . In Proceedings of the 20th National Conference on Artificial Intelligence. Morgan Kaufmann. Margaritis, D. 2005. Distribution-free learning of Bayesian network structure in continuous domains. In Proceedings of the 20th National Conference on Artificial Intelligence. Morgan Kaufmann."},{"key":"e_1_2_1_26_1","unstructured":"Margaritis D. and Thrun S. 1999. Bayesian network induction via local neighborhoods. In Advances in Neural Information Processing Systems 12 MIT Press 505--511.  Margaritis D. and Thrun S. 1999. Bayesian network induction via local neighborhoods. In Advances in Neural Information Processing Systems 12 MIT Press 505--511."},{"volume-title":"Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence. Morgan Kaufmann.","author":"Margaritis D.","key":"e_1_2_1_27_1","unstructured":"Margaritis , D. and Thrun , S . 2001. A Bayesian multiresolution independence test for continuous variables . In Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence. Morgan Kaufmann. Margaritis, D. and Thrun, S. 2001. A Bayesian multiresolution independence test for continuous variables. In Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence. Morgan Kaufmann."},{"volume-title":"Proceedings of UAI. 401--408","author":"Ordyniak S.","key":"e_1_2_1_28_1","unstructured":"Ordyniak , S. and Szeider , S . 2010. Algorithms and complexity results for exact Bayesian structure learning . In Proceedings of UAI. 401--408 . Ordyniak, S. and Szeider, S. 2010. Algorithms and complexity results for exact Bayesian structure learning. In Proceedings of UAI. 401--408."},{"volume-title":"Proceedings of UAI. 436--443","author":"Parviainen P.","key":"e_1_2_1_29_1","unstructured":"Parviainen , P. and Koivisto , M . 2009. Exact structure discovery in Bayesian networks with less space . In Proceedings of UAI. 436--443 . Parviainen, P. and Koivisto, M. 2009. Exact structure discovery in Bayesian networks with less space. In Proceedings of UAI. 436--443."},{"volume-title":"Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning.","author":"Pearl J.","key":"e_1_2_1_30_1","unstructured":"Pearl , J. and Verma , T . 1991. A theory of inferred causation . In Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning. Pearl, J. and Verma, T. 1991. A theory of inferred causation. In Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1390681.1442776"},{"volume-title":"Proceedings of UAI.","author":"Ramsey J.","key":"e_1_2_1_32_1","unstructured":"Ramsey , J. , Zhang , J. , and Spirtes , P . 2006. Adjacency-faithfulness and conservative causal inference . In Proceedings of UAI. Ramsey, J., Zhang, J., and Spirtes, P. 2006. Adjacency-faithfulness and conservative causal inference. In Proceedings of UAI."},{"key":"e_1_2_1_33_1","unstructured":"Richard J. and Wichern D. 2002. Applied Multivariate Statistical Analysis. Prentice-Hall Inc New Jersey.  Richard J. and Wichern D. 2002. Applied Multivariate Statistical Analysis. Prentice-Hall Inc New Jersey."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1248547.1248619"},{"key":"e_1_2_1_35_1","first-page":"62","article-title":"An algorithm for fast recovery of sparse causal graphs. Social Sci","volume":"9","author":"Spirtes P.","year":"1991","unstructured":"Spirtes , P. and Glymour , C. 1991 . An algorithm for fast recovery of sparse causal graphs. Social Sci . Comp. Rev. 9 , 1, 62 -- 72 . Spirtes, P. and Glymour, C. 1991. An algorithm for fast recovery of sparse causal graphs. Social Sci. Comp. Rev. 9, 1, 62--72.","journal-title":"Comp. Rev."},{"volume-title":"Proceedings of Advanced Computing for the Social Sciences.","author":"Spirtes P.","key":"e_1_2_1_36_1","unstructured":"Spirtes , P. , Glymour , C. , and Scheines , R . 1990. From probability to causality . In Proceedings of Advanced Computing for the Social Sciences. Spirtes, P., Glymour, C., and Scheines, R. 1990. From probability to causality. In Proceedings of Advanced Computing for the Social Sciences."},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Spirtes P. Glymour C. and Scheines R. 1993. Causation Prediction and Search. Springer Verlag Berlin.  Spirtes P. Glymour C. and Scheines R. 1993. Causation Prediction and Search. Springer Verlag Berlin.","DOI":"10.1007\/978-1-4612-2748-9"},{"volume-title":"Proceedings of UAI. 295--308","author":"Srinivas S.","key":"e_1_2_1_38_1","unstructured":"Srinivas , S. , Russell , S. J. , and Agogino , A. M . 1989. Automated construction of sparse Bayesian networks from unstructured probabilistic models and domain information . In Proceedings of UAI. 295--308 . Srinivas, S., Russell, S. J., and Agogino, A. M. 1989. Automated construction of sparse Bayesian networks from unstructured probabilistic models and domain information. In Proceedings of UAI. 295--308."},{"volume-title":"Proceedings of the 13th International Conference on Arti ficial Intelligence and Statistics (AISTATS). 358--365","author":"Tommi J.","key":"e_1_2_1_39_1","unstructured":"Tommi , J. , Sontag , D. , Globerson , A. , and Meila , M . 2010. Learning Bayesian network structure using lp relaxations . In Proceedings of the 13th International Conference on Arti ficial Intelligence and Statistics (AISTATS). 358--365 . Tommi, J., Sontag, D., Globerson, A., and Meila, M. 2010. Learning Bayesian network structure using lp relaxations. In Proceedings of the 13th International Conference on Arti ficial Intelligence and Statistics (AISTATS). 358--365."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956838"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-6889-7"},{"key":"e_1_2_1_42_1","first-page":"234","article-title":"A heuristic partial correlation-based algorithm for causal relationship discovery","volume":"2009","author":"Wang Z.","year":"2009","unstructured":"Wang , Z. and Chan , L. 2009 . A heuristic partial correlation-based algorithm for causal relationship discovery . In Proceedings of Intelligent Data Engineering and Automated Learning - IDEAL 2009. 234 -- 241 . Wang, Z. and Chan, L. 2009. A heuristic partial correlation-based algorithm for causal relationship discovery. In Proceedings of Intelligent Data Engineering and Automated Learning - IDEAL 2009. 234--241.","journal-title":"Proceedings of Intelligent Data Engineering and Automated Learning - IDEAL"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835944"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.2307\/2336490"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2362383.2362384","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2362383.2362384","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:22Z","timestamp":1750239262000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2362383.2362384"}},"subtitle":["An efficient algorithm for linear models"],"short-title":[],"issued":{"date-parts":[[2012,10]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["10.1145\/2362383.2362384"],"URL":"https:\/\/doi.org\/10.1145\/2362383.2362384","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2012,10]]},"assertion":[{"value":"2011-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-10-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}