High-dimensional classification using features annealed independence rules

Jianqing Fan, Yingying FanThe Annals of Statistics 2008 · DOI

TL;DR

This paper introduces a new classification method called Features Annealed Independence Rules (FAIR) designed for high-dimensional data, where the number of features far exceeds the number of samples. FAIR addresses the critical issue of noise accumulation in high-dimensional spaces that plagues standard methods, demonstrating that even seemingly robust techniques can perform as poorly as random guessing. By intelligently selecting a subset of informative features, FAIR significantly improves classification accuracy and interpretability.

What Problem Does This Paper Address?

In fields like genomics and proteomics, datasets often have thousands or even millions of features (e.g., gene expression levels) for a relatively small number of samples. This "high dimensionality" poses a significant challenge for traditional classification algorithms. A key problem is "noise accumulation": when estimating parameters (like means) from noisy data in a high-dimensional space, even small errors in each dimension can add up to a large overall error, making it difficult to distinguish between classes. The paper highlights that even established methods like the Fisher discriminant, and even the "independence rule" proposed to handle high dimensions, can suffer from this noise accumulation, performing no better than random chance. The authors aim to develop a classification method that is robust to this high dimensionality and can effectively identify and utilize the truly informative features.

Methods

The core of the proposed method, FAIR, involves a two-stage process:

  1. Feature Selection: The paper leverages the two-sample t-statistic to identify potentially important features. Under certain theoretical conditions, they show that this simple test can reliably select all truly informative features with high probability. This is a crucial step to filter out the vast majority of noisy, irrelevant features.
  2. Classification with Selected Features: Once a subset of features is selected, FAIR applies the independence classification rule (which assumes features are independent given the class) to this reduced set. This avoids the curse of dimensionality by operating in a lower-dimensional space defined by the selected features.

The paper also proposes a data-driven method to determine the optimal number of features to select, based on an upper bound of the classification error.

Datasets

The paper evaluates FAIR using:

  • Simulated Data: A simulation study is conducted to assess the theoretical results under controlled conditions.
  • Leukemia Dataset: A publicly available dataset from high-density Affymetrix oligonucleotide arrays, previously analyzed in Golub et al. (1999). It contains gene expression data for two classes of leukemia (ALL and AML).
  • Lung Cancer Dataset: Data from high-density Affymetrix oligonucleotide arrays for classifying malignant pleural mesothelioma (MPM) and adenocarcinoma (ADCA) of the lung, analyzed by Gordon et al. (2002).
  • Prostate Cancer Dataset: Data from Singh et al. (2002) for classifying prostate tumor and normal samples.

Key Insights and Ideas

  • The "Curse of Dimensionality" is Pervasive: Even methods designed for high dimensions, like the independence rule, can fail catastrophically due to noise accumulation when all features are used. This means that simply having more data doesn't automatically solve the problem if the dimensionality is too high.
  • Feature Selection is Non-Negotiable: The paper strongly argues that for high-dimensional classification, selecting a subset of truly informative features is not just beneficial, but essential for achieving good performance.
  • Simple Tools Can Be Powerful: The two-sample t-statistic, a fundamental statistical tool, is shown to be surprisingly effective for identifying important features in high dimensions under specific theoretical conditions.
  • FAIR Balances Signal and Noise: By first filtering out noise with the t-statistic and then applying a robust classifier on the reduced set, FAIR effectively balances the signal from important features against the noise from irrelevant ones.
  • Interpretability Gains: By focusing on a smaller set of selected features, FAIR also offers improved interpretability, which is crucial in applications like medical diagnosis.

Key Results

  • Theoretical Guarantees: The paper provides theoretical results showing that the two-sample t-test can select all important features with high probability. It also establishes an upper bound for the classification error of FAIR.
  • Simulation Performance: Simulations demonstrate that FAIR's classification error is close to that of an "oracle-assisted" version (which knows the true signal levels), significantly outperforming the independence rule without feature selection.
  • Real Data Performance:
    • Leukemia Data: FAIR selected 11 genes and achieved 1 training error and 1 test error, outperforming the nearest shrunken centroids (NSC) method which selected 21 genes and had 1 training error and 3 test errors.
  • Lung Cancer Data: FAIR used 31 genes with 0 training error and 7/149 test error, while NSC used 26 genes with 0 training error and 11/149 test error.
  • Prostate Cancer Data: FAIR selected 2 genes with 10/102 training error and 9/34 test error, while NSC selected 6 genes with 8/102 training error and 9/34 test error.
  • In general, FAIR consistently selected fewer features than NSC while achieving comparable or better classification accuracy, and demonstrated more stable feature selection.

Limitations and Future Work

  • Assumptions for Feature Selection: The theoretical guarantees for the t-statistic selecting all important features rely on specific conditions (e.g., sparsity of the signal, Cramér's condition for noise, and bounded diagonal elements of covariance matrices). While these are often reasonable, they might not hold in all real-world scenarios.
  • Oracle vs. Data-Driven Selection: The paper acknowledges that the data-driven selection of the number of features (using the t-statistic) can lead to slightly higher classification errors compared to an ideal scenario where the true important features are known beforehand (oracle).
  • Future Work: The authors suggest exploring other feature selection methods and investigating the impact of different choices for the thresholding parameter in FAIR. They also implicitly point towards the need for robust methods that can handle situations where the assumptions for perfect feature selection might be violated.

Summary updated

Abstract

Classification using high-dimensional features arises frequently in many contemporary statistical studies such as tumor classification using microarray or other high-throughput data. The impact of dimensionality on classifications is largely poorly understood. In a seminal paper, Bickel and Levina (2004) show that the Fisher discriminant performs poorly due to diverging spectra and they propose to use the independence rule to overcome the problem. We first demonstrate that even for the independence classification rule, classification using all the features can be as bad as the random guessing due to noise accumulation in estimating population centroids in high-dimensional feature space. In fact, we demonstrate further that almost all linear discriminants can perform as bad as the random guessing. Thus, it is paramountly important to select a subset of important features for high-dimensional classification, resulting in Features Annealed Independence Rules (FAIR). The conditions under which all the important features can be selected by the two-sample t-statistic are established. The choice of the optimal number of features, or equivalently, the threshold value of the test statistics are proposed based on an upper bound of the classification error. Simulation studies and real data analysis support our theoretical results and demonstrate convincingly the advantage of our new classification procedure.
BibTeX
@article{fan2008high,
  author = {Jianqing Fan and Yingying Fan},
  title = {{High-dimensional classification using features annealed independence rules}},
  journal = {The Annals of Statistics},
  year = {2008},
  doi = {10.1214/07-aos504},
}
Figure