From awodey@andrew.cmu.edu Mon Apr 30 00:21:22 2007 Date: Mon, 30 Apr 2007 00:21:26 -0400 From: Steve Awodey To: +dist+/afs/andrew.cmu.edu/usr18/awodey/dl/coll.dl@andrew.cmu.edu Subject: Philosophy Colloquium: Schulte ************************************************************ Philosophy Department Colloquium Carnegie Mellon University ************************************************************ "Learning Bayes Nets Based on Conditional Dependencies" Oliver Schulte Simon Fraser University Vancouver, Canada 4:30 PM Thursday, May 3 Baker Hall A53 **Reception at 4 in BH 135** Abstract: Constraint-based methods for learning Bayes nets typically rely on a statistical test to infer both conditional dependencies and independencies. In a 2004 paper, Kelly and Glymour proposed learning Bayes nets based on conditional {\em dependencies} alone. We develop this idea in two ways. 1. A new hybrid learning criterion combines dependency constraints with a model selection criterion: Search for a structure G that maximizes the score S, given the constraint that the structure must entail the observed dependencies. Simulation studies with GES and the BDeu scoring function provide evidence that the additional dependency information leads to an improved structure on small to medium sample sizes (e.g. $< 10^4$ data points with 10 variables). 2. We analyze a Bayes net learning model in which the learner receives an increasing sequence of conditional dependencies true in the underlying graph structure; in the limit the sequence is a complete enumeration of the true conditional dependencies. Standard learning-theoretic criteria determine a unique optimal method, which we show outputs graph structures that entail the observed dependencies with a minimum number of edges. Implementing this method is NP-hard (assuming that P = RP). The heuristic procedure considered in part 1 can be seen as an approximation of the learning-theoretically optimal method. Joint work with Wei Luo (Simon Fraser University) and Russ Greiner (University of Alberta) ********************************************************* Oliver Schulte is Professor of Philosophy at Simon Fraser University. He earned his PhD from the CMU Philosophy Department in 1997. ********************************************************* Colloquium information: http://www.andrew.cmu.edu/~awodey/colloquium/talks.htm ------------------------------------------------------ For further information, contact Steve Awodey. Email:  awodey@cmu.edu Phone: (412) 268-8947