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

2010/05/13 by Volker Nannen, Nannen, Volker · 3 citations
Computer Science · Mathematics · #AI-based Problem Solving and Planning #Algorithm #Artificial intelligence #Artificial neural network #Computability, Logic, AI Algorithms #Computer science #Evolutionary Algorithms and Applications #Kolmogorov complexity #Machine learning #Mathematical optimization #Mathematics #Minification #Minimum description length #Model selection #Overfitting #Selection (genetic algorithm) #cs.CC #cs.LG #msc:F.2.3

paper · pdf · doi:10.48550/arxiv.1005.2364

published in arXiv (Cornell University) (Cornell University) · 20 pages, Chapter 1 of The Paradox of Overfitting, Master's thesis, Rijksuniversiteit Groningen, 2003

openalex publication_date 2010/05/13 · arxiv created 2010/05/14 · arxiv updated 2010/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

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

Cited by

• General Mathematical Proof of Occam's Razor; Upgrading Theoretical Physicists' Methodology

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