Feature selection by higher criticism thresholding achieves the optimal phase diagram

DOI10.1098/RSTA.2009.0129zbMATH Open1185.62113arXiv0812.2263OpenAlexW3100205528WikidataQ51787285 ScholiaQ51787285MaRDI QIDQ3559955FDOQ3559955

Authors: David Donoho, Jiashun Jin 

Publication date: 8 May 2010

Published in: Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

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 $pe{e}_i$ denote the $P$-value associated to the $i$-th $z$-score and $pe{e}_{(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-pe{e}_{(i)})/sqrtpe{e}_{(i)}(1-pe{e}_{(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.

Full work available at URL: https://arxiv.org/abs/0812.2263

Recommendations

• Higher criticism for large-scale inference, especially for rare and weak effects
• Rare and weak effects in large-scale inference: methods and phase diagrams
• Optimal classification in sparse Gaussian graphic model
• On false discovery rate thresholding for classification under sparsity
• Higher criticism for detecting sparse heterogeneous mixtures.

zbMATH Keywords

false discovery ratephase diagramlinear classificationasymptotic rare/weak modelfeature selection by thresholdingFisher's separation measure

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Order statistics; empirical distribution functions (62G30)

Cites Work

• High-dimensional classification using features annealed independence rules
• Some theory for Fisher's linear discriminant function, `naive Bayes', and some alternatives when there are many more variables than observations
• Higher criticism for detecting sparse heterogeneous mixtures.
• Needles and straw in haystacks: Empirical Bayes estimates of possibly sparse sequences
• Asymptotic minimaxity of false discovery rate thresholding for sparse exponential data
• Goodness-of-fit tests via phi-divergences
• Estimation and confidence sets for sparse normal mixtures
• Properties of higher criticism under strong dependence
• Adapting to unknown sparsity by controlling the false discovery rate
• Higher criticism thresholding: Optimal feature selection when useful features are rare and weak
• Impossibility of successful classification when useful features are rare and weak
• Classification of sparse high-dimensional vectors

Cited In (28)

• Two-group classification with high-dimensional correlated data: a factor model approach
• Goodness-of-fit tests based on sup-functionals of weighted empirical processes
• Goodness of fit tests in terms of local levels with special emphasis on higher criticism tests
• Feature selection when there are many influential features
• Detection boundary in sparse regression
• High dimensional classifiers in the imbalanced case
• Optimal detection of heterogeneous and heteroscedastic mixtures
• Classification with many classes: challenges and pluses
• Higher criticism to compare two large frequency tables, with sensitivity to possible rare and weak differences
• Using visual statistical inference to better understand random class separations in high dimension, low sample size data
• Signal detection via Phi-divergences for general mixtures
• Estimating the amount of sparsity in two-point mixture models
• Signal localization: a new approach in signal discovery
• Tight conditions for consistency of variable selection in the context of high dimensionality
• The impossibility region for detecting sparse mixtures using the higher criticism
• Optimal classification in sparse Gaussian graphic model
• The intermediates take it all: asymptotics of higher criticism statistics and a powerful alternative based on equal local levels
• Rare and weak effects in large-scale inference: methods and phase diagrams
• Innovated higher criticism for detecting sparse signals in correlated noise
• Classification of sparse high-dimensional vectors
• Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
• Sparse microwave imaging: principles and applications
• Adaptive threshold-based classification of sparse high-dimensional data
• Identifying the support of rectangular signals in Gaussian noise
• Higher criticism for discriminating word-frequency tables and authorship attribution
• Fast rate of convergence in high-dimensional linear discriminant analysis
• Higher criticism for large-scale inference, especially for rare and weak effects
• Asymptotics of goodness-of-fit tests based on minimum p-value statistics

This page was built for publication: Feature selection by higher criticism thresholding achieves the optimal phase diagram

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3559955)