×

On the completeness of the semigraphoid axioms for deriving arbitrary from saturated conditional independence statements. (English) Zbl 1371.68273

Summary: Conditional independence (CI) statements occur in several areas of computer science and artificial intelligence, e.g., as embedded multivalued dependencies in database theory, disjunctive association rules in data mining, and probabilistic CI statements in probability theory. Although, syntactically, such constraints can always be represented in the form \(I(A,B|C)\), with \(A\), \(B\), and \(C\) subsets of some universe \(S\), their semantics is very dependent on their interpretation, and, therefore, inference rules valid under one interpretation need not be valid under another. However, all aforementioned interpretations obey the so-called semigraphoid axioms. In this paper, we consider the restricted case of deriving arbitrary CI statements from so-called saturated ones, i.e., which involve all elements of \(S\). Our main result is a necessary and sufficient condition under which the semigraphoid axioms are also complete for such derivations. Finally, we apply these results to the examples mentioned above to show that, for these semantics, the semigraphoid axioms are both sound and complete for the derivation of arbitrary CI statements from saturated ones.

MSC:

68T37 Reasoning under uncertainty in the context of artificial intelligence
68P15 Database theory
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Studený, M., Formal properties of conditional independence in different calculi of AI, (Symbolic and Quantitative Approaches to Reasoning and Uncertainty. Symbolic and Quantitative Approaches to Reasoning and Uncertainty, Lect. Notes Comput. Sci., vol. 747 (1993)), 341-348
[2] Fagin, R., Multivalued dependencies and a new normal form for relational databases, ACM Trans. Database Syst., 2, 262-278 (1977)
[3] Bykowski, A.; Rigotti, C., A condensed representation to find frequent patterns, (Proc. of the 20th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (2001), ACM Press: ACM Press New York), 267-273
[4] Dawid, A., Conditional independence in statistical theory, J. R. Stat. Soc. B, 41, 1-31 (1979) · Zbl 0408.62004
[5] Pearl, J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufmann Publishers Inc.
[6] Spohn, W., Stochastic independence, casual independence and shieldability, J. Philos. Log., 9, 73-99 (1980) · Zbl 0436.60004
[7] Spohn, W., Ordinal conditional functions: a dynamic theory of epistemic states, (Harper, W. L.; Skyrms, B., Causation in Decision, Belief Change, and Statistics, vol. II (1988), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 105-134
[8] Dempster, A., A generalization of Bayesian inference, J. R. Stat. Soc. B, 30, 205-247 (1968) · Zbl 0169.21301
[9] Shafer, G., A Mathematical Theory of Evidence (1976), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0359.62002
[10] Zadeh, L., Fuzzy sets as the basis for a theory of possibility, Fuzzy Sets Syst., 1, 3-28 (1978) · Zbl 0377.04002
[11] Sayrafi, B.; Van Gucht, D., Differential constraints, (Proc. of the 24th ACM Symposium on Principles of Database Systems (2005)), 348-357
[12] Sayrafi, B.; Van Gucht, D.; Gyssens, M., The implication problem for measure-based constraints, Inf. Syst., 33, 221-239 (2008)
[13] Dalkilic, M. M.; Robertson, E. L., Information dependencies, (Proc. of the 19th ACM Symposium on Principles of Database Systems (2000)), 245-253
[14] Lee, T. T., An information-theoretic analysis of relational databases. Part I: data dependencies and information metric, IEEE Trans. Softw. Eng., SE-13, 1049-1061 (1987)
[15] Studený, M., Probabilistic Conditional Independence Structures (2005), Springer-Verlag · Zbl 1070.62001
[16] Hemmecke, R.; Morton, J.; Shiu, A.; Sturmfels, B.; Wienand, O., Three counter-examples on semi-graphoids, Comb. Probab. Comput., 17, 239-257 (2008) · Zbl 1211.62197
[17] Bouckaert, R.; Studený, M., Racing algorithms for conditional independence inference, Int. J. Approx. Reason., 45, 386-401 (2007) · Zbl 1122.68130
[18] Bouckaert, R.; Hemmecke, R.; Lindner, S.; Studený, M., Efficient algorithms for conditional independence inference, J. Mach. Learn. Res., 11, 3453-3479 (2010) · Zbl 1242.62129
[19] Niepert, M.; Gyssens, M.; Sayrafi, B.; Van Gucht, D., On the conditional independence implication problem: a lattice-theoretic approach, Artif. Intell., 202, 29-51 (2013) · Zbl 1329.68250
[20] Studený, M., Conditional independence statements have no complete characterization, (Transactions of the 11th Prague Conference on Information Theory (1992)), 377-396 · Zbl 0764.60004
[21] Herrmann, C., On the undecidability of implications between embedded multivalued dependencies, Inf. Comput., 122, 221-235 (1995) · Zbl 1096.68608
[22] Herrmann, C., Corrigendum to “On the undecidability of implications between embedded multivalued database dependencies”, Inf. Comput.. Inf. Comput., Inf. Comput., 204, 1847-1851 (2006) · Zbl 1171.68449
[23] Grätzer, G. A., General Lattice Theory (1998), Birkhäuser-Verlag
[24] Link, S., Sound approximate reasoning about saturated conditional probabilistic independence under controlled uncertainty, J. Appl. Log., 11, 309-327 (2013) · Zbl 1284.68551
[25] Link, S., Reasoning about saturated conditional independence under uncertainty: axioms, algorithms, and Levesque’s situations to the rescue, (Proc. of the AAAI Conference on Artificial Intelligence (2013)), 612-618
[26] Malvestuto, F. M., A unique formal system for binary decompositions of database relations, probability distributions, and graphs, J. Inf. Sci., 59, 21-52 (1992) · Zbl 0764.68030
[27] Geiger, D.; Pearl, J., Logical and algorithmic properties of conditional independence and graphical models, Ann. Stat., 21, 2001-2021 (1993) · Zbl 0814.62006
[28] Gyssens, M.; Paredaens, J., Another view of functional and multivalued dependencies in the relational database model, Int. J. Parallel Program., 12, 247-267 (1983) · Zbl 0525.68066
[29] Pearl, J.; Verma, T., The logic of representing dependencies by directed graphs, (Proc. of the AAAI Conference on Artificial Intelligence (1987)), 374-379
[30] (Renooij, S. M.M. S.; Tabachneck-Schijf, H. J.M., Proc. of the 6th UAI Bayesian Modelling Applications Workshop (2008))
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.