R. R. Bouckaert, M. Studeny:
Racing algorithms for conditional independence inference.
International Journal of Approximate Reasoning
45 (2007), n.2, pp. 386-401.
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 so-called skeletal characterization of the
respective implication. Furthermore, unlike previous methods, the
method is able to handle more than five variables.
- AMS classification 68T30
- conditional independence
- racing algorithms
scanned pdf copy (1112kB) is already open-access available.
The paper is an extended version of the conference paper:
The paper builds on the ideas developed in the book:
- 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.
- M. Studeny:
Probabilistic Conditional Independence Structures. Springer-Verlag, London, 2005.