In this work, we address both the computational and modeling aspects
of Bayesian network structure learning. Several recent algorithms
can handle large networks by operating on the space of variable
orderings, but for technical reasons they cannot compute many
interesting structural features and require the use of a restrictive
prior. We introduce a novel MCMC method that utilizes the
deterministic output of the exact structure learning algorithm of
Koivisto and Sood to construct a fast-mixing proposal on the space
of DAGs. We show that in addition to fixing the order-space
algorithms' shortcomings, our method outperforms other existing
samplers on real datasets by delivering more accurate structure and
higher predictive likelihoods in less compute time. Next, we discuss
current models of intervention and propose a novel approach named
the uncertain intervention model, whereby the targets of an
intervention can be learned in parallel to the graph's causal
structure. We validate our model experimentally using synthetic data
generated from known ground truth. We then apply our model to two
biological datasets that have been previously analyzed using
Bayesian networks. On the T-cell dataset of Sachs et al. we show
that the uncertain intervention model is able to better model the
density of the data compared to previous techniques, while on the
ALL dataset of Yeoh et al. we demonstrate that our method can be
used to directly estimate the genetic effects of the disease.
Follow this link for software and documentation
- Daniel Eaton, Kevin Murphy (2007). Belief net structure learning from uncertain interventions. Journal of Machine Learning Research, Special Topic on Causality. Submitted, June 30, 2007.
- Daniel Eaton (2007). MSc thesis: Bayesian structure learning for the uncertain experimentalist. University of British Columbia, Department Computer Science.
- Daniel Eaton, Kevin Murphy (2007). Bayesian structure learning using dynamic programming and MCMC. UAI.
- Daniel Eaton, Kevin Murphy (2007). Exact Bayesian structure learning from uncertain interventions. AI & Statistics.
- Daniel Eaton, Kevin Murphy (2006). Bayesian structure learning using dynamic programming and MCMC. NIPS Workshop on Causality and Feature Selection.
July-21-2007. UAI talk (presented by Kevin Murphy). Paper [2774kB PDF]
June-30-2007. Submitted paper to JMLR, special issue on Causality.
June-18-2007. MSc thesis accepted by committee and faculty of graduate studies. MSc thesis [5674kB PDF]
June-11-2007. MSc thesis submitted to committee and defended.
May-4-2007. UAI paper accepted as a plenary talk.
March-22-2007. AIStats poster presented in Puerto Rico.
March-14-2007. Group meeting talk on UAI paper.
March-2-2007. Submitted a paper to UAI 2007. "Bayesian structure learning using dynamic programming and MCMC", a much-expanded/extended version of the NIPS Workshop paper.
Feb-9-2007. Missed the ICML submission deadline due to lackluster results.
Jan-15-2007. Happy NY! Resumed structure learning work after a month-long hiatus. Aiming for an ICML submission.
Dec-20-2006. AIStats paper accepted as a poster.
Dec-8-2006. Poster presented - Poster [7.3MB PDF], Paper [274kB PDF]
Nov-15-2006. NIPS Causality workshop paper accepted as a poster
Nov-11-2006. Submitted paper to NIPS 2006 Workshop on Causality and Feature Selection : "Bayesian structure learning using dynamic programming and MCMC"
Oct-31-2006. Group meeting presentation (ppt) on Koivisto/Sood algorithm
Oct-18-2006. Submitted paper to AI Stats 2007: "Exact Bayesian structure learning from uncertain interventions"
Oct-1-2006. Decided to do a paper using Koivisto
Sept-19-2006. Kevin's suggestion to do an AI Stats paper on structure learning