A Robust Independence Test for ConstraintBased Learning of Causal Structure
Denver Dash, Marek Druzdzel
Abstract:
Constraintbased (CB) learning is a formalism for learning a causal network with a database D by performing a series of conditionalindependence tests to infer structural information. This paper considers a new test of independence that combines ideas from Bayesian learning, Bayesian network inference, and classical hypothesis testing to produce a more reliable and robust test. The new test can be calculated in the same asymptotic time and space required for the standard tests such as the chisquared test, but it allows the specification of a prior distribution over parameters and can be used when the database is incomplete. We prove that the test is correct, and we demonstrate empirically that, when used with a CB causal discovery algorithm with noninformative priors, it recovers structural features more reliably and it produces networks with smaller KLDivergence, especially as the number of nodes increases or the number of records decreases. Another benefit is the dramatic reduction in the probability that a CB algorithm will stall during the search, providing a remedy for an annoying problem plaguing CB learning when the database is small.
Keywords: Robust Independence Test Constraint Based Learning of Causal Structure
Pages: 167174
PS Link: null
PDF Link: /papers/03/p167dash.pdf
BibTex:
@INPROCEEDINGS{Dash03,
AUTHOR = "Denver Dash
and Marek Druzdzel",
TITLE = "A Robust Independence Test for ConstraintBased Learning of Causal Structure",
BOOKTITLE = "Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI03)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2003",
PAGES = "167174"
}

