An implementation of the iterative proportional fitting procedure by propagation trees. (English) Zbl 1061.65500

Badsberg, J. H.; Malvestuto, F. M.

Comput. Stat. Data Anal. 37, No. 3, 297-322 (2001).

Summary: The space-saving implementation of the iterative proportional fitting procedure proposed by R. Jirousek and S. Preucil [Comput. Stat. Data Anal. 19, No. 2, 177–189 (1995; Zbl 0875.65122)] can be improved by applying the tree-computation techniques designed for Markov networks. The optimisation problem raised by the use of Markovian propagation trees is solved. Next, an even better implementation is obtained using certain trees, here introduced and called fast propagation trees, which are obtained by ‘simplifying” optimal Markovian propagation trees.

MSC:

65C60	Computational problems in statistics (MSC2010)
05C90	Applications of graph theory

Keywords:

Acyclic hypergraph; Iterative proportional fitting procedure; Markov extension; Probabilistic database; Propagation tree

Citations:

Zbl 0875.65122

References:

[1]	Ahuja, R. K.; Magnanti, M. L.; Orlin, J. B.: Network flows.. (1993) · Zbl 1201.90001
[2]	Almond, R., Kong, A., 1993. Optimality issues in constructing a Markov tree from graphical models. Unpublished manuscript.
[3]	Arnborg, S.; Corneil, D. G.; Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic discrete math. 9, 277-284 (1993) · Zbl 0611.05022
[4]	Badsberg, J.H., 1995. An environment for graphical models. Part I: efficient algorithms for estimation in contingency tables. Ph.D. Thesis, Department of Mathematics and Computer Science, Ålborg University, Denmark.
[5]	Badsberg, J.H., 1996. Decomposition of graphs and hypergraphs with identification of conformal hypergraphs. Research Report R 96-2032. Department of Mathematics & Computer Science, Ålborg University, Denmark.
[6]	Becker, A., Geiger, D., 1997. A sufficiently fast algorithm for finding close to optimal junction trees. Abstracts of the II IASC World Conference, Pasadena.
[7]	Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M.: On the desirability of acyclic database schemes. J. assoc. Comput. Mach 30, 479-513 (1983) · Zbl 0624.68087
[8]	Berge, C.: Hypergraphs.. (1989) · Zbl 0334.05117
[9]	Bishop, Y. M. M.; Fienberg, S. E.; Holland, P. W.: Discrete multivariate analysis, theory and practice.. (1975) · Zbl 0332.62039
[10]	Bodlaender, H. L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305-1317 (1996) · Zbl 0864.68074
[11]	Csiszár, I.: I-divergence geometry of probability distributions and minimization problems. Ann. probab. 3, 146-158 (1975) · Zbl 0318.60013
[12]	Darroch, J. N.; Lauritzen, S. L.; Speed, M. P.: Markov fields and log–linear interaction models for contingency tables. Ann. statist. 8, 522-539 (1980) · Zbl 0444.62064
[13]	Dawid, A. P.: Applications of a general propagation algorithm for probabilistic expert systems. Statist. comput. 2, 1992 (1992)
[14]	Deming, W. E.; Stephan, F. F.: On a least squares adjustment of a sampled frequency table when the expected marginal totals are known. Ann. of math. Statist. 11, 427-444 (1940) · Zbl 0024.05502
[15]	Denteneer, D.; Verbeek, A.: A fast algorithm for iterative proportional Fitting in log–linear models. Comput. statist. Data anal. 3, 251-264 (1986) · Zbl 0591.65098
[16]	Diestel, R.: Graph decompositions.. (1990) · Zbl 0726.05001
[17]	Golumbic, M. C.: Algorithmic graph theory and perfect graphs.. (1980) · Zbl 0541.05054
[18]	Haberman, S. J.: Log–linear models for contingency tables.. (1974) · Zbl 0294.62026
[19]	Jensen, F.V., 1988. Junction trees and decomposable hypergraphs. Research Report, JUDEX DATA SYSTEMER, Ålborg, Denmark.
[20]	Jensen, F.V., Jensen, F., 1994. Optimal junction trees, Proceedings of the X Conference on Uncertainty in Artificial Intelligence, pp. 400–406.
[21]	Jirousek, R.: Solution of the marginal problem and decomposable distributions. Kybernetika 27, 403-412 (1991) · Zbl 0752.60009
[22]	Jirousek, R.; Preucil, S.: On the effective implementation of the iterative proportional Fitting procedure. Comput. statist. Data anal. 19, 177-189 (1995) · Zbl 0875.65122
[23]	Kellerer, H. G.: Verteilungsfunktionen mit gegebenen marginalverteilungen. Z. wahrscheinlichkeitstheorie verw. Gebiete 3, 247-270 (1964) · Zbl 0126.34003
[24]	Kjærluff, U.: Optimal decomposition of probabilistic networks by simulated annealing. Comput. statist. Data anal. 2, 7-17 (1992)
[25]	Kloks, M.: Treewidth: computations and approximations.. Lecture notes in computer science 842 (1994) · Zbl 0825.68144
[26]	Larrañaga, P.; Kuijpers, C. M. H.; Poza, M.; Murga, R. H.: Decomposing Bayesian networks: triangulation of the moral graph with genetic algorithms. Statist. comput. 7, 19-34 (1997)
[27]	Lauritzen, S. L.: Propagation of probabilities. J. amer. Statist. assoc. 87, 420 (1992) · Zbl 0850.62094
[28]	Lauritzen, S. L.: Graphical models.. (1996) · Zbl 0907.62001
[29]	Lauritzen, S. L.; Speed, M. P.; Vijayan, K.: Decomposable graphs and hypergraphs. J. austral. Math. soc. Ser. E 36, 12-29 (1984) · Zbl 0533.05046
[30]	Lauritzen, S. L.; Spiegelhalter, D. J.: Local computations with probabilities on graphical structures and their application to expert systems. J. royal statist. Soc. ser. A 50, 157-224 (1988) · Zbl 0684.68106
[31]	Leimer, H. -G.: Optimal decompositions by clique-separators. Discrete math. 113, 99-123 (1993) · Zbl 0793.05128
[32]	Maier, D.: The theory of relational databases.. (1983) · Zbl 0519.68082
[33]	Malvestuto, F. M.: Existence of extensions and product extensions for discrete probability distributions. Discrete math. 69, 61-77 (1988) · Zbl 0637.60021
[34]	Malvestuto, F. M.: Computing the maximum-entropy extension of given discrete probability distributions. Comput. statist. Data anal. 8, 299-311 (1989) · Zbl 0726.62012
[35]	Malvestuto, F. M.: Computing marginals in graphical log–linear models.. Computing science and statistics 29(2), 52-58 (1997)
[36]	Malvestuto, F. M.: A hypergraph-theoretic analysis of collapsibility and decomposability for extended log-linear models. Statistics and computing 11, 155-169 (2001)
[37]	Malvestuto, F. M.; Moscarini, M.: A fast algorithm for query optimization in universal-relation databases. J. comput. System sci. 56, 299-309 (1998) · Zbl 0913.68060
[38]	Malvestuto, F. M.; Moscarini, M.: Decomposition of a hypergraph by partial-edge separators. Theoret. comput. Sci. 237, No. 1–2, 57-79 (2000) · Zbl 0939.68089
[39]	Rose, D. J.; Tarjan, R. E.; Lueker, G. S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5, 266-283 (1976) · Zbl 0353.65019
[40]	Sanders, D. P.: On linear recognition of tree-width at most four. SIAM J. Discrete math. 9, 101-117 (1995) · Zbl 0847.05087
[41]	Shafer, G.: Probabilistic expert systems.. CBMS-NSF regional conference series in applied mathematics 67 (1996) · Zbl 0866.68108
[42]	Shibata, Y.: On the tree representation of chordal graphs. J. graph theory 12, 421-428 (1988) · Zbl 0654.05022
[43]	Spiegelhalter, D. J.: Probabilistic reasoning in predictive expert systems.. Proceedings of the conference on uncertainty in artificial intelligence. (1986)
[44]	Tarjan, R. E.: Decomposition by clique-separators. Discrete math. 55, 221-232 (1985) · Zbl 0572.05039
[45]	Tarjan, R. E.; Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13, 566-579 (1984) · Zbl 0545.68062
[46]	Vorob’ev, N. N.: Consistent families of measures and their extensions. Theory probab. Appl. 7, 147-163 (1962) · Zbl 0201.49102
[47]	Vorob’ev, N. N.: Markov measures and Markov extensions. Theor. prob. Appl. 8, 420-429 (1963) · Zbl 0126.13701
[48]	Wen, W.X., 1989. Optimal decomposition of belief networks. Technical Report, Dept. of CS, The University of Melbourne.
[49]	Wen, W.X., 1990. Optimal decomposition of belief networks. Proceedings of the VI Workshop on Uncertainty in Artificial Intelligence. pp. 245–256.
[50]	Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic discrete math. 2, 77-79 (1981) · Zbl 0496.68033