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 BNstructures, 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