Amplifying Inter-Message Distance: On Information Divergence Measures in Big Data

Rui She, Shanyun Liu, Pingyi Fan

TL;DR

This paper introduces a new "Message Identification" (M-I) divergence, a parametric measure designed to better distinguish between probability distributions, especially in big data scenarios. They propose an efficient estimation algorithm and demonstrate its effectiveness in outlier detection, showing it can amplify differences between distributions more effectively than traditional measures like KL divergence.

What Problem Does This Paper Address?

In the era of big data, accurately measuring the "distance" or difference between probability distributions is crucial for various machine learning tasks like classification, clustering, and anomaly detection. While existing measures like Kullback-Leibler (KL) and Renyi divergence are widely used, they can sometimes struggle to clearly differentiate between similar distributions or may not optimally leverage the vast amounts of data available. The authors identify a need for a divergence measure that can not only quantify the difference between distributions but also actively "amplify" these differences, making it easier to detect subtle distinctions, particularly in the context of big data where computational efficiency and robust estimation are paramount.

Methods

The core of this paper is the introduction of a novel parametric M-I divergence. This divergence measure includes a tunable parameter that allows for the amplification of the information distance between distributions. The authors then delve into its theoretical properties, including non-negativity, monotonicity, convexity, and inequality relationships with existing divergences.

To address the challenge of estimating this divergence from big data, they propose a multidimensional kernel estimator with a weight window. This approach leverages kernel density estimation techniques adapted for discrete distributions and incorporates a smoothing parameter to optimize estimation. Building upon this, they introduce a weighted ensemble estimator for M-I divergence. This ensemble approach combines multiple estimators to improve robustness and convergence rates, specifically aiming to reduce the mean squared error (MSE) of the divergence estimation. Finally, they apply this framework to an outlier detection problem within a statistical sequence model.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and simulation-based evaluation using synthetic data generated according to specific distributions (e.g., binomial distributions for outlier detection).

Key Insights and Ideas

  • Parametric Amplification: The M-I divergence's key innovation is its tunable parameter, which can actively amplify the distance between distributions. This is crucial for distinguishing subtle differences, especially in noisy big data.
  • Improved Estimation Convergence: The proposed weighted ensemble kernel estimator significantly improves the convergence rate of the mean squared error for divergence estimation, from O(Γ<sup>-j/d</sup>) to O(Γ<sup>-1</sup>). This means the estimator becomes more accurate faster as more data (Γ) is available.
  • Outlier Detection Efficacy: The M-I divergence, particularly with the ensemble estimator, demonstrates superior performance in outlier detection compared to traditional measures like KL and Renyi divergence, highlighting its practical utility.
  • Theoretical Foundation: The paper provides a solid theoretical grounding for the M-I divergence, establishing its desirable properties like non-negativity and convexity, which are essential for its reliable application.

Key Results

  • The proposed M-I divergence is shown to be non-negative, monotonically non-decreasing with its parameter, and jointly convex.
  • The weighted ensemble kernel estimator for M-I divergence achieves a mean squared error convergence rate of O(Γ<sup>-1</sup>), a significant improvement over previous methods.
  • In outlier detection experiments, the M-I divergence, especially when estimated using the weighted ensemble method, consistently outperformed KL and Renyi divergences in terms of ROC curves, AUC, and F-score. This indicates its greater ability to distinguish between typical and outlier data sequences.

Limitations and Future Work

  • Parameter Selection: While the paper introduces a parametric divergence, a detailed method for optimal parameter selection for M-I divergence in various applications is suggested as future work.
  • Generalizability: The current work focuses on discrete distributions. Extending the M-I divergence and its estimation methods to continuous distributions would be a valuable next step.
  • Real-world Applications: While the paper demonstrates effectiveness in a simulated outlier detection scenario, further investigation into its application in diverse real-world big data problems (e.g., classification, clustering, anomaly detection in various domains) is warranted.
  • Computational Complexity: While the paper focuses on improving convergence rates, a detailed analysis of the computational complexity of the proposed algorithms for very large datasets would be beneficial.

Summary updated

Abstract

Message identification (M-I) divergence is an important measure of the information distance between probability distributions, similar to Kullback-Leibler (K-L) and Renyi divergence. In fact, M-I divergence with a variable parameter can make an effect on characterization of distinction between two distributions. Furthermore, by choosing an appropriate parameter of M-I divergence, it is possible to amplify the information distance between adjacent distributions while maintaining enough gap between two nonadjacent ones. Therefore, M-I divergence can play a vital role in distinguishing distributions more clearly. In this paper, we first define a parametric M-I divergence in the view of information theory and then present its major properties. In addition, we design a M-I divergence estimation algorithm by means of the ensemble estimator of the proposed weight kernel estimators, which can improve the convergence of mean squared error from O(Γ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-j/d</sup> ) to O(Γ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1</sup> ) (j ∈ (0, d]). We also discuss the decision with M-I divergence for clustering or classification, and investigate its performance in a statistical sequence model of big data for the outlier detection problem.
BibTeX
@inproceedings{she2017amplifying,
  author = {Rui She and Shanyun Liu and Pingyi Fan},
  title = {{Amplifying Inter-Message Distance: On Information Divergence Measures in Big Data}},
  booktitle = {IEEE Access},
  year = {2017},
  url = {https://openreview.net/forum?id=rxixy3zeOe},
}
Figure