Time Is Flying By

Good news, the refactoring of the elastic-net and lasso classes is done and has been merged into the scikit-learn master some time ago.

I invested some time learning about the hdf5 data format to upload some dataset to mldata.org . Sadly the documentation of mldata.org is very sparse and in case of the used hdf5 data format, outdated too. I have been in contact with the maintainer but I still don't have working specs. I decided to put this task at rest for the moment.

I have a Python prototype working for the new coordinate descent algorithm that  I'm now about to integrate step by step into scikit-learn .



This version will be written in Cython to speed thins up. I hope that I can beat the execution time of the current implementation soon.

Refactoring linear model code and first benchmark plots

During the last week, I spend some time refactoring the Elastic Net and Lasso classes in scikit-learn. The goal is to obtain a unique interface for the sparse and dense implementations of this model. The format of the input data is used to determine, whether the sparse implementation is used or not. This has the advantage that the user can use the same class for sparse and dense data.

The first benchmark reports are available thanks to Vlads work to adapt vbench to work with scikit-learn ( check out his blog post ).

The plot shows how the execution time changed over time during the past 180 days, for fitting an elastic-net penalized logistic regression on the leukemia data set.

Scikit-learn currently wraps the LIBLINEAR library to fit logistic regression models. As a comparison, the implementation of glmnet 1.7.4 using the R package glmnet took 188 milliseconds to fit the leukemia data set. Next week will bring more benchmark evaluations on different data sets.

 Setting up benchmark tests


This GSOC project aims to improve the execution time of some linear models implemented in scikit-learn. Before I start with any code enhancements I want to have an evaluation on how the actual implementations compare with other state of the art implementations. These evaluations will be based on real world data sets with different characteristics. The following shows some of the ideas and the questions that will be addressed next.


1. data sets

binary:

name	size	N (train/test)	p	#nz (train)	used in	format
Leukemia	1.9M	72	3571	dense	[1]	RData
Newsgroup	9.4M	11,314	777,811	0.05%	[1]	RData
Internet-Ad	49K	2359	1430	1.2%	[1]	RData
a9a	2.3M/1.1M	32,561 / 16,281	123	451,592 (11%)	[2]	libsvm
real-sim	33.6M	72,309	20,958	3,709,083 (0.2%)	[2]	libsvm
rcv1	13.1M/432M	20,242 / 677,399	47,236	49,556,258 (0.15%)	[2]	libsvm

multiclass:

name	size	#class	N(train/test)	p	#nz	used in	format
news20	3.6M/0.9M	20	15,935 / 3,993	1,355,191	9,097,916 (0,03%)	[2]	libsvm
Cancer	22M	14	144	16,063	dense	[1]	RData

regression:

name	size	N	p	#nz	used in	format
Prostate Cancer Data		97	9	dense	[3]	RData

ref:

[1] Friedman, J., T. Hastie, and R. Tibshirani. “Regularization Paths for Generalized Linear Models via Coordinate Descent.” Journal of Statistical Software 33, no. 1 (2010): 1.

p.20 download data

[2] Tibshirani, R., J. Bien, J. Friedman, T. Hastie, N. Simon, J. Taylor, and R.J. Tibshirani. “Strong Rules for Discarding Predictors in Lasso-type Problems.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) (2011).

p.3214 download data

[3] Tibshirani, R. “Regression Shrinkage and Selection via the Lasso.” Journal of the Royal Statistical Society. Series B (Methodological) (1996): 267–288.

Q: Which data sets should be used?
Q: Format to store them?
Q: Other regression type data sets?


2 problems to benchmark

• l2 loss*
• log loss*
• multi-logit*

with l1 and l1 & l2 penalty

Q: Settings to use in benchmarking (penalty value etc. ) ?

2.1 external reference implementations

• glmnet
• glmnet-python ( version? )
• R glmnet package + rpy2 (latest version)
• liblinear
• liblinear + python interface (latest version)

Q: How to time execution to achieve a fair comparison ?
Q: Which glmnet interface should be used?


3 scikit-learn implementations speed development tracking
tracking of execution times for the scikit-learn implementations of (2) on data sets (1)

vbench

Q: Already some example code available for scikit-learn ?

Good News,
this project has been accepted for GSOC 2012.

This is my proposal for the Google Summer of Code 2012.

Optimizing sparse linear models using coordinate descent and strong rules.

Abstract

Scikit-learn is a Python machine learning library that aims to be easy to use through a well designed interface. Dependencies are kept to a minimum and the extensive use of NumPy, SciPy and Matplotlib give great computing power and ease the understanding of the codebase.
Data sets with far more features than samples are rapidly gaining on popularity and bring the class of linear models back to focus. This project will bring additional state of the art optimization routines for sparse linear models to scikit-learn and even further reduce dependencies. This task includes high test coverage, documentation, examples and intensive benchmarking.

Linear models are used for regression as well as for classification tasks. In both cases penalty terms can be used to obtain an implicit feature selection. To efficiently solve these penalized linear models is the main focus of this project.

The here proposed improvements will be beneficial for a wide range of general problems and specialized domains such as gene expression analysis, compressed sensing, and sparse encoding.

Outline
During the project, I will implement glmnet[1], a cyclic coordinate descent algorithm to solve penalized linear regression and classification problems. Considerable speedup is achieved for example through the use of weighted updates and active set of features.
With the implementation of strong rules[2] a large number of variables can be excluded before the optimization. This rule is especially powerful in sparse problems. A speedup factor of 20 and more is reported[1] for certain problems over the standard glmnet implementation.
As a complement to glmnet the LARS algorithm will be extended to deal with elastic net (L1 +L2) penalties.

References

1. http://www.stanford.edu/~hastie/Papers/glmnet.pdf
2. http://www-stat.stanford.edu/~jbien/jrssb2011strong.pdf
3. http://www.jmlr.org/papers/volume11/yuan10c/yuan10c.pdf