High-dimensional classification using features annealed independence rules

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 poorly understood. In a seminal paper, Bickel and Levina [Bernoulli 10 (2004) 989--1010] 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 poor 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 poorly as the random guessing. Thus, it is 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.

Published in at http://dx.doi.org/10.1214/07-AOS504 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Statistical Challenges with High Dimensionality: Feature Selection in Knowledge Discovery
• Best subset selection, persistence in high-dimensional statistical learning and optimization under $l_1$ constraint
• To how many simultaneous hypothesis tests can normal, Student's t or bootstrap calibration be applied?

Cited by in corpus (71)

• Challenges of Big Data Analysis
• Sure independence screening in generalized linear models with NP-dimensionality
• Network exploration via the adaptive LASSO and SCAD penalties
• A unified approach to model selection and sparse recovery using regularized least squares
• Sparse linear discriminant analysis by thresholding for high dimensional data
• Higher Criticism for Large-Scale Inference, Especially for Rare and Weak Effects
• The fused Kolmogorov filter: A nonparametric model-free screening method
• Gene ranking and biomarker discovery under correlation
• Variable selection in linear mixed effects models
• Feature selection in omics prediction problems using cat scores and false nondiscovery rate control
• High-Dimensional Sparse Additive Hazards Regression
• Innovated interaction screening for high-dimensional nonlinear classification
• Independence test for high dimensional data based on regularized canonical correlation coefficients
• Feature selection by Higher Criticism thresholding: optimal phase diagram
• A Selective Overview of Variable Selection in High Dimensional Feature Space (Invited Review Article)
• A majorization-minimization approach to variable selection using spike and slab priors
• Asymptotic equivalence of regularization methods in thresholded parameter space
• Rank discriminants for predicting phenotypes from RNA expression
• Asymptotic properties for combined $L_1$ and concave regularization
• Optimal classification in sparse Gaussian graphic model
• Simultaneous sparse estimation of canonical vectors in the p>>N setting
• Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime
• CLT for linear spectral statistics of normalized sample covariance matrices with the dimension much larger than the sample size
• Efficient active learning of sparse halfspaces with arbitrary bounded noise
• Optimal feature selection for sparse linear discriminant analysis and its applications in gene expression data
• Impacts of high dimensionality in finite samples
• QUADRO: A supervised dimension reduction method via Rayleigh quotient optimization
• Regularization in High-Dimensional Regression and Classification via Random Matrix Theory
• Optimal variable selection in multi-group sparse discriminant analysis
• Feature selection when there are many influential features
• ExSIS: Extended Sure Independence Screening for Ultrahigh-dimensional Linear Models
• Asymptotic Properties of High-Dimensional Random Forests
• High-dimensional sparse classification using exponential weighting with empirical hinge loss
• Nonparametric Screening under Conditional Strictly Convex Loss for Ultrahigh Dimensional Sparse Data
• Optimal Covariance Estimation for Condition Number Loss in the Spiked Model
• Ensemble Quantile Classifier
• Continuum directions for supervised dimension reduction
• On Two Simple and Effective Procedures for High Dimensional Classification of General Populations
• Feature space reduction method for ultrahigh-dimensional, multiclass data: Random forest-based multiround screening (RFMS)
• RANK: Large-Scale Inference with Graphical Nonlinear Knockoffs
• Integrative genetic risk prediction using nonparametric empirical Bayes classification
• The cumulative Kolmogorov filter for model-free screening in ultrahigh dimensional data
• A multivariate adaptive stochastic search method for dimensionality reduction in classification
• Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance
• Sparse Generalized Eigenvalue Problem: Optimal Statistical Rates via Truncated Rayleigh Flow
• Variational Discriminant Analysis with Variable Selection
• TULIP: A Toolbox for Linear Discriminant Analysis with Penalties
• Minimax optimal high-dimensional classification using deep neural networks
• Scalable Acceleration for Classification-Based Derivative-Free Optimization
• Towards Understanding the Impact of Model Size on Differential Private Classification
• Optimal estimation of functionals of high-dimensional mean and covariance matrix
• A Normality Test for High-dimensional Data based on a Nearest Neighbor Approach
• Strong Sure Screening of Ultra-high Dimensional Data with Interaction Effects
• Likelihood Adaptively Modified Penalties
• Classification of high-dimensional data with spiked covariance matrix structure
• High dimensional gaussian classification
• One-Bit Compressed Sensing via One-Shot Hard Thresholding
• Fast Multi-Class Probabilistic Classifier by Sparse Non-parametric Density Estimation
• Dynamic Supervised Principal Component Analysis for Classification
• Big data need physical ideas and methods
• High Dimensional Classification through ${\ell }_0$-Penalized Empirical Risk Minimization
• Different thresholding methods on Nearest Shrunken Centroid algorithm
• On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise
• A Doubly-Enhanced EM Algorithm for Model-Based Tensor Clustering
• An Improved Modified Cholesky Decomposition Method for Precision Matrix Estimation
• Variational Nonparametric Discriminant Analysis
• Variable selection and basis learning for ordinal classification
• On the Necessity of Irrelevant Variables
• A reproducing kernel Hilbert space framework for functional data classification
• Simultaneous Differential Network Analysis and Classification for High-dimensional Matrix-variate Data, with application to Brain Connectivity Alteration Detection and fMRI-guided Medical Diagnoses of Alzheimer's Disease
• Diagonally-Dominant Principal Component Analysis