Ideal MDL and Its Relation To Bayesianism

: Statistics based inference methods like minimum message length (MML) and minimum description length (MDL), are widely applied approaches. They are the tools to use with particular machine learning praxis such as simulated annealing, genetic algorithms, genetic programming, artificial neural networks, and the like. These methods select the hypothesis which minimizes the sum of the length of the description of the hypothesis (also called `model') and the length of the description of the data relative to the hypothesis. Ideally, MDL uses shortest effective descriptions and is expressed in terms of Kolmogorov complexity. We derive Ideal MDL from first principles and explain correspondences and differences between MDL and Bayesian reasoning, and in particular why the latter is prone to overfitting and the former isn't. In particular we show that Ideal MDL can be reduced to the Bayesian approach using the universal prior distribution, provided the minimum description length is reached for ..