Earlier Ideas

Empirical Evaluation of MDL

An Empirical Investigation of the MDL Principle

Tim Van Allen, Chris Dutchyn and Russell Greiner

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.

Determining whether a Belief Net is Consistent with Auxiliary Information

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

Russell Greiner, Chris Darken and Jie Cheng

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

Russell Greiner and Chris Darken

Conditional Independence Structures and Graphical Models,  Toronto, September 1999.

Longer version (in preparation)

Return to Greiner's home page