A Short Introduction to Model Selection, Kolmogorov Complexity and Minimum Description Length (MDL)

2010/05/13 by Volker Nannen, Nannen, Volker
Computer Science · #Computability, Logic, AI Algorithms #Evolutionary Algorithms and Applications #AI-based Problem Solving and Planning

paper · pdf · doi:10.48550/arxiv.1005.2364

Abstract

The concept of overfitting in model selection is explained and demonstrated with an example. After providing some background information on information theory and Kolmogorov complexity, we provide a short explanation of Minimum Description Length and error minimization. We conclude with a discussion of the typical features of overfitting in model selection.

Citations

• On Computable Numbers, with an Application to the Entscheidungsproblem

Related

• Applying MDL to Learning Best Model Granularity
• Minimum Encoding Approaches for Predictive Modeling
• A tutorial introduction to the minimum description length principle
• Kolmogorov's Structure Functions and Model Selection
• Revisiting minimum description length complexity in overparameterized models