Law recognition via histogram-based estimation

Guilhem Coq, X. Li, Olivier Alata, Yannis Pousset, Christian OlivierICASSP 2009 · OpenReview

Abstract

In this paper, we study the problem of recognizing an unknown probability density function from one of its sample which is of interest in signal and image processing or telecommunication applications. By opposition with the classical Kolmogorov-Smirnov method based on empirical cumulative functions, we consider histogram estimators of the density itself built from our data. Those histograms are generated via model selection, more specifically via a codelength-based information criterion. From the histograms, we may compute a Kullback-Leibler distance to any theoretical law which is used to complete the recognition. We apply this histogram-based method for law recognition in a theoretical setup where the true density is known as well as in a real setup where data come from radio channel propagation experimentation.

Introduction

Identifying the underlying probability distribution (or "law") of a dataset is a fundamental task in signal processing and telecommunications. For instance, determining whether radio interference follows a Rayleigh, Nakagami, or Weibull distribution is critical for system design. While the Kolmogorov-Smirnov (KS) test is the standard tool for this, it relies on empirical cumulative functions and can be sensitive to noise. This paper proposes an alternative: estimating the probability density function (PDF) directly using optimized histograms and performing recognition via Kullback-Leibler (KL) divergence.

Methodology: Information-Theoretic Histogram Selection

The primary challenge in histogram-based estimation is bin selection. Too many bins lead to overfitting (noise), while too few lead to underfitting (loss of detail). The authors address this using the Minimum Description Length (MDL) principle, treating histogram selection as a data compression problem.

The Information Criterion (CRIT)

A mathematical criterion is derived to minimize the total "codelength" required to describe the data. This involves balancing the cost of identifying which bin each data point belongs to against the cost of specifying the point's exact location within its bin. The optimal histogram minimizes this criterion. The authors compare regular histograms (fixed bin widths) and dynamic histograms (variable bin widths optimized via dynamic programming).

Recognition via KL Divergence

Once the optimal histogram is constructed, recognition is performed by calculating the KL distance between the estimated histogram and a set of candidate theoretical distributions. The distribution with the minimum distance is selected as the best fit.

Experimental Setup

The method was validated using both synthetic and real-world datasets. Synthetic data involved samples of varying sizes ($n=100$ to $3000$) generated from known distributions. Real-world validation used simulated signal attenuation for a radio channel in both Line of Sight (LOS) and Non-Line of Sight (NLOS) environments.

Simulated radio channel environment showing transmitter and receiver positions for LOS and NLOS scenarios.

Results and Discussion

The experimental results demonstrate that the histogram-based approach, particularly using dynamic binning, offers significant advantages over traditional methods.

Performance Comparison

As shown in the figure below, the "KL Dynamic" method consistently achieves a higher recognition rate (RR) than the KS test across various sample sizes. Interestingly, the optimized histograms typically use fewer than 50 bins, suggesting that the MDL-based binning acts as a natural noise filter. While finding the optimal dynamic histogram requires $O(R^2)$ operations, the gain in accuracy justifies the computational cost for these applications.

Recognition Rate (RR) comparison between histogram-based KL methods and the Kolmogorov-Smirnov (KS) test.

Real-World Application

In the radio propagation setup, the method correctly identified the Weibull distribution as the optimal fit for LOS scenarios, consistent with physical propagation models. The study also highlighted that "standard" empirical histograms (using rules of thumb) perform poorly, emphasizing the necessity of the optimization step.

Conclusion

This paper demonstrates that information-theoretic histogram estimation is a powerful alternative to the KS test for law recognition. By optimizing bin widths through the MDL principle, the method provides a more robust and accurate identification of underlying probability distributions in both theoretical and practical signal processing applications.

Summary updated

Abstract

In this paper, we study the problem of recognizing an unknown probability density function from one of its sample which is of interest in signal and image processing or telecommunication applications. By opposition with the classical Kolmogorov-Smirnov method based on empirical cumulative functions, we consider histogram estimators of the density itself built from our data. Those histograms are generated via model selection, more specifically via a codelength-based information criterion. From the histograms, we may compute a Kullback-Leibler distance to any theoretical law which is used to complete the recognition. We apply this histogram-based method for law recognition in a theoretical setup where the true density is known as well as in a real setup where data come from radio channel propagation experimentation.
BibTeX
@inproceedings{coq2009law,
  author = {Guilhem Coq and X. Li and Olivier Alata and Yannis Pousset and Christian Olivier},
  title = {{Law recognition via histogram-based estimation}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2009},
  url = {https://openreview.net/forum?id=TYrxuOR64i},
}

Loading related content...

Figure