A new algorithm for decomposition of graphical models. (English) Zbl 1254.05190
Summary: In this paper, we combine Leimer’s algorithm with the MCS-M algorithm to decompose graphical models into marginal models on prime blocks. It is shown by experiments that our method has an easier and faster implementation than Leimer’s algorithm.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68W05 | Nonnumerical algorithms |
| 62H99 | Multivariate analysis |
References:
| [1] | Berry, A., Blair, J.R.S., Heggernes, P., Peyton, B.W. Maximum cardinality search for computing minimal triangulations of graph. Algorithmica, 39: 287–298 (2004) · Zbl 1090.68080 · doi:10.1007/s00453-004-1084-3 |
| [2] | Blair, J.R.S., Peyton, B.W. An introduction to chordal graphs and clique trees. Graph Theory and Sparse Matrix Computation, IMA Volumes in Mathematics and its Applications, 56: 1–30 (1993) · Zbl 0803.68081 · doi:10.1007/978-1-4613-8369-7_1 |
| [3] | Dempster, A.P. Covariance selection. Biometrics, 28: 157–175 (1972) · doi:10.2307/2528966 |
| [4] | Darroch, J.N., Lauritzen, S.L., Speed, T.P. Markov-fields and log-linear models for contingency tables. Annals of Statistics, 8: 522–539 (1980) · Zbl 0444.62064 · doi:10.1214/aos/1176345006 |
| [5] | Flores, M.J., Gámez, J. Triangulation of Bayesian networks by retriangulation. International Journal of Intelligent Systems, 18(2): 153–164 (2003) · Zbl 1028.68166 · doi:10.1002/int.10079 |
| [6] | Friedman, N. Inferring cellular networks using probabilistic graphical models. Science, 303: 799–805 (2004) · doi:10.1126/science.1094068 |
| [7] | Geng, Z. Algorithm AS244: Decomposability and collapsibility for log-linear models. Applied Statistics, 38: 189–197 (1989) · doi:10.2307/2347694 |
| [8] | Geng, Z., Wang, C., Zhao, Q. Decomposition of search for v-structures in DAGs. Journal of Multivariate Analysis, 96: 282–294 (2005) · Zbl 1137.62420 · doi:10.1016/j.jmva.2004.10.012 |
| [9] | Jirousek, R., Preucil, S. On the effective implementation of the iterative proportional fitting procedure. Computational Statistics & Data Analysis, 19: 177–189 (1995) · Zbl 0875.65122 · doi:10.1016/0167-9473(93)E0055-9 |
| [10] | Lauritzen, S.L. Graphical Models. Clarendon Press, Oxford, 1996 · Zbl 0907.62001 |
| [11] | Lauritzen, S.L. Lectures on Contingency Tables. http://www.stats.ox.ac.uk/steffen/papers/cont.pdf , 2002 |
| [12] | Lauritzen, S.L., Spiegelhalter, D.J. Local computations with probabilities on graphical structures and their application to expert systems (with discussion). Journal of the Royal Statistical Society, Series B, 50: 157–224 (1998) · Zbl 0684.68106 |
| [13] | Lauritzen, S.L., Wermuth, N. Graphical models for associations between variables, some of which are qualitative and some quantitative. Annals of Statistics, 17: 31–57 (1989) · Zbl 0669.62045 · doi:10.1214/aos/1176347003 |
| [14] | Leimer, H.G. Optimal decomposition by cliques separators. Discrete Mathematics, 113: 99–123 (1993) · Zbl 0793.05128 · doi:10.1016/0012-365X(93)90510-Z |
| [15] | Liu, B.H., Guo, J.H., Jing, B.Y. A note on minimal d-separation trees for structural learning. Artificial Intelligence, 174: 442–448 (2010) · Zbl 1211.68290 · doi:10.1016/j.artint.2010.01.002 |
| [16] | Ma, S., Gong, Q., Bohnert, H.J. An Arabidopsis gene network based on the graphical Gaussian model. Genome Research, 17: 1614–1625 (2007) · doi:10.1101/gr.6911207 |
| [17] | Malvestuto, F.M. A hypergraph-theoretic analysis of collapsibility and decomposability for extended loglinear models. Statistics and Computing, 11(2): 155–169 (2001) · doi:10.1023/A:1008979300007 |
| [18] | Olesen, K., Madsen, A. Maximal prime subgraph decomposition of Bayesian networks. IEEE Transactions on Systems, Man and Cybernetics, B, 32: 21–31 (2002) · doi:10.1109/3477.979956 |
| [19] | Pearl, J. Causality: Models, Reasoning, and Inference. Cambridge University Press, Cambridge, 2000 · Zbl 0959.68116 |
| [20] | Rose, D.J., Tarjan, R.E., Lueker, G.S. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5: 266–283 (1976) · Zbl 0353.65019 · doi:10.1137/0205021 |
| [21] | Sachs, K., Perez, O., Pe’er, D., Lauffenburger, D.A., Nolan, G.P. Causal protein-signaling networks derived from multiparameter single-cell data. Science, 308: 523–529 (2005) · doi:10.1126/science.1105809 |
| [22] | Tarjan, R.E. Decomposition by clique separators. Discrete Mathematics, 55: 221–232 (1985) · Zbl 0572.05039 · doi:10.1016/0012-365X(85)90051-2 |
| [23] | Tarjan, R.E., Yannakakis, M. Simple linear-time algorithms to test chordality of graphs, test acyclicicty of hypergraphs and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 13: 566–579 (1984) · Zbl 0545.68062 · doi:10.1137/0213035 |
| [24] | Verma, T., Pearl, J. Equivalence and synthesis of causal models. In: Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence, Elsevier, Amsterdam, 1990, 255–268 |
| [25] | Wen, W.X. Optimal decomposition of belief networks. In: Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, 1990, 209–224 · Zbl 0742.68073 |
| [26] | Xie, X., Geng, Z. A recursive method for structural learning of directed acyclic graphs. Journal of Machine Learning Research, 9: 459–483 (2008) · Zbl 1225.68222 |
| [27] | Xie, X., Geng, Z., Zhao, Q. Decomposition of structural learning about directed acyclic graphs. Artificial Intelligence, 170: 422–439 (2006) · Zbl 1131.68510 · doi:10.1016/j.artint.2005.12.004 |
| [28] | Xu, P.F., Guo, J.H. Improving the compilation stage of propagation algorithm of Bayesian networks by decomposition. Submitted for publication (2010) |
| [29] | Xu, P.F., Guo, J.H., He, X. An improved iterative proportional scaling procedure for Gaussian graphical models. Journal of Computational and Graphical Statistics, 20(2): 417–431 (2011) · doi:10.1198/jcgs.2010.09044 |
| [30] | Xu, P.F., Guo, J.H., Tang, M.L. Structural learning for Bayesian networks by testing complete separators in prime blocks. Computational Statistics & Data Analysis, 55: 3135–3147 (2011) · Zbl 1271.62048 · doi:10.1016/j.csda.2011.06.017 |
| [31] | Zhang, N.L., Poole, D. Exploiting causal independence in Bayesian network inference. Journal of Artificial Intelligence Research, 5: 301–328 (1996) · Zbl 0900.68384 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
