Bayesian Classification and Feature Selection from Finite Data Sets

Frans Coetzee, Steve Lawrence, C. Lee GilesUAI 2000

TL;DR

This paper investigates the theoretical limitations of the Neyman-Pearson (NP) design procedure for feature selection, particularly when dealing with finite datasets. It reveals that while individual classifier performance can be estimated accurately, the NP procedure's ability to correctly rank feature subsets degrades significantly as the number of features increases, potentially leading to suboptimal choices.

What Problem Does This Paper Address?

Feature selection aims to identify the smallest subset of features that yields a desired level of classification performance. This is crucial for reducing computational complexity and improving generalization. A common theoretical benchmark for achievable performance on a feature subset is the Receiver Operating Curve (ROC). The Neyman-Pearson (NP) design procedure is a standard method for calculating this ROC when class conditional densities are known. However, in practice, these densities must be estimated from finite data, introducing errors. This paper tackles the problem of how these estimation errors, combined with the NP procedure's reliance on ranking likelihood ratios, impact the ability to reliably select optimal feature subsets, especially as the dimensionality of the feature space grows.

Methods

The authors analyze the Neyman-Pearson (NP) design procedure in the context of finite data. They formalize the Bayesian design process as a search procedure and derive quantitative bounds on the error propagation. Key methods include:

  • Statistical Analysis of Error Propagation: They analyze how errors in density estimates (specifically, histogram estimates of class conditional probabilities) affect the calculation of performance metrics like the Receiver Operating Curve (ROC).
  • Likelihood Ratio Ranking: The NP procedure relies on ranking likelihood ratios derived from these density estimates. The paper investigates the impact of errors in this ranking.
  • Beta Distribution Modeling: The uncertainty in estimated bin probabilities (from histograms) is modeled using beta distributions. The properties of these distributions and their ratios are analyzed to understand error bounds.
  • Confidence Intervals and Bounds: The authors derive bounds (e.g., using Chebychev bounds) to quantify the confidence in performance estimates and the likelihood ranking.
  • Data-Adaptive NP Design: A novel approach is proposed where bins with low confidence estimates are merged to improve the robustness of the NP procedure.

Datasets

The paper does not introduce new datasets. Instead, it uses a synthetic example with two classes and binary features to illustrate the concepts and demonstrate the findings. The analysis is primarily theoretical and statistical, relying on simulated data generated from known (or assumed) underlying distributions.

Key Insights and Ideas

  • Performance vs. Ranking: While the performance of an individual classifier can be estimated accurately even with many features (given enough data), the NP procedure for finding the best classifier (and thus the ROC) becomes unreliable as feature dimensionality increases.
  • The "Curse of Dimensionality" for Ranking: As the number of features (and thus possible feature vectors) grows exponentially, the number of samples per bin in the estimated density becomes sparse. This leads to unreliable likelihood ratio estimates and incorrect ranking of feature subsets by the NP procedure.
  • Suboptimal Classifier Selection: Errors in the NP ranking can lead to selecting a set of classifiers that do not truly lie on the optimal ROC curve, resulting in a "Naive Estimated Performance Curve" (NEPC) that is biased and potentially worse than expected.
  • Data-Adaptive Solutions: The paper suggests that simply increasing data might not solve the ranking problem for high-dimensional feature sets. Data-adaptive methods, like merging bins with low confidence, are proposed to make the NP procedure more robust.
  • Practical Limits on Feature Subset Size: The analysis implies that for reliable feature subset ranking using the NP procedure, there might be a practical limit on the size of the feature subset that can be considered, even with ample data.

Key Results

  • Error Propagation Bounds: Quantitative bounds are derived relating data size, feature subset size, and confidence in ROC performance estimates.
  • Degradation of NP Ranking: The probability of correctly sorting likelihood ratios decreases significantly as the number of features increases. This is illustrated by the divergence of the Naive Estimated Performance Curve (NEPC) from the true ROC and the Estimated Performance Curve (EPC) in simulations as dimensionality increases.
  • Bias in NEPC: The NEPC (using design data for evaluation) is shown to be biased, often overestimating performance, especially in higher dimensions.
  • Data-Adaptive Improvement: The proposed data-adaptive NP design method (merging bins) showed improved sort confidence and reduced bias in the NEPC in their experiments.

Limitations and Future Work

  • Theoretical Focus: The analysis is largely theoretical, with empirical validation primarily through synthetic examples.
  • Computational Intractability: The exact joint statistics of likelihoods are intractable, necessitating approximations and bounds.
  • "Curse of Dimensionality" for NP: The core limitation identified is that the NP procedure itself is susceptible to the curse of dimensionality, making it difficult to reliably rank large feature subsets.
  • Future Work: The authors suggest further investigation into using biased performance estimates for searching (as opposed to expensive cross-validation) and exploring other search procedures that might be more robust to dimensionality. They also note that further exploitation of statistical results for algorithm design remains an open problem.

Summary updated

BibTeX
@inproceedings{coetzee2000bayesian,
  author = {Frans Coetzee and Steve Lawrence and C. Lee Giles},
  title = {{Bayesian Classification and Feature Selection from Finite Data Sets}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2000},
}
Figure