Descriptive Dimensionality and Its Characterization of MDL-based Learning and Change Detection
This work provides a foundational framework for analyzing MDL-based methods in machine learning, with potential applications in model selection and anomaly detection.
The paper introduces descriptive dimension (Ddim), a new information-theoretic measure of model dimensionality, and shows that it governs the convergence rate of MDL learning algorithms and error probabilities in change detection tasks.
This paper introduces a new notion of dimensionality of probabilistic models from an information-theoretic view point. We call it the "descriptive dimension"(Ddim). We show that Ddim coincides with the number of independent parameters for the parametric class, and can further be extended to real-valued dimensionality when a number of models are mixed. The paper then derives the rate of convergence of the MDL (Minimum Description Length) learning algorithm which outputs a normalized maximum likelihood (NML) distribution with model of the shortest NML codelength. The paper proves that the rate is governed by Ddim. The paper also derives error probabilities of the MDL-based test for multiple model change detection. It proves that they are also governed by Ddim. Through the analysis, we demonstrate that Ddim is an intrinsic quantity which characterizes the performance of the MDL-based learning and change detection.