Kybernetika 56 no. 5, 850-874, 2020

Contribution of Frantisek Matus to the research on conditional independence

Milan StudenýDOI: 10.14736/kyb-2020-5-0850

Abstract:

An overview is given of results achieved by F. Matúš on probabilistic conditional independence (CI). First, his axiomatic characterizations of stochastic functional dependence and unconditional independence are recalled. Then his elegant proof of discrete probabilistic representability of a matroid based on its linear representability over a finite field is recalled. It is explained that this result was a basis of his methodology for constructing a probabilistic representation of a given abstract CI structure. His embedding of matroids into (augmented) abstract CI structures is recalled and his contribution to the theory of semigraphoids is mentioned as well. Finally, his results on the characterization of probabilistic CI structures induced by four discrete random variables and by four regular Gaussian random variables are recalled. Partial probabilistic representability by binary random variables is also mentioned.

Keywords:

conditional independence, matroid, polymatroid, entropy function, semimatroid, semigraphoid

Classification:

62H05, 05B35, 68T30

paper.pdf

References:

  1. G. Birkhoff: Lattice Theory. Third edition. American Mathematical Society, Colloquium Publications 25, Providence 1995.   CrossRef
  2. V. Chvátal and B. Wu: On Reichenbach's causal betweenness. Erkenntnis 76 (2012), 41-48.   DOI:10.1007/s10670-011-9321-z
  3. V. Chvátal, F. Matúš and Y. Zwólš: Patterns of conjuctive forks. A 2016 manuscript {\tt arXiv/1608.03949}.   CrossRef
  4. D. Cox, J. Little and D. O'Shea: Ideals, Varieties, and Algorithms. Springer, New York 1997.   CrossRef
  5. A. P. Dawid: Conditional independence in statistical theory. J. Royal Statist. Soc. B 41 (1979), 1, 1-31.   DOI:10.1111/j.2517-6161.1979.tb01052.x
  6. A. P. Dawid: Separoids: a mathematical framework for conditional independence and irrelevance. Ann. Math. Artif. Intell. 32 (2001), 1/4, 335-372.   DOI:10.1023/a:1016734104787
  7. S. Fujishige: Submodular Functions and Optimization. Second edition. Elsevier, Amsterdam 2005.   CrossRef
  8. D. Geiger, A. Paz and J. Pearl: Axioms and algorithms for inferences involving probabilistic independences. Inform. Comput. 91 (1991), 1, 128-141.   DOI:10.1016/0890-5401(91)90077-f
  9. D. Geiger and J. Pearl: Logical and algorithmic properties of conditional independence and graphical models. Ann. Statist. 21 (1993), 4, 2001-2021.   DOI:10.1214/aos/1176349407
  10. A. W. Ingleton: Conditions for representability and transversality of matroids. In: Lecture Notes in Computer Science 211, Springer, 1971, pp. 62-67.   DOI:10.1007/bfb0061075
  11. S. L. Lauritzen: Graphical Models. Clarendon Press, Oxford 1996.   CrossRef
  12. M. Loéve: Probability Theory, Foundations, Random Sequences. Van Nostrand, Toronto 1955.   CrossRef
  13. R. Lněnička and F. Matúš: On Gaussian conditional independence structures. Kybernetika 43 (2007), 3, 327-342.   CORPUS:16748330
  14. F. M. Malvestuto: A unique formal system for binary decompositions of database relations, probability distributions and graphs. Inform. Sci. 59 (1992), 21-52.   DOI:10.1016/0020-0255(92)90042-7
  15. F. Matúš: Independence and Radon Projections on Compact Groups (in Slovak). Thesis for CSc. Degree in Theoretical Computer Science, Institute of Information Theory and Automation, Czechoslovak Academy of Sciences, Prague 1988.   CrossRef
  16. F. Matúš: Abstract functional dependency structures. Theor. Computer Sci. 81 (1991), 117-126.   DOI:10.1016/0304-3975(91)90319-w
  17. F. Matúš: On equivalence of Markov properties over undirected graphs. J. Appl. Probab. 29 (1992), 745-749.   DOI:10.1017/s0021900200043552
  18. F. Matúš: Ascending and descending conditional independence relations. In: Trans. 11th Prague Conference on Information Theory, Statistical Decision Functions and Random Processes, volume B, Academia, Prague 1992, pp. 189-200.   CrossRef
  19. F. Matúš: Stochastic independence, algebraic independence and abstract connectedness. Theor. Computer Sci. 134 (1994), 455-471.   DOI:10.1016/0304-3975(94)90248-8
  20. F. Matúš: Probabilistic conditional independence structures and matroid theory: background. Int. J. General Systems 22 (1994), 185-196.   DOI:10.1080/03081079308935205
  21. F. Matúš: Extreme convex set functions with many non-negative differences. Discrete Math. 135 (1994), 177-191.   DOI:10.1016/0012-365x(93)e0100-i
  22. F. Matúš and M. Studený: Conditional independences among four random variables I. Combinatorics, Probability and Computing 4 (1995), 269-278.   DOI:10.1017/s0963548300001644
  23. F. Matúš: Conditional independences among four random variables II. Combinator. Probab. Comput. 4 (1995), 407-417.   DOI:10.1017/s0963548300001747
  24. F. Matúš: Conditional independence structures examined via minors. Ann. Math. Artif. Intell. 21 (1997), 99-128.   DOI:10.1023/a:1018957117081
  25. F. Matúš: Conditional independences among four random variables III: final conclusion. Combinator. Probab. Comput. 8 (1999), 269-276.   DOI:10.1017/s0963548399003740
  26. F. Matúš: Lengths of semigraphoid inferences. Ann. Math. Artif. Intell. 35 (2002), 287-294.   DOI:10.1023/a:1014525817725
  27. F. Matúš: Towards classification of semigraphoids. Discr. Math. 277 (2004), 115-145.   DOI:10.1016/s0012-365x(03)00155-9
  28. F. Matúš: Conditional independences in Gaussian vectors and rings of polynomials. In: Proc. WCII 2002, Lecture Notes in Artificial Intelligence 3301, Springer, Berlin 2005, pp. 152-161.   CORPUS:1893239
  29. F. Matúš: On conditional independence and log-convexity. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques 48 (2012), 4, 1137-1147.   DOI:10.1214/11-aihp431
  30. F. Matúš: On patterns of conditional independences and covariance signs among binary variables. Acta Math. Hungar. 154 (2018), 2, 511-524.   DOI:10.1007/s10474-018-0799-6
  31. M. Mouchart and J. M. Rolin: A note on conditional independences with statistical applications. Statistica 44 (1984), 557-584.   ECON:630
  32. H. Q. Nguyen: Semimodular functions and combinatorial geometries. Trans. Amer. Math. Soc. 238 (1978), 355-383.   DOI:10.1090/S0002-9947-1978-0491269-9
  33. J. G. Oxley: Matroid Theory. Oxford University Press, Oxford 1992.   CrossRef
  34. J. Pearl: Probabilistic Reasoning in Intelligent Systems - Networks of Plausible Inference. Morgan Kaufmann, San Francisco 1988.   CrossRef
  35. H. Reichenbach: The Direction of Time. University of California Press, Los Angeles 1956.   CrossRef
  36. W. Spohn: Stochastic independence, causal independence and shieldability. J. Philosoph. Logic 9 (1980), 1, 73-99.   DOI:10.1007/bf00258078
  37. M. Studený: Conditional independence relations have no finite complete characterization. In: Trans. 11th Prague Conference on Information Theory, Statistical Decision Functions and Random Processes, volume B, Academia, Prague 1992, pp. 377-396.   CrossRef
  38. M. Studený: Structural semigraphoids. Int. J. General Syst. 22 (1994), 207-217.   DOI:10.1080/03081079308935207
  39. M. Studený: Semigraphoids and structures of probabilistic conditional independence. Ann. Math. Artif. Intell. 21 (1997), 71-98.   DOI:10.1023/a:1018905100242
  40. M. Studený: Probabilistic Conditional Independence Structures. Springer, London 2005.   CrossRef
  41. H. Whitney: On the abstract properties of linear dependence. Amer. J. Math. 57 (1935), 3, 509-533.   DOI:10.2307/2371182
  42. J. Whittaker: Graphical Models in Applied Multivariate Statistics. John Wiley and Sons, Chichester 1990.   CrossRef
  43. R. W. Yeung: Information Theory and Network Coding. Springer, New York 2008.   CrossRef
  44. Z. Zhang and R. W. Yeung: A non-Shannon-type conditional inequality of information quantities. IEEE Trans. Inform. Theory 43 (1997), 1982-1986.   DOI:10.1109/18.641561
  45. G. M. Ziegler: Lectures on Polytopes. Springer, New York 1995.   CrossRef