Differential Message Importance Measure: A New Approach to the Required Sampling Number in Big Data Structure Characterization

Shanyun Liu, Rui She, Pingyi Fan

This paper, published in early 2018, introduces a novel information-theoretic framework for a classic problem: How many samples do you actually need to understand a big data structure? By moving beyond traditional entropy, the authors provide a new lens for looking at data collection and goodness-of-fit.

TL;DR

The authors propose the Differential Message Importance Measure (DMIM), a new metric for continuous variables that prioritizes rare but important events. By linking DMIM to the Kolmogorov-Smirnov statistic, they derive a distribution-free criterion to determine the optimal sampling size needed to characterize big data structures without wasting resources.

What Problem Does This Paper Address?

In the era of big data, we rarely process entire datasets; instead, we rely on sampling. This raises a fundamental "Goldilocks" problem:

  • Too many samples waste computational power, storage, and time.
  • Too few samples lead to biased models that fail to capture the true underlying distribution.

While tools like the Kolmogorov-Smirnov (K-S) test or Kullback-Leibler (KL) divergence exist to measure "goodness-of-fit," the authors argue these methods don't intuitively describe the process of information collection. They wanted a measure that reflects how the "importance" of the messages we receive changes as we collect more data, particularly in scenarios like intrusion detection where rare events (small probability) are the most critical.

Methods

The core contribution is the definition of Differential Message Importance Measure (DMIM).

  1. The Formula: Unlike Shannon entropy, which uses a logarithmic weight ($-\int f \log f$), DMIM uses an exponential weight: $$l(X) = \int_S f(x)e^{-f(x)} dx$$ This mathematical structure ensures that events with small probabilities are given higher "importance" labels.

  2. Analytical Extensions: The authors prove that DMIM can be expressed as an infinite series of Rényi Entropies.

  3. Approximations: Because the integral for DMIM is often difficult to solve analytically (especially for Normal distributions), the authors provide high-precision approximations for cases where the variance ($\sigma$) is either very large or very small.
  4. The Sampling Criterion: They define a relative importance $\gamma(n)$ for $n$ sample points. By analyzing how this value converges as $n \to \infty$, they establish a "DMIM deviation" ($\epsilon$) that dictates the gap between an empirical distribution and the true theoretical distribution.

Datasets

The paper is primarily theoretical and mathematical. To validate their theorems, the authors used synthetic datasets generated via Monte Carlo simulations. They tested their models against several standard probability distributions:

  • Normal (Gaussian)
  • Uniform
  • Exponential
  • Gamma
  • Beta
  • Laplace
  • Nakagami-m (used to simulate multipath fading in communications)

Key Insights and Ideas

  • The "Importance" Shift: DMIM is specifically designed for "small probability event" importance. In big data, the most common data points are often the least interesting; DMIM helps quantify the value of the outliers.
  • Diminishing Marginal Utility: The authors show that DMIM is bounded between 0 and 1. As you collect more samples, the "relative importance" increases rapidly at first and then levels off. This mirrors the real-world intuition that the 1,000th sample tells you much more about a distribution than the 1,000,000th sample.
  • Distribution-Free Sampling: One of the most powerful findings is that the required sample size $n$ can be determined based on the variance of the variable and the desired DMIM deviation, regardless of the specific shape of the distribution.
  • K-S Equivalence: They prove that the deviation of DMIM is mathematically equivalent to the Kolmogorov-Smirnov statistic, providing a bridge between classical statistics and information theory.

Key Results

  • Sampling Formula: The authors derived a concrete lower bound for the number of samples ($n$) required to reach a specific accuracy ($\epsilon$): $$n \geq \frac{1}{4\pi\sigma^2 \ln^2(1-\epsilon)}$$
  • Normal Distribution Accuracy: For Gaussian data, the approximation $\tilde{l}_2(X) = e^{-1/(2\sqrt{\pi}\sigma)}$ was shown to have a relative error of less than 1% when $\sigma > 1.25$.
  • Convergence: Simulations of the Nakagami-m distribution confirmed that as the DMIM deviation $\epsilon$ decreases (meaning more samples are taken), the empirical CDF (Cumulative Distribution Function) converges almost perfectly to the real CDF.

Limitations and Future Work

  • Univariate Focus: The current paper focuses on single random variables. While foundational, real-world big data is highly multivariate.
  • Joint DMIM: The authors explicitly mention that they intend to develop a "joint differential message importance measure" to handle multiple variables simultaneously.
  • Computational Complexity: While the approximations are fast, calculating the exact DMIM for complex, non-standard distributions in real-time remains a challenge.
  • Real-World Noise: The study assumes independent and identically distributed (i.i.d.) samples; future work could explore how DMIM performs with correlated data or non-stationary streams.

Summary updated

Abstract

The sample size is a fundamental problem in statistics, which also plays a very important role in data collection for big data scenario, especially in the characterization of data structure. This paper considers this problem from the perspective of message importance by transforming the sampling procedure into the process of collecting message importance. To this end, we define differential message importance measure (DMIM) as a measure of message importance for continuous random variable similar to differential entropy and calculate the DMIM for some common distributions. Based on DMIM, this paper proposes a new approach to the required sampling number, where the DMIM deviation is constructed to characterize the process of collecting message importance. In fact, the DMIM deviation is a new criterion to choose sample size to be large enough that the message importance of sample set differs from the whole message importance by no more than the specified amount. In order to visually display that the DMIM deviation can guarantee the statistical performance to some extent, we transformed the difference of message importance into the Kolmogorov-Smirnov statistic. Theoretical analyses and numerical results also demonstrate that the new approach is distribution-free and satisfies the Glivenko-Cantelli theorem, which agrees with the previous results in statistics. Moreover, the connection between message importance and distribution goodness-of-fit is established, which verifies that analyzing the data collection with taking message importance into account is feasible.
BibTeX
@inproceedings{liu2018differential,
  author = {Shanyun Liu and Rui She and Pingyi Fan},
  title = {{Differential Message Importance Measure: A New Approach to the Required Sampling Number in Big Data Structure Characterization}},
  booktitle = {IEEE Access},
  year = {2018},
  url = {https://openreview.net/forum?id=apuFAk3T410},
}

Loading related content...

Figure