Focusing on a probability element: Parameter selection of message importance measure in big data

Rui She, Shanyun Liu, Yunquan Dong, Pingyi Fan

TL;DR

This paper introduces a refined method for tuning the Message Importance Measure (MIM), an information-theoretic tool designed specifically to highlight rare events in big data. By setting the importance coefficient as the reciprocal of a target probability, researchers can "zoom in" on specific anomalies, making MIM a more surgical tool for fraud and intrusion detection than traditional Shannon entropy.

What Problem Does This Paper Address?

In the world of Big Data, we are often looking for a needle in a haystack—think of a single fraudulent credit card transaction among millions of legitimate ones, or a subtle sign of a network intrusion. Traditional information theory measures, like Shannon entropy, are designed to characterize the entire distribution, effectively focusing on the "majority" subsets.

While previous work introduced the Message Importance Measure (MIM) to target minority subsets, the selection of its parameters was often imprecise. Specifically, older methods tended to focus only on the event with the absolute minimum probability, ignoring other significant but rare anomalies. This paper seeks to provide a rigorous mathematical framework for selecting MIM parameters that can focus on any specific probability element of interest.

Methods

The core of the paper revolves around the Parametric MIM, defined as: $$L(\mathbf{p}, \varpi) = \log \sum_{i=1}^{n} p_i e^{\varpi(1-p_i)}$$ where $\varpi$ is the importance coefficient. The authors propose several key methodological advancements:

  1. Reciprocal Parameter Selection: They define a functional relationship where the importance coefficient $\varpi_j$ is set to $1/p_j$. This ensures that the probability element $p_j$ becomes the "Principal Component" of the measure.
  2. Optimization via KKT Conditions: For scenarios where the exact probability of an anomaly isn't known but a range is suspected (prior probability), the authors use Karush-Kuhn-Tucker (KKT) conditions to find an optimal $\varpi^*$ that maximizes the measure's sensitivity.
  3. Statistical Convergence Analysis: Using the Law of Large Numbers and the Central Limit Theorem, the authors model how this measure behaves as more data is collected, proving that the empirical MIM converges even when the data is noisy.

Datasets

The paper is primarily theoretical and uses synthetic statistical distributions to validate its mathematical properties rather than specific real-world "big data" repositories. The distributions used for evaluation include:

  • Binomial Distribution
  • Poisson Distribution
  • Geometric Distribution
  • Normal (Gaussian) Distribution
  • Rayleigh Distribution
  • Uniform Distribution (used as a baseline for comparison)

Key Insights and Ideas

  • The "Focus" Effect: By choosing $\varpi = 1/p_j$, the term associated with $p_j$ in the MIM equation dominates the sum. This allows a practitioner to effectively "ignore" the background noise of frequent events and amplify the signal of a specific rare event.
  • Monotonicity: The authors prove a "Chain Rule" for MIM, showing that as the importance coefficient increases, the overall measure increases. This provides a predictable "volume knob" for importance.
  • Sensitivity to Non-Uniformity: Unlike Shannon entropy, which is maximized by a uniform distribution, MIM (when focused on rare events) is significantly higher for skewed distributions. This makes it much better at flagging "unusual" states in a system.
  • Robustness to Noise: The analysis shows that while small-probability events cause fluctuations in empirical data, the expected value of the MIM remains a stable and reliable indicator for anomaly detection as the sample size grows.

Key Results

  • Analytical Solution for $\varpi^*$: The authors derived a specific Taylor expansion to approximate the optimal importance coefficient for binary distributions, providing a practical formula for engineers to use.
  • Numerical Validation: Plots (Figures 2 and 3 in the paper) demonstrate that for Poisson and Geometric distributions, the operational MIM is significantly higher than for a uniform distribution when focusing on rare elements.
  • Property Verification: The paper successfully proves four major properties of the parametric MIM, including the "Principal Component" property, which mathematically guarantees that the chosen probability element will dictate the measure's behavior.

Limitations and Future Work

  • Prior Knowledge Dependency: The method works best when you have an idea of the probability range of the anomalies you are looking for. If the "target" probability is completely unknown, selecting the initial $\varpi$ remains a challenge.
  • Computational Complexity: While the math is elegant, calculating exponential sums over massive datasets can be computationally intensive compared to simpler heuristics.
  • Future Directions: The authors suggest that the next step is to design specific, high-efficiency algorithms that implement this parametric MIM for real-time anomaly detection in complex, high-dimensional big data environments.

Summary updated

Abstract

Message importance measure (MIM) is applicable to characterize the importance of information in the scenario of big data, similar to entropy in information theory. In fact, MIM with a variable parameter can make an effect on the characterization of distribution. Furthermore, by choosing an appropriate parameter of MIM, it is possible to emphasize the message importance of a certain probability element in a distribution. Therefore, parametric MIM can play a vital role in anomaly detection of big data by focusing on probability of an anomalous event. In this paper, we propose a parameter selection method of MIM focusing on a probability element and then present its major properties. In addition, we discuss the parameter selection with prior probability, and investigate the availability in a statistical processing model of big data for anomaly detection problem.
BibTeX
@inproceedings{she2017focusing,
  author = {Rui She and Shanyun Liu and Yunquan Dong and Pingyi Fan},
  title = {{Focusing on a probability element: Parameter selection of message importance measure in big data}},
  booktitle = {ICC},
  year = {2017},
  url = {https://openreview.net/forum?id=XB0H7lCZ12},
}

Loading related content...

Figure