Tree and local computations in a cross–entropy minimization problem with marginal constraints

Malvestuto, Francesco M.

Kybernetika, Tome 46 (2010) no. 4, pp. 621-654

Abstract (VO)

In probability theory, Bayesian statistics, artificial intelligence and database theory the minimum cross-entropy principle is often used to estimate a distribution with a given set $P$ of marginal distributions under the proportionality assumption with respect to a given ``prior'' distribution $q$. Such an estimation problem admits a solution if and only if there exists an extension of $P$ that is dominated by $q$. In this paper we consider the case that $q$ is not given explicitly, but is specified as the maximum-entropy extension of an auxiliary set $Q$ of distributions. There are three problems that naturally arise: (1) the existence of an extension of a distribution set (such as $P$ and $Q$), (2) the existence of an extension of $P$ that is dominated by the maximum entropy extension of $Q$, (3) the numeric computation of the minimum cross-entropy extension of $P$ with respect to the maximum entropy extension of $Q$. In the spirit of a divide-and-conquer approach, we prove that, for each of the three above-mentioned problems, the global solution can be easily obtained by combining the solutions to subproblems defined at node level of a suitable tree.

Détail

Classification : 62A10, 93E12
Keywords: cross-entropy; acyclic hypergraph; connection tree; junction tree; probabilistic database; relational database

Bibliographie

[1] Asmussen, S., Edwards, D.: Collapsibility and response variables in contingency tables. Biometrika 70 (1983), 367–378. | DOI | MR | Zbl

[2] Bacharach, M.: Biproportional Matrices and Input-Output Change. Cambridge University Press, Cambridge 1970. | MR | Zbl

[3] Badsberg, J.-H., Malvestuto, F. M.: An implementation of the iterative proportional fitting procedure by propagation trees. Comput. Statist. Data Analysis 37 (2001), 297–322. | DOI | MR | Zbl

[4] Beeri, C., Vardi, M.: On the Properties of Full Join Dependencies. Adv. Database Theory I, Plenum Press, New York 1981.

[5] Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. Assoc. Comput. Mach. 30 (1983), 479–513. | DOI | MR | Zbl

[6] Berge, C.: Hypergraphs. North-Holland, Amsterdam 1989. | MR | Zbl

[7] Berge, C.: Discrete Multivariate Analysis. MIT Press, Cambridge 1975.

[8] Csiszár, I.: I-divergence geometry of probability distributions and minimization problems. Ann. Probab. 3 (1975), 146–158. | DOI | MR

[9] Csiszár, I.: Maxent, mathematics, and information theory. In: Proc. Internat. Workshop on “Maximum entropy and Bayesian methods", 1995, pp. 35–50. | MR

[10] Dall’Aglio, G., Kotz, K., Salinetti, G.: Advances in Probability Distributions with Given Marginals. Kluwer Academic Pub., Dordrecht, Boston, London 1991. | MR

[11] Darroch, J. N., Ratcliff, D.: Generalized iterative scaling for log-linear models. Ann. Math. Statist. 43 (1972), 1470–1480. | DOI | MR | Zbl

[12] Deming, W. E.: Statistical Adjustment of Data. Dover Pub., New York 1943. | MR | Zbl

[13] Deming, W. E., Stephan, F. F.: On a least squares adjustment of a sampled frequency table when the expected marginal totals are known. Ann. Math. Statist. 11 (1940), 427–444. | DOI | MR | Zbl

[14] Endo, Y., Takemura, A. I.: Iterative proportional scaling via decomposable submodels for contingency tables. Comput. Statist. Data Analysis 53 (2009), 966–978. | DOI | MR

[15] Fienberg, S. E.: An iterative procedure for estimation in contingency tables. Ann. Math. Statist. 41 (1970), 907–917. | DOI | MR | Zbl

[16] Fienberg, S. E., Meyer, M. M.: Iterative proportional fitting. In: Encyclopedia of Statistical Sciences (S. Kotz, N. L. Johnson, and C. B. Read, eds.), 4, John Wiley and Sons, New York, pp.  275–279.

[17] Haberman, S. J.: Log-linear Models for Contingency Tables. University of Chicago Press, Chicago 1974.

[18] Ireland, C. T., Kullback, S.: Contingency tables with given marginals. Biometrika 55 (1968), 179–188. | DOI | MR | Zbl

[19] Jiroušek, R.: Composition of probability measures on finite spaces. In: Proc. XIII Internat. Conf. Uncertainty in Artificial Intelligence 1997, pp. 274–281.

[20] Jiroušek, R., Přeučil, S.: On the effective implementation of the iterative proportional fitting procedure. Comput. Statist. Data Analysis 19 (1995), 177–189. | DOI

[21] Johnson, R. W.: Axiomatic characterization of the directed divergences and their linear combinations. IEEE Trans. Inform. Theory 25 (1979), 709–716. | DOI | MR | Zbl

[22] Kellerer, H. G.: Verteilungsfunktionen mit gegebenen marginalverteilungen. Zeitschrift Wahrscheinlichkeitstheorie und Verw. Gebiete 3 (1964), 247–270. | DOI | MR | Zbl

[23] Kellerer, H. G.: Masstheoretische marginalprobleme. Math. Annalen 153 (1964), 168–198. | DOI | MR | Zbl

[24] Kern-Isberner, G.: Characterizing the principle of minimum-cross entropy within a conditional-logical framework. Artificial Intelligence 98 (1998), 169–208. | DOI | MR | Zbl

[25] Ku, H. H., Kullback, S.: Interaction in multidimensional contingency tables: an information-theoretic approach. J. Res. Nat. Bur. Standards - Math. Sci. 72 B (1968), 159–199. | MR | Zbl

[26] Lauritzen, S. L.: Graphical Models. Oxford Science Pub., Clarendom Press, Oxford 1996. | MR

[27] Lauritzen, S. L., Speed, M. P., Vijayan, K.: Decomposable graphs and hypergraphs. J. Austral. Math. Soc. Ser. A 36 (1984), 12–29. | DOI | MR | Zbl

[28] Lauritzen, S. L., Spiegelhalter, D. J.: Local computations with probabilities on graphical structures and their application to expert systems. J. Roy. Stat. Soc. Ser. B 50 (1988), 157–224. | MR | Zbl

[29] Leimer, G.: Optimal decomposition by clique separators. Discrete Math. 113 (1993), 99–123. | DOI | MR | Zbl

[30] Leontief, W. W.: The Structure of American Economy 1919–1929. Oxford University Press, New York 1941.

[31] Leontief, W. W., Strout, A.: Multiregional input-output analysis. In: Structural Interdependence and Economic Development, 1963, pp. 119–169.

[32] Madigan, D., Mosurski, K.: An extension of the results of Asmussen and Edwards on collapsibility in contingency tables. Biometrika 77 (1990), 315–319. | DOI | MR | Zbl

[33] Madigan, D., Mosurski, K.: Errata: An extension of the results of Asmussen and Edwards on collapsibility in contingency tables. Biometrika 86 (1999) 973. | MR

[34] Maier, D.: The Theory of Relational Databases. Computer Science Press, 1983. ( http://web.cecs.pdx.edu/ maier/TheoryBook/TRD.html) | MR | Zbl

[35] Maier, D., Ullman, J. D.: Connections in acyclic hypergraphs. Theoret. Comput. Sci. 32 (1984), 185–199. | DOI | MR | Zbl

[36] Malvestuto, F. M.: Answering queries in categorical data bases. In: Proc. VI ACM Symp. Principles of Database Systems 1987, pp. 87–96.

[37] Malvestuto, F. M.: Existence of extensions and product extensions for discrete probability distributions. Discrete Math. 69 (1988), 61–77. | DOI | MR | Zbl

[38] Malvestuto, F. M.: Computing the maximum-entropy extension of given discrete probability distributions. Computat. Statist. Data Anal. 8 (1989), 299–311. | DOI | MR | Zbl

[39] Malvestuto, F. M.: Testing implication of hierarchical loglinear models for discrete probability distributions. Statist. Computing 6 (1996), 169–176. | DOI

[40] Malvestuto, F. M.: A hypergraph-theoretic analysis of collapsibility and decomposability for extended loglinear models. Statist. Computing 11 (2001), 155–169. | DOI | MR

[41] Malvestuto, F. M.: From conditional independences to factorization constraints with discrete random variables. Ann. Math. Artificial Intelligence 35 (2002), 253–285. | DOI | MR | Zbl

[42] Malvestuto, F. M.: Canonical and monophonic convexities in hypergraphs. Discrete Math. 309 (2009), 4287–4298. | DOI | MR | Zbl

[43] Malvestuto, F. M., Moscarini, M.: A fast algorithm for query optimization in universal-relation databases. J. Comput. System Sci. 56 (1998), 299–309. | DOI | MR | Zbl

[44] Malvestuto, F. M., Moscarini, M.: Decomposition of a hypergraph by partial-edge separators. Theoret. Comput. Sci. 237 (2000), 57–79. | DOI | MR | Zbl

[45] Malvestuto, F. M., Pourabbas, E.: Customized answers to summary queries via aggregate views. In: Proc. XVI Intl. Conf. Scientific & Statistical Database Management 2004, pp. 193–202.

[46] Malvestuto, F. M., Pourabbas, E.: Local computation of answers to table queries on summary databases. In: Proc. XVII Intl. Conf. Scientific & Statistical Database Management 2005, pp. 263–272.

[47] Matúš, F.: Discrete marginal problem for complex measures. Kybernetika 24 (1988), 36–46. | MR

[48] Matúš, F.: On the maximum-entropy extensions of probability measures over undirected graphs. In: Proc. III Workshop Uncertainty Processing in Expert Systems 1994, pp. 181–198.

[49] Matúš, F., Flusser, J.: Image representations via a finite Radon transform. IEEE Trans. Pattern Analysis and Machine Intelligence 15 (1993), 996–1006. | DOI

[50] Purcell, N. J., Kish, L.: Estimation for small domains. Biometrics 35 (1979), 365–384. | DOI | MR | Zbl

[51] Purcell, N. J., Kish, L.: Postcensal estimates for local areas (or domains). Internat. Statist. Rev. 48 (1980), 3–18. | DOI | Zbl

[52] Rüschendorf, L.: Convergence of the iterative proportional fitting procedure. Ann. Statist. 23 (1995), 1160–1174. | DOI | MR

[53] Shore, J. E., Johnson, R. W.: Properties of cross-entropy minimization. IEEE Trans. Inform. Theory 27 (1981), 472–482. | DOI | MR | Zbl

[54] Stephan, F. F.: An iterative method of adjusting sample frequencies tables when expected marginal totals are known. Ann. Math. Statist. 13 (1942), 166–178. | DOI | MR

[55] Stone, R., Brown, A.: A Computable Model for Economic Growth: A Programme for Growth, No. 1. Chapman Hall, London 1962.

[56] Tarjan, R. E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce hypergraphs. SIAM J. Comput. 13 (1984), 566–579. | DOI | MR

[57] Vomlel, J.: Integrating inconsistent data in a probabilistic model. J. Appl. Non-Classical Logics 14 (2004), 365–386. | DOI | Zbl

[58] Vorob’ev, N. N.: Consistent families of measures and their extensions. Theor. Prob. Appl. 7 (1962), 147–163. | DOI

[59] Vorob’ev, N. N.: Markov measures and Markov extensions. Theor. Prob. Appl. 8 (1963), 420–429. | DOI | MR

[60] Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Mathematics 2 (1981), 77–79. | DOI | MR | Zbl

[61] Yannakakis, M.: Algorithms for acyclic database schemes. In: Proc. VII Internat. Conf. Very Large Data Bases 1981, pp. 82–94.