Feature selection by Higher Criticism thresholding: optimal phase diagram

Abstract

We consider two-class linear classification in a high-dimensional, low-sample size setting. Only a small fraction of the features are useful, the useful features are unknown to us, and each useful feature contributes weakly to the classification decision -- this setting was called the rare/weak model (RW Model). We select features by thresholding feature $z$-scores. The threshold is set by {\it higher criticism} (HC). Let $\pee_i$ denote the $P$-value associated to the $i$-th $z$-score and $\pee_{(i)}$ denote the $i$-th order statistic of the collection of $P$-values. The HC threshold (HCT) is the order statistic of the $z$-score corresponding to index $i$ maximizing $(i/n - \pee_{(i)})/\sqrt{\pee_{(i)}(1-\pee_{(i)})}$. The ideal threshold optimizes the classification error. In \cite{PNAS} we showed that HCT was numerically close to the ideal threshold. We formalize an asymptotic framework for studying the RW model, considering a sequence of problems with increasingly many features and relatively fewer observations. We show that along this sequence, the limiting performance of ideal HCT is essentially just as good as the limiting performance of ideal thresholding. Our results describe two-dimensional {\it phase space}, a two-dimensional diagram with coordinates quantifying "rare" and "weak" in the RW model. Phase space can be partitioned into two regions -- one where ideal threshold classification is successful, and one where the features are so weak and so rare that it must fail. Surprisingly, the regions where ideal HCT succeeds and fails make the exact same partition of the phase diagram. Other threshold methods, such as FDR threshold selection, are successful in a substantially smaller region of the phase space than either HCT or Ideal thresholding.

4 figures, 24 pages

References in corpus (5)

• High-dimensional classification using features annealed independence rules
• Goodness-of-fit tests via phi-divergences
• Properties of higher criticism under strong dependence
• Estimation and confidence sets for sparse normal mixtures
• Asymptotic minimaxity of False Discovery Rate thresholding for sparse exponential data

Cited by in corpus (13)

• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Innovated higher criticism for detecting sparse signals in correlated noise
• Higher Criticism for Large-Scale Inference, Especially for Rare and Weak Effects
• Tight conditions for consistency of variable selection in the context of high dimensionality
• Signal Identification for Rare and Weak Features: Higher Criticism or False Discovery Rates?
• Optimal classification in sparse Gaussian graphic model
• Goodness of fit tests in terms of local levels with special emphasis on higher criticism tests
• A novel algorithm for simultaneous SNP selection in high-dimensional genome-wide association studies
• Higher Criticism to Compare Two Large Frequency Tables, with sensitivity to Possible Rare and Weak Differences
• Feature selection when there are many influential features
• Higher Criticism for Discriminating Word-Frequency Tables and Testing Authorship
• Superconsistency of Tests in High Dimensions
• Higher criticism for rare and weak non-proportional hazard deviations in survival analysis