universvm/0000755000304100017630000000000011323365346011532 5ustar fabeekybuniversvm/usvm.cpp0000755000304100017630000020230511323365270013231 0ustar fabeekyb/*********************************************************************** * * UNIVERSVM IMPLEMENTATION * Copyright (C) 2005 Fabian Sinz Max Planck Institute for Biological Cybernetics * * Includes parts of LUSH Lisp Universal Shell: * Copyright (C) 2002 Leon Bottou, Yann Le Cun, AT&T Corp, NECI. * * Includes parts of libsvm. * * * This program is free software except for military or military related use; * If you don't come under the above exception you can redistribute it * and/or modify it under the terms of the GNU General Public License as * published by the Free Software Foundation; either version 2 of the * License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA * ***********************************************************************/ /* Version 1.2 - 16.10.2008 */ /* 16.10.2008 Fix bug (Matteo Roffilli - roffilli@csr.unibo.it): enable sorting in split_file_load function #include */ /* 16.10.2008 Fix bug (thanks to Enrico Angelini): kgamma should be fixed at 1/k as in LIBSVM kgamma=-1 */ /* 16.10.2008 Fix bug (thanks to Cash Costello): The documentation is not matching up with the code. The documentation says to set -V to 2 and -o to 1 for the ramp loss. I only see the ramp loss used if -V is set to 0. if (sample_type(sv->Aperm[ip[i]]) == TRAINSAMP && use_universum == RAMPUNI){ */ #ifdef _WIN32_ #include #include #include #include //Portability Update by Matteo Roffilli roffilli@csr.unibo.it #define NAN ((float)1e-30) /* Not A Number - Indicate a wrong or non significant value - Must always be tested, i.e. never assume that it's "close to zero, anyway" ! Could be any value, esp IEEE error or infinity formats. */ #else #include #include #include #include #include #include #endif #include "svqp2/svqp2.h" #include "svqp2/vector.h" #ifdef _WIN32_ int isnan(double x) { if(x<=NAN) return 1; else return 0; } #endif #ifdef MEX #include "mex.h" #endif // various kernels #define LINEAR 0 #define POLY 1 #define RBF 2 #define SIGMOID 3 #define CUSTOM 4 // different univserum training algorithms #define MULTIUNI 1 #define RAMPUNI 2 char *kernel_type_table[] = {"linear","polynomial","rbf","sigmoid","custom"}; char *optimizer_table[] = {"svqp2","cccp"}; #define SVQP 0 #define CCCP 1 #define ONLINE 1 #define ONLINE_WITH_FINISHING 2 #define VERYBIG pow(10.0,100) #define CCCP_TOL 0.0 #define TRAIN 0 #define TEST 1 #define UNIVERSUM 2 #define UNLABELED 3 #define SV 4 #define TRAINSAMP 0 #define UNIVESAMP 1 #define UNLABSAMP 2 #define EXTRASAMP 4 #define MAX_LOOPS 20 // maximum number of loops for tsvm training, should converge before this value, anyway.. #include #include #include /*********************** Split file storage class ******************/ class ID // class to hold split file indices and labels { public: int x; int y; ID() : x(0), y(0) {} ID(int x1,int y1) : x(x1), y(y1) {} }; // IDs will be sorted by index, not by label. bool operator<(const ID& x, const ID& y) { return x.x < y.x; } /*********************** Little Stopwatch class ******************/ using namespace std; class stopwatch { public: stopwatch() : start(std::clock()){} //start counting time ~stopwatch(); double get_time(){ clock_t total = clock()-start;; return double(total)/CLOCKS_PER_SEC; }; void reset(){ start= clock(); }; private: std::clock_t start; }; stopwatch::~stopwatch() { // clock_t total = clock()-start; //get elapsed time //cout<<"total of ticks for this activity: "< X; // feature vectors vector Y; // labels vector < vector > multi_Y; // labels for multiclass vector kparam; // kernel parameters vector x_square; // norms of input vectors, used for RBF vector data_map[5]; // maps to the indices of train/test/... data vector global_ext_K; // additional kernel column for transduction vector labels; // all different labels, that occured in the datafiles /* Variables for the model*/ vector alpha; // alpha_i, SV weights vector< vector > multi_alpha; // alpha_ij for multiclass vector multi_b0; // thresholds for multiclass double b0; // threshold int use_b0=1; // use threshold via constraint \sum a_i y_i =0 int kernel_type=LINEAR; // specifies the type of the kernel vector beta; // vector with betas for transduction vector Yest; // temporary vector to store the prediction vector < vector > D; // 2D vector to store the function values of the test points double C_star = VERYBIG; // C, penalty for the alpha of the special kernel column /* Algorithm parameters*/ double degree=3,kgamma=-1,coef0=0; // kernel params int cl=2; // number of classes int optimizer=SVQP; // strategy of optimization int folds=-1; // if folds=-1 --> no cross validation, else do folds fold CV int use_ext_K = 0; // use extra kernel column? int do_multi_class = 0; // do multiclass? int prob_size = 0; // size of the problem (different to dataset size!) int fill_level = 0; // temporary variable for setting up the problem /* Programm behaviour*/ char report_file_name[1024]; // filename for the training report char split_file_name[1024]="\0"; // filename for the splits int cache_size=256; // 256Mb cache size as default double epsgr=1e-3; // tolerance on gradients long long kcalcs=0; // number of kernel evaluations int binary_files=0; int use_universum = 0; // specifies the training algorithm used for universum vector splits; bool justtest = 0; // if justtest, then universvm tests on the specified model /* Other */ int seed=0; vector training_time; ///****************************** Functions *************************************/ void exit_with_help() { fprintf(stdout, "\nUSAGE: usvm [options] training_set_file [model_file]\n\n" "\n" "Trains a SVM, TSVM or USVM with specified parameters. If a model_file is\n" "specified after the training_set_file, then the learnt model will be stored\n" "there. If the model_file is supplied by the switch -F, then UniverSVM will\n" "test the specified model on the data that is supplied as training data and \n" "the test data supplied by -T. So\n" " universvm [options] -T testfile trainfile\n" "has the same effect as doing\n" " universvm [options] trainfile model \n" " universvm [options] -F model testfile\n" "\n" "OPTIONS:\n" "FILE/DATA OPTIONS:\n" "-T test_set_file: test model on test set\n" "-U universum_file : use universum (it's also possible to include universum points \n" " with label -2 in the training file)\n" "-F model_file : Test the model stored in model_file on training AND test data (specified by -T)\n" "-u unlabeled_data_file : use unlabeled data (transductive SVM).\n" " (it's also possible to include unlabeled points\n" " with label -3 in the training file)\n" "-B file format : files are stored in the following format:\n" " 0 -- libsvm ascii format (default)\n" " 1 -- binary format\n" " 2 -- split file format\n" "-f file : output report file to given destination\n" "-D file : output function values on test set(s) to given destination\n" "\nOPTIMIZATION OPTIONS:\n" "-V universum variant:\n" " 0 -- Standard universum training (default)\n" " 1 -- Train SVM with universum by making it a 3-class multiclass\n" " problem and adding the decision rules for {+1,U} vs. -1 and\n" " {-1,U} vs. +1 (0=off default)\n" " This switch works only for binary at the moment.\n" " 2 -- Train universum with ramp loss. This option requires \"-o 1\".\n" "-o optimizer: set different optimizers\n" " 0 -- quadratic programm\n" " 1 -- convex concave procedure (if you choose a transductive SVM,\n" " this option will be chosen automatically)\n" "-G gap : set gap parameter for universum (default 0.05) \n" "-I use_ridge : Add the ridge 1/C to the kernel matrix.\n" "-r coef0 : set coef0 in kernel function (default 0)\n" "-c cost : set the parameter C of C-SVC (default 1)\n" "-C cost : set the parameter C for universum points\n" "-a cost : set the parameter C for balancing constraint\n" "-z cost : set the parameter C for unlabeled points (defaul is z = (l/u)*C\n" " where l is the number of training points and u is the number of\n" " unlabeled points).\n" "-m cachesize : set cache memory size in MB (default 256)\n" "-e epsilon : set tolerance of termination criterion (default 0.001)\n" "-s s : s parameter for ramp loss (default: -1 )\n" "-S s : s parameter for transductive SVM loss (default: 0)\n" "\nMODEL OPTIONS:\n" "-t kernel_type : set type of kernel function (default 0)\n" " 0 -- linear: u'*v\n" " 1 -- polynomial: (gamma*u'*v + coef0)^degree\n" " 2 -- radial basis function: exp(-gamma*|u-v|^2)\n" " 3 -- sigmoid: tanh(gamma*u'*v + coef0)\n" " 4 -- custom: k(x_i,x_j) = X(i,j)\n" "-d degree : set degree in kernel function (default 3)\n" "-g gamma : set gamma in kernel function (default 1/k)\n" "-b bias: use constraint sum alpha_i y_i =0 (default 1=on)\n" "-w weight: set the coefficient for the \"extra example\" (balacing constraint)\n" " in the linear part of the optimization problem (default = sum(y_i)) \n" "-v n : do cross validation with n folds\n" "-M k : perform a multiclass training on k classes labeled with k different\n" "\tintegers >= 0 (default: 0)\n" ); exit(1); } // ******************* Parse Functions ************************************** void parse_command_line(int argc, char **argv, char *input_file_name, char *universum_file_name, char *testset_file_name, char *unlabeled_file_name, char *model_file_name, char *fval_file_name) { int i; // parse options for(i=1;i=argc) exit_with_help(); strcpy(input_file_name, argv[i]); if(i0) { if(splitpos<(int)splits.size() && splits[splitpos].x==msz) { v=lasvm_sparsevector_create(); X.push_back(v); splitpos++; } } else { v=lasvm_sparsevector_create(); X.push_back(v); } ++msz; //printf("%d\n",m); elements=0; break; case ':': ++elements; break; case EOF: goto out; default: ; } } out: rewind(fp); max_index = 0;splitpos=0; for(i=0;i0) { if(splitpos<(int)splits.size() && splits[splitpos].x==i) { write=2;splitpos++; } } else write=1; int label; fscanf(fp,"%d",&label); // printf("%d %d\n",i,label); if(write) { if(splits.size()>0) { if(splits[splitpos-1].y!=0 && splits[splitpos-1].y!=-99) Y.push_back(splits[splitpos-1].y); else Y.push_back(label); } else Y.push_back(label); } while(1) { int c; do { c = getc(fp); if(c=='\n') goto out2; } while(isspace(c)); ungetc(c,fp); fscanf(fp,"%d:%lf",&index,&value); if (write==1) lasvm_sparsevector_set(X[m+i],index,value); if (write==2) lasvm_sparsevector_set(X[m+splitpos-1],index,value); // <-- was this the (and the only) bug? if (index>max_index) max_index=index; } out2: label=1; // dummy } fclose(fp); msz=X.size()-m; printf("examples: %d features: %d\n",msz,max_index); return msz; } int binary_load_data(char *filename) { int msz,i=0,j; lasvm_sparsevector_t* v; int nonsparse=0; ifstream f; f.open(filename,ios::in|ios::binary); // read number of examples and number of features int sz[2]; f.read((char*)sz,2*sizeof(int)); if (!f) { printf("File writing error in line %d of %s.\n",i,filename); exit(1);} msz=sz[0]; max_index=sz[1]; vector val; vector ind; val.resize(max_index); if(max_index>0) nonsparse=1; int splitpos=0; for(i=0;i0) { if(splitpos<(int)splits.size() && splits[splitpos].x==i) { mwrite=1;splitpos++; v=lasvm_sparsevector_create(); X.push_back(v); } } else { mwrite=1; v=lasvm_sparsevector_create(); X.push_back(v); } if(nonsparse) // non-sparse binary file { f.read((char*)sz,1*sizeof(int)); // get label if(mwrite) { if(splits.size()>0 && (splits[splitpos-1].y!=0 && splits[splitpos-1].y!=-99)) Y.push_back(splits[splitpos-1].y); else Y.push_back(sz[0]); } f.read((char*)(&val[0]),max_index*sizeof(float)); if(mwrite) for(j=0;j0 && (splits[splitpos-1].y!=0 && splits[splitpos-1].y!=-99)) Y.push_back(splits[splitpos-1].y); else Y.push_back(sz[0]); } val.resize(sz[1]); ind.resize(sz[1]); f.read((char*)(&ind[0]),sz[1]*sizeof(int)); f.read((char*)(&val[0]),sz[1]*sizeof(float)); if(mwrite) for(j=0;jmax_index) max_index=ind[j]; } } } f.close(); msz=X.size()-m; printf("examples: %d features: %d\n",msz,max_index); return msz; } void load_data_file(char *filename) { int msz,i,ft; splits.resize(0); int bin=binary_files; if(bin==0) // if ascii, check if it isn't a split file.. { FILE *f=fopen(filename,"r"); if(f == NULL) { fprintf(stderr,"Can't open input file \"%s\"\n",filename); exit(1); } char c; fscanf(f,"%c",&c); if(c=='f') bin=2; // found split file! } switch(bin) // load diferent file formats { case 0: // libsvm format msz=libsvm_load_data(filename); break; case 1: msz=binary_load_data(filename); break; case 2: ft=split_file_load(filename); if(ft==0) {msz=libsvm_load_data(filename); break;} else {msz=binary_load_data(filename); break;} default: fprintf(stderr,"Illegal file type '-B %d'\n",bin); exit(1); } if(kernel_type==RBF) { x_square.resize(m+msz); for(i=0;i= -1) data_map[TRAIN].push_back(i); else if (Y[i] == -2) data_map[UNIVERSUM].push_back(i); // universum has -2 else if (Y[i] == -3) data_map[UNLABELED].push_back(i); // unlabeled has -3 } m_old = m; printf("\n"); //load universum data printf("Universum: \n"); if (universum_file_name[0] != '\0'){ load_data_file(universum_file_name); for(int i=m_old;i!=m;++i){ Y[i]=-2; data_map[UNIVERSUM].push_back(i); } } else printf("No Universum specified!\n"); m_old = m; printf("\n"); //load test data printf("Test Data: \n"); if (testset_file_name[0] != '\0'){ load_data_file(testset_file_name); printf("Done!\n"); for(int i=m_old;i!=m;++i){ data_map[TEST].push_back(i); } }else printf("No test set specified!\n"); m_old = m; printf("\n"); printf("Unlabeled Data: \n"); if (unlabeled_file_name[0] != '\0'){ load_data_file(unlabeled_file_name); printf("Done!\n"); for(int i=m_old;i != m;++i){ Y[i] =-3; data_map[UNLABELED].push_back(i); } }else printf("No unlabeled data specified!\n"); // if C for unlabeled = 0, it should not use it if (C3 == 0.0) data_map[UNLABELED].resize(0); // KEEP? printf("\n"); printf("\n\nData successfully loaded:\n \tNumber of training examples: %i\n \tNumber of test examples: %i\n",data_map[TRAIN].size(),data_map[TEST].size()); printf("\tNumber of unlabeled examples: %i\n \tNumber of examples in universum: %i\n\n",data_map[UNLABELED].size(),data_map[UNIVERSUM].size()); // uncomment in future version } void load_model_param(const char *model_file_name){ FILE *fp = fopen(model_file_name,"rb"); if(fp==NULL){ fprintf(stderr,"Model file does not exist!\n"); exit(1); } double alpha0 = 0.0; int num_sv = 0; // read parameters char cmd[81]; while(1) { fscanf(fp,"%80s",cmd); if(strcmp(cmd,"b0")==0){ fscanf(fp,"%lf",&b0); printf("\tb0: %g\n",b0); }else if(strcmp(cmd,"kernel_type")==0){ fscanf(fp,"%80s",cmd); int i = 0; for(i=0;kernel_type_table[i];++i){ if(strcmp(kernel_type_table[i],cmd)==0){ kernel_type=i; break; } } if (i == sizeof(kernel_type_table)){ fprintf(stderr,"kernel_type not know\n"); exit(1); }else{ printf("\tkernel_type: %s\n",kernel_type_table[kernel_type]); } }else if(strcmp(cmd,"degree")==0){ fscanf(fp,"%lf",°ree); printf("\tdegree: %g\n",degree); }else if(strcmp(cmd,"kgamma")==0){ fscanf(fp,"%lf",&kgamma); printf("\tkgamma: %g\n",kgamma); }else if(strcmp(cmd,"coef0")==0){ fscanf(fp,"%lf",&coef0); printf("\tcoef0: %g\n",coef0); }else if(strcmp(cmd,"alpha0")==0){ fscanf(fp,"%lf",&alpha0); printf("\talpha0: %g\n",alpha0); }else if(strcmp(cmd,"total_sv")==0){ fscanf(fp,"%d",&num_sv); printf("\tNumber of SVs: %d\n",num_sv); }else if(strcmp(cmd,"SV")==0){ while(1){ int c = getc(fp); if(c==EOF || c=='\n') break; } break; }else{ fprintf(stderr,"unknown text in model file\n"); exit(1); } } fclose(fp); } int load_model(const char *model_file_name) { FILE *fp = fopen(model_file_name,"rb"); if(fp==NULL){ fprintf(stderr,"Model file does not exist!\n"); exit(1); } double alpha0 = 0.0; int num_sv = 0; // read parameters char cmd[81]; while(1) { fscanf(fp,"%80s",cmd); if(strcmp(cmd,"b0")==0){ fscanf(fp,"%lf",&b0); printf("\tb0: %g\n",b0); }else if(strcmp(cmd,"kernel_type")==0){ fscanf(fp,"%80s",cmd); int i = 0; for(i=0;kernel_type_table[i];++i){ if(strcmp(kernel_type_table[i],cmd)==0){ kernel_type=i; break; } } if (i == sizeof(kernel_type_table)){ fprintf(stderr,"kernel_type not know\n"); exit(1); }else{ printf("\tkernel_type: %s\n",kernel_type_table[kernel_type]); } }else if(strcmp(cmd,"degree")==0){ fscanf(fp,"%lf",°ree); printf("\tdegree: %g\n",degree); }else if(strcmp(cmd,"kgamma")==0){ fscanf(fp,"%lf",&kgamma); printf("\tkgamma: %g\n",kgamma); }else if(strcmp(cmd,"coef0")==0){ fscanf(fp,"%lf",&coef0); printf("\tcoef0: %g\n",coef0); }else if(strcmp(cmd,"alpha0")==0){ fscanf(fp,"%lf",&alpha0); printf("\talpha0: %g\n",alpha0); }else if(strcmp(cmd,"total_sv")==0){ fscanf(fp,"%d",&num_sv); printf("\tNumber of SVs: %d\n",num_sv); }else if(strcmp(cmd,"SV")==0){ while(1){ int c = getc(fp); if(c==EOF || c=='\n') break; } break; }else{ fprintf(stderr,"unknown text in model file\n"); exit(1); } } // read sv_coef and SV int index; double value; int elements = 0; int msz = 0; int i =0; long pos = ftell(fp); lasvm_sparsevector_t* v; elements = 0; while(1){ int c = fgetc(fp); switch(c){ case '\n': v=lasvm_sparsevector_create(); X.push_back(v); ++msz; elements=0; break; case ':': ++elements; break; case EOF: goto out; default: ; } } out: fseek(fp,pos,SEEK_SET); max_index = 0; for(i=0;imax_index) max_index=index; } out2: if (tmp_alpha != 0) data_map[SV].push_back(m+i); else data_map[UNLABELED].push_back(m+i); //tmp_alpha=1.0; // dummy } fclose(fp); if (data_map[UNLABELED].size() > 0) alpha.push_back(alpha0); msz=X.size()-m; printf("examples: %d features: %d\n",msz,max_index); printf("|SV|: %d |unlabeled|: %d\n",data_map[SV].size(),data_map[UNLABELED].size()); return msz; } //******************* Kernel functions *********************** double kernel(int i, int j, void *kparam) { double dot; if (use_ext_K && (i == (int) X.size() || j == (int) X.size())){ return global_ext_K[min(i, j )]; } dot=lasvm_sparsevector_dot_product(X[i],X[j]); // sparse, linear kernel switch(kernel_type) { case LINEAR: break; case POLY: dot= pow(kgamma*dot+coef0,degree); break; case RBF: dot= exp(-kgamma*(x_square[i]+x_square[j]-2*dot)); break; case SIGMOID: dot=tanh(kgamma*dot+coef0); break; case CUSTOM: dot=lasvm_sparsevector_get(X[i],j); // was j+1, but this was wrong at least in the mex-wrapped version //printf("k(%d,%d)=%g\n", i, j, dot); break; } kcalcs++; if (i==j && ker_ridge!=0){ switch(sample_type(i)){ case UNIVESAMP: dot += 1/C2; break; case UNLABSAMP: dot += 1/C3; break; case TRAINSAMP: dot += 1/C; break; } } return dot; } void compute_extra_K(){ printf("Computing kernel values for extra column ..."); global_ext_K.resize(X.size()+1); for (int i = 0; i !=(int) X.size()+1; ++i) global_ext_K[i] = 0.0; // initialize with zero // if (C_star == 0.0 and !justtest){ if (C_star == 0.0 && !justtest){ printf(" [OK]\n"); return; // if the alpha for balancing is set to 0, there's nothing to do } for (int i = 0; i !=(int) X.size(); ++i){ for (int j = 0; j != (int) data_map[UNLABELED].size(); ++j){ global_ext_K[i] += kernel(i,data_map[UNLABELED][j],NULL); } global_ext_K[i] /= (double)data_map[UNLABELED].size(); } for (int i = 0; i !=(int) data_map[UNLABELED].size(); ++i){ global_ext_K[X.size()] += global_ext_K[data_map[UNLABELED][i]]; } global_ext_K[X.size()] /= (double)data_map[UNLABELED].size(); printf(" [OK]\n"); } int mt1,mt2; FILE *fp; /************************* Testing routines ******************************************/ double calc_multi_class_accuracy(vector< vector > *muYest){ int pred, acc; double max; acc = 0; for (int j = 0; j != (int) data_map[TEST].size(); ++j){ max =(*muYest)[0][j]; pred = labels[0]; for (int i = 1; i != do_multi_class; ++i){ if ((*muYest)[i][j] > max){ max = (*muYest)[i][j]; pred = labels[i]; } } if (Y[data_map[TEST][j]] == pred) ++acc; } printf("===========================================\n"); printf(" Accuracy= %g (%d/%d)\n",(acc/(double)data_map[TEST].size())*100,((int)acc),data_map[TEST].size()); printf("===========================================\n"); return 100 * (double)acc/(double)data_map[TEST].size(); } double test_current_model(char *fname){ int i,j; double y,balconstr; double acc=0; // don't add the ridge while testing on training data int ker_ridge_tmp; ker_ridge_tmp =ker_ridge; ker_ridge = 0; // clear vector that stores test results Yest.resize(0); D.resize(D.size()+1); for(i=0;i!=(int)data_map[TEST].size();++i){ y=b0; balconstr = 0.0; // calc kernel between the test and the mean of all unlabeled examples if (data_map[UNLABELED].size() > 0){ balconstr += global_ext_K[data_map[TEST][i]]; // add to decision function with unconstraint alpha y+=alpha[m]*balconstr;// alpha_0*K_i0 + b } // calc remaining part of decision function for(j=0;j=0) y=1; else y=-1; if(((int)y)==Y[data_map[TEST][i]]) acc++; } // store the function values for the report file for (int i = 0; i !=(int) Yest.size(); ++i) D[D.size()-1].push_back(Yest[i]); if (do_multi_class == 0){ printf("===========================================\n"); printf(" Accuracy= %g (%d/%d)\n",(acc/(double)data_map[TEST].size())*100,((int)acc),data_map[TEST].size()); printf("===========================================\n"); } // set back ker_ridge ker_ridge = ker_ridge_tmp; return (acc/(double)data_map[TEST].size())*100; } double test_current_multi_class_model(char *fname){ vector< vector > multi_Yest; multi_Yest.resize(do_multi_class); for (int i = 0; i != do_multi_class; ++i){ alpha = multi_alpha[i]; b0 = multi_b0[i]; test_current_model(fname); for (int j = 0; j != (int) data_map[TEST].size(); ++j){ multi_Yest[i].push_back(Yest[j]); } } if (!use_universum == MULTIUNI){ return calc_multi_class_accuracy(&multi_Yest); }else{ Yest.resize(0); int y = 0; int acc = 0; D.resize(D.size()+1); for (int i = 0; i !=(int) data_map[TEST].size(); ++i){ Yest.push_back(multi_Yest[0][i] *(double)labels[0] + multi_Yest[1][i]*(double)labels[1]); if (Yest[i] >= 0) y = 1; else y = -1; if (y == Y[data_map[TEST][i]]) ++acc; } for (int i = 0; i !=(int) Yest.size(); ++i) D[D.size()-1].push_back(Yest[i]); printf("===========================================\n"); printf(" Accuracy= %g (%d/%d)\n",(acc/(double)data_map[TEST].size())*100,((int)acc),data_map[TEST].size()); printf("===========================================\n"); return (acc/(double)data_map[TEST].size())*100; } } /*************************** postprocessing routines ************************************/ vector get_unswap_permutation(SVQP2* sv){ vector retval(sv->n); for (int i=0; i< sv->n; i++) retval[sv->pivot[i]] = i; return retval; } void set_alphas_b0(SVQP2* sv){ alpha.resize(0); b0 = 0; if (data_map[UNLABELED].size() > 0){ // add extra column alpha alpha.resize(m+1); // alpha of proportion of label constraint // alpha[m]+=sv->x[prob_size-1]; // fill in special alpha }else{ alpha.resize(m); // keeps as many alphas as vectors } // set all alphas to zero for(int i=0;i<(int)alpha.size();i++){ alpha[i]=0;} // only training vectors may have non-zero alpha for(int i=0;i< sv->n;i++){ alpha[sv->Aperm[i]]+=sv->x[i]; // fill in learnt svs if(sv->x[i]>maxa) maxa=(sv->x[i]); if(-(sv->x[i])>maxa) maxa=-(sv->x[i]); } if (optimizer == SVQP){ b0=(sv->gmin+ sv->gmax)/2.0; } //printf("Maximum alpha=%g\n",maxa); } /************************* preprocessing routines*********************************************/ void setup_standard_svm_problem(SVQP2* sv){ fill_level = 0; (*sv).verbosity=verbosity; (*sv).Afunction=kernel; (*sv).Aclosure=(void*) &kparam; (*sv).maxcachesize=(long int) 1024*1024*cache_size; (*sv).sumflag=use_b0; (*sv).epsgr=epsgr; for(int j=0;j<(int)data_map[TRAIN].size();++j){ sv->Aperm[fill_level] = data_map[TRAIN][j]; if (Y[data_map[TRAIN][j]] <0){ sv->b[fill_level]= -1; sv->cmin[fill_level]=-C; sv->cmax[fill_level]=0; }else{ sv->b[fill_level]= 1; sv->cmin[fill_level]=0; sv->cmax[fill_level]=C; } fill_level++; } } void extend_to_universum_problem(SVQP2* sv){ double switchoff = 1.0-(double)(use_universum==RAMPUNI);// don't update first loop for ramp universum prob. for(int j=0;j<(int)data_map[UNIVERSUM].size();++j){ // negative label universum point sv->Aperm[fill_level] = data_map[UNIVERSUM][j]; sv->b[fill_level]= -1 * -gap; sv->cmin[fill_level]=-C2*switchoff; sv->cmax[fill_level]=0; fill_level++; // positive label universum point sv->Aperm[fill_level] = data_map[UNIVERSUM][j]; sv->b[fill_level]= 1 * -gap; sv->cmin[fill_level]=0; sv->cmax[fill_level]=C2*switchoff; fill_level++; } } void setup_ramp_svm_problem(SVQP2* sv,bool firstloop){ if (firstloop){ printf("Setting up standard SVM problem..."); setup_standard_svm_problem(sv); }else{ vector ip = get_unswap_permutation(sv); printf("Updating ramp loss SVM problem..."); for(int j=0; j != sv->n;++j){ if (sample_type(sv->Aperm[ip[j]]) == TRAINSAMP){ if (Y[sv->Aperm[ip[j]]] == -1){ // negative label sv->cmin[ip[j]]=-C -beta[j]; sv->cmax[ip[j]]=-beta[j]; // initialized to zero }else{ // positive label sv->cmin[ip[j]]=-beta[j]; sv->cmax[ip[j]]=C -beta[j]; // initialized to zero } } } } printf("\t[OK]\n"); } void extend_to_tsvm_problem(SVQP2* sv,bool firstloop){ if (firstloop){ printf("Setting up transductive SVM problem..."); // add unlabeled points twice to problem; order - + - + ... for(int j=0;j<(int)data_map[UNLABELED].size();++j){ sv->Aperm[fill_level] = data_map[UNLABELED][j]; sv->b[fill_level]= -1; sv->cmin[fill_level]=0; sv->cmax[fill_level]=0; // initialized to zero fill_level++; sv->Aperm[fill_level] = data_map[UNLABELED][j]; sv->b[fill_level]= 1; sv->cmin[fill_level]=0; sv->cmax[fill_level]=0; // initialized to zero fill_level++; } // setup conditions for last special transductive column sv->cmin[sv->n -1] = -C_star; sv->cmax[sv->n -1] = C_star; sv->b[sv->n -1] = un_weight; sv->Aperm[sv->n -1] = X.size(); Y.push_back(-4); }else{ vector ip = get_unswap_permutation(sv); printf("Updating ramp loss transductive SVM problem..."); bool negsamp = 1; // change box constraint for new optimization problem with changed variables for(int j=0;jAperm[ip[j]]) == UNLABSAMP){ if (negsamp){ // negative label sv->cmin[ip[j]]=-C3-beta[j]; sv->cmax[ip[j]]=-beta[j]; // bounds for negative label unlabeled point negsamp = 0; }else{ // positive label sv->cmin[ip[j]]=-beta[j]; sv->cmax[ip[j]]=C3-beta[j]; // bounds for positive labeled unlabeled point negsamp = 1; } } } } printf("\t[OK]\n"); } void extend_to_ramp_universum_problem(SVQP2* sv,bool firstloop){ if (firstloop){ printf("Extending to SVM + universum problem..."); extend_to_universum_problem(sv); }else{ printf("Updating ramp loss SVM universum..."); // change box constraint for new optimization problem with changed variables bool negsamp = 1; vector ip = get_unswap_permutation(sv); for(int j=0; j < prob_size;++j){ if (sample_type(sv->Aperm[ip[j]]) == UNIVESAMP){ if (negsamp){ // negative label sv->cmin[ip[j]]=-C2-beta[j]; sv->cmax[ip[j]]=-beta[j]; // update bounds for negative label universum point negsamp = 0; }else{ // positive label sv->cmin[ip[j]]=-beta[j]; sv->cmax[ip[j]]=C2-beta[j]; // update bounds for positive labeled universum point negsamp = 1; } } } } printf("\t[OK]\n"); } /************************* optimization **********************************/ double do_ramp_loop(SVQP2* sv,bool firstiter){ double beta_diff = 0.0; double y; int extra = (int)(data_map[UNLABELED].size() > 0); double uniLabel = 0.0; int sparsity = 0; bool neg_uni = 1; bool neg_unlab = 1; sv->run(firstiter,false); // first run?, last run = false vector ip = get_unswap_permutation(sv); printf("Updating w and b ... "); vector fvals_without_b; // Cache kernel expansions for beta update for(int i=0;ix[ip[i]] != 0.0) ++sparsity; fvals_without_b.push_back(sv->b[ip[i]] - sv->g[ip[i]]); // y = f(x) - b } // compute b(t+1) b0 = (sv->gmin+ sv->gmax)/2.0; // compute beta(t+1) for training point but only if we are not doing any transduction for(int i=0;iAperm[ip[i]]) == TRAINSAMP && use_universum == RAMPUNI){ // determine new beta[i](t+1) if (Y[sv->Aperm[ip[i]]]*yAperm[ip[i]]]*C)*(beta[i]-Y[sv->Aperm[ip[i]]]*C); beta[i] = Y[sv->Aperm[ip[i]]]*C; }else{ beta_diff += (beta[i])*(beta[i]); beta[i] = 0.0; } }else if (sample_type(sv->Aperm[ip[i]]) == UNIVESAMP){ // compute beta(t+1) for universum point if (neg_uni){ // negative label uniLabel = -1.0; }else{ // positive label uniLabel = 1.0; } neg_uni = !neg_uni; if (uniLabel*yAperm[ip[i]]) == UNLABSAMP){ if (neg_unlab){ // negative label uniLabel = -1.0; }else{ // positive label uniLabel = 1.0; } neg_unlab = !neg_unlab; if (uniLabel*yrun(false,true); //cleanup hack return retval; //return mean quadratic error } void reset_alphas(SVQP2* sv){ for (int i = 0; i != sv->n;++i){ sv->x[i] = 0.0; } } /********************************** Saving Functions ************************************/ void print_fvals(char* fval_file_name){ FILE *fp2; fp2 = fopen(fval_file_name,"w"); fprintf(fp2,"\n# function values\n"); for (int i = 0; i !=(int) D.size(); ++i){ fprintf(fp2,"f{%i} = [ %g",i+1,D[i][0]); for (int j = 1; j != (int) D[i].size(); ++j) fprintf(fp2," ,%g",D[i][j]); fprintf(fp2,"];\n"); } fclose(fp2); } void print_model_file(char* model_file_name){ FILE *fp2; fp2 = fopen(model_file_name,"w"); fprintf(fp2,"b0 %g\n",b0); fprintf(fp2,"kernel_type %s\n",kernel_type_table[kernel_type]); fprintf(fp2,"kgamma %.15g\n",kgamma); fprintf(fp2,"degree %g\n",degree); fprintf(fp2,"coef0 %g\n",coef0); if (alpha.size() == m+1)// write out balancing constraint alpha fprintf(fp2,"alpha0 %.15g\n",alpha[m]); int num_sv = 0; for(int i=0;ipairs; p->index>=0; p++) { fprintf(fp2," %d:%.15g ", p->index, p->value); } fprintf(fp2,"\n"); } // write out unlabeled data for(int i=0;ipairs; p->index>=0; p++) { fprintf(fp2," %d:%.8g ", p->index, p->value); } fprintf(fp2,"\n"); } fclose(fp2); } void print_report(vector testerr){ FILE *fp2; fp2 = fopen(report_file_name,"w"); fprintf(fp2,"# data set sizes\n"); fprintf(fp2,"training=%i\n",data_map[TRAIN].size()); fprintf(fp2,"test=%i\n",data_map[TEST].size()); fprintf(fp2,"unlabeled=%i\n",data_map[UNLABELED].size()); //fprintf(fp2,"universum=%i\n",data_map[UNIVERSUM].size()); if (folds == -1){ fprintf(fp2,"\n# training parameters\n"); }else{ fprintf(fp2,"\n# %i-fold cross validation parameters\n",folds); } fprintf(fp2,"c=%g\n",C); fprintf(fp2,"C=%g\n",C2); fprintf(fp2,"z=%g\n",C3); fprintf(fp2,"t=%i\n",kernel_type); if (optimizer == CCCP) fprintf(fp2,"s=%g\n",s_ramp); fprintf(fp2,"G=%g\n",gap); if (data_map[UNLABELED].size() > 0){ fprintf(fp2,"S=%g\n",s_trans); fprintf(fp2,"_train=%g\n",un_weight); } switch (kernel_type){ case RBF: fprintf(fp2,"kernel=RBF\n"); fprintf(fp2,"g=%g\n",kgamma); break; case SIGMOID: fprintf(fp2,"kernel=SIGMOID\n"); fprintf(fp2,"r=%g\n",coef0); break; case POLY: fprintf(fp2,"kernel=POLY\n"); fprintf(fp2,"r=%g\n",coef0); fprintf(fp2,"d=%g\n",degree); break; default: fprintf(fp2,"kernel=LINEAR\n"); break; } fprintf(fp2,"r=%g\n",coef0); fprintf(fp2,"\n# algorithm parameters\n"); fprintf(fp2,"o=%i\n",optimizer); fprintf(fp2,"optimizer=%s\n",optimizer_table[optimizer]); fprintf(fp2,"Max_alpha=%g\n",maxa); fprintf(fp2,"\n# training times\n"); for (int i = 0; i !=(int) training_time.size(); ++i){ fprintf(fp2,"time %i =%g\n",i+1,training_time[i]); } fprintf(fp2,"\n# accuracies\n"); for (int i = 0; i !=(int) testerr.size()-1; ++i){ fprintf(fp2,"fold %i =%g\n",i+1,testerr[i]); } fprintf(fp2,"mean accuracy=%g\n",testerr[testerr.size()-1]); fclose(fp2); } /********************************************************************************************/ void setup_problem(SVQP2* sv){ if (optimizer == SVQP && data_map[UNLABELED].size() == 0){ setup_standard_svm_problem(sv); if (data_map[UNIVERSUM].size() > 0){// train SVQP with universum? extend_to_universum_problem(sv); } }else if (optimizer == CCCP || data_map[UNLABELED].size() > 0){ if (data_map[UNLABELED].size() > 0){ // train transductive svm? b0 = 0.0; if (isnan(un_weight)) { un_weight = 0.0; for (int i = 0; i !=(int) data_map[TRAIN].size();++i){ un_weight += (double)Y[data_map[TRAIN][i]]; } un_weight /= (double) data_map[TRAIN].size(); } if (optimizer == CCCP){ setup_ramp_svm_problem(sv,1); }else{ setup_standard_svm_problem(sv); } beta.resize(0); for (int i = 0; i != prob_size; ++i){ beta.push_back(0.0); } if (data_map[UNIVERSUM].size() > 0){// train transductive CCCP with universum? extend_to_ramp_universum_problem(sv,1); } // extend to unlabeled problem if (data_map[UNLABELED].size() > 0) extend_to_tsvm_problem(sv,1); }else{ // train non-transductive svm beta.resize(0); b0 = 0.0; // initialize loop variables for (int i = 0; i != prob_size; ++i){ beta.push_back(0.0); } setup_ramp_svm_problem(sv,1); if (data_map[UNIVERSUM].size() > 0){// train CCCP with universum? extend_to_ramp_universum_problem(sv,1); } } } } void training(SVQP2* sv){ printf("\nTraining ...\n"); stopwatch* stop = new stopwatch(); double start_time; stop->reset(); start_time = stop->get_time(); if (data_map[UNLABELED].size() > 0) use_ext_K = 1; if (optimizer == SVQP && data_map[UNLABELED].size() == 0){ sv->run(true,true); }else if(optimizer == CCCP || data_map[UNLABELED].size() > 0){ double beta_diff = 1.0; beta_diff = do_ramp_loop(sv,1); int numloops=0; while ((beta_diff > CCCP_TOL) && numloops 0) {// train CCCP with universum? extend_to_ramp_universum_problem(sv,0); } } if (data_map[UNLABELED].size() > 0) {// train transductive CCCP? extend_to_tsvm_problem(sv,0); } reset_alphas(sv); beta_diff = do_ramp_loop(sv,0); } if(numloops==MAX_LOOPS) {printf("Max number of loops exceeded!\n");} use_ext_K = 0; } training_time.push_back(stop->get_time()-start_time); delete stop; printf("\nTraining done ...\n"); } void search_for_different_labels(){ labels.resize(0); bool found = 0; for (int i = 0; i !=(int) Y.size(); ++i) { for (int j = 0; j != (int) labels.size(); ++j) { if (Y[i] < -1 || Y[i] == labels[j]){ found = 1; break;} } if (!found && Y[i]>=-1) labels.push_back(Y[i]); if ((int) labels.size() == do_multi_class && do_multi_class != 0) break; found = 0; } } void setup_labels_for_multiclass(){ printf("Setting up labels for multiclass ..."); multi_Y.resize(do_multi_class); for (int j = 0; j != (int) Y.size(); ++j){ for (int i = 0; i != do_multi_class; ++i){ if (Y[j] == labels[i]) multi_Y[i].push_back(1); else if (Y[j] < 0) multi_Y[i].push_back(Y[j]); else multi_Y[i].push_back(-1); } } printf("\t[OK]\n"); } void multi_class_training(){ /* Do single multi-class training and testing */ vector Ybck = Y; SVQP2* sv; for (int i = 0; i != do_multi_class; ++i){ sv = new SVQP2(prob_size); Y = multi_Y[i]; setup_problem(sv); printf("---------------------------------\n"); printf(" Training %i vs. Rest\n",labels[i]); printf(" Overall size of training set: %i\n",sv->n); printf("---------------------------------\n"); training(sv); // processing results set_alphas_b0(sv); multi_alpha[i].resize(0); for (int j = 0; j != (int) alpha.size(); ++j){ multi_alpha[i].push_back(alpha[j]); } multi_b0.push_back(b0); delete sv; } Y = Ybck; } void setup_folds(vector < vector >* a, vector < vector >* b){ // store train and test indices in trainfolds and testfolds // generate folds ... // get training data vector < vector > label_map; label_map.resize(labels.size()); // get indices of positive and negative labels for (int i = 0; i !=(int) data_map[TRAIN].size(); ++i){ for (int k = 0; k != (int) labels.size(); ++k){ if (Y[data_map[TRAIN][i]] == labels[k]){ label_map[k].push_back(data_map[TRAIN][i]); break; } } } int balancecv=0; vector props; props.resize(labels.size()); int propsum = 0; for (int k = 0; k != (int) labels.size(); ++k){ // for each label props[k] = label_map[k].size()/folds; // count how many we can put in each fold propsum += props[k]; if (props[k] < 1){ printf("Warning: making sure each fold has enough training examples of each class, using subsampling instead.\n"); balancecv=1; } } (*a).resize(folds); (*b).resize(folds); vector pointers; for (int k = 0; k != (int) labels.size(); ++k) pointers.push_back(0); if(!balancecv){ for (int i = 0; i != folds-1; ++i){ // get training vectors before testfold for (int k = 0; k != (int) labels.size(); ++k){ for (int j = 0; j != (int) pointers[k]; ++j){ (*a)[i].push_back(label_map[k][j]); } } // get test fold for (int k = 0; k != (int) labels.size(); ++k){ for (int j = pointers[k]; j != (int) pointers[k] + props[k]; ++j){ (*b)[i].push_back(label_map[k][j]); } } // update pointers for (int k = 0; k != (int) labels.size(); ++k){ pointers[k] += props[k]; } // get training vectors after testfold for (int k = 0; k != (int) labels.size(); ++k){ for (int j = pointers[k]; j != (int) label_map[k].size(); ++j){ (*a)[i].push_back(label_map[k][j]); } } } // get training vectors before testfold for (int k = 0; k != (int) labels.size(); ++k){ for (int j = 0; j != (int) pointers[k]; ++j){ (*a)[folds-1].push_back(label_map[k][j]); } } // get the remaining stuff in test fold for (int k = 0; k != (int) labels.size(); ++k){ for (int j = pointers[k]; j != (int) label_map[k].size(); ++j){ (*b)[folds-1].push_back(label_map[k][j]); } } }else{// force to add a point from each class int i,j,k,p,q; //printf("jasons method on %d splits, %d labels %d %d\n",folds,labels.size(),labels[0],labels[1]); int labs=labels.size(); vector data; int train_m = data_map[TRAIN].size(); //train_m was =m before. for(i=0;i accus; D.resize(0); int training_set_size = 0; // remember training set size for special universum training parse_command_line(argc, argv, input_file_name, universum_file_name, testset_file_name,unlabeled_file_name,model_file_name, fval_file_name); // overwrite parameter configureation with the stored one if (justtest) load_model_param(model_file_name); /** Catch some errors **/ if (use_universum == MULTIUNI && do_multi_class){ printf("%i\n", use_universum); fprintf(stderr,"Error: Universum Training with multiclass does not support multiclass at the moment.\n"); return 1; } /**------------------**/ printf("---------------------------------\n"); printf(" Initialization \n"); printf("---------------------------------\n"); if(split_file_name[0]!='\0') split_file_load(split_file_name); load_data(input_file_name, universum_file_name, testset_file_name,unlabeled_file_name); search_for_different_labels(); // check how many different labels we have (universum and unlabeled excluded) printf("Data contains %i classes \n\n",labels.size()); // set default value for z (=C3) if (C3 < 0) C3 = (((double)data_map[TRAIN].size())/((double)data_map[UNLABELED].size()))*C; if (!justtest){// if we train a model for (int i = 0; i != do_multi_class; ++i){ printf(" Training %i vs. Rest\n",labels[i]); } prob_size = data_map[TRAIN].size() + data_map[UNIVERSUM].size()*2 + data_map[UNLABELED].size()*2; if (data_map[UNLABELED].size() > 0){ ++prob_size; // last special column for transductive constraint compute_extra_K(); // setup extended column } // train SVQP2* sv = new SVQP2(prob_size); // catch special training switch for universum if (use_universum == MULTIUNI){ printf("Setting up labels for multiclass universum training ... "); training_set_size = data_map[TRAIN].size(); prob_size -= data_map[UNIVERSUM].size(); int newLab = max(labels[0],labels[1])+1; labels.push_back(newLab); for (int i = 0; i !=(int) data_map[UNIVERSUM].size();++i){ data_map[TRAIN].push_back(data_map[UNIVERSUM][i]); Y[data_map[UNIVERSUM][i]] = newLab; } data_map[UNIVERSUM].resize(0); do_multi_class = 3; printf(" [OK]\n"); } sv = new SVQP2(prob_size); if (folds == -1){ // no cv if (do_multi_class == 0){ printf("---------------------------------\n"); printf(" Training \n"); printf("---------------------------------\n"); setup_problem(sv); training(sv); // processing results set_alphas_b0(sv); // test printf("---------------------------------\n"); printf(" Testing \n"); printf("---------------------------------\n"); if (data_map[TEST].size() > 0){ printf("Testing on test set with %i examples:\n",data_map[TEST].size()); accus.push_back(test_current_model(model_file_name)); }else{ printf("Testing on training set with %i examples:\n",data_map[TRAIN].size()); data_map[TEST] = data_map[TRAIN]; accus.push_back(test_current_model(model_file_name)); ///test_current_model(model_file_name); } delete sv; }else{ ///////////////// Start multi_class /////////////////////////////// multi_alpha.resize(do_multi_class); setup_labels_for_multiclass(); if (use_universum == MULTIUNI) --do_multi_class; multi_class_training(); printf("---------------------------------\n"); printf(" Testing \n"); printf("---------------------------------\n"); if (data_map[TEST].size() > 0){ printf("Testing on test set with %i examples:\n",data_map[TEST].size()); }else{ if (use_universum == MULTIUNI) data_map[TRAIN].resize(training_set_size); printf("Testing on training set with %i examples:\n",data_map[TRAIN].size()); data_map[TEST] = data_map[TRAIN]; } accus.push_back(test_current_multi_class_model(model_file_name)); } ///////////////// End multi_class /////////////////////////////// }else{ vector < vector > trainfold, testfold; setup_folds(&trainfold, &testfold); double meanacc = 0.0; double foldacc; if (do_multi_class > 0) setup_labels_for_multiclass(); for (int fold = 0; fold != folds; ++fold){ data_map[TRAIN] = trainfold[fold]; data_map[TEST] = testfold[fold]; prob_size = data_map[TRAIN].size() + data_map[UNIVERSUM].size()*2 + data_map[UNLABELED].size()*2; if (data_map[UNLABELED].size() > 0) ++prob_size; // last special column for transductive constraint printf("---------------------------------\n"); printf(" Training fold (%i/%i)\n",fold+1,folds); printf(" Overall size of training set: %i\n",prob_size); printf("---------------------------------\n"); if (do_multi_class == 0){ SVQP2* sv = new SVQP2(prob_size); setup_problem(sv); training(sv); // processing results set_alphas_b0(sv); foldacc = test_current_model(model_file_name); meanacc += foldacc; accus.push_back(foldacc); delete sv; }else{ multi_alpha.resize(do_multi_class); multi_class_training(); printf("---------------------------------\n"); printf(" Testing \n"); printf("---------------------------------\n"); if (data_map[TEST].size() > 0){ printf("Testing on test set with %i examples:\n",data_map[TEST].size()); }else{ printf("Testing on training set with %i examples:\n",data_map[TRAIN].size()); data_map[TEST].resize(0); for (int i = 0; i !=(int) data_map[TRAIN].size(); ++i) data_map[TEST].push_back(data_map[TRAIN][i]); } foldacc = test_current_multi_class_model(model_file_name); meanacc += foldacc; accus.push_back(foldacc); } } meanacc /= double(folds); accus.push_back(meanacc); printf("===========================================\n"); printf("\nMean Cross Validation Accuracy: %g\n", meanacc); printf("===========================================\n"); } if (report_file_name[0] != '\0'){ print_report(accus); } if (model_file_name[0] != '\0'){ print_model_file(model_file_name); } }else{ printf("Loading model file...\n"); alpha.resize(0); for (int i = 0; i != m; ++i) alpha.push_back(0.0); // set all alpha's of nonSV to zero data_map[SV].resize(0); data_map[UNLABELED].resize(0); int msz = load_model(model_file_name); if(kernel_type==RBF){ x_square.resize(m+msz); for(int i=0;i 0){ use_ext_K = 1; compute_extra_K(); } // we are testing on the data sepcified with -T and training for (int i = 0; i != data_map[TRAIN].size(); ++i){ data_map[TEST].push_back(data_map[TRAIN][i]); } test_current_model(model_file_name); } if (fval_file_name[0] != '\0'){ print_fvals(fval_file_name); } return 0; } #endif #ifdef MEX void mexFunction( int nlhs, // Number of left hand side (output) arguments mxArray *plhs[], // Array of left hand side arguments int nrhs, // Number of right hand side (input) arguments const mxArray *prhs[] // Array of right hand side arguments ) { double *X_; double *Y_; char cmd_[1000]; int argc; char *argv[100]; char input_file_name[1024]; input_file_name[0] = '\0'; char model_file_name[1024]; model_file_name[0] = '\0'; vector accus; D.resize(0); int training_set_size = 0; // remember training set size for special universum training if (nrhs!=3) mexErrMsgTxt("3 input arguments needed.\n"); if (nlhs!=2) mexErrMsgTxt("2 output arguments needed.\n"); m = mxGetM (prhs[0]); max_index = mxGetN (prhs[0]); X_ = mxGetPr(prhs[0]); if (mxGetM(prhs[1]) != m) mexErrMsgTxt("Dimension error.\n"); Y_ = mxGetPr(prhs[1]); mxGetString(prhs[2],cmd_,1000); argv[1] = cmd_; argc = 2; for (char *p=cmd_; *p != '\0'; p++) { if (*p == ' ') { *p = '\0'; while (*(++p) == ' '); argv[argc++] = p; } } argv[argc++] = "dummy file"; parse_command_line(argc, argv, input_file_name, NULL, NULL, NULL, NULL, NULL); lasvm_sparsevector_t* v; for (int i=0; i= -1) data_map[TRAIN].push_back(i); else if (Y[i] == -2) data_map[UNIVERSUM].push_back(i); // universum has -2 else if (Y[i] == -3) data_map[UNLABELED].push_back(i); // unlabeled has -3 for (int j=0; j 0){ ++prob_size; // last special column for transductive constraint compute_extra_K(); // setup extended column } // train SVQP2* sv = new SVQP2(prob_size); // catch special training switch for universum if (use_universum == MULTIUNI){ printf("Setting up labels for multiclass universum training ... "); training_set_size = data_map[TRAIN].size(); prob_size -= data_map[UNIVERSUM].size(); int newLab = max(labels[0],labels[1])+1; labels.push_back(newLab); for (int i = 0; i !=(int) data_map[UNIVERSUM].size();++i){ data_map[TRAIN].push_back(data_map[UNIVERSUM][i]); Y[data_map[UNIVERSUM][i]] = newLab; } data_map[UNIVERSUM].resize(0); do_multi_class = 3; printf(" [OK]\n"); } sv = new SVQP2(prob_size); if (do_multi_class == 0){ printf("---------------------------------\n"); printf(" Training \n"); printf("---------------------------------\n"); setup_problem(sv); training(sv); // processing results set_alphas_b0(sv); plhs[0] = mxCreateDoubleMatrix(alpha.size(),1,mxREAL); // array for alphas double *p=mxGetPr(plhs[0]); for (int i=0; i< alpha.size(); i++) p[i]= alpha[i]; plhs[1] = mxCreateDoubleMatrix(1,1,mxREAL); *mxGetPr(plhs[1]) = b0; delete sv; }else{ ///////////////// Start multi_class /////////////////////////////// multi_alpha.resize(do_multi_class); setup_labels_for_multiclass(); if (use_universum == MULTIUNI) --do_multi_class; multi_class_training(); plhs[0] = mxCreateDoubleMatrix(alpha.size(),do_multi_class,mxREAL); // array for alphas plhs[1] = mxCreateDoubleMatrix(1,do_multi_class,mxREAL); double *p1=mxGetPr(plhs[0]); double *p2=mxGetPr(plhs[1]); for (int i=0; i #include #include "messages.h" lasvm_message_t lasvm_message_level = LASVM_INFO; lasvm_message_proc_t *lasvm_message_proc = 0; static void defaultproc(lasvm_message_t level, const char *fmt, va_list ap) { if (level <= lasvm_message_level) vprintf(fmt, ap); #ifdef LUSH if (level <= LASVM_ERROR) { extern void run_time_error(const char *s); run_time_error("lasvm error"); } #endif if (level <= LASVM_ERROR) abort(); } void lasvm_error(const char *fmt, ...) { lasvm_message_proc_t *f = lasvm_message_proc; va_list ap; va_start(ap,fmt); if (! f) f = defaultproc; (*f)(LASVM_ERROR,fmt,ap); va_end(ap); abort(); } void lasvm_warning(const char *fmt, ...) { lasvm_message_proc_t *f = lasvm_message_proc; va_list ap; va_start(ap,fmt); if (! f) f = defaultproc; (*f)(LASVM_WARNING,fmt,ap); va_end(ap); } void lasvm_info(const char *fmt, ...) { lasvm_message_proc_t *f = lasvm_message_proc; va_list ap; va_start(ap,fmt); if (! f) f = defaultproc; (*f)(LASVM_INFO,fmt,ap); va_end(ap); } void lasvm_debug(const char *fmt, ...) { lasvm_message_proc_t *f = lasvm_message_proc; va_list ap; va_start(ap,fmt); if (! f) f = defaultproc; (*f)(LASVM_DEBUG,fmt,ap); va_end(ap); } void lasvm_assertfail(const char *file,int line) { lasvm_error("Assertion failed: %s:%d\n", file, line); } universvm/svqp2/svqp2.o0000644000304100017630000004671011323365270014044 0ustar fabeekybELF>+@@ HHtHGHt HBHGHG~HFH7HGH8HHxHHGAUAATUHSC\-HHuLcDHHB<)HcHJ<HIHIcHMbP?H<HMXB LH4I#B ;HU(HHHHEHEHE Le8EHHU0HcHHHcHHELLEPHEpDžDžHU@H@xDHHU`HcDHcHHHHHHDžHEhƅDžHHDžHEHHAE1HDH:HH9uH11@HHE HA9LE(1f.HHHM@HU0HHE8I0HH9HHHuH[]A\A]f.AUAATUHSC\-HHuLcDHHB<)HcHJ<HIHIcB H<LH4I#B ;IMbP?I@xDHU(HHHHEHEHE Le8EHHU0HcHHHcHHELL]PLUXLM`HEpHU@HcDHcHHHHDžDžHHHDžHHEhHƅDžHDžEHHAE1HDH:HH9uH11@HHE HA9LE(1f.HHHM@HU0HHE8I0HH9HHHuH[]A\A]f.H\$Ld$1Hl$Ll$H(oI9tn~FHcHAt$I|$ II11fD9Ή~!AH9 fDH E1HA\$t)Ml$ HcHH\$Hl$Ld$Ll$ H(ÐfHl$Ll$HcLt$H\$ILd$L|$HHHAֈL$LHD4ffDATUHSHHOhIH9~Yt]H9EhƅI|1>1HI1HHLL;eh~HHH9u[]LA\DHH51HHfffff.ATUSHH 9fWD${HL$tK`fWȀ{HD$tC`DCxD$ELHK@1LC(f(1f.A f.vHC8f.vCxf.vHC0f.vKxAAXH9YXf(YH []A\@@_HcLLHfDIIH9fWE11D$@AHA9HK@L)A\(f.T$ztH$S1DH{H$9}HcH HfH HHHZY9\AHA9VDLL1HK@L1IIHIH9fDHcLLC(HfIIH9fW1E1D$@I9YHK@B!f.T$ztH$S1ɉH{H$9}HcH HfH HHHZY9\YfWD$ATAUHcSHHHG@H\f.zuH[]A\DH$S1DHDK$E~>H11fDHHHHZY9K\HS@HHHH[]A\Ðf.AWAVAUATUSHHXHcDHD$8E~1HD$8BH9HT$@fEWAD$,D$0HT$HEHT$fWfD.OHIcMcHJ Bf.vHDLf(EIAHHHCxHD$8L8HD$8T$0H8T$0D$,D$0;}9D$,HDHDHIH{@NHS0L[8HL D$7JCHT$\\f.v f(D$7CXKPA\B\Zf.\Kx^f.f(E1XڋLHC@\~A11fAH\HH9ZY\ŃED|$@Dt$DtgSPCB \f.rHD$1BXfB.s|$7DHA@fEWEDHDALT$fEWED EIcHDD9HLk8L[@ELc0H@ AAlA4\\eHH1H11HHHHZY9\̃@DH@XfWf.wHD`LHS@HC8\AHEfW%H5HH|$t H|$H[]A\A]A^A_1ٻH|$Hft H|$H@AUAATAUHSHDGEH@UPHu0f(fWf(\f.HM811\ f.v9fDLf(\Df.v\LHf.bD9uEqEL~ H=HDžDž1DžHfDHfWD\UxfWHH5Hf(f(fTfUfVf($EX$f.}HH$$HfW\UxfW9f(f(fTfUfVo}L~f(HH5AH$}H$WH$$WEt@Et8EL~H=$$H$H$~/DH1f(HH[]A\A]f.HHH5[]A\A]EEL~ H=H1HH[]A\A]Df(AHH51[a5 SVQP2 error: %s @ Setting up cache ...* it:%d l:%d |g|:%f w:%f *. it:%d l:%d |g|:%f .! it:%d l:%d |g|:%f ! it:%d l:%d |g|:%f w:%f @ Reached maxcachesize (%ld MB) Function is not convex (negative curvature)Initial x[] does not satisfy inequality constraint Cleaning and unswapping cache...5SVQP2?zPLRx $P,<FBEA D(I0,lFBEA D(I0Z0$\J^P4BBE E(A0D8D@AH$< AEG0,dBBE A(A0$BDA RH RH,SH4LBEB B(A0A8DPJL ZJO$BAD $BAA G@$BDD G04<DBBB B(A0A8G4t,BBB B(A0A8GP,BED D(D@GCC: (Ubuntu 4.3.3-5ubuntu4) 4.3.3.symtab.strtab.shstrtab.rela.text.data.bss.gcc_except_table.rodata.str1.1.rodata.str1.8.rela.data.rel.ro._ZTV5SVQP2.rodata._ZTS5SVQP2.rela.data.rel.ro._ZTI5SVQP2.rodata.cst8.rodata.cst16.rodata.cst4.rela.eh_frame.rela.data.DW.ref.__gxx_personality_v0.comment.note.GNU-stack.group%@,%HP%PO%XR `7$8>H &$,$1$MC2$R2x%f@& aJH ~`&p&J0&& &&J*M *$**,(3) :G        $). (4: @ )F CL \R qX ^ sd Xj Ep ZvPPF! F\!3 FU h}  0 @ R RS`  %+9ZP_f`0D, !!+!svqp2.cpp.LC4.LC5.LC6.LC7.LC8.LC3.LC9.LC10.LC11.LC14.LC15.LC16.LC19.LC20.LC13.LC21.LC12.LC17.LC18_ZN5SVQP24Arow6refileEPS0__ZN5SVQP2C1Ei_GLOBAL_OFFSET_TABLE__ZTV5SVQP2_Znam_ZN5SVQP2C2Ei_ZN5SVQP24Arow6resizeEi_ZdaPv_ZN5SVQP26getrowEiib_ZN5SVQP210cache_swapEii_ZN5SVQP24swapEii_ZN5SVQP26shrinkEv_Unwind_Resume_ZN5SVQP26unswapEv__gxx_personality_v0_ZN5SVQP24ArowD1Ev_ZN5SVQP24ArowD2Ev_ZN5SVQP210cache_finiEv_ZdlPv_ZN5SVQP2D1Ev_ZN5SVQP2D2Ev_ZN5SVQP2D0Ev_ZN5SVQP210cache_initEv_Znwm_ZN5SVQP25errorEPKcstdoutfputc__fprintf_chk_ZN5SVQP24infoEPKcS1_z__vfprintf_chkfflush_ZN5SVQP211cache_cleanEv_ZN5SVQP28unshrinkEb_ZN5SVQP26togbarEi_ZN5SVQP211iterate_gs2Ev_ZN5SVQP211iterate_gs1Ev_ZN5SVQP23runEbbputs_ZTI5SVQP2_ZTS5SVQP2_ZTVN10__cxxabiv117__class_type_infoEDW.ref.__gxx_personality_v0h ,--- ,--.-"-r0+)E/))/,  3 34 -| 3 0 5 8 ; 8! ;C ,S :d 0u 0 , : 0 0 ,:$050F0r:@-@ 05M B[Cm|D Bc BFGN/c)EH1H1H1I-`Hv11J>y3J(0@HAh0p5-H1]~JQ Y Am 0 0 5 i!n!Nv!?!I!I!!"EC"Ka"4"""E"L%#/#NA#:I#6t# #E#!##N#:#6 $"'$# 2 0 0 0 0 0O;0#AO<>QPR(@Pp @ h q  0 @  0P`Y `@0I%x9 7universvm/svqp2/svqp2.cpp0000755000304100017630000004313211323365270014366 0ustar fabeekyb// -*- C++ -*- /*********************************************************************** * * LUSH Lisp Universal Shell * Copyright (C) 2002 Leon Bottou, Yann Le Cun, AT&T Corp, NECI. * Includes parts of TL3: * Copyright (C) 1987-1999 Leon Bottou and Neuristique. * Includes selected parts of SN3.2: * Copyright (C) 1991-2001 AT&T Corp. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA * ***********************************************************************/ /*********************************************************************** * $Id: svqp2.cpp,v 1.7 2006/01/27 06:56:13 agbs Exp $ **********************************************************************/ ////////////////////////////////////// /// /// SVQP2 uses a gauss-seidel/smo method. /// It also implements proper caching etc. /// /// Leon Bottou - 2004 /// ///////////////////////////////////// #include "svqp2.h" #include #include #include #ifndef GBAR # define GBAR 1 #endif #ifndef HMG # define HMG 1 #endif // --------- utilities template class vec { private: T *d; public: vec(int n) : d(new T[n]) { } ~vec() { delete [] d; } T& operator[](int n) { return d[n]; } const T& operator[](int n) const { return d[n]; } operator T*() { return d; } operator const T*() { return d; } private: vec(const vec&); T& operator=(const vec&); }; template inline T min(T a, T b) { if (a < b) return a; else return b; } template inline T max(T a, T b) { if (a < b) return b; else return a; } template inline void exch(T &v1, T &v2) { T tmp = v1; v1 = v2; v2 = tmp; } // --------- messages void SVQP2::info(const char *s1, const char *s2, ...) { if (verbosity > 0) { const char *fmt = s1; if (s2 && (verbosity>1 || vdots>=40 || !fmt)) fmt = s2; if (fmt && fmt[0]) { va_list ap; va_start(ap, s2); vfprintf(stdout, fmt, ap); va_end(ap); fflush(stdout); vdots += 1; if (fmt[1]) vdots = 0; } } } int SVQP2::error(const char *message) { if (verbosity>0 && vdots>0) fprintf(stdout,"\n"); if (verbosity>0) fprintf(stdout,"SVQP2 error: %s\n", message); errmsg = message; return -1; } // --------- cache struct SVQP2::Arow { Arow *prev; Arow *next; int ai; int sz; #if HMG float diag; #endif float *d; public: Arow(int); ~Arow(); void refile(Arow *after); long resize(int nsz); }; inline SVQP2::Arow::Arow(int ai) : prev(0), next(0), ai(ai), sz(0), d(0) { } SVQP2::Arow::~Arow() { delete [] d; } void SVQP2::Arow::refile(Arow *after) { if (prev && next) { prev->next = next; next->prev = prev; } if (sz > 0) { next = after->next; prev = after; next->prev = this; prev->next = this; } else { prev = 0; next = 0; } } long SVQP2::Arow::resize(int nsz) { if (nsz != sz) { float *nd = 0; if (nsz > 0) { nd = new float[nsz]; for (int i=0; inext = lru; lru->prev = lru; vec c(n); for (int i=0; iai != ai) p = p->next; if (! p) { p = new Arow(ai); #if HMG p->diag = (*Afunction)(ai, ai, Aclosure); #endif p->next = c[h]; c[h] = p; } rows[i] = p; } } void SVQP2::cache_fini() { if (lru) { Arow *l = 0; for (int i=0; iprev = rows[i]->next = 0; for (int i=0; iprev) { rows[i]->next = l; l = rows[i]; l->prev = l; rows[i] = 0; } while (l) { Arow *n = l; l = l->next; delete n; } curcachesize = 0; delete lru; lru = 0; } } long SVQP2::cache_clean() { if (curcachesize > maxcachesize) { if (! hitcache) info("@","@ Reached maxcachesize (%ld MB)\n",(maxcachesize>>20)); hitcache = true; while ((curcachesize > maxcachesize) && (lru->prev != lru)) { Arow *p = lru->prev; curcachesize += p->resize(0); p->refile(0); } } return curcachesize; } void SVQP2::cache_swap(int i, int j) { if (lru) { exch(rows[i],rows[j]); Arow *row = lru->next; while (row != lru) { Arow *nextrow = row->next; if (i < row->sz) { if (j < row->sz) exch(row->d[i], row->d[j]); else curcachesize += row->resize(i); } else { if (j < row->sz) curcachesize += row->resize(j); } row = nextrow; } } } float * SVQP2::getrow(int i, int len, bool hot) { Arow *row = rows[i]; int osz = row->sz; if (osz >= len) { if (hot) row->refile(lru); return row->d; } curcachesize += row->resize(len); float *d = row->d; int ai = Aperm[i]; for (int j=osz; jrefile(lru); else if (! osz) row->refile(lru->prev); return d; } void SVQP2::swap(int i, int j) { if (i != j) { exch(Aperm[i], Aperm[j]); exch(b[i], b[j]); exch(cmin[i], cmin[j]); exch(cmax[i], cmax[j]); exch(x[i], x[j]); exch(g[i], g[j]); #if GBAR exch(gbar[i], gbar[j]); exch(xbar[i], xbar[j]); #endif exch(pivot[i], pivot[j]); cache_swap(i,j); } } void SVQP2::unswap(void) { vec rpivot(n); for (int i=0; i gmax) && (x[i] < cmax[i])) gmax = gi; if ((gi < gmin) && (x[i] > cmin[i])) gmin = gi; } if (sumflag) { for (int i=0; i= gmax) && (x[i] >= cmax[i]-epskt)) || ((gi <= gmin) && (x[i] <= cmin[i]+epskt)) ) swap(i--, --l); } } else { for (int i=0; i= 0) && (x[i] >= cmax[i]-epskt)) || ((gi <= 0) && (x[i] <= cmin[i]+epskt)) ) swap(i--, --l); } } } void SVQP2::unshrink(bool usegbar) { if (l < n) { #if GBAR if (usegbar) { // recompute gradients from gbar for (int i=l; i gmax) && (x[i] < cmax[i])) gmax = gi; if ((gi < gmin) && (x[i] > cmin[i])) gmin = gi; sum += xi * (b[i] + g[i]); } w = sum / 2; } // --------- iterate #define RESULT_FIN 0 #define RESULT_SHRINK 1 int SVQP2::iterate_gs1() { int icount = 0; int pcount = 0; vec mark(l); for(int i=0; i gmax) && (x[i] < cmax[i])) { gmax = gi; imax = i; } if ((gi < gmin) && (x[i] > cmin[i])) { gmin = gi; imin = i; } } if (gmin + gmax < 0) imax = imin; bool down = (g[imax]<0); // Exit tests if (gmax - gmin < epsgr) return RESULT_FIN; icount += 1; if (! mark[imax]) pcount += 2; mark[imax] = true; if (pcount= epskt) { ostep = fabs(g[imax]) / curvature; if (ostep < step) { hit = false; step = ostep; } } else if (curvature + epskt < 0) return error("Function is not convex (negative curvature)"); // update x and g if (down) step = - step; x[imax] += step; for (int j=0; j mark(l); for(int i=0; isz < l) continue; float *arow = rows[i]->d; double cmaxi = cmax[i]-x[i]; double cmini = cmin[i]-x[i]; for (int j=0; j=epsgr && cmaxi>epskt && x[j]-cmin[j]>epskt) { step = min(cmaxi, x[j]-cmin[j]); curvature = arow[i] + rows[j]->diag - 2*arow[j]; step = min(step * curvature, gradient); } else if (gradient<=-epsgr && cmini<-epskt && x[j]-cmax[j]<-epskt) { step = max(cmini, x[j]-cmax[j]); curvature = arow[i] + rows[j]->diag - 2*arow[j]; step = max(step * curvature, gradient); } else continue; gain = step * ( 2 * gradient - step ); if (gain > maxgain * curvature) { maxgain = gain / curvature; imin = i; imax = j; } } } } if (maxgain > 0) { if (g[imin] > g[imax]) exch(imin, imax); gmax = g[imax]; gmin = g[imin]; } else { imax = imin = -1; #endif // Determine extreme gradients gmax = -maxst; gmin = maxst; for (int i=0; i gmax) && (x[i] < cmax[i])) { gmax = gi; imax = i; } if ((gi < gmin) && (x[i] > cmin[i])) { gmin = gi; imin = i; } } // Exit tests if (gmax - gmin < epsgr) return RESULT_FIN; #if HMG } #endif if (! mark[imax]) pcount += 1; mark[imax] = true; if (! mark[imin]) pcount += 1; mark[imin] = true; icount += 1; if (pcount= epskt) { ostep = (gmax - gmin) / curvature; if (ostep < step) { hit = false; step = ostep; } } else if (curvature + epskt < 0) return error("Function is not convex (negative curvature)"); // update x and g x[imax] += step; x[imin] -= step; for (int j=0; j=cmax[imax]-epskt) if (x[imin]<=cmin[imin]+epskt) flag = false; #endif #if GBAR if (down) togbar(imin); else togbar(imax); #endif } } } // --------- run int SVQP2::run(bool first, bool last) { int status = 0; double gn = maxst; // check constraints for (int i = 0; i != n; ++i) if (x[i] - cmin[i] < -epskt || x[i] - cmax[i] > epskt){ // fprintf(stderr,"%g < %g or %g > %g or %g: \n",x[i],cmin[i],x[i],cmax[i],x[i]-cmin[i],x[i]-cmax[i]); return error("Initial x[] does not satisfy inequality constraint"); } // pseudo optimization: I just unswaps the cache and does a cache_fini if (!first && last){ if (verbosity > 0) printf("\nCleaning and unswapping cache...\n"); cache_fini(); unswap(); return 0; } // prepare in the first iteration if (first){ if (verbosity > 0) printf("\nSetting up cache ...\n"); cache_init(); } vdots = 0; iter = 0; l = 0; unshrink(false); // loop for(;;) { // incorporate unshrink(true); gn = max(0.0, gmax-gmin); info("*","* it:%d l:%d |g|:%f w:%f\n", iter, l, gn, w); // test termination if (gn < epsgr) break; // minimize for(;;) { if (sumflag) status = iterate_gs2(); else status = iterate_gs1(); if (status <= RESULT_FIN) break; // shrink int p = l; shrink(); // display gn = max(0.0, gmax-gmin); if (l < p) info(".",". it:%d l:%d |g|:%f\n", iter, l, gn); else if (verbosity >= 3) info("!","! it:%d l:%d |g|:%f\n", iter, l, gn); } if (status < 0) break; } // finish // finish if there's no iterated optimization if (first && last){ if (verbosity > 0) printf("\nCleaning and unswapping cache...\n"); cache_fini(); unswap(); } if (status < 0) return status; if (vdots>0) info(0," it:%d l:%d |g|:%f w:%f\n", iter, l, gn, w); return iter; } universvm/svqp2/vector.h0000755000304100017630000000577311323365270014273 0ustar fabeekyb/*********************************************************************** * * LUSH Lisp Universal Shell * Copyright (C) 2002 Leon Bottou, Yann Le Cun, AT&T Corp, NECI. * Includes parts of TL3: * Copyright (C) 1987-1999 Leon Bottou and Neuristique. * Includes selected parts of SN3.2: * Copyright (C) 1991-2001 AT&T Corp. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA * ***********************************************************************/ /*********************************************************************** * $Id: vector.h,v 1.4 2006/01/27 06:56:13 agbs Exp $ **********************************************************************/ #ifndef VECTOR_H #define VECTOR_H #include #include #ifdef __cplusplus__ extern "C" { #if 0 } #endif #endif /* ------------------------------------- */ /* SIMPLE VECTORS */ typedef struct lasvm_vector_s { int size; float data[1]; } lasvm_vector_t; lasvm_vector_t *lasvm_vector_create(int size); void lasvm_vector_destroy(lasvm_vector_t *v); double lasvm_vector_dot_product(lasvm_vector_t *v1, lasvm_vector_t *v2); /* ------------------------------------- */ /* SPARSE VECTORS */ typedef struct lasvm_sparsevector_pair_s { int index; float value; } lasvm_sparsevector_pair_t; typedef struct lasvm_sparsevector_s { int size; int maxsize; lasvm_sparsevector_pair_t *pairs; } lasvm_sparsevector_t; lasvm_sparsevector_t *lasvm_sparsevector_create(void); void lasvm_sparsevector_destroy(lasvm_sparsevector_t *v); void lasvm_sparsevector_clear(lasvm_sparsevector_t *v); void lasvm_sparsevector_set(lasvm_sparsevector_t *v, int index, double data); double lasvm_sparsevector_get(lasvm_sparsevector_t *v, int index); lasvm_sparsevector_t *lasvm_sparsevector_combine(lasvm_sparsevector_t *v1, double coeff1, lasvm_sparsevector_t *v2, double coeff2); double lasvm_sparsevector_dot_product(lasvm_sparsevector_t *v1, lasvm_sparsevector_t *v2); /* lasvm_sparsevector_foreach -- To iterate on the sparsevector pairs. Use as follows: lasvm_sparsevector_t *v = somevector(); lasvm_sparsevector_pair_t *p; lasvm_sparsevector_foreach(p, v) { printf(" %d:%.8g", p->index, p->value); } */ #define lasvm_sparsevector_foreach(p, v) \ for(p=v->pairs; p->index>=0; p++) #ifdef __cplusplus__ } #endif #endif universvm/svqp2/messages.h0000755000304100017630000000526211323365270014571 0ustar fabeekyb/*********************************************************************** * * LUSH Lisp Universal Shell * Copyright (C) 2002 Leon Bottou, Yann Le Cun, AT&T Corp, NECI. * Includes parts of TL3: * Copyright (C) 1987-1999 Leon Bottou and Neuristique. * Includes selected parts of SN3.2: * Copyright (C) 1991-2001 AT&T Corp. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA * ***********************************************************************/ /*********************************************************************** * $Id: messages.h,v 1.2 2005/11/16 03:58:41 agbs Exp $ **********************************************************************/ #ifndef MESSAGES_H #define MESSAGES_H #include #ifdef __cplusplus__ extern "C" { #if 0 } #endif #endif /* Message levels */ typedef enum { LASVM_ERROR, LASVM_WARNING, LASVM_INFO, LASVM_DEBUG } lasvm_message_t; /* lasvm_message_level --- Default routine will print every message more severe than this. */ extern lasvm_message_t lasvm_message_level; /* lasvm_message_proc --- The routine to handle messages. The default routine will print everything with message level less than lasvm_message_level and abort when message level is LASVM_ERROR. */ typedef void lasvm_message_proc_t(lasvm_message_t, const char*, va_list); extern lasvm_message_proc_t *lasvm_message_proc; /* lasvm_error, lasvm_warning, lasvm_info, lasvm_debug --- Convenience functions to display messages and signal errors. */ extern void lasvm_error(const char *fmt, ...); extern void lasvm_warning(const char *fmt, ...); extern void lasvm_info(const char *fmt, ...); extern void lasvm_debug(const char *fmt, ...); /* ASSERT --- Macro for quickly inserting debugging checks. */ #ifdef NDEBUG # define ASSERT(x) /**/ #else # define ASSERT(x) do { if (!(x))\ lasvm_assertfail(__FILE__,__LINE__);\ } while(0) #endif void lasvm_assertfail(const char *file,int line); #ifdef __cplusplus__ } #endif #endif universvm/svqp2/svqp2.h0000755000304100017630000001260211323365270014031 0ustar fabeekyb// -*- C++ -*- /*********************************************************************** * * LUSH Lisp Universal Shell * Copyright (C) 2002 Leon Bottou, Yann Le Cun, AT&T Corp, NECI. * Includes parts of TL3: * Copyright (C) 1987-1999 Leon Bottou and Neuristique. * Includes selected parts of SN3.2: * Copyright (C) 1991-2001 AT&T Corp. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA * ***********************************************************************/ /*********************************************************************** * $Id: svqp2.h,v 1.4 2006/01/27 06:56:13 agbs Exp $ **********************************************************************/ ////////////////////////////////////// /// /// SVQP2 uses a gauss-seidel/smo method. /// It also implements proper caching etc. /// /// Leon Bottou - 2004 /// ///////////////////////////////////// // ================================================================ // Quadratic Program Solver // ================================================================ // SVQP2 - abstract class for convex programming class SVQP2 { // Maximize - 1/2 x.A.x + b.x // with Cmin_i <= x_i <= Cmax_i // and (optionally) sum_i x_i = constant public: // DESTRUCTOR. virtual ~SVQP2(); // CONSTRUCTOR: // Argument 'n' is the dimension of vectors x,b,cmin,cmax. // The constructor allocates all arrays. // The user must then set all input variables properly. // These are marked as 'MANDATORY INPUT' or 'OPTIONAL INPUT' SVQP2(int n); // READ-ONLY VARIABLE: // Dimension of the problem. // This is set by the constructor. const int n; // MANDATORY INPUT: AFUNCTION, ACLOSURE, APERM // Matrix A is represented by several variables. // Element A[i][j] is accessed as // (*Afunction)(Aperm[i], Aperm[j], Aclosure); // Array Aperm[] initially contains 1...n but can be changed. // Cache space is not wasted when the same integer appears twice. double (*Afunction)(int, int, void *); void *Aclosure; int *Aperm; // MANDATORY INPUT: B, CMIN, CMAX // Space is already allocated for these vectors. // The initial value, 0, must be replaced. double *b; double *cmin; double *cmax; // MANDATORY INPUT/OUTPUT: X // You must provide a feasible X as initial input. // This vector is initially set to 0 which might not be feasible. double *x; // OPTIONAL INPUT: SUMFLAG // This flag indicates whether the equality constraint // should be considered. Default: true. bool sumflag; // OPTIONAL INPUT: VERBOSITY // Set this to 0 for quiet operation. // Set this to 2 for very verbose operation. // Set this to 3 to enable more debugging code. int verbosity; // OPTIONAL INPUTS: // - EPSKT is the tolerance for checking KKT conditions (default 1e-20) // - EPSGR is the maximal L0 norm of the gradient on exit (default 1e-3) // - MAXST is the maximal conjugate gradient step (default 1e20) double epskt; double epsgr; double maxst; // OPTIONAL INPUT: MAXCACHESIZE // Size in bytes of the cache of kernel values. // Default: 256M. long maxcachesize; // PUBLIC FUNCTION: run // Runs the solver. // Returns -1 on error, >=0 otherwise. int run(bool,bool); // OUTPUT: ERRMSG // Error message const char *errmsg; // OUTPUT: GMIN, GMAX, W // - W is the optimal value of the objective function // - GMIN, GMAX are the active gradient bounds. // The SVM threshold is (GMIN+GMAX)/2... double gmin; double gmax; double w; double *g ; // [l] Gradient int *pivot; // [n] Pivoting vector // INTERNAL protected: int iter; // total iterations int l; // Active set size double *xbar ; // [n] Another x double *gbar ; // [n] Gradient at xbar long curcachesize; // Current cache size struct Arow; // Cached rows Arow **rows; // [n] Cached rows Arow *lru; // Most recently used cache row double *dmem; // Allocated memory int *imem; // Allocated memory int vdots; // Infodot counter bool hitcache; // Did I hit the cache size limit. protected: void info(const char*, const char *, ...); int error(const char *message); void cache_init(void); void cache_fini(void); long cache_clean(void); void cache_swap(int, int); float *getrow(int, int, bool hot=true); void swap(int, int); void unswap(void); void togbar(int); void shrink(void); void unshrink(bool); int iterate_gs1(void); int iterate_gs2(void); private: SVQP2(const SVQP2&); SVQP2& operator=(const SVQP2&); }; universvm/svqp2/vector.o0000644000304100017630000001532011323365270014264 0ustar fabeekybELF> @@ 9fWɉN~$fW1DYDH9ZXf(fDHOHvfWɋfxx9~Hyf(@}HffDAHYFHZXSHHHtHCH[ffff.DHl$H\$H~;}HcH<HcHHt5+HHl$H\$HfH=GDH=1LOAAxQ1HcI 9u,FfDDBD9'BDHcI 9t9|؍zD9~fW@AZATUSHHCHCAHH~hH{11HHDH;3|A9|&DHc)HLHDHDHH9uHtHkDcH[]A\1H{H=1FH=1dfAWAVAUIATUSH8/LOf.zLcNI~11HIHA;6|9'Hc)I HDI@HH9uHtT$$$T$WA^Mf1@MxIAU9EHcHIăZY‰MffZ@yDAUx7HcIĐAEIAUZYffZ@Hyэ{AHcHHcHHmA6RI~11DHHDHA;6|9.Hc)HLHDHDfHH9uHtInA^H []A\A]LA^~6AEHcIIăZYÉffZ@MAEZZYYXffZ.ztHcÃIHHIFfDHcIfEHMZYffZ@HyN1I~1I~DH=1H=1$T$(svqp2/vector.cFunction malloc() has returned zero zPRx $:<hT#Al xN yBFA 4BBB E(A0A8Fp }AAG ,,>BBB D(A0GPGCC: (Ubuntu 4.3.3-5ubuntu4) 4.3.3.symtab.strtab.shstrtab.rela.text.data.bss.rodata.str1.1.rodata.str1.8.rodata.cst8.rela.eh_frame.rela.data.DW.ref.__gxx_personality_v0.comment.note.GNU-stack.group@  P & , 12 @2 %OH aP X\ p k  $    u    :J@h# x";Opy} >DY! vector.c.LC1.LC2.LC0_Z24lasvm_vector_dot_productP14lasvm_vector_sS0__Z30lasvm_sparsevector_dot_productP20lasvm_sparsevector_sS0__Z26lasvm_sparsevector_destroyP20lasvm_sparsevector_s_GLOBAL_OFFSET_TABLE_free_Z20lasvm_vector_destroyP14lasvm_vector_s_Z19lasvm_vector_createimalloc_Z16lasvm_assertfailPKci_Z11lasvm_errorPKcz_Z22lasvm_sparsevector_getP20lasvm_sparsevector_si_Z25lasvm_sparsevector_createv_Z22lasvm_sparsevector_setP20lasvm_sparsevector_sid_Z24lasvm_sparsevector_clearP20lasvm_sparsevector_s_Z26lasvm_sparsevector_combineP20lasvm_sparsevector_sdS0_d__gxx_personality_v0DW.ref.__gxx_personality_v0C M[ b+   $ Jp wP     (@@Xpp0universvm/svqp2/messages.o0000644000304100017630000000726011323365270014575 0ustar fabeekybELF>8@@  HHT$0Ht$(HHDHL$8LD$@LL$HHH)H$)x)p)h)`)X)P)H)@HH$D$0HH$HD$HD$ HHD$HlHDHfffff.HHT$0Ht$(HHDHL$8LD$@LL$HHH)H$)x)p)h)`)X)P)H)@HH$D$0HH$HD$HD$ HHD$HHDHfffff.HHT$0Ht$(HHDHL$8LD$@LL$HHH)H$)x)p)h)`)X)P)H)@HH$D$0HH$HD$HD$ HHD$HHDHfffff.HHT$0Ht$(HH?LD$@LL$HHL$8HH)H$)x)p)h)`)X)P)H)@HH$D$0HH$HD$HD$ HHD$H1HD1@HH=1ffff.HS;8~ ~"[@HHHH8Assertion failed: %s:%d zPRx $G<GTGlG9HGCC: (Ubuntu 4.3.3-5ubuntu4) 4.3.3.symtab.strtab.shstrtab.rela.text.data.bss.rodata.str1.1.rela.eh_frame.rela.data.DW.ref.__gxx_personality_v0.comment.note.GNU-stack.group@ PI &,12E@ TpO vx$8 p   : 9  A FZp@ ! messages.c_ZL11defaultproc15lasvm_message_tPKcP13__va_list_tag.LC0_Z11lasvm_debugPKcz_GLOBAL_OFFSET_TABLE_lasvm_message_proc_Z10lasvm_infoPKcz_Z13lasvm_warningPKcz_Z11lasvm_errorPKczabort_Z16lasvm_assertfailPKcilasvm_message_levelstdout__vfprintf_chk__gxx_personality_v0DW.ref.__gxx_personality_v0j *     + >E(@Xp@universvm/svqp2/vector.c0000755000304100017630000001545211323365270014261 0ustar fabeekyb/*********************************************************************** * * LUSH Lisp Universal Shell * Copyright (C) 2002 Leon Bottou, Yann Le Cun, AT&T Corp, NECI. * Includes parts of TL3: * Copyright (C) 1987-1999 Leon Bottou and Neuristique. * Includes selected parts of SN3.2: * Copyright (C) 1991-2001 AT&T Corp. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA * ***********************************************************************/ /*********************************************************************** * $Id: vector.c,v 1.4 2006/01/27 06:56:13 agbs Exp $ **********************************************************************/ #include #include #include #include #include "messages.h" #include "vector.h" #ifdef __cplusplus__ #define this mythis #define or myor #define and myand #endif #ifndef min # define min(a,b) (((a)<(b))?(a):(b)) #endif #ifndef max # define max(a,b) (((a)>(b))?(a):(b)) #endif static void* xmalloc(int n) { void *p = malloc(n); if (! p) lasvm_error("Function malloc() has returned zero\n"); return p; } /* ------------------------------------- */ /* SIMPLE VECTORS */ lasvm_vector_t * lasvm_vector_create(int size) { lasvm_vector_t *v; ASSERT(size>1); v = (lasvm_vector_t*)xmalloc(sizeof(lasvm_vector_t) + (size-1)*sizeof(double)); v->size = size; return v; } void lasvm_vector_destroy(lasvm_vector_t *v) { v->size = 0; free(v); } double lasvm_vector_dot_product(lasvm_vector_t *v1, lasvm_vector_t *v2) { int i; int n = min(v1->size, v2->size); double sum = 0; for (i=0; idata[i] * v2->data[i]; return sum; } /* ------------------------------------- */ /* SPARSE VECTORS */ static void resize(lasvm_sparsevector_t *v, int n) { int i; lasvm_sparsevector_pair_t *newpairs; if (n < v->size) n = v->size; newpairs = (lasvm_sparsevector_pair_t*)xmalloc(sizeof(lasvm_sparsevector_pair_t)*(n+1)); for (i=0; isize; i++) newpairs[i] = v->pairs[i]; for (; i<=n; i++) newpairs[i].index = -1; if (v->pairs) free(v->pairs); v->pairs = newpairs; v->maxsize = n; } static lasvm_sparsevector_pair_t * makeroom(lasvm_sparsevector_t *v) { int n = v->size + v->size/2; if (n < v->size + 16) n = v->size + 16; resize(v, n); return v->pairs; } lasvm_sparsevector_t * lasvm_sparsevector_create(void) { lasvm_sparsevector_t *v; v = (lasvm_sparsevector_t*)xmalloc(sizeof(lasvm_sparsevector_t)); v->size = 0; v->maxsize = 0; v->pairs = 0; makeroom(v); return v; } void lasvm_sparsevector_clear(lasvm_sparsevector_t *v) { v->size = 0; resize(v, 0); } void lasvm_sparsevector_destroy(lasvm_sparsevector_t *v) { if (v->pairs) free(v->pairs); v->pairs = 0; free(v); } static lasvm_sparsevector_pair_t * search(lasvm_sparsevector_t *v, int index) { int lo = 0; int hi = v->size - 1; lasvm_sparsevector_pair_t *pairs = v->pairs; while (lo <= hi) { int d = (lo + hi + 1) / 2; if (index == pairs[d].index) return &pairs[d]; else if (index < pairs[d].index) hi = d-1; else lo = d+1; } return 0; } double lasvm_sparsevector_get(lasvm_sparsevector_t *v, int index) { lasvm_sparsevector_pair_t *p = search(v, index); return (p) ? p->value : 0; } void lasvm_sparsevector_set(lasvm_sparsevector_t *v, int index, double value) { int size = v->size; lasvm_sparsevector_pair_t *pairs = v->pairs; if (value) { if (index>pairs[size-1].index && sizemaxsize) { // quick append pairs[size].index = index; pairs[size].value = value; v->size = size + 1; } else { lasvm_sparsevector_pair_t *p = search(v, index); if (p) { // update p->value = value; } else { // insert int i; if (size >= v->maxsize) pairs = makeroom(v); for (i=size; i>0 && pairs[i-1].index>index; i--) pairs[i] = pairs[i-1]; pairs[i].index = index; pairs[i].value = value; v->size = size + 1; } } } else { lasvm_sparsevector_pair_t *p = search(v, index); if (p) { // remove int i; for (i=p-pairs; i<=size; i++) pairs[i] = pairs[i+1]; v->size = size - 1; } } } lasvm_sparsevector_t * lasvm_sparsevector_combine(lasvm_sparsevector_t *v1, double c1, lasvm_sparsevector_t *v2, double c2) { int k = 0; lasvm_sparsevector_pair_t *pairs; lasvm_sparsevector_pair_t *p1 = v1->pairs; lasvm_sparsevector_pair_t *p2 = v2->pairs; lasvm_sparsevector_t *r = lasvm_sparsevector_create(); resize(r, v1->size + v2->size); pairs = r->pairs; while (p1->index>=0 && p2->index>=0) { if (p1->index < p2->index) { pairs[k].index = p1->index; pairs[k].value = c1 * p1->value; k++; p1++; } else if (p1->index > p2->index) { pairs[k].index = p2->index; pairs[k].value = c2 * p2->value; k++; p2++; } else { float value = c1 * p1->value + c2 * p2->value; if (value) { pairs[k].index = p1->index; pairs[k].value = value; k++; } p1++; p2++; } } while (p1->index>=0) { pairs[k].index = p1->index; pairs[k].value = c1 * p1->value; k++; p1++; } while (p2->index>=0) { pairs[k].index = p2->index; pairs[k].value = c2 * p2->value; k++; p2++; } r->size = k; resize(r, k); return r; } double lasvm_sparsevector_dot_product(lasvm_sparsevector_t *v1, lasvm_sparsevector_t *v2) { double sum = 0; lasvm_sparsevector_pair_t *p1 = v1->pairs; lasvm_sparsevector_pair_t *p2 = v2->pairs; while (p1->index>=0 && p2->index>=0) { if (p1->index < p2->index) p1++; else if (p1->index > p2->index) p2++; else { sum += p1->value * p2->value; p1++; p2++; } } return sum; } universvm/build_windows.bat0000644000304100017630000000101611323365346015071 0ustar fabeekybrem Makefile for univerSVM software (c) 2005 for .NET 2005 console rem by Matteo Roffilli - roffilli@csr.unibo.it rem rem tested also on Windows Vista + .NET 2008 console del *.obj del universvm.exe cl /EHsc /D_CRT_SECURE_NO_DEPRECATE /TP /Ox /W3 /c svqp2/vector.c cl /EHsc /D_CRT_SECURE_NO_DEPRECATE /TP /Ox /W3 /c svqp2/messages.c cl /EHsc /D_CRT_SECURE_NO_DEPRECATE /TP /Ox /W3 /c svqp2/svqp2.cpp cl /EHsc /D_WIN32_ /D_CRT_SECURE_NO_DEPRECATE /Ox /W3 /Feuniversvm.exe vector.obj messages.obj svqp2.obj usvm.cpp universvm/Makefile0000755000304100017630000000276011323365270013176 0ustar fabeekyb#Makefile for univerSVM software (c) 2005 CXX= g++ MEXFLAGS= -DMATLAB_MEX_FILE -DMEX USEMEXFLAGS= CFLAGS= -O3 SVQPSRC= svqp2/svqp2.cpp svqp2/vector.c svqp2/messages.c USVM= universvm USVM64= universvm64 LSVM2BIN= libsvm2bin BIN2LSVM= bin2libsvm USVMSRC= usvm.cpp LSVM2BINSRC= libsvm2bin.cpp BIN2LSVMSRC= bin2libsvm.cpp MEX = ./mex svqp: $(SVQPSRC) $(CXX) $(CFLAGS) $(USEMEXFLAGS) -fPIC -o svqp2/vector.o -c svqp2/vector.c $(CXX) $(CFLAGS) $(USEMEXFLAGS) -fPIC -o svqp2/messages.o -c svqp2/messages.c $(CXX) $(CFLAGS) $(USEMEXFLAGS) -fPIC -o svqp2/svqp2.o -c svqp2/svqp2.cpp mex: $(USVMSRC) $(SVQPSRC) make "USEMEXFLAGS=$(MEXFLAGS)" svqp $(MEX) $(MEXFLAGS) $(USVMSRC) svqp2/svqp2.o svqp2/messages.o svqp2/vector.o universvm: $(USVMSRC) $(CXX) $(CFLAGS) $(USEMEXFLAGS) -o $(USVM) $(USVMSRC) $(SVQPSRC) $(ONLINESRC) -lm universvm64: $(USVMSRC) $(CXX) $(CFLAGS) $(USEMEXFLAGS) -o $(USVM64) $(USVMSRC) $(SVQPSRC) $(ONLINESRC) -lm libsvm2bin: $(LSVM2BINSRC) $(CXX) $(CFLAGS) $(USEMEXFLAGS) -o $(LSVM2BIN) $(LSVM2BINSRC) $(SVQPSRC) $(ONLINESRC) -lm bin2libsvm: $(BIN2LSVMSRC) $(CXX) $(CFLAGS) $(USEMEXFLAGS) -o $(BIN2LSVM) $(BIN2LSVMSRC) $(SVQPSRC) $(ONLINESRC) -lm all: $(USVMSRC) $(LSVM2BINSRC) $(CXX) $(CFLAGS) $(USEMEXFLAGS) -o $(USVM) $(USVMSRC) $(SVQPSRC) $(ONLINESRC) -lm $(CXX) $(CFLAGS) $(USEMEXFLAGS) -o $(LSVM2BIN) $(LSVM2BINSRC) $(SVQPSRC) $(ONLINESRC) -lm $(CXX) $(CFLAGS) $(USEMEXFLAGS) -o $(BIN2LSVM) $(BIN2LSVMSRC) $(SVQPSRC) $(ONLINESRC) -lm universvm/libsvm2bin.cpp0000755000304100017630000000746511323365270014320 0ustar fabeekyb #include #include #include #include #include #include #include #include #include #include #include "svqp2/svqp2.h" #include "svqp2/vector.h" using namespace std; vector X; // feature vectors vector Y; // labels int m; // number of examples int sparse=1; int max_index = 0; void libsvm_load_data(char *filename) // loads the same format as LIBSVM { int index; double value; int elements, i; FILE *fp = fopen(filename,"r"); lasvm_sparsevector_t* v; int splitpos=0; if(fp == NULL) { fprintf(stderr,"Can't open input file \"%s\"\n",filename); exit(1); } else printf("\"%s\".. ",filename); int msz = 0; elements = 0; while(1) { int c = fgetc(fp); switch(c) { case '\n': v=lasvm_sparsevector_create(); X.push_back(v); ++msz; //printf("%d\n",m); elements=0; break; case ':': ++elements; break; case EOF: goto out; default: ; } } out: rewind(fp); for(i=0;imax_index) max_index=index; } out2: label=1; // dummy } fclose(fp); m=X.size(); printf("examples: %d features: %d\n",m,max_index); } void fullbin_save(char *fname) { int i,j; ofstream f; f.open(fname,ios::out|ios::binary); // write number of examples and number of features int sz[2]; sz[0]=m; sz[1]=max_index; f.write((char*)sz,2*sizeof(int)); if (!f) { printf("File writing error in line %d.\n",i); exit(1);} float buf[max_index+1]; for(i=0;iindex>max_index) { printf("error! index %d??\n",p->index); exit(1); } buf[p->index]=p->value; } f.write((char*)buf,max_index*sizeof(float)); } f.close(); } void bin_save(char *fname) { int i,j; ofstream f; f.open(fname,ios::out|ios::binary); // write number of examples and a 0 to say that the matrix is sparse int sz[2]; sz[0]=m; sz[1]=0; f.write((char*)sz,2*sizeof(int)); if (!f) {printf("File writing error in line %d.\n",i); exit(1);} float buf[max_index]; int ind[max_index]; for(i=0;iindex,p->value); buf[max_index]=p->value; ind[max_index]=p->index; max_index++; } sz[0]=Y[i]; // write label sz[1]=max_index; // write length of example (how many nonsparse entries) f.write((char*)sz,2*sizeof(int)); f.write((char*)ind,max_index*sizeof(int)); // write indices f.write((char*)buf,max_index*sizeof(float)); // write values if (!f) {printf("File writing error in line %d.\n",i); exit(1);} } f.close(); } int main(int argc, char **argv) { printf("\n"); printf("libsvm2bin file converter\n"); printf("_________________________\n"); if(argc<3 || (argc==3 && strcmp("-F",argv[1])==0)) { printf("usage: %s [-F] \n",argv[0]); printf(" -F full matrix : forces full rather than sparse matrix storage.\n"); exit(0); } if(strcmp(argv[1],"-F")==0) { sparse=0;printf("[storing as a full matrix]\n"); libsvm_load_data(argv[2]); fullbin_save(argv[3]); } else { libsvm_load_data(argv[1]); bin_save(argv[2]); } } universvm/bin2libsvm.cpp0000755000304100017630000000547311323365270014315 0ustar fabeekyb#include #include #include #include #include #include #include #include #include #include #include "svqp2/vector.h" using namespace std; vector X; // feature vectors vector Y; // labels int m; // number of examples int sparse=1; int max_index = 0; int binary_load_data(char *filename) { int msz,i=0,j; lasvm_sparsevector_t* v; int nonsparse=0; ifstream f; f.open(filename,ios::in|ios::binary); // read number of examples and number of features int sz[2]; f.read((char*)sz,2*sizeof(int)); if (!f) { printf("File writing error in line %d.\n",i); exit(1);} msz=sz[0]; max_index=sz[1]; vector val; vector ind; val.resize(max_index); if(max_index>0) nonsparse=1; for(i=0;imax_index) max_index=ind[j]; } } } f.close(); msz=X.size(); printf("examples: %d features: %d\n",msz,max_index); return msz; } void libsvm_save(char *fname) { FILE *f = fopen(fname,"w"); for(int i=0;iindex>max_index) { printf("error! index %d??\n",p->index); exit(1); } fprintf(f," %d:%.15g", p->index, p->value); } fprintf(f,"\n"); } fclose(f); } int main(int argc, char **argv) { printf("\n"); printf("bin2libsvm file converter\n"); printf("_________________________\n"); if(argc!=3) { printf("usage: %s \n",argv[0]); exit(10); } m = binary_load_data(argv[1]); libsvm_save(argv[2]); return 0; }