Published on Wed Oct 21 2009

Sparsification and feature selection by compressive linear regression

Florin Popescu, Daniel Renz

The Minimum Description Length (MDL) principle states that the optimal model for a given data set is that which compresses it best. As in other formulations such as the LASSO and forward step-wise regression we are interested in sparsifying the feature set while preserving generalization ability.

0
0
0
Abstract

The Minimum Description Length (MDL) principle states that the optimal model for a given data set is that which compresses it best. Due to practial limitations the model can be restricted to a class such as linear regression models, which we address in this study. As in other formulations such as the LASSO and forward step-wise regression we are interested in sparsifying the feature set while preserving generalization ability. We derive a well-principled set of codes for both parameters and error residuals along with smooth approximations to lengths of these codes as to allow gradient descent optimization of description length, and go on to show that sparsification and feature selection using our approach is faster than the LASSO on several datasets from the UCI and StatLib repositories, with favorable generalization accuracy, while being fully automatic, requiring neither cross-validation nor tuning of regularization hyper-parameters, allowing even for a nonlinear expansion of the feature set followed by sparsification.

Fri Nov 20 2015
Machine Learning
Data Representation and Compression Using Linear-Programming Approximations
Dracula is a new framework for unsupervised feature selection. It learns a dictionary of -grams that compresses a given corpus and recursively compresses its own dictionary. Dracula is a `deep' extension of Compressive Feature Learning.
0
0
0
Sat Jul 14 2018
Machine Learning
A Unified Framework for Sparse Relaxed Regularized Regression: SR3
Regularized regression problems are ubiquitous in statistical modeling and machine learning. Sparse regression in particular has been instrumental in scientific model discovery. We propose a framework for sparse relaxed regularized regression, called SR3. We demonstrate the advantages of SR3 across a range of regularization problems.
0
0
0
Thu May 23 2019
Machine Learning
Naive Feature Selection: Sparsity in Naive Bayes
We propose a sparse version of naive Bayes, which can be used for feature selection. This leads to a combinatorial maximum-likelihood problem, for which we provide an exact solution. We prove that our bound becomes tight as the marginal contributions of additional features decrease.
0
0
0
Tue Sep 21 2010
Machine Learning
Safe Feature Elimination for the LASSO and Sparse Supervised Learning Problems
We describe a fast method to eliminate features (variables) in l1 -penalized least-square regression (or LASSO) problems. The elimination of features leads to a potentially substantial reduction in running time, specially for large values of the penalty parameter.
0
0
0
Mon Jun 26 2017
Machine Learning
High-dimensional classification by sparse logistic regression
We consider high-dimensional binary classification by sparse logistic regression. We propose a model/feature selection procedure based on penalized maximum likelihood with a complexity penalty on the model size. We derive the non-asymptotic bounds for the resulting misclassification excess risk.
0
0
0
Sat Jun 27 2020
Machine Learning
Picasso: A Sparse Learning Library for High Dimensional Data Analysis in R and Python
We describe a new library named picasso, which implements a unified framework of pathwise coordinate optimization for a variety of sparse learning problems. The library is coded in C++ and has user-friendly R and Python wrappers.
0
0
0