This directory includes sources used in the following paper:

Cho-Jui Hsieh, Kai-Wei Chang,  Chih-Jen Lin, S. Sundararajan,
and S. Sathiya Keerthi. A Dual Coordinate Descent Method for
Large-scale Linear SVM, 2008.

This code has been tested under 32 and 64-bit Linux environments
using python 2.5.

You will be able to regenerate experiment results in the paper. However,
results may be slightly different due to the randomness, the CPU
speed, and the load of your computer.

Please cite the above article if you find this tool useful. Please
also read the COPYRIGHT before using this tool.


Prepare Data Sets for Experiments
=================================

Type

% ./gen_data.py

The script will download four data sets (a9a, real-sim, news20.binary,
rcv1_test.binary) from LIBSVM Data page, and do a 80/20 split for
training and testing; then store *.train and *.test in the 'data'
directory. Due to the randomness, the training and testing split
may be different each time.

Note that you need wget and bunzip2, which are called by gen_data.py


Installation for Experiments
============================

Install PEGASOS and SVMPERF in the directory 'pegasos' and 'svmperf'
repectively by the instructions in the last two sections of this file.

Except PEGASOS and SVMPERF, other solvers,modified from the liblinear
package, are implemented in the 'liblinear' directory.

Type

% make clean all;

to build the codes.

Compare L1-SVM solvers: PEGASOS, SVMPERF, DCDL1 (without shrinking)
===================================================================

Type

% python ./compare_l1.py

to compare these implementations. The results are stored in the 'log'
directory. Use the values in columns 'time', 'testing', 'primalf', and 'dualf'
to generate Figures 1 and 2.

Note that SVMPERF and DCDL1 solve L1-SVM problem via the dual, while
PEGASOS solves the primal. We show both primal and dual objective
values od dual-based methods.

Compare L2-SVM Solvers: TRON, PCD, DCDL2 (without shrinking)
============================================================

Type

% python ./compare_l2.py

to compare these implementations. The results are stored in the 'log'
directory. Use the values in columns 'time', 'testing', 'primalf', and 'dualf'
to generate Figures 1 and 2.

Note that DCDL2 solves L2-SVM problem via the dual, while TRON and PCD
solve the primal. We show both primal and dual objective values for
DCDL2.

Compare DCD Method with/without Shrinking
=========================================

Type

% python ./compare_shrinking.py

to compare DCD with/without shrinking. The results are stored in the
'log' directory.  Use the values in columns 'time' and 'primalf' to
draw the figures.

How to Install PEGASOS for Experiments
======================================

Download the .tar.gz file from

http://ttic.uchicago.edu/~shai/code/pegasos.tgz

and untar the file.

Follow the instructions to modify pegasos_optimize.cc to output the training time,
objective value and testing accuracy after each l steps:

1. In function scale(double s) of WeightVector.h
      - after line 64 (void scale(double s){)
        add following code:

        --------------------
        if (my_a <= 1.0e-200)
              make_my_a_one(); // solve numerical problems
        --------------------

2. In function LearnReturnLast(...) of pegasos_optimize.cc
      - after line 377 ("long endTime;"):
        add following code:

        ---------------------
        int clock_start_time = clock();
        int total_time = 0;
        ---------------------

      - after line 442: ( "} // else -- no projection")
        add following code:

        ---------------------
        // to output training time, objective value, and testing accuracy after each l step
        if( i % num_examples ==0){
              total_time += clock() - clock_start_time;
              norm_value = W.snorm();
              obj_value = norm_value * lambda / 2.0;
              loss_value = 0.0;

              for (uint j=0; j < Dataset.size(); ++j) {
              double cur_loss = 1 - Labels[j]*(W * Dataset[j]);
              if (cur_loss < 0.0) cur_loss = 0.0;
                    loss_value += cur_loss/num_examples;
                    obj_value += cur_loss/num_examples;
              }
              double error = 0.0;
              for (uint j=0; j < testDataset.size(); ++j) {
                    double cur_loss = 1.0 - testLabels[j]*(W * testDataset[j]);
                    if (cur_loss >= 1.0) error += 1.0;
              }
              if (testDataset.size() != 0) {
                    error /= testDataset.size();
              }

              printf("iter %d time %lf primalf %lf accuracy %lf\n",i, (double)total_time/CLOCKS_PER_SEC, obj_value/lambda, 1.0-error);
              clock_start_time = clock();
      }
      ---------------------

3. Type

% make

in directory 'pegasos' to build the package.

How to Install SVMPERF for Experiments
======================================

Download the .tar.gz file from

http://svmlight.joachims.org/svm_perf.html

then untar the zip file in directory "svmperf".

Follow the instrcutions to modify svmperf to output the training time,
objective value and testing accuracy after each steps:

1. svm_light/svm_common.h
     - modify line 38 as:

       ---------------------
       #define CFLOAT double
       ---------------------

     - modify line 42 as:

       ---------------------
       #define FVAL double
       ---------------------

       (We use double precision of floating point numbers in experiments)

2. svm_struct/svm_struct_main.c
     - add a global variable after line 40:

       ---------------------
           char testsamplefile[200]; /* file with testing examples*/
       ---------------------

     - line 77: add a parameter , "svm_learn_struct_joint(....., testsamplefile)"
     - line 79: add a parameter , "svm_learn_struct_joint(....., testsamplefile)"
     - line 81: add a parameter , "svm_learn_struct_joint(....., testsamplefile)"
     - add following codes after line 185
       ( "case 'y': i++; (*verbosity)=atol(argv[i]); break; " ):

       ---------------------
       case 'T': i++; strcpy(testsamplefile, argv[i]) ; break;
       ---------------------

3. svm_struct/svm_struct_learn.h,
     - modify line 71 as:

       ---------------------
       STRUCTMODEL *sm, int alg_type, char *testsamplefile);
       ---------------------

4. svm_struct_api.c
     - add following code after line 1320
       ( "if(!teststats->test_data_unlabeled) {" ):

       ---------------------
       int tmp = sparm->loss_function;
       ---------------------

     - add following code after line 1331:
       ( "teststats->avgprec=avgprec(ex.y,ypred);" ):

       ---------------------
       sparm->loss_function = tmp;
       ---------------------

5. svm_struct/svm_struct_learn.c,
     - modify line 463 as:

       ---------------------
       STRUCTMODEL *sm, int alg_type, char *testsamplefile)
       ---------------------

     - add following codes after line 498:
       ( "int cached_constraint;" ):

       ---------------------
       SAMPLE testsample;
       if(testsamplefile != NULL)
           testsample = read_struct_examples(testsamplefile, &sparm);
       ---------------------

     - add following codes after line 813
       ( "rt_total+=MAX(get_runtime()-rt1,0);" ):

       ---------------------
       // evalute runing time of each svmperf step
       printf("Runtime in cpu-seconds: %.2f\n",
           rt_total/100.0);

       // evalute primal objective value
       slacksum=0;
       for(j=0;j<cset.m;j++)
           slacksum=MAX(slacksum, \
               cset.rhs[j]-classify_example(svmModel,cset.lhs[j]));
       alphasum=0;
       for(i=0; i<cset.m; i++)
           alphasum+=alpha[i]*cset.rhs[i];
       modellength=model_length_s(svmModel,kparm);
       printf("Primal objective value: pval=%.6f\n",
           (0.5*modellength*modellength+sparm->C*(slacksum+ceps)) );

       // evalute dual objective value
       alphasum=0;
       for(i=0; i<cset.m; i++)
           alphasum+=alpha[i]*cset.rhs[i];

       modellength=model_length_s(svmModel,kparm);
       printf("Dual objective value: dval=%.6f\n",
           alphasum-0.5*modellength*modellength);

       LABEL y;
       STRUCT_TEST_STATS teststats;

       y = classify_struct_example(testsample.examples[0].x, sm, sparm);
       eval_prediction(0,testsample.examples[0],y,sm,sparm,&teststats);
       print_struct_testing_stats(testsample,sm,sparm,&teststats);
       ---------------------

6. Type

%make

in directory 'svmperf' to build the package.
