Parallel Feature Selection Inspired by Group Testing

This paper presents a parallel feature selection method for classification that scales up to very high dimensions and large data sizes. Our original method is inspired by group testing theory, under which the feature selection procedure consists of a collection of randomized tests to be performed in parallel. Each test corresponds to a subset of features, for which a scoring function may be applied to measure the relevance of the features in a classification task. We develop a general theory providing sufficient conditions under which true features are guaranteed to be correctly identified. Superior performance of our method is demonstrated on a challenging relation extraction task from a very large data set that have both redundant features and sample size in the order of millions. We present comprehensive comparisons with state-of-the-art feature selection methods on a range of data sets, for which our method exhibits competitive performance in terms of running time and accuracy. Moreover, it also yields substantial speedup when used as a pre-processing step for most other existing methods.

Authors

• Yingbo Zhou University at Buffalo, State University of New York
• Utkarsh Porwal
• Ce Zhang Carnegie Mellon University
• Hung Ngo
• XuanLong Nguyen
• Christopher Ré Stanford University
• Venu Govindaraju Sargur N. Srihari

Keywords

No keywords are indexed for this paper.