26 May 2003, MDL and classification, revisited, Troy Lee

Abstract:
The Minimum Description Length (MDL) Principle is a powerful method for model selection. The theoretical development of MDL has mostly centered around probabilistic modeling. Yet practical applications of MDL often involve models which are best viewed as predictors rather than probability distributions. The standard example is classification, one of the most popular applications of MDL ever since its inception. MDL has been applied to such non-probabilistic models in various ways. We review these approaches and show that, contrary to what is often thought, they can exhibit some rather problematic behaviour: on the theoretical side, it is not known whether the resulting procedures are consistent (none of the existing proof techniques can be applied). On the practical side, the methods can behave quite unreasonably for small data samples. We analyze the reasons for this undesirable behaviour and propose a radical, general and surprising solution to the problem.