Usage Instructions for software implementing the algorithms described in the manuscript:

'Algorithms for Sparse Linear Classifiers in the
Online/Massive Data Setting'

by
Suhrid Balakrishnan and David Madigan

Last update: Nov 2005

Overview

MATLAB code is provided for implementing the three algorithms
described in the paper, 1. The online algorithm, 2. The multi-pass
algorithm and 3. The reduced memory multi-pass algorithm. A toy
dataset is provided which the users can directly apply the methods
to. Detailed comments in the code make for application to other
datasets with minimal tweaking.


User Guide

The code is self contained except for some random variable generation
routines for which the users will need the Statistics toolbox for
MATLAB installed/licensed. The code consists of a small number m-files
which we hope contains enough documentation to be readily usable.


The algorithms can be deployed on the toy dataset without any
modifications. The toy dataset, data.txt, is an 800 Kb sparse dataset
with 10 variables (11 parameters for a linear model counting the
intercept), and 10,000 observations. The data is drawn from a logistic
regression model with the following parameters (also available in the
included file parameter_values.dat):


  2.5859368e-001 (intercept)
  7.6056726e-001
 -3.6018988e-001
  8.7605871e-001
  9.1281862e-001
 -3.0241555e-001
 -8.2009207e-001
  0.0000000e+000
  0.0000000e+000
  0.0000000e+000
 -3.1889138e-001

As can be seen, three variables have zero coefficients (are noise variables). 

The algorithms all employ MATLAB main program scripts (mainprog_*****.m) to run, where **** is one of:

1. ONLINE 	-For the online algorithm
2. MP 		-For the multi-pass algorithm
or
3. RMMP 	-For the reduced memory multi-pass algorithm

In order to run an algorithm on the toy dataset, simply type in its
name at the Matlab command prompt. In order to run it on a data set
other than the toy example, the comments show one where to input the
filename. Finally, an m-file is also provided for making predictions
from a model output by these algorithms. Various statistics are also
computed.


Directory Listing

apoxll_logistic_vec.m  
apoxll_probit_vec.m    
readblock.m                        
shooting.m             
logistic.m             
probit.m           
MainProg_ONLINE.m      
MainProg_MP.m         
MainProg_RMMP.m 
make_predictions.m     

data.txt   
Readme.txt             
parameter_values.txt 

Most m-files have internal comments that should be available when typing help in MATLAB.
Acknowledgments

We would like to acknowledge support for this project from the National Science Foundation
(NSF grant IIS-9988642) and the Multidisciplinary Research Program of the Department
of Defense (MURI N00014-00-1-0637).

Legal Notice

Software is free for non-commercial use.

Software is provided as is, without any guarantee. Authors are not responsible for implications from the use of this software.

Feedback

Questions, comments, bug reports welcome by email: suhrid@paul.rutgers.edu
