ml-lab / s3fs

Simultaneous Safe Screening of Features and Samples in Doubly Sparse Modeling (ICML 2016)

#Simultaneous Safe Screening of Features and Samples in Doubly Sparse Modeling (ICML'16)

##Abstract

The problem of learning a sparse model is conceptually interpreted as the process of identifying active features/samples and then optimizing the model over them. Recently introduced safe screening allows us to identify a part of non-active features/samples. So far, safe screening has been individually studied either for feature screening or for sample screening. In this paper, we introduce a new approach for safely screening features and samples simultaneously by alternatively iterating feature and sample screening steps. A significant advantage of considering them simultaneously rather than individually is that they have a synergy effect in the sense that the results of the previous safe feature screening can be exploited for improving the next safe sample screening performances, and vice-versa. We first theoretically investigate the synergy effect, and then illustrate the practical advantage through intensive numerical experiments for problems with large numbers of features and samples.

##Result

Safe screening and keeping rates for classification problems. The three plots in the left show the individual safe feature/sample screening rates (the middle and the bottom ones are for alpha i star = 0 and alpha i star = pm 1, respectively). The three plots in the center show the additional safe screening rates by simultaneously considering feature and sample screenings. The gray area in these center plots corresponds to the blue area in the corresponding left plot. In these gray area, the individual safe screening performances are good enough (screening rate > 0.95) and additional screening is unnecessary. The top right and middle right plots show the safe keeping rates for feature and samples, respectively. The bottom right plot shows the numbers of non-active features and samples for various values of lambda.

##Environmental Requirement

• gcc version > 4.8.0
• cmake version > 2.8.12

##About Source code for Simultaneous Safe Screening of Features and Samples in Doubly Sparse Modeling. We wrote the code in C++ along with Eigen3.3-alpha1 library for some numerical computations.

##How to Compile

cd s3fs
cmake .
make

Usage

###We support LIBSVM data fortmat only ( LIBSVM datasets ).

###Elastic net + smoothed hinge loss (model selection task) with SPDC

• non-screeing: ./test/elastic_smooth_module -s 14 -e 1e-9 [dataset_filename]
• simultaneous safe screeing: ./test/elastic_smooth_module -s 15 -e 1e-9 - d 1 [dataset_filename]
• safe feature screeing: ./test/elastic_smooth_module -s 16 -e 1e-9 -d 1 [dataset_filename]
• safe sample screeing: ./test/elastic_smooth_module -s 17 -e 1e-9 - d 1 [dataset_filename]

###Elastic net + smoothed epsilon-insensitive loss (model selection task) with SPDC

• non-screeing: ./test/elastic_soft_module -s 14 -e 1e-9 [dataset_filename]
• simultaneous safe screeing: ./test/elastic_soft_module -s 15 -e 1e-9 - d 1 [dataset_filename]
• safe feature screeing: ./test/elastic_soft_module -s 16 -e 1e-9 -d 1 [dataset_filename]
• safe sample screeing: ./test/elastic_soft_module -s 17 -e 1e-9 - d 1 [dataset_filename]

##LISENCE MIT