M. Studeny:
Semigraphoids and structures of probabilistic conditional independence.
Annals of Mathematics and Artificial Intelligence
21 (1997), n. 1, pp. 7198.
 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 finitevalued
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 graphbased logic for reasoning about relevance
relations. In Advances in Artificial Intelligence II
(B. du Boulay, D. Hogg, and L. Steels eds.) ,
NorthHolland, Amsterdam 1987, pp. 357363.
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. 377396.
 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. 14, pp. 165178.