Revisiting Probability Distribution Assumptions for Information Theoretic Feature Selection

Yuan Sun, Wei Wang, Michael Kirley, Xiaodong Li, Jeffrey Chan

Abstract

Information-theoretic feature selection often relies on low-order approximations of Mutual Information (MI) to bypass the curse of dimensionality. These approximations are rooted in implicit probability distribution assumptions. This paper identifies a critical normalization flaw in the widely used Geometric Mean Distribution (GMD) assumption and proposes the Arithmetic Mean Distribution (AMD) as a mathematically sound alternative. Evaluation across 29 datasets demonstrates that AMD-based methods consistently outperform traditional Feature Independence Distribution (FID) and GMD-based approaches in classification accuracy.

Introduction

In machine learning, feature selection is essential for enhancing model efficiency and interpretability. Mutual Information (MI) serves as a robust metric for measuring statistical dependence between features and class labels. However, calculating MI for high-dimensional data is computationally prohibitive due to the "curse of dimensionality," requiring the estimation of joint probability densities that grow exponentially with the number of features.

To address this, researchers employ low-order approximations that analyze features in small groups. While effective, these methods rest on implicit assumptions regarding the underlying probability distributions. This research evaluates the realism of these assumptions and their impact on classifier accuracy.

Theoretical Framework and Methods

The study categorizes feature selection methods into three primary distribution assumption families:

  1. Feature Independence Distribution (FID): Assumes features are independent, simplifying computation but often failing to capture real-world complexities. It underlies algorithms such as MIM and MIFS.
  2. Geometric Mean Distribution (GMD): A more flexible assumption using the geometric mean of conditional densities. Popular methods like mRMR and JMI are based on GMD. However, GMD densities often fail to normalize (sum to 1), leading to biased or negative MI values.
  3. Arithmetic Mean Distribution (AMD): The proposed alternative. By utilizing the arithmetic mean of conditional densities, AMD maintains the flexibility of GMD while ensuring mathematical soundness through consistent normalization.
Mapping of information-theoretic objective functions to distribution assumptions and existing literature.

The authors demonstrate a "Unified Theory of Feature Selection," showing that many disparate algorithms are actually variations of the same GMD assumption, differing only in the interaction order ($k$) considered.

Experimental Evaluation

The proposed AMD framework was tested against 29 real-world datasets from the UCI Machine Learning Repository, spanning biological data, image processing, and general classification tasks. Feature counts ranged from 13 to nearly 10,000.

Performance was measured using K-Nearest Neighbor (KNN) and Support Vector Machine (SVM) classifiers. The key findings include:

  • AMD Superiority: Methods utilizing the AMD assumption consistently achieved the best average rankings in classification accuracy across both MI and Variational Information (VI) frameworks.
  • Normalization Impact: The discovery of the normalization flaw in GMD-based methods (like mRMR) explains why they may underestimate total probability and skew feature rankings. AMD fixes this theoretical gap.
  • State-of-the-Art Comparison: AMD-based methods outperformed modern techniques such as MRI, SPEC, and CMIM.
Average ranking of FID, GMD, and AMD assumptions across 29 datasets for SVM and KNN classifiers. Lower ranks indicate better performance.

Conclusion

The Arithmetic Mean Distribution (AMD) provides a robust, normalized alternative to traditional distribution assumptions in information-theoretic feature selection. While higher-order interactions ($k$) improve performance, they increase computational complexity. Future work will focus on exploring more sophisticated distribution relaxations that balance complexity with the ability to capture intricate feature dependencies.

Summary updated

Abstract

Feature selection has been shown to be beneficial for many data mining and machine learning tasks, especially for big data analytics. Mutual Information (MI) is a well-known information-theoretic approach used to evaluate the relevance of feature subsets and class labels. However, estimating high-dimensional MI poses significant challenges. Consequently, a great deal of research has focused on using low-order MI approximations or computing a lower bound on MI called Variational Information (VI). These methods often require certain assumptions made on the probability distributions of features such that these distributions are realistic yet tractable to compute. In this paper, we reveal two sets of distribution assumptions underlying many MI and VI based methods: Feature Independence Distribution and Geometric Mean Distribution. We systematically analyze their strengths and weaknesses and propose a logical extension called Arithmetic Mean Distribution, which leads to an unbiased and normalised estimation of probability densities. We conduct detailed empirical studies across a suite of 29 real-world classification problems and illustrate improved prediction accuracy of our methods based on the identification of more informative features, thus providing support for our theoretical findings.
BibTeX
@inproceedings{sun2020revisiting,
  author = {Yuan Sun and Wei Wang and Michael Kirley and Xiaodong Li and Jeffrey Chan},
  title = {{Revisiting Probability Distribution Assumptions for Information Theoretic Feature Selection}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i04.6050},
}
Figure