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,
SpringerVerlag, Berlin  Heidelberg 2005, pp. 221232.
 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 socalled
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. SpringerVerlag, London, 2005.