Earlier Ideas

An Empirical Investigation of the MDL Principle

This paper provides an empirical exploration of the ``minimum description length'' (MDL) principle, in the context of learning Bayesian belief nets (BNs). In one set of experiments, with relatively few variables, we comprehensively constructed the entire set of BN-structures, while in other tests, dealing with larger sets of variables, we carefully subsampled the space of structures. In each situation, we compared the BN with the smallest MDL score to various other BNs, including the ``fully independent'', ``complete'', and Chow Liu networks, to see which had the best ``true likelihood'' score, over the entire distribution of tuples. Our findings partially characterize when MDL is an appropriate heuristic, and when it is not.

How an Expert can use Imperfect Knowledge to Improve an Imperfect Theory

Proceedings of the Seventeenth Conference on UNcertainty in Artificial Intelligence (UAI-01), Seattle, August 2001

This report addresses the challenge of using auxiliary information I_A to improve a given theory, encoded as a belief net B_E. In contrast with many other ``knowledge revision'' systems, we deal with the situation where this I_A may be imperfect, which means B_E should not necessarily incorporate that information. Instead, we provide tools to help the expert decide how to use I_A. After providing objective criteria for measuring how much I_A differs from B_E, we discuss ways to evaluate whether this difference is statistically significant. We then provide tools to isolate the differences --- to tell the domain expert which parts of the belief net (eg, which links, and/or which nodes) account for the discrepancy.

​Two of our tools involve techniques that are of independent interest: viz., the use of a non-central chi^2-test to compute the relative likelihood of two similar belief nets, and a sensitivity analysis that provides the ``error-bars'' around the answers returned by a belief net, as a function of the samples used to learn it.

Determining whether a Belief Net is Consistent with Auxiliary Information

Proceedings of the Seventeenth Conference on UNcertainty in Artificial Intelligence (UAI-01), Seattle, August 2001

Conditional Independence Structures and Graphical Models, Toronto, September 1999