A New MDL Measure for Robust Rule Induction

We present a generalization of a particular Minimum Description Length (MDL) measure that sofar has been used for pruning decision trees only. The generalized measure is applicable to (propositional) rule sets directly. Furthermore the new measure also does not suffer from problems reported for various MDL measures in the ML literature. The new measure is information-theoretically plausible and yet still simple and therefore efficiently computable. It is incorporated in a propositional Foil-like learner called Knopf. We report on favorable results in various purely symbolic propositional domains. Both rule quality in terms of simplicity (and syntactic closeness to the respective underlying theory where known) and predictive accuracy of induced theories are convincing. 1 Introduction The Minimum Description Length (MDL) Principle [Rissanen 78], sometimes also called the Minimum Message Length (MML) Principle, has been successfully applied in Machine Learning, both for inducing decisi..