Combinatorial feature selection problems

Motivated by frequently recurring themes in information retrieval and related disciplines, we define a genre of problems called combinatorial feature selection problems. Given a set S of multidimensional objects, the goal is to select a subset K of relevant dimensions (or features) such that some desired property /spl Pi/ holds for the set S restricted to K. Depending on /spl Pi/, the goal could be to either maximize or minimize the size of the subset K. Several well-studied feature selection problems can be cast in this form. We study the problems in this class derived from several natural and interesting properties /spl Pi/, including variants of the classical p-center problem as well as problems akin to determining the VC-dimension of a set system. Our main contribution is a theoretical framework for studying combinatorial feature selection, providing (in most cases essentially tight) approximation algorithms and hardness results for several instances of these problems.

Authors

• Moses Charikar
• Venkatesan Guruswami
• Ravi Kumar 0001
• Sridhar Rajagopalan
• Amit Sahai

Keywords

• Computer science
• Bridges
• Multidimensional systems
• Approximation algorithms
• Bonding
• US Department of Defense
• Data engineering
• Data mining
• Risk management
• Data processing
• Selection Problem
• Feature Selection Problem
• Running
• Analysis Algorithm
• Estimation Algorithm
• Data Clustering
• Steps Of Algorithm
• Number Of Centers
• Interesting Problem
• Set Of Dimensions
• Triangle Inequality
• Polynomial-time Algorithm
• Pair Of Vectors
• Clustering Problem
• Algorithm Running
• Distinct Problems
• Hardness Results
• Distinct Vectors
• Hidden Problem
• Optimal Radius
• Clique Of Size
• Bernoulli Model
• Cluster Radius
• Distinct Elements
• Dimensionality Reduction
• Distinct Points
• Similar Estimates
• Hamming Distance
• Exponential Dependence