R. R. Bouckaert, M. Studeny: Racing algorithms for conditional independence inference. International Journal of Approximate Reasoning 45 (2007), n.2, pp. 386-401.

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 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

Keywords
conditional independence
inference
imset
racing algorithms

A 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: