M. Studeny: Description of structures of stochastic conditional independence by means of faces and imsets. (a series of 3 papers)
1st part: introduction and basic concepts. International Journal of General Systems 23 (1994), n. 2, p. 123-137.
2nd part: basic theory. International Journal of General Systems 23 (1995), n. 3, pp. 201-219.
3rd part: examples of use and appendices. International Journal of General Systems 23 (1995), n. 4, pp. 323-341.

Global abstract (for all three parts)
The work presents a new approach to the mathematical description of stochastic conditional independence structures among a finite number of random variables. The new approach is related to the classic approaches, that is to the use of directed acyclic graphs (probabilistic influence diagrams or Bayesian nets), undirected graphs (Markov nets) and dependency models (namely semigraphoids). The approach provides a deductive mechanism to infer probabilistically valid consequences of input affirmative information about conditional independence structure. This mechanism is much more powerful than the use of semigraphoids as it includes, from the classic point of view, an infinite number of inference rules. Nevertheless, from the theoretical point of view, it is finitely implementable. The developed theory is illustrated by examples showing how it is computer managable.

The series of papers is in principle self-contained, but several propositions have their proofs based on the results of the paper:
M. Studeny: Convex cones in finite-dimensional real vector spaces. Kybernetika 29 (1993), n. 2, pp. 180-200.

Abstract of the first part
The first part contains the Introduction in which the history of the description of conditional independence structures is recalled and the construction of the presented theory is explained by means of illustrative diagrams. Then basic concepts including the concept of imset are defined or recalled. Finally, several assertions concerning quasiorderings on imsets are presented.

Abstract of the second part
The central concept of face (with respect to an arbitrary continous linear ordering on imsets) and the corresponding deductive mechanism (facial implication) are introduced. The class of all faces constitutes a lattice which, in the case of a finitely established ordering, is shown to be finite. Moreover, the atoms and co-atoms of the lattice are characterized and two possible representations of faces are emphasized: by means of generating imsets and by means of portraits. Then a particular ordering, called the structural ordering, is studied. The class of faces with respect to this ordering is identified with a certain class of dependency models which includes all models of probabilistic conditional independence structures.

Abstract of the third part
This part contains several examples that indicate how to implement the facial deductive mechanism and show how to transform information about conditional independence structure given in the form of a dependency model, influence diagram, or Markov net into the form of an imset. Another example shows that the facial deductive mechanism is indeed more powerful than the semigraphoid one. A simple method of proving the probabilistic soundness of an inference rule is presented. The advantages of, disadvantages of, and prospects for the presented approach are discussed in the Conclusions. Two appendices contain some supplementary results about the structural ordering of imsets.

AMS classification 62H05, 68T30, 52B99, 94A17

conditional independence
structural ordering (imset, face)

A scanned pdf copy of the first part (925kB) is available.
A scanned pdf copy of the second part (1050kB) is available.
A scanned pdf copy of the third part (1048kB) is available.
Moreover, the content of the series of papers is covered by the DrSc thesis "On mathematical description of probabilistic conditional independence structures".