Abstract
Traditional histogram construction often relies on fixed-width bins, which can lead to either oversmoothing or excessive noise. This paper introduces a principled approach to density estimation using variable-width histograms based on the Minimum Description Length (MDL) principle. By framing histogram construction as a data compression problem and utilizing the Normalized Maximum Likelihood (NML) distribution, the authors provide a mathematically rigorous method for optimal bin selection. We demonstrate that this approach effectively captures complex data distributions and converges rapidly to the true density as sample sizes increase.
Introduction: The Regularity Trap
Histograms are fundamental tools for data visualization and density estimation. However, standard implementations typically employ equal-width bins, creating a "Goldilocks" dilemma. In datasets featuring both flat regions and sharp peaks, a regular histogram must choose between blurring significant features (too few bins) or introducing spurious noise in sparse regions (too many bins).
To overcome these limitations, irregular histograms with variable-width bins are required. The challenge lies in the search space: identifying the optimal number and location of bin edges (cut points) among many candidates is computationally expensive. Furthermore, a robust criterion is needed to prevent overfitting when the number of parameters (bins) is not fixed.
Methodology: Compression as Learning
The authors propose a model selection framework rooted in the Minimum Description Length (MDL) principle. The core insight is that the model which compresses the data most efficiently is the one that has best captured its underlying structure.
The NML Criterion
The method utilizes the Normalized Maximum Likelihood (NML) distribution. Unlike Bayesian approaches, NML does not require a prior distribution and is "minimax optimal," providing the shortest possible code length for the data. A significant contribution of this work is the efficient calculation of "parametric complexity"—a typically difficult normalizing constant. The authors demonstrate that for histograms, this complexity is equivalent to a multinomial model, allowing for a fast, linear-time recursive calculation.
Dynamic Programming Search
To navigate the exponential search space of potential bin configurations, the authors employ a Dynamic Programming (DP) algorithm. By decomposing the problem into optimal $K$-bin sub-problems for subsets of the data, the search complexity is reduced to $O(E^2 \cdot K_{max})$, where $E$ is the number of candidate cut points. This ensures that the globally optimal irregular histogram can be found in polynomial time.
Experimental Evaluation
The method was tested on synthetic Gaussian finite mixtures (gm2, gm5, gm6, and gm8) to compare estimated densities against known ground truths.
Visual Accuracy and Robustness
The algorithm demonstrates a remarkable ability to place narrow bins in high-density regions while maintaining wide bins in the tails. Notably, the method exhibits strong small sample robustness. As shown in Figure 1, even with only 100 data points, the MDL criterion selects a simple, conservative model rather than overfitting to local noise.
Quantitative Convergence
The performance was quantified using the Hellinger distance, which measures the difference between the estimated and true probability distributions. The results indicate that NML-optimal histograms converge rapidly toward the true density as the sample size $N$ increases across all tested mixture models.
Discussion and Future Work
The MDL-based approach provides a data-driven, parameter-free method for histogram construction that naturally protects against overfitting. While the current DP algorithm is efficient, future work may explore scaling to even larger datasets by optimizing candidate point selection. Additionally, these histograms could significantly improve the performance of Naive Bayes classifiers by providing more accurate discretization of continuous features.
Summary updated