Efficiently identify important features in mixed sparse classifiers with fewer measurements
Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Less Measurements
Machine LearningData Structures and Algorithms
Summary
When data comes from several different simple rules that each pay attention to only a few important features, it's hard to figure out which features really matter. This paper looks at how to find those important features even when you only get limited, noisy signals telling you whether a guess is positive or negative. The authors present clever ways to pick and interpret these signals that need fewer tries and are faster to decode than before. Their methods work both when you adaptively choose your next guesses and when you fix all guesses in advance.
What this means in practice
- •For data engineers: Improve feature selection speed and accuracy in systems using multiple sparse linear classifiers for large-scale data.
- •For signal processing teams: Enhance recovery of sparse signals from sign-only measurements in mixed-source sensing environments.
Authors
Xiaxin Li, Arya Mazumdar
Abstract
The support recovery problem in mixture of linear classifiers intends to identify which features actually matter when data is generated by a mixture of several linear decision rules. In particular, the aim is to recover the support (nonzero coordinates) of $l$ unknown $k$-sparse vectors from sign measurements. Each measurement is generated by selecting one of the $l$ vectors uniformly at random, and returning the sign of its inner product with a chosen measurement vector. In this paper, we propose adaptive and non-adaptive schemes that significantly improve upon prior results by reducing the number of measurements and achieving sublinear decoding time simultaneously. In particular, our adaptive constructions substantially reduce measurements compared to existing approaches, while also lowering decoding complexity from super-quadratic to sublinear in the ambient dimension. We further provide a non-adaptive scheme that improves previous measurement bounds while maintaining efficient decoding. Overall, our approach yields a more efficient trade-off between sample complexity and decoding time for support recovery in mixture models than previously known methods.