R. R. Bouckaert, M. Studeny:
Racing for conditional independence inference.
In Symbolic and Quantitative Approaches to Reasoning with Uncertainty
(L. Godo ed.), Lecture Notes in Artificial Intelligence 3571,
Springer-Verlag, Berlin - Heidelberg 2005, pp. 221-232.
- Abstract
-
In this article, we consider the computational aspects of deciding
whether a conditional independence statement t is implied by a list
of conditional independence statements L using the implication related
to the method of structural imsets.
We present two methods which have the interesting complementary properties
that one method performs well to prove that t is implied by L, while the
other performs well to prove that t is not implied by L. However, both
methods do not perform well the opposite. This gives rise to a parallel
algorithm in which both methods race against each other in order to
determine effectively whether t is or is not implied.
Some empirical evidence is provided that suggest this racing algorithms
method performs a lot better than an existing method based on so-called
skeletal characterization of the respective implication.
Furthermore, the method is able to handle more than five variables.
- AMS classification 68T30
- Keywords
- conditional independence
- inference
- imset
- racing algorithms
- A
pdf version (256kB) is available.
The contribution builds on the ideas developed in the book:
- M. Studeny:
Probabilistic Conditional Independence Structures. Springer-Verlag, London, 2005.