Empirical Evaluation of MDL
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.
a Belief Net is Consistent with Auxiliary Information
Russell Greiner, Chris Darken and Jie
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.
Russell Greiner and Chris Darken
Independence Structures and Graphical Models, Toronto, September
version (in preparation)
Return to Greiner's