Feature Selection for Ridge Regression with Provable Guarantees
| Autor: | Paul, Saurabh, Drineas, Petros |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We introduce single-set spectral sparsification as a deterministic sampling based feature selection technique for regularized least squares classification, which is the classification analogue to ridge regression. The method is unsupervised and gives worst-case guarantees of the generalization power of the classification function after feature selection with respect to the classification function obtained using all features. We also introduce leverage-score sampling as an unsupervised randomized feature selection method for ridge regression. We provide risk bounds for both single-set spectral sparsification and leverage-score sampling on ridge regression in the fixed design setting and show that the risk in the sampled space is comparable to the risk in the full-feature space. We perform experiments on synthetic and real-world datasets, namely a subset of TechTC-300 datasets, to support our theory. Experimental results indicate that the proposed methods perform better than the existing feature selection methods. Comment: To appear in Neural Computation. A shorter version of this paper appeared at ECML-PKDD 2014 under the title "Deterministic Feature Selection for Regularized Least Squares Classification." |
| Databáze: | arXiv |
| Externí odkaz: |
|