Racing algorithms for conditional independence inference

Remco Bouckaert

doi:10.1016/j.ijar.2006.06.018

2007-07-01

Remco Bouckaert *

Milan Studený

DOI：10.1016/j.ijar.2006.06.018

原文链接

查看原文

摘要

En 中文

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 I 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. (C) 2006 Elsevier Inc. All rights reserved.

Keyword:

conditional independence

inference

imset

algorithm