Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
conditional independence; matroid; polymatroid; entropy function; semigraphoid; semimatroid
conditional independence; matroid; polymatroid; entropy function; semigraphoid; semimatroid
Summary:
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.
References:
[1] Birkhoff, G.: Lattice Theory. Third edition. American Mathematical Society, Colloquium Publications 25, Providence 1995. MR 0598630
[2] Chvátal, V., Wu, B.: On Reichenbach's causal betweenness. Erkenntnis 76 (2012), 41-48. DOI 10.1007/s10670-011-9321-z | MR 2874714
[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 2290010 | Zbl 1118.13001
[5] Dawid, A. P.: Conditional independence in statistical theory. J. Royal Statist. Soc. B 41 (1979), 1, 1-31. DOI 10.1111/j.2517-6161.1979.tb01052.x | MR 0535541
[6] Dawid, A. P.: Separoids: a mathematical framework for conditional independence and irrelevance. Ann. Math. Artif. Intell. 32 (2001), 1/4, 335-372. DOI 10.1023/a:1016734104787 | MR 1859870
[7] Fujishige, S.: Submodular Functions and Optimization. Second edition. Elsevier, Amsterdam 2005. MR 2171629
[8] Geiger, D., Paz, A., Pearl, J.: Axioms and algorithms for inferences involving probabilistic independences. Inform. Comput. 91 (1991), 1, 128-141. DOI 10.1016/0890-5401(91)90077-f | MR 1097266
[9] Geiger, D., Pearl, J.: Logical and algorithmic properties of conditional independence and graphical models. Ann. Statist. 21 (1993), 4, 2001-2021. DOI 10.1214/aos/1176349407 | MR 1245778
[10] Ingleton, A. W.: Conditions for representability and transversality of matroids. In: Lecture Notes in Computer Science 211, Springer, 1971, pp. 62-67. DOI 10.1007/bfb0061075 | MR 0337664
[11] Lauritzen, S. L.: Graphical Models. Clarendon Press, Oxford 1996. MR 1419991
[12] Loéve, M.: Probability Theory, Foundations, Random Sequences. Van Nostrand, Toronto 1955. MR 0066573
[13] Lněnička, R., Matúš, F.: On Gaussian conditional independence structures. Kybernetika 43 (2007), 3, 327-342. DOI | MR 2362722
[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 10.1016/0020-0255(92)90042-7 | MR 1128204
[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 10.1016/0304-3975(91)90319-w | MR 1103102
[17] Matúš, F.: On equivalence of Markov properties over undirected graphs. J. Appl. Probab. 29 (1992), 745-749. DOI 10.1017/s0021900200043552 | MR 1174448
[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 10.1016/0304-3975(94)90248-8 | MR 1304673
[20] Matúš, F.: Probabilistic conditional independence structures and matroid theory: background. Int. J. General Systems 22 (1994), 185-196. DOI 10.1080/03081079308935205
[21] Matúš, F.: Extreme convex set functions with many non-negative differences. Discrete Math. 135 (1994), 177-191. DOI 10.1016/0012-365x(93)e0100-i | MR 1310880
[22] Matúš, F., Studený, M.: Conditional independences among four random variables I. Combinatorics, Probability and Computing 4 (1995), 269-278. DOI 10.1017/s0963548300001644 | MR 1356579
[23] Matúš, F.: Conditional independences among four random variables II. Combinator. Probab. Comput. 4 (1995), 407-417. DOI 10.1017/s0963548300001747 | MR 1377558
[24] Matúš, F.: Conditional independence structures examined via minors. Ann. Math. Artif. Intell. 21 (1997), 99-128. DOI 10.1023/a:1018957117081 | MR 1479010
[25] Matúš, F.: Conditional independences among four random variables III: final conclusion. Combinator. Probab. Comput. 8 (1999), 269-276. DOI 10.1017/s0963548399003740 | MR 1702569
[26] Matúš, F.: Lengths of semigraphoid inferences. Ann. Math. Artif. Intell. 35 (2002), 287-294. DOI 10.1023/a:1014525817725 | MR 1899955
[27] Matúš, F.: Towards classification of semigraphoids. Discr. Math. 277 (2004), 115-145. DOI 10.1016/s0012-365x(03)00155-9 | MR 2033729
[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. DOI
[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 10.1214/11-aihp431 | MR 3052406
[30] Matúš, F.: 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 | MR 3773837
[31] Mouchart, M., Rolin, J. M.: A note on conditional independences with statistical applications. Statistica 44 (1984), 557-584. DOI | MR 0818481
[32] Nguyen, H. Q.: Semimodular functions and combinatorial geometries. Trans. Amer. Math. Soc. 238 (1978), 355-383. DOI 10.1090/S0002-9947-1978-0491269-9 | MR 0491269
[33] Oxley, J. G.: Matroid Theory. Oxford University Press, Oxford 1992. MR 1207587
[34] Pearl, J.: Probabilistic Reasoning in Intelligent Systems - Networks of Plausible Inference. Morgan Kaufmann, San Francisco 1988. MR 0965765
[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 10.1007/bf00258078 | MR 0563250
[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 10.1080/03081079308935207
[39] Studený, M.: Semigraphoids and structures of probabilistic conditional independence. Ann. Math. Artif. Intell. 21 (1997), 71-98. DOI 10.1023/a:1018905100242 | MR 1479009
[40] Studený, M.: Probabilistic Conditional Independence Structures. Springer, London 2005. MR 3183760 | Zbl 1070.62001
[41] Whitney, H.: On the abstract properties of linear dependence. Amer. J. Math. 57 (1935), 3, 509-533. DOI 10.2307/2371182 | MR 1507091
[42] Whittaker, J.: Graphical Models in Applied Multivariate Statistics. John Wiley and Sons, Chichester 1990. MR 1112133
[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 10.1109/18.641561 | MR 1481054
[45] Ziegler, G. M.: Lectures on Polytopes. Springer, New York 1995. MR 1311028 | Zbl 0823.52002
Search
Partner of
