Contribution of František Matúš to the research on conditional independence

Studený, Milan

Kybernetika, Tome 56 (2020) no. 5, pp. 850-874

Abstract (VO)

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.

Détail

DOI : 10.14736/kyb-2020-5-0850

Classification : 05B35, 62H05, 68T30
Keywords: conditional independence; matroid; polymatroid; entropy function; semigraphoid; semimatroid

Bibliographie

[1] Birkhoff, G.: Lattice Theory. Third edition. American Mathematical Society, Colloquium Publications 25, Providence 1995. | MR

[2] Chvátal, V., Wu, B.: On Reichenbach's causal betweenness. Erkenntnis 76 (2012), 41-48. | DOI | MR

[3] Chvátal, V., Matúš, F., Zwólš, Y.: Patterns of conjuctive forks. A 2016 manuscript arXiv/1608.03949.

[4] Cox, D., Little, J., O'Shea, D.: Ideals, Varieties, and Algorithms. Springer, New York 1997. | MR | Zbl

[5] Dawid, A. P.: Conditional independence in statistical theory. J. Royal Statist. Soc. B 41 (1979), 1, 1-31. | DOI | MR

[6] Dawid, A. P.: Separoids: a mathematical framework for conditional independence and irrelevance. Ann. Math. Artif. Intell. 32 (2001), 1/4, 335-372. | DOI | MR

[7] Fujishige, S.: Submodular Functions and Optimization. Second edition. Elsevier, Amsterdam 2005. | MR

[8] Geiger, D., Paz, A., Pearl, J.: Axioms and algorithms for inferences involving probabilistic independences. Inform. Comput. 91 (1991), 1, 128-141. | DOI | MR

[9] Geiger, D., Pearl, J.: Logical and algorithmic properties of conditional independence and graphical models. Ann. Statist. 21 (1993), 4, 2001-2021. | DOI | MR

[10] Ingleton, A. W.: Conditions for representability and transversality of matroids. In: Lecture Notes in Computer Science 211, Springer, 1971, pp. 62-67. | DOI | MR

[11] Lauritzen, S. L.: Graphical Models. Clarendon Press, Oxford 1996. | MR

[12] Loéve, M.: Probability Theory, Foundations, Random Sequences. Van Nostrand, Toronto 1955. | MR

[13] Lněnička, R., Matúš, F.: On Gaussian conditional independence structures. Kybernetika 43 (2007), 3, 327-342. On-Gaussian-conditional-independence-structures-Lnenicka-Matus/b2eb861a48a45cea586108d3b5e1c8c99a85e5bb | MR

[14] Malvestuto, F. M.: A unique formal system for binary decompositions of database relations, probability distributions and graphs. Inform. Sci. 59 (1992), 21-52. | DOI | MR

[15] Matúš, F.: 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.

[16] Matúš, F.: Abstract functional dependency structures. Theor. Computer Sci. 81 (1991), 117-126. | DOI | MR

[17] Matúš, F.: On equivalence of Markov properties over undirected graphs. J. Appl. Probab. 29 (1992), 745-749. | DOI | MR

[18] Matúš, F.: 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.

[19] Matúš, F.: Stochastic independence, algebraic independence and abstract connectedness. Theor. Computer Sci. 134 (1994), 455-471. | DOI | MR

[20] Matúš, F.: Probabilistic conditional independence structures and matroid theory: background. Int. J. General Systems 22 (1994), 185-196. | DOI

[21] Matúš, F.: Extreme convex set functions with many non-negative differences. Discrete Math. 135 (1994), 177-191. | DOI | MR

[22] Matúš, F., Studený, M.: Conditional independences among four random variables I. Combinatorics, Probability and Computing 4 (1995), 269-278. | DOI | MR

[23] Matúš, F.: Conditional independences among four random variables II. Combinator. Probab. Comput. 4 (1995), 407-417. | DOI | MR

[24] Matúš, F.: Conditional independence structures examined via minors. Ann. Math. Artif. Intell. 21 (1997), 99-128. | DOI | MR

[25] Matúš, F.: Conditional independences among four random variables III: final conclusion. Combinator. Probab. Comput. 8 (1999), 269-276. | DOI | MR

[26] Matúš, F.: Lengths of semigraphoid inferences. Ann. Math. Artif. Intell. 35 (2002), 287-294. | DOI | MR

[27] Matúš, F.: Towards classification of semigraphoids. Discr. Math. 277 (2004), 115-145. | DOI | MR

[28] Matúš, F.: 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. Conditional-Independences-in-Gaussian-Vectors-and-Mattt/846f0101f60d9f4bc8c558d748fc9d6ddcbbdca7

[29] Matúš, F.: On conditional independence and log-convexity. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques 48 (2012), 4, 1137-1147. | DOI | MR

[30] Matúš, F.: On patterns of conditional independences and covariance signs among binary variables. Acta Math. Hungar. 154 (2018), 2, 511-524. | DOI | MR

[31] Mouchart, M., Rolin, J. M.: A note on conditional independences with statistical applications. Statistica 44 (1984), 557-584. DOI  | MR

[32] Nguyen, H. Q.: Semimodular functions and combinatorial geometries. Trans. Amer. Math. Soc. 238 (1978), 355-383. | DOI | MR

[33] Oxley, J. G.: Matroid Theory. Oxford University Press, Oxford 1992. | MR

[34] Pearl, J.: Probabilistic Reasoning in Intelligent Systems - Networks of Plausible Inference. Morgan Kaufmann, San Francisco 1988. | MR

[35] Reichenbach, H.: The Direction of Time. University of California Press, Los Angeles 1956.

[36] Spohn, W.: Stochastic independence, causal independence and shieldability. J. Philosoph. Logic 9 (1980), 1, 73-99. | DOI | MR

[37] Studený, M.: 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.

[38] Studený, M.: Structural semigraphoids. Int. J. General Syst. 22 (1994), 207-217. | DOI

[39] Studený, M.: Semigraphoids and structures of probabilistic conditional independence. Ann. Math. Artif. Intell. 21 (1997), 71-98. | DOI | MR

[40] Studený, M.: Probabilistic Conditional Independence Structures. Springer, London 2005. | MR | Zbl

[41] Whitney, H.: On the abstract properties of linear dependence. Amer. J. Math. 57 (1935), 3, 509-533. | DOI | MR

[42] Whittaker, J.: Graphical Models in Applied Multivariate Statistics. John Wiley and Sons, Chichester 1990. | MR

[43] Yeung, R. W.: Information Theory and Network Coding. Springer, New York 2008.

[44] Zhang, Z., Yeung, R. W.: A non-Shannon-type conditional inequality of information quantities. IEEE Trans. Inform. Theory 43 (1997), 1982-1986. | DOI | MR

[45] Ziegler, G. M.: Lectures on Polytopes. Springer, New York 1995. | MR | Zbl