Semigraphoids and structures of probabilistic conditional independence.
Annals of Mathematics and Artificial Intelligence
21 (1997), n. 1, pp. 71-98.
- 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
- probabilistic reasoning
- (probabilistic) conditional independence
- independency model
- inference rule
- axiomatic characterization of conditional independence
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.