Robust independence testing for constraint-based learning of causal structure
Denver H. Dash, Marek J. Drużdżel · 2003
This paper considers a method that com-bines ideas from Bayesian learning, Bayesian network inference, and classical hypothesis testing to produce a more reliable and ro-bust test of independence for constraint-based (CB) learning of causal structure. Our method produces a smoothed contingency ta-ble NXY Z that can be used with any test of independence that relies on contingency ta-ble statistics. NXY Z can be calculated in the same asymptotic time and space required to calculate a standard contingency table, al-lows the specification of a prior distribution over parameters, and can be calculated when the database is incomplete. We provide the-oretical justification for the procedure, and with synthetic data we demonstrate its bene-fits empirically over both a CB algorithm us-ing the standard contingency table, and over a greedy Bayesian algorithm. We show that, even when used with noninformative priors, it results in better recovery of structural fea-tures and it produces networks with smaller KL-Divergence, especially as the number of nodes increases or the number of records de-creases. Another benefit is the dramatic re-duction in the probability that a CB algo-rithm will stall during the search, providing a remedy for an annoying problem plaguing CB learning when the database is small. 1