Approximation Logics for Subclasses of Probabilistic Conditional Independence and Hierarchical Dependence on Incomplete Data

Sebastian Link ()
Additional contact information
Sebastian Link: The University of Auckland

A chapter in Dependence Logic, 2016, pp 183-217 from Springer

Abstract: Abstract Probabilistic conditional independence constitutes a principled approach to handle knowledge and uncertainty in artificial intelligence, and is fundamental in probability theory and multivariate statistics. Similarly, first-order hierarchical dependence provides an expressive framework to capture the semantics of an application domain within a database system, and is essential for the design of databases. For complete data it is well known that the implication problem associated with probabilistic conditional independence is not axiomatizable by a finite set of Horn rules (Studený, Conditional independence relations have no finite complete characterization. In: Kubik, S., Visek, J. (eds.) Transactions of the 11th Prague Conference on Information Theory, Statistical Decision Functions and Random Processes, pp. 377–396. Kluwer, Dordrecht, 1992), and the implication problem for first-order hierarchical dependence is undecidable (Herrmann, Inf. Comput. 122(2):221–235, 1995). Moreover, both implication problems do not coincide (Studený, Conditional independence relations have no finite complete characterization. In: Kubik, S., Visek, J. (eds.) Transactions of the 11th Prague Conference on Information Theory, Statistical Decision Functions and Random Processes, pp. 377–396. Kluwer, Dordrecht, 1992) and neither of them is equivalent to the implication problem of some fragment of Boolean propositional logic (Sagiv et al., J. ACM 28(3):435–453, 1981). In this article, generalized saturated conditional independence and full first-order hierarchical dependence over incomplete data are investigated as expressive subclasses of probabilistic conditional independence and first-order hierarchical dependence, respectively. The associated implication problems are axiomatized by a finite set of Horn rules, and both shown to coincide with that of a propositional fragment under interpretations in the well-known approximation logic $$\mathcal{S}$$ -3. Here, the propositional variables in the set $$\mathcal{S}$$ are interpreted classically, and correspond to random variables as well as attributes on which incomplete data is not permitted to occur.

Keywords: Probabilistic Conditional Independence; Hierarchical Dependencies; Implication Problem; Horn Rules; Boolean Propositional Logic (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-31803-5_9

Ordering information: This item can be ordered from
http://www.springer.com/9783319318035

DOI: 10.1007/978-3-319-31803-5_9

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().