×

A logical approach to context-specific independence. (English) Zbl 1477.03068

Summary: Directed acyclic graphs (DAGs) constitute a qualitative representation for conditional independence (CI) properties of a probability distribution. It is known that every CI statement implied by the topology of a DAG is witnessed over it under a graph-theoretic criterion of \(d\)-separation. Alternatively, all such implied CI statements are derivable from the local independencies encoded by a DAG using the so-called semi-graphoid axioms. We consider Labeled Directed Acyclic Graphs (LDAGs) modeling graphically scenarios exhibiting context-specific independence (CSI). Such CSI statements are modeled by labeled edges, where labels encode contexts in which the edge vanishes. We study the problem of identifying all independence statements implied by the structure and the labels of an LDAG. We show that this problem is coNP-hard for LDAGs and formulate a sound extension of the semi-graphoid axioms for the derivation of such implied independencies. Finally we connect our study to certain qualitative versions of independence ubiquitous in database theory and teams semantics.

MSC:

03B48 Probability and inductive logic
03B60 Other nonclassical logic
05C20 Directed graphs (digraphs), tournaments
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Boutilier, C.; Friedman, N.; Goldszmidt, M.; Koller, D., Context-specific independence in Bayesian networks, (Proceedings of the Twelfth International Conference on Uncertainty in Artificial Intelligence. Proceedings of the Twelfth International Conference on Uncertainty in Artificial Intelligence, UAI’96 (1996), Morgan Kaufmann Publishers Inc.: Morgan Kaufmann Publishers Inc. San Francisco, CA, USA), 115-123
[2] Bravo, L.; Fan, W.; Ma, S., Extending dependencies with conditions, (Koch, C.; Gehrke, J.; Garofalakis, M. N.; Srivastava, D.; Aberer, K.; Deshpande, A.; Florescu, D.; Chan, C. Y.; Ganti, V.; Kanne, C.; Klas, W.; Neuhold, E. J., Proceedings of the 33rd International Conference on Very Large Data Bases. Proceedings of the 33rd International Conference on Very Large Data Bases, University of Vienna, Austria, September 23-27, 2007 (2007), ACM), 243-254
[3] Chickering, D. M.; Heckerman, D.; Meek, C., A Bayesian approach to learning Bayesian networks with local structure, (Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence (1997)), 80-89
[4] Dawid, A. P., Conditional independence in statistical theory, J. Roy. Statist. Soc. Ser. B (Methodological), 41, 1, 1-31 (1979) · Zbl 0408.62004
[5] Durand, A.; Hannula, M.; Kontinen, J.; Meier, A.; Virtema, J., Probabilistic team semantics, (Foundations of Information and Knowledge Systems - 10th International Symposium, FoIKS 2018, Proceedings. Foundations of Information and Knowledge Systems - 10th International Symposium, FoIKS 2018, Proceedings, Lecture Notes in Computer Science (2018), Springer) · Zbl 1508.03057
[6] Durand, A.; Hannula, M.; Kontinen, J.; Meier, A.; Virtema, J., Approximation and dependence via multiteam semantics, Annals of Mathematics and Artificial Intelligence · Zbl 1459.03031
[7] Fan, W.; Geerts, F.; Jia, X.; Kementsietsidis, A., Conditional functional dependencies for capturing data inconsistencies, ACM Trans. Database Syst., 33, 2, 6:1-6:48 (2008)
[8] Friedman, N.; Goldszmidt, M., Learning Bayesian Networks With Local Structure, Learning in Graphical Models, vol. 89 (1998), Springer · Zbl 0910.68176
[9] Galliani, P., Inclusion and exclusion dependencies in team semantics – on some logics of imperfect information, Ann. Pure Appl. Logic, 163, 1, 68-84 (2012) · Zbl 1250.03047
[10] Geiger, D.; Heckerman, D., Knowledge representation and inference in similarity networks and Bayesian multinets, Artificial Intelligence, 82, 1, 45-74 (1996) · Zbl 1517.68360
[11] Geiger, D.; Pearl, J., On the logic of causal models, (Proceedings of the Fourth Annual Conference on Uncertainty in Artificial Intelligence. Proceedings of the Fourth Annual Conference on Uncertainty in Artificial Intelligence, UAI ’88 (1990), North-Holland Publishing Co.: North-Holland Publishing Co. Amsterdam, The Netherlands, The Netherlands), 3-14
[12] Geiger, D.; Verma, T.; Pearl, J., Identifying independence in Bayesian networks, Networks, 20, 5, 507-534 (1990) · Zbl 0724.05066
[13] Geiger, D.; Paz, A.; Pearl, J., Axioms and algorithms for inferences involving probabilistic independence, Inform. and Comput., 91, 1, 128-141 (1991) · Zbl 0800.68842
[14] Grädel, E.; Väänänen, J. A., Dependence and independence, Studia Logica, 101, 2, 399-410 (2013) · Zbl 1272.03125
[15] Gyssens, M.; Niepert, M.; Gucht, D. V., On the completeness of the semigraphoid axioms for deriving arbitrary from saturated conditional independence statements, Inform. Process. Lett., 114, 11, 628-633 (2014) · Zbl 1371.68273
[16] Hannula, M., Reasoning about embedded dependencies using inclusion dependencies, (Davis, M.; Fehnker, A.; McIver, A.; Voronkov, A., Logic for Programming, Artificial Intelligence, and Reasoning - 20th International Conference, LPAR-20 2015, Suva, Fiji, November 24-28, 2015, Proceedings. Logic for Programming, Artificial Intelligence, and Reasoning - 20th International Conference, LPAR-20 2015, Suva, Fiji, November 24-28, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9450 (2015), Springer), 16-30 · Zbl 1471.68083
[17] Hannula, M., Axiomatizing first-order consequences in independence logic, Ann. Pure Appl. Logic, 166, 1, 61-91 (2015) · Zbl 1343.03027
[18] Hannula, M.; Kontinen, J., A finite axiomatization of conditional independence and inclusion dependencies, Inform. and Comput., 249, 121-137 (2016) · Zbl 1435.68076
[19] Herrmann, C., On the undecidability of implications between embedded multivalued database dependencies, Inform. and Comput., 122, 2, 221-235 (1995) · Zbl 1096.68608
[20] Koller, D.; Friedman, N., Probabilistic Graphical Models: Principles and Techniques (2009), MIT Press
[21] Kontinen, J.; Väänänen, J. A., Axiomatizing first-order consequences in dependence logic, Ann. Pure Appl. Logic, 164, 11, 1101-1117 (2013) · Zbl 1315.03062
[22] Link, S., Reasoning about saturated conditional independence under uncertainty: axioms, algorithms, and levesque’s situations to the rescue, (Proc. AAAI (2013), AAAI Press)
[23] Link, S., Sound approximate reasoning about saturated conditional probabilistic independence under controlled uncertainty, J. Appl. Log., 11, 3, 309-327 (2013) · Zbl 1284.68551
[24] Link, S., Frontiers for propositional reasoning about fragments of probabilistic conditional independence and hierarchical database decompositions, Theoret. Comput. Sci., 603, 111-131 (2015) · Zbl 1330.68279
[25] Ma, S.; Fan, W.; Bravo, L., Extending inclusion dependencies with conditions, Theoret. Comput. Sci., 515, 64-95 (2014) · Zbl 1277.68067
[26] Niepert, M.; Gyssens, M.; Sayrafi, B.; Gucht, D. V., On the conditional independence implication problem: a lattice-theoretic approach, Artificial Intelligence, 202, 29-51 (2013) · Zbl 1329.68250
[27] Nyman, H.; Pensar, J.; Corander, J., Context-specific and local independence in Markovian dependence structures, (Abramsky, S.; Kontinen, J.; Väänänen, J.; Vollmer, H., Dependence Logic: Theory and Applications (2016), Springer International Publishing: Springer International Publishing Cham), 219-234 · Zbl 1429.62181
[28] Paolini, G., Independence logic and abstract independence relations, Math. Logic Q., 61, 3, 202-216 (2015) · Zbl 1360.03075
[29] Paolini, G.; Väänänen, J., Dependence logic in pregeometries and ω-stable theories, J. Symbolic Logic, 81, 1, 32-55 (2016) · Zbl 1368.03041
[30] Pearl, J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA
[31] Pensar, J.; Nyman, H. J.; Koski, T.; Corander, J., Labeled directed acyclic graphs: a generalization of context-specific independence in directed graphical models, Data Min. Knowl. Discov., 29, 2, 503-533 (2015) · Zbl 1403.68206
[32] Pensar, J.; Nyman, H.; Lintusaari, J.; Corander, J., The role of local partial independence in learning of Bayesian networks, Internat. J. Approx. Reason., 69, 91-105 (2016) · Zbl 1344.68192
[33] Poole, D.; Zhang, N. L., Exploiting contextual independence in probabilistic inference, J. Artificial Intelligence Res., 18, 263-313 (2003) · Zbl 1056.68144
[34] Studeny, M., Conditional independence relations have no finite complete characterization, (Kubik, S.; Visek, J., Transactions of the 11th Prague Conference vol. B, Information Theory, Statistical Decision Functions and Random Processes (1992), Kluwer: Kluwer Dordrecht-Boston-London), 377-396 · Zbl 0764.60004
[35] Väänänen, J., Dependence Logic: A New Approach to Independence Friendly Logic, London Mathematical Society Student Texts, vol. 70 (2007), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1117.03037
[36] Verma, T.; Pearl, J., Causal networks: semantics and expressiveness, (Shachter, R. D.; Levitt, T. S.; Kanal, L. N.; Lemmer, J. F., UAI ’88: Proceedings of the Fourth Annual Conference on Uncertainty in Artificial Intelligence. UAI ’88: Proceedings of the Fourth Annual Conference on Uncertainty in Artificial Intelligence, Minneapolis, MN, USA, July 10-12, 1988 (1988)), 69-78, North-Holland
[37] Wong, S.; Butz, C.; Wu, D., On the implication problem for probabilistic conditional independency, Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 30, 6, 785-805 (2000)
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.