A Geometric Theory of Feature Selection and Distance-Based Measures

Kilho Shin, Adrian Pino AnguloIJCAI 2015

Introduction

Feature selection is a fundamental process in machine learning, identifying the optimal subset of attributes to determine a target class. While often conceptualized as a "distance" to an ideal feature set, this interpretation has historically remained metaphorical. This paper establishes a rigorous geometric theory by mapping feature sets into a universal $L^p$ metric space. A key contribution is the proof that the standard Bayesian risk is a specific case ($p=1$) of a broader family of distance-based measures, and that higher values of $p$ yield metrics with significantly better correlation to classification performance.

Theoretical Framework: Mapping Features to Geometry

The proposed framework projects feature sets from any dataset into a shared metric space through several key steps:

  1. Coherent Mappings: Defining requirements like naming and localization invariance to ensure mathematically sound comparisons across disparate datasets.
  2. $L^p$ Space Projection: Representing feature sets as points within a subspace of an $L^p$ metric space.
  3. Quotient Spaces: Utilizing quotient spaces to treat equivalent data representations (e.g., permuted class labels) as single points.
  4. Distance-to-Consistency: Defining the metric $\widehat{\mu}_{\ell^p}$ as the shortest distance from a feature set's projection to the region of "perfectly consistent" sets.
Geometric projection of feature sets into a universal metric space.

The authors demonstrate that for $p=1$, this geometric distance $\widehat{\mu}_{\ell^1}$ is mathematically identical to the Bayesian risk (inconsistency rate). This provides a novel geometric foundation for one of the most widely used tools in the field.

Experimental Evaluation

The theory was validated using 12 UCI datasets spanning medical, image processing, and general classification domains. The researchers evaluated the distance-to-consistency measure $\widehat{\mu}_{\ell^p}$ for $p \in \{1, 2, 3, 4, 5\}$ against the AUC-ROC performance of three distinct classifiers: Naïve Bayes, C4.5 decision trees, and Support Vector Machines (SVM).

Results and Insights

The empirical results confirm that $p > 1$ measures offer superior properties for feature selection.

  • Enhanced Correlation: As $p$ increases, the negative correlation between the geometric distance and classification accuracy strengthens. This indicates that $L^p$ distances for $p > 1$ are more reliable indicators of classifier performance than the traditional $L^1$ (Bayesian risk) measure.
  • Linearity and Stability: Scatter plots show that $p > 1$ measures produce tighter, more linear clusters with less noise compared to the $p=1$ case.
  • Algorithmic Invariance: These improvements were consistent across all three tested classifiers, suggesting that the geometric measures capture fundamental data properties independent of the specific learning algorithm.
  • Topological Advantages: The authors note that the space is compact under $d_p$ for $p > 1$, but not for $d_1$. This topological difference likely contributes to the more stable and predictable behavior of higher-order measures in practical applications.
Scatter plots of AUC vs. distance for different p values across multiple classifiers.

Conclusion

By formalizing feature selection within a geometric framework, this work provides a unifying theory for distance-based measures. The identification of Bayesian risk as the $L^1$ special case suggests that exploring higher-order $L^p$ spaces can lead to more effective feature selection metrics. Future research will explore the topological reasons for the superiority of $p > 1$ and extend the theory to continuous data.

Summary updated

BibTeX
@inproceedings{shin2015geometric,
  author = {Kilho Shin and Adrian Pino Angulo},
  title = {{A Geometric Theory of Feature Selection and Distance-Based Measures}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}

Loading related content...

Figure