R. R. Bouckaert, M. Studeny:
Racing algorithms for conditional independence inference.
International Journal of Approximate Reasoning
45 (2007), n.2, pp. 386401.
 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
independence implication provided by the method of structural
imsets. We present two algorithmic 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 well perform 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 suggests this racing
algorithms method performs considerably better than an existing
method based on socalled skeletal characterization of the
respective implication. Furthermore, unlike previous methods, the
method is able to handle more than five variables.
 AMS classification 68T30
 Keywords
 conditional independence
 inference
 imset
 racing algorithms

A
scanned pdf copy (1112kB) is already openaccess available.
The paper is an extended version of the conference paper:
 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.
The paper builds on the ideas developed in the book:
 M. Studeny:
Probabilistic Conditional Independence Structures. SpringerVerlag, London, 2005.