Kybernetika 46 no. 4, 621-654, 2010

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

Francesco M. Malvestuto

Abstract:

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.

Keywords:

cross-entropy, acyclic hypergraph, connection tree, junction tree, probabilistic database, relational database

Classification:

93E12, 62A10

References:

  1. S. Asmussen and D. Edwards: Collapsibility and response variables in contingency tables. Biometrika {\mi 70} (1983), 367--378.   CrossRef
  2. M. Bacharach: Biproportional Matrices and Input-Output Change. Cambridge University Press, Cambridge 1970.   CrossRef
  3. J.-H. Badsberg, F.\ and M. Malvestuto: An implementation of the iterative proportional fitting procedure by propagation trees. Comput. Statist. Data Analysis {\mi 37} (2001), 297--322.   CrossRef
  4. C. Beeri and M. Vardi: On the Properties of Full Join Dependencies. Adv. Database Theory I, Plenum Press, New York 1981.   CrossRef
  5. C. Beeri, R. Fagin, D. Maier, and M. Yannakakis: On the desirability of acyclic database schemes. J. Assoc. Comput. Mach. {\mi 30} (1983), 479--513.   CrossRef
  6. C. Berge: Hypergraphs. North-Holland, Amsterdam 1989.   CrossRef
  7. I. Csisz\'ar: I-divergence geometry of probability distributions and minimization problems. Ann. Probab. {\mi 3} (1975), 146--158.   CrossRef
  8. I. Csisz\'ar: Maxent, mathematics, and information theory. In: Proc. Internat. Workshop on ``Maximum entropy and Bayesian methods", 1995, pp.\,35--50.   CrossRef
  9. G. Dall'Aglio, K. Kotz, and G. Salinetti (eds.): Advances in Probability Distributions with Given Marginals. Kluwer Academic Pub., Dordrecht, Boston, London 1991.   CrossRef
  10. J.\, N. Darroch and D. Ratcliff: Generalized iterative scaling for log-linear models. Ann. Math. Statist. {\mi 43} (1972), 1470--1480.   CrossRef
  11. W.\, E. Deming, F.\ and F. Stephan: On a least squares adjustment of a sampled frequency table when the expected marginal totals are known. Ann. Math. Statist. {\mi 11} (1940), 427--444.   CrossRef
  12. Y. Endo, A.\ and I. Takemura: Iterative proportional scaling via decomposable submodels for contingency tables. Comput. Statist. Data Analysis {\mi 53} (2009), 966--978.   CrossRef
  13. S.\ and E. Fienberg: An iterative procedure for estimation in contingency tables. Ann. Math. Statist. {\mi 41} (1970), 907--917.   CrossRef
  14. S.\, E. Fienberg, M.\ and M. Meyer: Iterative proportional fitting. In: Encyclopedia of Statistical Sciences (S. Kotz, N.\,L. Johnson, and C.\,B. Read, eds.), {\mi 4}, John Wiley and Sons, New York, pp.\, 275--279.   CrossRef
  15. S.\ and J. Haberman: Log-linear Models for Contingency Tables. University of Chicago Press, Chicago 1974.   CrossRef
  16. C.\, T. Irel, and S. Kullback: Contingency tables with given marginals. Biometrika {\mi 55} (1968), 179--188.   CrossRef
  17. ek: Composition of probability measures on finite spaces. In: Proc. XIII Internat. Conf. Uncertainty in Artificial Intelligence 1997, pp.\,274--281.   CrossRef
  18. il: On the effective implementation of the iterative proportional fitting procedure. Comput. Statist. Data Analysis {\mi 19} (1995), 177--189.   CrossRef
  19. R.\ and W. Johnson: Axiomatic characterization of the directed divergences and their linear combinations. IEEE Trans. Inform. Theory {\mi 25} (1979), 709--716.   CrossRef
  20. H.\ and G. Kellerer: Masstheoretische marginalprobleme. Math. Annalen {\mi 153} (1964), 168--198.   CrossRef
  21. H.\, H. Ku and S. Kullback: Interaction in multidimensional contingency tables: an information-theoretic approach. J. Res. Nat. Bur. Standards - Math. Sci. {\mi 72 B} (1968), 159--199.   CrossRef
  22. S.\ and L. Lauritzen: Graphical Models. Oxford Science Pub., Clarendom Press, Oxford 1996.   CrossRef
  23. S.\, L. Lauritzen, M.\, P. Speed and K. Vijayan: Decomposable graphs and hypergraphs. J. Austral. Math. Soc. Ser. {\mi A 36} (1984), 12--29.   CrossRef
  24. S.\, L. Lauritzen, D.\ and J. Spiegelhalter: Local computations with probabilities on graphical structures and their application to expert systems. J. Roy. Stat. Soc. Ser. {\mi B 50} (1988), 157--224.   CrossRef
  25. D. Madigan and K. Mosurski: An extension of the results of Asmussen and Edwards on collapsibility in contingency tables. Biometrika {\mi 77} (1990), 315--319.   CrossRef
  26. D. Madigan and K. Mosurski: Errata: An extension of the results of Asmussen and Edwards on collapsibility in contingency tables. Biometrika {\mi 86} (1999) 973.   CrossRef
  27. F.\ and M. Malvestuto: Answering queries in categorical data bases. In: Proc. VI ACM Symp. Principles of Database Systems 1987, pp.\,87--96.   CrossRef
  28. F.\ and M. Malvestuto: Existence of extensions and product extensions for discrete probability distributions. Discrete Math. {\mi 69} (1988), 61--77.   CrossRef
  29. F.\ and M. Malvestuto: Computing the maximum-entropy extension of given discrete probability distributions. Computat. Statist. Data Anal. {\mi 8} (1989), 299--311.   CrossRef
  30. F.\ and M. Malvestuto: Testing implication of hierarchical loglinear models for discrete probability distributions. Statist. Computing {\mi 6} (1996), 169--176.   CrossRef
  31. F.\ and M. Malvestuto: A hypergraph-theoretic analysis of collapsibility and decomposability for extended loglinear models. Statist. Computing {\mi 11} (2001), 155--169.   CrossRef
  32. F.\ and M. Malvestuto: From conditional independences to factorization constraints with discrete random variables. Ann. Math. Artificial Intelligence {\mi 35} (2002), 253--285.   CrossRef
  33. F.\, M. Malvestuto and M. Moscarini: A fast algorithm for query optimization in universal-relation databases. J. Comput. System Sci. {\mi 56} (1998), 299--309.   CrossRef
  34. F.\ and F. Stephan: An iterative method of adjusting sample frequencies tables when expected marginal totals are known. Ann. Math. Statist. {\mi 13} (1942), 166--178.   CrossRef
  35. R.\, E. Tarjan and M. Yannakakis: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce hypergraphs. SIAM J. Comput. {\mi 13} (1984), 566--579.   CrossRef