On mathematical description of probabilistic conditional independence
thesis for DrSc degree, Institute of Information Thoery and Automation,
Academy of Sciences of the Czech Republic, Prague, May 2001, 192 pages.
The first chapter of the thesis is a motivation account. The
second chapter is an overview of basic definitions, tools and
results concerning the concept of probabilistic conditional
independence (CI). The third chapter is an overview of graphical
methods for description of probabilistic CI structures which use
graphs whose nodes correspond to single random variables. The
emphasis is put on classic approaches which use undirected graphs,
acyclic directed graphs and chain graphs but advanced graphical
methods developed in last six years of 20-th century are mentioned
as well. Since graphical methods cannot solve satisfactorily an
important theoretical question of completeness a non-graphical method
of description of probabilistic CI structures which solves this
problem is proposed in the remaining chapters. The method uses
certain integer-valued functions on the power set of the set of
variables called structural imsets and is safely applicable
to the description of CI structures induced by probability
measures with finite multiinformation, in particular structures
induced by discrete measures, by non-degenerate Gaussian
measures and by conditional Gaussian measures. The notion of
structural imset is introduced in the fourth chapter where it is
shown that three ways of relating structural imsets to probability
measures are equivalent. In particular, Markov condition is
equivalent to a certain product formula. The fifth chapter
introduces another way of description of probabilistic CI
structures, namely by means of supermodular functions. It is
shown that the class of structural models, that is models
which can be described by structural imsets, coincides with the
class of models which can be described by supermodular functions.
The relation of both ways of description of structural models is
lucidly interpreted as a duality relation in terms of an algebraic
concept of Galois connection. Atoms and coatoms of the lattice of
structural models are characterized and the lattice is shown to be both
atomistic and coatomistic finite lattice.
The sixth chapter is devoted to relevant implication between structural
imsets called facial implication. Two characterizations of facial
implication are given and some theoretical questions related to computer
implementation of facial implication are solved. Moreover, a
method of adaptation of the proposed method to a specific
distribution framework is outlined. The seventh chapter deals with
the problem of choice of a suitable representative of a class of
(facially) equivalent structural imsets and gives some formulas
for 'translation' of basic graphical models into structural
imsets. The eighth chapter is an overview of open problems to be
studied in order to tackle with practical questions. The Appendix
is an overview of concepts and facts which are supposed to be
elementary and can be omitted by an advanced reader.
- AMS classification 62H05, 60A05, 68T30
- (probabilistic) conditional independence structures
- graphical models
- multinformation function
- structural imsets
- supermodular functions
- facial implication
- facial and Markov equivalence
pdf copy (converted postscript version) (1439kB) is available.
WARNING: the file is very long, it has 192 pages and contains
some colorful pictures.
The thesis presents in a compact updated form a mathematical
method developed in the following earlier papers:
- M. Studeny:
International Journal of General
Systems 22 (1994), n. 2, pp. 207-217.
- M. Studeny:
Description of structures of stochastic conditional independence
by means of faces and imsets. (a series of 3 papers)
introduction and basic concepts. International Journal of General
Systems 23 (1994), n. 2, p. 123-137.
basic theory. International Journal of General Systems 23
(1995), n. 3, pp. 201-219.
examples of use and appendices. International Journal
of General Systems 23 (1995), n. 4, pp. 323-341.
Nevertheless, the content of the series of papers is covered by the thesis.
- M. Studeny:
Description of conditional independence structures by means of imsets:
a connection with product formula validity. In Uncertainty in
Intelligent Systems (B. Bouchon-Meunier, L. Valverde,
R.R. Yager eds.) North-Holland, Amsterdam - London - New York -
Tokyo 1993, pp. 179-194.
- M. Studeny, R.R. Bouckaert, T. Kocka:
Extreme supermodular set functions over five variables.
Research report n. 1977, Institute of Information Theory and Automation,
Prague, January 2000 (32 pages).
Moreover, the result of the work is also an
electronic catalogue of representatives extreme supermodular set functions
over five variables.