Abstract

The concept of conditional independence has an important role in probabilistic reasoning, that is a branch of artificial intelligence where knowledge is modelled by means of a multidimensional finite-valued probability distribution. The probabilistic conditional independence structures are described by means of semigraphoids, that is the lists of conditional independence statements closed under four particular inference rules, which have at most two antecedents. It is known that every conditional independence model is a semigraphoid, but the converse is not true. In this paper, the semigraphoid closure of every couple of conditional independence statements is proved to be a conditional independence model. The substantial step to it is to show that every probabilistically sound inference rule for axiomatic characterization of conditional independence properties (= axiom), having at most two antecedents, is a consequence of the semigraphoid inference rules. Moreover, all potential dominant triplets of the mentioned semigraphoid closure are found.

AMS classification 62H05, 60A05, 68T30, 03B30

Keywords

probabilistic reasoning

(probabilistic) conditional independence

independency model

semigraphoid

inference rule

axiomatic characterization of conditional independence

A pdf version (440kB) is available.

The problem solved in the paper is motivated by the works:

• J. Pearl: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufman, San Mateo CA 1988.
• J. Pearl and A. Paz: Graphoids: a graph-based logic for reasoning about relevance relations. In Advances in Artificial Intelligence II (B. du Boulay, D. Hogg, and L. Steels eds.) , North-Holland, Amsterdam 1987, pp. 357-363.

It also partially builds on the works:

• M. Studeny: Conditional independence relations have no finite complete characterization. In Information Theory, Statistical Decision Functions and Random Processes. Transactions of the 11th Prague Conference vol. B (S. Kubik, J.A. Visek eds.), Kluwer, Dordrecht - Boston - London (also Academia, Prague) 1992, pp. 377-396.
• D. Geiger and J. Pearl: Logical and algorithmical properties of independence and their application to Bayesian networks. Annals of Mathematics and Artificial Intelligence 2 (1990), n. 1-4, pp. 165-178.