lasvm-source/0000755000400500003220000000000011234340337011763 5ustar leonbCSIlasvm-source/la_svm.cpp0000640000400500003220000006072111234340174013751 0ustar leonbCSI// -*- Mode: c++; c-file-style: "stroustrup"; -*- using namespace std; #include #include #include #include #include #include #include #include #include "vector.h" #include "lasvm.h" #define LINEAR 0 #define POLY 1 #define RBF 2 #define SIGMOID 3 #define ONLINE 0 #define ONLINE_WITH_FINISHING 1 #define RANDOM 0 #define GRADIENT 1 #define MARGIN 2 #define ITERATIONS 0 #define SVS 1 #define TIME 2 const char *kernel_type_table[] = {"linear","polynomial","rbf","sigmoid"}; 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; }; private: std::clock_t start; }; stopwatch::~stopwatch() { clock_t total = clock()-start; //get elapsed time cout<<"Time(secs): "< X; // feature vectors vector Y; // labels vector kparam; // kernel parameters vector alpha; // alpha_i, SV weights double b0; // threshold /* Hyperparameters */ int kernel_type=RBF; // LINEAR, POLY, RBF or SIGMOID kernels double degree=3,kgamma=-1,coef0=0;// kernel params int use_b0=1; // use threshold via constraint \sum a_i y_i =0 int selection_type=RANDOM; // RANDOM, GRADIENT or MARGIN selection strategies int optimizer=ONLINE_WITH_FINISHING; // strategy of optimization double C=1; // C, penalty on errors double C_neg=1; // C-Weighting for negative examples double C_pos=1; // C-Weighting for positive examples int epochs=1; // epochs of online learning int candidates=50; // number of candidates for "active" selection process double deltamax=1000; // tolerance for performing reprocess step, 1000=1 reprocess only vector select_size; // Max number of SVs to take with selection strategy (for early stopping) vector x_square; // norms of input vectors, used for RBF /* Programm behaviour*/ int verbosity=1; // verbosity level, 0=off int saves=1; 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; vector splits; int max_index=0; vector iold, inew; // sets of old (already seen) points + new (unseen) points int termination_type=0; void exit_with_help() { fprintf(stdout, "Usage: la_svm [options] training_set_file [model_file]\n" "options:\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" "-o optimizer: set the type of optimization (default 1)\n" " 0 -- online \n" " 1 -- online with finishing step \n" "-t kernel_type : set type of kernel function (default 2)\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" "-s selection: set the type of selection strategy (default 0)\n" " 0 -- random \n" " 1 -- gradient-based \n" " 2 -- margin-based \n" "-T termination: set the type of early stopping strategy (default 0)\n" " 0 -- number of iterations \n" " 1 -- number of SVs \n" " 2 -- time-based \n" "-l sample: number of iterations/SVs/seconds to sample for early stopping (default all)\n" " if a list of numbers is given a model file is saved for each element of the set\n" "-C candidates : set number of candidates to search for selection strategy (default 50)\n" "-d degree : set degree in kernel function (default 3)\n" "-g gamma : set gamma in kernel function (default 1/k)\n" "-r coef0 : set coef0 in kernel function (default 0)\n" "-c cost : set the parameter C of C-SVC\n" "-m cachesize : set cache memory size in MB (default 256)\n" "-wi weight: set the parameter C of class i to weight*C (default 1)\n" "-b bias: use a bias or not i.e. no constraint sum alpha_i y_i =0 (default 1=on)\n" "-e epsilon : set tolerance of termination criterion (default 0.001)\n" "-p epochs : number of epochs to train in online setting (default 1)\n" "-D deltamax : set tolerance for reprocess step, 1000=1 call to reprocess >1000=no calls to reprocess (default 1000)\n" ); exit(1); } void parse_command_line(int argc, char **argv, char *input_file_name, char *model_file_name) { int i; int clss; double weight; // parse options for(i=1;i'9')) break; } i--; break; case 'd': degree = atof(argv[i]); break; case 'g': kgamma = atof(argv[i]); break; case 'r': coef0 = atof(argv[i]); break; case 'm': cache_size = (int) atof(argv[i]); break; case 'c': C = atof(argv[i]); break; case 'w': clss= atoi(&argv[i-1][2]); weight = atof(argv[i]); if (clss>=1) C_pos=weight; else C_neg=weight; break; case 'b': use_b0=atoi(argv[i]); break; case 'B': binary_files=atoi(argv[i]); break; case 'e': epsgr = atof(argv[i]); break; case 'p': epochs = atoi(argv[i]); break; case 'D': deltamax = atoi(argv[i]); break; case 'C': candidates = atoi(argv[i]); break; case 'T': termination_type = atoi(argv[i]); break; default: fprintf(stderr,"unknown option\n"); exit_with_help(); } } saves=select_size.size(); if(saves==0) select_size.push_back(100000000); // determine filenames if(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) 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[splitpos-1],index,value); 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.\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; 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) 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) 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;imax_alpha) max_alpha=alpha[i]; if(-alpha[i]>max_alpha) max_alpha=-alpha[i]; } alpha_tol=max_alpha/1000.0; for(i=0;i0) { if(alpha[i] >= alpha_tol) sv1++; } else { if(-alpha[i] >= alpha_tol) sv2++; } } return sv1+sv2; } int libsvm_save_model(const char *model_file_name) // saves the model in the same format as LIBSVM { FILE *fp = fopen(model_file_name,"w"); if(fp==NULL) return -1; count_svs(); // printf("nSV=%d\n",sv1+sv2); fprintf(fp,"svm_type c_svc\n"); fprintf(fp,"kernel_type %s\n", kernel_type_table[kernel_type]); if(kernel_type == POLY) fprintf(fp,"degree %g\n", degree); if(kernel_type == POLY || kernel_type == RBF || kernel_type == SIGMOID) fprintf(fp,"gamma %g\n", kgamma); if(kernel_type == POLY || kernel_type == SIGMOID) fprintf(fp,"coef0 %g\n", coef0); fprintf(fp, "nr_class %d\n",2); fprintf(fp, "total_sv %d\n",sv1+sv2); { fprintf(fp, "rho %g\n",b0); } fprintf(fp, "label 1 -1\n"); fprintf(fp, "nr_sv"); fprintf(fp," %d %d",sv1,sv2); fprintf(fp, "\n"); fprintf(fp, "SV\n"); for(int j=0;j<2;j++) for(int i=0;ipairs; while (p1) { fprintf(fp,"%d:%.8g ",p1->index,p1->data); p1 = p1->next; } fprintf(fp, "\n"); } fclose(fp); return 0; } double kernel(int i, int j, void *kparam) { double dot; kcalcs++; dot=lasvm_sparsevector_dot_product(X[i],X[j]); // sparse, linear kernel switch(kernel_type) { case LINEAR: return dot; case POLY: return pow(kgamma*dot+coef0,degree); case RBF: return exp(-kgamma*(x_square[i]+x_square[j]-2*dot)); case SIGMOID: return tanh(kgamma*dot+coef0); } return 0; } void finish(lasvm_t *sv) { int i,l; if (optimizer==ONLINE_WITH_FINISHING) { fprintf(stdout,"..[finishing]"); int iter=0; do { iter += lasvm_finish(sv, epsgr); } while (lasvm_get_delta(sv)>epsgr); } l=(int) lasvm_get_l(sv); int *svind,svs; svind= new int[l]; svs=lasvm_get_sv(sv,svind); alpha.resize(m); for(i=0;i from new set into old set { int i,ind=-1; for(i=0;i<(int)inew.size();i++) { if(inew[i]==val) {ind=i; break;} } if (ind>=0) { inew[ind]=inew[inew.size()-1]; inew.pop_back(); iold.push_back(val); } } int select(lasvm_t *sv) // selection strategy { int s=-1; int t,i,r,j; double tmp,best; int ind=-1; switch(selection_type) { case RANDOM: // pick a random candidate s=rand() % inew.size(); break; case GRADIENT: // pick best gradient from 50 candidates j=candidates; if((int)inew.size()deltamax && deltamax<1000) { t2=lasvm_reprocess(sv,epsgr); } } if (verbosity==2) { l=(int) lasvm_get_l(sv); printf("l=%d process=%d reprocess=%d\n",l,t1,t2); } else if(verbosity==1) if( (i%100)==0){ fprintf(stdout, "..%d",i); fflush(stdout); } l=(int) lasvm_get_l(sv); for(k=0;k<(int)select_size.size();k++) { if ( (termination_type==ITERATIONS && i==select_size[k]) || (termination_type==SVS && l>=select_size[k]) || (termination_type==TIME && sw->get_time()>=select_size[k]) ) { if(saves>1) // if there is more than one model to save, give a new name { // save current version before potential finishing step int save_l,*save_sv; double *save_g, *save_alpha; save_l=(int)lasvm_get_l(sv); save_alpha= new double[l];lasvm_get_alpha(sv,save_alpha); save_g= new double[l];lasvm_get_g(sv,save_g); save_sv= new int[l];lasvm_get_sv(sv,save_sv); finish(sv); char tmp[1000]; timer+=sw->get_time(); //f << i << " " << count_svs() << " " << kcalcs << " " << timer << endl; if(termination_type==TIME) { sprintf(tmp,"%s_%dsecs",model_file_name,i); fprintf(stdout,"..[saving model_%d secs]..",i); } else { fprintf(stdout,"..[saving model_%d pts]..",i); sprintf(tmp,"%s_%dpts",model_file_name,i); } libsvm_save_model(tmp); // get back old version //fprintf(stdout, "[restoring before finish]"); fflush(stdout); lasvm_init(sv, save_l, save_sv, save_alpha, save_g); delete save_alpha; delete save_sv; delete save_g; delete sw; sw=new stopwatch; // reset clock } select_size[k]=select_size[select_size.size()-1]; select_size.pop_back(); } } if(select_size.size()==0) break; // early stopping, all intermediate models saved } inew.resize(0);iold.resize(0); // start again for next epoch.. for(i=0;iget_time(); //f << m << " " << count_svs() << " " << kcalcs << " " << timer << endl; } if(verbosity>0) printf("\n"); l=count_svs(); printf("nSVs=%d\n",l); printf("||w||^2=%g\n",lasvm_get_w2(sv)); printf("kcalcs="); cout << kcalcs << endl; //f.close(); lasvm_destroy(sv); lasvm_kcache_destroy(kcache); } int main(int argc, char **argv) { printf("\n"); printf("la SVM\n"); printf("______\n"); char input_file_name[1024]; char model_file_name[1024]; parse_command_line(argc, argv, input_file_name, model_file_name); load_data_file(input_file_name); train_online(model_file_name); libsvm_save_model(model_file_name); } lasvm-source/libsvm2bin.cpp0000640000400500003220000001062311234340306014530 0ustar leonbCSI// -*- Mode: c++; c-file-style: "stroustrup"; -*- using namespace std; #include #include #include #include #include #include #include #include "vector.h" 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; 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=0,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;ipairs; while (p ) { if(p->index>max_index) { printf("error! index %d??\n",p->index); exit(1); } buf[p->index]=p->data; p = p->next; } f.write((char*)buf,max_index*sizeof(float)); } f.close(); } void bin_save(char *fname) { int i=0; 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;ipairs; max_index=0; while (p ) { //printf("%d:%g ",p->index,p->data); buf[max_index]=p->data; ind[max_index]=p->index; p = p->next; 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]); } } lasvm-source/la_test.cpp0000640000400500003220000003232411234340251014115 0ustar leonbCSI// -*- mode: c++; c-file-style: "stroustrup"; -*- using namespace std; #include #include #include #include #include #include #include #include #include "vector.h" #define LINEAR 0 #define POLY 1 #define RBF 2 #define SIGMOID 3 const char *kernel_type_table[] = {"linear","polynomial","rbf","sigmoid"}; 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; } int m,msv; // training and test set sizes vector X; // feature vectors for test set vector Xsv;// feature vectors for SVs vector Y; // labels vector alpha; // alpha_i, SV weights double b0; // threshold int use_b0=1; // use threshold via constraint \sum a_i y_i =0 int kernel_type=RBF; // LINEAR, POLY, RBF or SIGMOID kernels double degree=3,kgamma=-1,coef0=0;// kernel params vector x_square; // norms of input vectors, used for RBF vector xsv_square; // norms of test vectors, used for RBF char split_file_name[1024]="\0"; // filename for the splits int binary_files=0; vector splits; int max_index=0; void exit_with_help() { fprintf(stdout, "\nUsage: la_test [options] test_set_file model_file output_file\n" "options:\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"); exit(1); } int split_file_load(char *f) { int binary_file=0,labs=0,inds=0; FILE *fp; fp=fopen(f,"r"); if(fp==NULL) {printf("[couldn't load split file: %s]\n",f); exit(1);} char dummy[100],dummy2[100]; unsigned int i,j=0; for(i=0;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) 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[splitpos-1],index,value); 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.\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; 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) 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) 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;imax_index) max_index=index; } out2: label=1; // dummy } printf("loading model: %d svs\n",msv); if(kernel_type==RBF) { xsv_square.resize(msv); for(i=0;i=0) y=1; else y=-1; if(((int)y)==Y[i]) acc++; } printf("accuracy= %g (%d/%d)\n",(acc/m)*100,((int)acc),m); fclose(fp); } void parse_command_line(int argc, char **argv, char *input_file_name, char *model_file_name, char *output_file_name) { int i; // parse options for(i=1;i=argc) exit_with_help(); strcpy(input_file_name, argv[i]); if(i #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 */ lasvm_sparsevector_t * lasvm_sparsevector_create(void) { lasvm_sparsevector_t *v; v = (lasvm_sparsevector_t*)xmalloc(sizeof(lasvm_sparsevector_t)); v->size = 0; v->npairs = 0; v->pairs = 0; v->last = &v->pairs; return v; } void lasvm_sparsevector_clear(lasvm_sparsevector_t *v) { lasvm_sparsevector_pair_t *p = v->pairs; while (p) { lasvm_sparsevector_pair_t *q = p->next; free(p); p = q; } v->size = 0; v->npairs = 0; v->pairs = NULL; v->last = &v->pairs; } void lasvm_sparsevector_destroy(lasvm_sparsevector_t *v) { lasvm_sparsevector_clear(v); free(v); } double lasvm_sparsevector_get(lasvm_sparsevector_t *v, int index) { lasvm_sparsevector_pair_t *p = v->pairs; ASSERT(index>=0); while (p && p->index < index) p = p->next; if (p && p->index == index) return p->data; return 0; } static void quickappend(lasvm_sparsevector_t *v, int index, double data) { lasvm_sparsevector_pair_t *d; d = (lasvm_sparsevector_pair_t*)xmalloc(sizeof(lasvm_sparsevector_pair_t)); ASSERT(index >= v->size); d->next = 0; d->index = index; d->data = data; *(v->last) = d; v->last = &(d->next); v->size = index + 1; v->npairs += 1; } void lasvm_sparsevector_set(lasvm_sparsevector_t *v, int index, double data) { if (index >= v->size) { /* Quick append */ quickappend(v, index, data); } else { /* Slow insert */ lasvm_sparsevector_pair_t **pp = &v->pairs; lasvm_sparsevector_pair_t *p, *d; while ( (p=*pp) && (p->indexnext); ASSERT(p); if (p && p->index == index) { p->data = data; return; } d = (lasvm_sparsevector_pair_t*)xmalloc(sizeof(lasvm_sparsevector_pair_t)); d->next = p; d->index = index; d->data = data; *pp = d; v->npairs += 1; } } lasvm_sparsevector_t * lasvm_sparsevector_combine(lasvm_sparsevector_t *v1, double c1, lasvm_sparsevector_t *v2, double c2) { lasvm_sparsevector_t *r; lasvm_sparsevector_pair_t *p1 = v1->pairs; lasvm_sparsevector_pair_t *p2 = v2->pairs; r = lasvm_sparsevector_create(); while (p1 && p2) { if (p1->index < p2->index) { quickappend(r, p1->index, c1*p1->data); p1 = p1->next; } else if (p1->index > p2->index) { quickappend(r, p2->index, c2*p2->data); p2 = p2->next; } else { quickappend(r, p1->index, c1*p1->data + c2*p2->data); p1 = p1->next; p2 = p2->next; } } while (p1) { quickappend(r, p1->index, c1*p1->data); p1 = p1->next; } while (p2) { quickappend(r, p2->index, c2*p2->data); p2 = p2->next; } 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 && p2) { if (p1->index < p2->index) p1 = p1->next; else if (p1->index > p2->index) p2 = p2->next; else { sum += p1->data * p2->data; p1 = p1->next; p2 = p2->next; } } return sum; } lasvm-source/vector.h0000640000400500003220000000532110336653214013436 0ustar leonbCSI/*********************************************************************** * * 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 2005/11/16 00:10:01 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; double 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 { struct lasvm_sparsevector_pair_s *next; int index; double data; } lasvm_sparsevector_pair_t; typedef struct lasvm_sparsevector_s { int size; int npairs; lasvm_sparsevector_pair_t *pairs; lasvm_sparsevector_pair_t **last; } 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); #ifdef __cplusplus__ } #endif #endif lasvm-source/bin2libsvm.cpp0000644000400500003220000000553611234340327014546 0ustar leonbCSI// -*- Mode: c++; c-file-style: "stroustrup"; -*- using namespace std; #include #include #include #include #include #include #include "vector.h" 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;ipairs; while (p ) { if(p->index>max_index) { printf("error! index %d??\n",p->index); exit(1); } fprintf(f," %d:%.15g", p->index, p->data); p = p->next; } 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; } lasvm-source/Makefile0000640000400500003220000000147510336727342013435 0ustar leonbCSI#Makefile for la_svm software (c) 2005 #SHELL=/bin/sh CXX= g++ CFLAGS= -O3 -Wall TOOLS= vector.c messages.c kernel.c kcache.c lasvm.c TOOLSINCL= vector.h messages.h kernel.h kcache.h lasvm.h LASVMSRC= la_svm.cpp LATESTSRC= la_test.cpp LSVM2BINSRC= libsvm2bin.cpp BIN2LSVMSRC= bin2libsvm.cpp all: la_svm la_test libsvm2bin bin2libsvm la_svm: $(LASVMSRC) $(TOOLS) $(TOOLSINCL) $(CXX) $(CFLAGS) -o la_svm $(LASVMSRC) $(TOOLS) -lm la_test: $(LATESTSRC) $(TOOLS) $(TOOLSINCL) $(CXX) $(CFLAGS) -o la_test $(LATESTSRC) $(TOOLS) -lm libsvm2bin: $(LSVM2BINSRC) $(TOOLS) $(TOOLSINCL) $(CXX) $(CFLAGS) -o libsvm2bin $(LSVM2BINSRC) $(TOOLS) -lm bin2libsvm: $(BIN2LSVMSRC) $(TOOLS) $(TOOLSINCL) $(CXX) $(CFLAGS) -o bin2libsvm $(BIN2LSVMSRC) $(TOOLS) -lm clean: FORCE rm 2>/dev/null la_svm la_test libsvm2bin bin2libsvm FORCE: lasvm-source/kcache.h0000640000400500003220000001131410336653214013351 0ustar leonbCSI/*********************************************************************** * * 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: kcache.h,v 1.4 2005/11/16 00:10:01 agbs Exp $ **********************************************************************/ #ifndef KCACHE_H #define KCACHE_H #ifdef __cplusplus__ extern "C" { #if 0 } #endif #endif /* ------------------------------------- */ /* GENERIC KERNEL TYPE */ /* --- lasvm_kernel_t This is the type for user defined symmetric kernel functions. It returns the Gram matrix element at position ,. Argument represents arbitrary additional information. */ #ifndef LASVM_KERNEL_T_DEFINED #define LASVM_KERNEL_T_DEFINED typedef double (*lasvm_kernel_t)(int i, int j, void* closure); #endif /* ------------------------------------- */ /* CACHE FOR KERNEL VALUES */ /* --- lasvm_kcache_t This is the opaque data structure for a kernel cache. */ typedef struct lasvm_kcache_s lasvm_kcache_t; /* --- lasvm_kcache_create Returns a cache object for kernel . The cache handles a Gram matrix of size x at most. Argument is passed to the kernel function . */ lasvm_kcache_t* lasvm_kcache_create(lasvm_kernel_t kernelfunc, void *closure); /* --- lasvm_kcache_destroy Deallocates a kernel cache object. */ void lasvm_kcache_destroy(lasvm_kcache_t *self); /* --- lasvm_kcache_set_maximum_size Sets the maximum memory size used by the cache. Argument indicates the maximum cache memory in bytes The default size is 256Mb. */ void lasvm_kcache_set_maximum_size(lasvm_kcache_t *self, long entries); /* --- lasvm_kcache_get_maximum_size Returns the maximum cache memory. */ long lasvm_kcache_get_maximum_size(lasvm_kcache_t *self); /* --- lasvm_kcache_get_current_size Returns the currently used cache memory. This can slighly exceed the value specified by . */ long lasvm_kcache_get_current_size(lasvm_kcache_t *self); /* --- lasvm_kcache_query Returns the possibly cached value of the Gram matrix element (,). This function will not modify the cache geometry. */ double lasvm_kcache_query(lasvm_kcache_t *self, int i, int j); /* --- lasvm_kcache_query_row Returns the first elements of row of the Gram matrix. The cache user can modify the order of the row elements using the lasvm_kcache_swap() functions. Functions lasvm_kcache_i2r() and lasvm_kcache_r2i() convert from example index to row position and vice-versa. */ float *lasvm_kcache_query_row(lasvm_kcache_t *self, int i, int len); /* --- lasvm_kcache_status_row Returns the number of cached entries for row i. */ int lasvm_kcache_status_row(lasvm_kcache_t *self, int i); /* --- lasvm_kcache_discard_row Indicates that we wont need row i in the near future. */ void lasvm_kcache_discard_row(lasvm_kcache_t *self, int i); /* --- lasvm_kcache_i2r --- lasvm_kcache_r2i Return an array of integer of length at least containing the conversion table from example index to row position and vice-versa. */ int *lasvm_kcache_i2r(lasvm_kcache_t *self, int n); int *lasvm_kcache_r2i(lasvm_kcache_t *self, int n); /* --- lasvm_kcache_swap_rr --- lasvm_kcache_swap_ii --- lasvm_kcache_swap_ri Swaps examples in the row ordering table. Examples can be specified by indicating their row position (, ) or by indicating the example number (, ). */ void lasvm_kcache_swap_rr(lasvm_kcache_t *self, int r1, int r2); void lasvm_kcache_swap_ii(lasvm_kcache_t *self, int i1, int i2); void lasvm_kcache_swap_ri(lasvm_kcache_t *self, int r1, int i2); #ifdef __cplusplus__ } #endif #endif lasvm-source/lasvm.c0000640000400500003220000003524710336653214013263 0ustar leonbCSI/*********************************************************************** * * LASVM -- online svm. * Copyright (C) 2005 NEC Labs America * * 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: lasvm.c,v 1.4 2005/11/16 00:10:01 agbs Exp $ **********************************************************************/ #include #include #include #include #include #include #include "messages.h" #include "kcache.h" #include "lasvm.h" #ifndef min # define min(a,b) (((a)<(b))?(a):(b)) #endif #ifndef max # define max(a,b) (((a)>(b))?(a):(b)) #endif #ifndef FLT_MAX # define FLT_MAX 1e+20 #endif #ifndef FLT_EPSILON # define FLT_EPSILON 1e-6 #endif #if USE_CBLAS # include # unded USE_FLOAT # define USE_FLOAT 1 #endif #if USE_FLOAT # define real_t float #else # define real_t double #endif static void * xmalloc(int n) { void *p = malloc(n); if (! p) lasvm_error("Function malloc() has returned NULL.\n"); return p; } static void * xrealloc(void *ptr, int n) { if (! ptr) ptr = malloc(n); else ptr = realloc(ptr, n); if (! ptr) lasvm_error("Function realloc() has returned NULL.\n"); return ptr; } struct lasvm_s { lasvm_kcache_t *kernel; int sumflag; real_t cp; real_t cn; int maxl; int s; int l; real_t *alpha; real_t *cmin; real_t *cmax; real_t *g; real_t gmin, gmax; int imin, imax; int minmaxflag; }; static void checksize(lasvm_t *self, int l) { int maxl = max(l,256); while (maxl < l) maxl += maxl; self->alpha = (real_t*)xrealloc(self->alpha, maxl*sizeof(real_t)); self->cmin = (real_t*)xrealloc(self->cmin, maxl*sizeof(real_t)); self->cmax = (real_t*)xrealloc(self->cmax, maxl*sizeof(real_t)); self->g = (real_t*)xrealloc(self->g, maxl*sizeof(real_t)); self->maxl = maxl; } lasvm_t * lasvm_create( lasvm_kcache_t *cache, int sumflag, double cp, double cn ) { lasvm_t *self = (lasvm_t*)xmalloc(sizeof(lasvm_t)); memset(self, 0, sizeof(lasvm_t)); self->kernel = cache; self->cp = cp; self->cn = cn; self->sumflag = sumflag; checksize(self, 0); return self; } void lasvm_destroy( lasvm_t *self ) { if (self->alpha) free(self->alpha); if (self->cmin) free(self->cmin); if (self->cmax) free(self->cmax); if (self->g) free(self->g); memset(self, 0, sizeof(lasvm_t)); free(self); } int lasvm_get_l( lasvm_t *self ) { return self->l; } double lasvm_get_cp( lasvm_t *self ) { return self->cp; } double lasvm_get_cn( lasvm_t *self ) { return self->cn; } int lasvm_get_alpha(lasvm_t *self, double *alpha) { int i; int l = self->l; for (i=0; ialpha[i]; return l; } int lasvm_get_sv(lasvm_t *self, int *sv) { int i; int l = self->l; int *r2i = lasvm_kcache_r2i(self->kernel, l); for (i=0; il; for (i=0; ig[i]; return l; } static void minmax( lasvm_t *self ) { if (! self->minmaxflag) { int i; int l = self->s; int imin = -1; int imax = -1; real_t gmin = 0; real_t gmax = 0; real_t *alpha = self->alpha; real_t *g = self->g; real_t *cmin = self->cmin; real_t *cmax = self->cmax; if (self->sumflag) { gmin = FLT_MAX; gmax = -FLT_MAX; } for (i=0; icmin[i]) { imin = i; gmin = gi; } if (gi>gmax && aigmin = gmin; self->gmax = gmax; self->imin = imin; self->imax = imax; self->minmaxflag = 1; } } static int gs1( lasvm_t *self, int i, double epsgr) { int l = self->s; real_t g; real_t step, ostep, curv; float *row; int *r2i; /* Determine coordinate to process */ if (i < 0) { minmax(self); if (self->gmin + self->gmax < 0) i = self->imin; else i = self->imax; if (i < 0) return 0; } /* Determine maximal step */ g = self->g[i]; if (g < 0) { step = self->alpha[i] - self->cmin[i]; if (self->gmax - g < epsgr) return 0; } else { step = self->cmax[i] - self->alpha[i]; if (g - self->gmin < epsgr) return 0; } /* Determine curvature */ r2i = lasvm_kcache_r2i(self->kernel, l); row = lasvm_kcache_query_row(self->kernel, r2i[i], l); curv = row[i]; if (curv >= FLT_EPSILON) { ostep = fabs(g)/curv; if (ostep < step) step = ostep; } else if (curv + FLT_EPSILON <= 0) lasvm_error("Kernel is not positive (negative curvature)\n"); /* Perform update */ if (g < 0) step = -step; self->alpha[i] += step; #if USE_CBLAS cblas_saxpy(l, -step, row, 1, self->g, 1); #else { int j; for (j=0; jg[j] -= step * row[j]; } #endif self->minmaxflag = 0; return 1; } static int gs2( lasvm_t *self, int imin, int imax, double epsgr) { int l = self->s; real_t gmin, gmax; real_t step, ostep, curv; float *rmin, *rmax; int *r2i; /* Determine coordinate to process */ if (imin < 0 || imax < 0) { minmax(self); if (imin < 0) imin = self->imin; if (imax < 0) imax = self->imax; } if (imin < 0 || imax < 0) return 0; gmin = self->g[imin]; gmax = self->g[imax]; if (gmax - gmin < epsgr) return 0; /* Determine maximal step */ step = self->alpha[imin] - self->cmin[imin]; ostep = self->cmax[imax] - self->alpha[imax]; if (ostep < step) step = ostep; /* Determine curvature */ r2i = lasvm_kcache_r2i(self->kernel, l); rmin = lasvm_kcache_query_row(self->kernel, r2i[imin], l); rmax = lasvm_kcache_query_row(self->kernel, r2i[imax], l); curv = rmax[imax]+rmin[imin]-rmax[imin]-rmin[imax]; if (curv >= FLT_EPSILON) { real_t ostep = (gmax - gmin) / curv; if (ostep < step) step = ostep; } else if (curv + FLT_EPSILON <= 0) lasvm_error("Kernel is not positive (negative curvature)\n"); /* Perform update */ self->alpha[imax] += step; self->alpha[imin] -= step; #if USE_CBLAS cblas_saxpy(l, -step, rmax, 1, self->g, 1); cblas_saxpy(l, step, rmin, 1, self->g, 1); #else { int j; for (j=0; jg[j] -= step * ( rmax[j] - rmin[j] ); } #endif self->minmaxflag = 0; return 1; } static void swap( lasvm_t *self, int r1, int r2) { #define swap(type, v) \ { type tmp = self->v[r1]; \ self->v[r1]=self->v[r2]; \ self->v[r2]=tmp; } lasvm_kcache_swap_rr(self->kernel, r1, r2); swap(real_t, alpha); swap(real_t, cmin); swap(real_t, cmax); swap(real_t, g); if (self->minmaxflag) { if (self->imin==r1) self->imin=r2; if (self->imin==r2) self->imin=r1; if (self->imax==r1) self->imax=r2; if (self->imax==r2) self->imax=r1; } #undef swap } static void evict( lasvm_t *self ) { int i; int l = self->l; real_t *alpha = self->alpha; real_t *cmin = self->cmin; real_t *cmax = self->cmax; real_t *g = self->g; if (self->sumflag) { real_t gmin, gmax; minmax(self); gmin = self->gmin; gmax = self->gmax; for (i=0; i=gmax && 0>=cmax[i]) || (g[i]<=gmin && 0<=cmin[i]) ) swap(self, i--, --l); self->l = self->s = l; } else { for (i=0; i=0 && 0>=cmax[i]) || (g[i]<=0 && 0<=cmin[i]) ) swap(self, i--, --l); self->l = self->s = l; } } int lasvm_process( lasvm_t *self, int xi, double y ) { int l = self->l; int *i2r = 0; float *row = 0; real_t g; int j; /* Checks */ if (self->s != self->l) lasvm_error("lasvm_process(): internal error\n"); if (y != +1 && y != -1) lasvm_error("lasvm_process(): argument y must be +1 or -1\n"); /* Bail out if already in expansion? */ i2r = lasvm_kcache_i2r(self->kernel, 1+xi); if (i2r[xi] < l) return self->l; /* Compute gradient */ g = y; if (l > 0) { row = lasvm_kcache_query_row(self->kernel, xi, l); for (j=0; jalpha[j] * row[j]; } /* Decide insertion */ if (self->sumflag) { minmax(self); if (self->gmin < self->gmax) if ((y>0 && ggmin) || (y<0 && g>self->gmax) ) { lasvm_kcache_discard_row(self->kernel, xi); return 0; } } else { if (y * g < 0) { lasvm_kcache_discard_row(self->kernel, xi); return 0; } } /* Insert */ checksize(self, l+1); lasvm_kcache_swap_ri(self->kernel, l, xi); self->alpha[l] = 0; self->g[l] = g; if (y > 0) { self->cmin[l] = 0; self->cmax[l] = self->cp; } else { self->cmin[l] = - self->cn; self->cmax[l] = 0; } self->l = self->s = l+1; /* Process */ if (! self->sumflag) gs1(self, l, 0); else if (y > 0) gs2(self, -1, l, 0); else gs2(self, l, -1, 0); self->minmaxflag = 0; return self->l; } int lasvm_reprocess(lasvm_t *self, double epsgr) { int status; if (self->s != self->l) lasvm_error("lasvm_process(): internal error\n"); if (self->sumflag) status = gs2(self, -1, -1, epsgr); else status = gs1(self, -1, epsgr); evict(self); if (status) return self->l; return 0; } static void shrink(lasvm_t *self) { int i; int s = self->s; real_t *alpha = self->alpha; real_t *cmin = self->cmin; real_t *cmax = self->cmax; real_t *g = self->g; if (self->sumflag) { real_t gmin, gmax; minmax(self); gmin = self->gmin; gmax = self->gmax; for (i=0; i=gmax && alpha[i]>=cmax[i]) || (g[i]<=gmin && alpha[i]<=cmin[i]) ) swap(self, i--, --s); self->s = s; } else { for (i=0; i=0 && alpha[i]>=cmax[i]) || (g[i]<=0 && alpha[i]<=cmin[i]) ) swap(self, i--, --s); self->s = s; } } static void unshrink(lasvm_t *self) { int l = self->l; int s = self->s; if (s < l) { real_t *alpha = self->alpha; real_t *g = self->g; int *r2i = lasvm_kcache_r2i(self->kernel, l); real_t a; int i,j; for(i=s; i0) ? 1.0 : -1.0; for(j=0; jkernel, xj); float *row = lasvm_kcache_query_row(self->kernel, r2i[j], l); for (i=s; ikernel, xj); } self->minmaxflag = 0; self->s = l; } } int lasvm_finish(lasvm_t *self, double epsgr) { int iter = 0; int siter = 0; int status = self->l; while( status ) { if (iter >= siter) { shrink(self); siter = iter + min(1000,self->l); } if (self->sumflag) status = gs2(self, -1, -1, epsgr); else status = gs1(self, -1, epsgr); iter++; } unshrink(self); evict(self); return iter; } double lasvm_get_delta(lasvm_t *self) { double d; minmax(self); d = self->gmax - self->gmin; return max(0, d); } double lasvm_get_b(lasvm_t *self) { if (self->sumflag) { minmax(self); return - (self->gmax + self->gmin) / 2; } return 0; } double lasvm_get_w2(lasvm_t *self) { int i; int l = self->l; real_t *alpha = self->alpha; real_t *g = self->g; real_t s = 0; for (i=0; i0) s += alpha[i] * ( g[i] + 1.0 ); else if (alpha[i]<0) s += alpha[i] * ( g[i] - 1.0 ); return s/2.0; } double lasvm_predict(lasvm_t *self, int xi) { int l = self->l; float *row = lasvm_kcache_query_row(self->kernel, xi, l); real_t *alpha = self->alpha; real_t s = 0; if (self->sumflag) minmax(self); #if USE_CBLAS s = cblas_sdot(l, alpha, 1, row, 1); #else { int j; for (j=0; jsumflag) s += (self->gmin + self->gmax) / 2; return s; } double lasvm_predict_nocache(lasvm_t *self, int xi) { int cached = lasvm_kcache_status_row(self->kernel, xi); real_t s = lasvm_predict(self, xi); if (! cached) /* do not keep what was not cached */ lasvm_kcache_discard_row(self->kernel, xi); return s; } void lasvm_init( lasvm_t *self, int l, const int *sv, const double *alpha, const double *g ) { int i,k; if (l <= 0) lasvm_error("Argument l should be positive.\n"); checksize(self, l); self->l = 0; for (i=k=0; ikernel, k, sv[i]); self->alpha[k] = alpha[i]; if (alpha[i]>0) { self->cmin[k] = 0; self->cmax[k] = self->cp; self->g[k] = +1; } else { self->cmin[k] = - self->cn; self->cmax[k] = 0; self->g[k] = -1; } if (g) self->g[k] = g[i]; k++; } } if (! g) { int *r2i = lasvm_kcache_r2i(self->kernel, k); for (i=0; ig[i]; float *row = lasvm_kcache_query_row(self->kernel, r2i[i] , k); #if USE_CBLAS s -= cblas_sdot(k, self->alpha, 1, row, 1); #else { int j; for (j=0; jalpha[j] * row[j]; } #endif self->g[i] = s; } } self->l = self->s = k; } lasvm-source/messages.c0000640000400500003220000000533710336653214013745 0ustar leonbCSI/*********************************************************************** * * 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.c,v 1.4 2005/11/16 00:10:01 agbs Exp $ **********************************************************************/ #include #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); } lasvm-source/lasvm.h0000640000400500003220000001175510336714122013262 0ustar leonbCSI/*********************************************************************** * * LASVM -- online svm. * Copyright (C) 2005 NEC Labs America * * 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: lasvm.h,v 1.5 2005/11/16 20:36:34 agbs Exp $ **********************************************************************/ #ifndef LASVM_H #define LASVM_H #include "kcache.h" /* --- lasvm_t Opaque type representing the LASVM state. */ typedef struct lasvm_s lasvm_t; /* --- lasvm_create Creates a lasvm object. You must first create and configure a kernel cache object for your chosen kernel. Never associate a same cache object with several lasvm objects. Argument indicates whether the equality constraint should be honored (i.e. whether the svm has a bias term). Setting to zero should be considered experimental. Arguments and are the C values for positive and negative examples. */ lasvm_t *lasvm_create( lasvm_kcache_t *cache, int sumflag, double cp, double cn ); /* --- lasvm_destroy Deallocates a lasvm object. The associated kernel cache must be deallocated separately. */ void lasvm_destroy( lasvm_t *self ); /* --- lasvm_get_l Returns the number of support vectors. */ int lasvm_get_l( lasvm_t *self ); /* --- lasvm_process Perform the PROCESS operation on example with index . Argument is the example label and must be +1 or -1. Returns the number of SVs if a change has been made. Otherwise returns zero. */ int lasvm_process( lasvm_t *self, int xi, double y ); /* --- lasvm_reprocess Performs the REPROCESS operation with a tolerance on the gradients. Returns the number of SVs if a change has been made. Otherwise returns zero. */ int lasvm_reprocess(lasvm_t *self, double epsgr); /* --- lasvm_finish Specialized version of REPROCESS used for the finishing step. Calling is essentially similar to calling several times. However it runs faster because it performs the shrinking optimization. Returns the number of iterations. */ int lasvm_finish(lasvm_t *self, double epsgr); /* -- lasvm_get_cp, lasvm_get_cn Returns the values of parameter C for positive and negative examples. */ double lasvm_get_cp( lasvm_t *self ); double lasvm_get_cn( lasvm_t *self ); /* --- lasvm_get_delta Returns the maximal gradient exploitable by a subsequent REPROCESS operation. Calling REPROCESS with smaller than delta returns immediately. */ double lasvm_get_delta(lasvm_t *self); /* --- lasvm_get_alpha Copies the support vector coefficients into array . Coefficients are positive for positive example and negative for negative examples. */ int lasvm_get_alpha(lasvm_t *self, double *alpha); /* --- lasvm_get_alpha Returns the support vector indices into array . Similar information can be obtained using . */ int lasvm_get_sv(lasvm_t *self, int *sv); /* --- lasvm_get_g Returns the gradient of the dual objective function with respect to each support vector coefficient. */ int lasvm_get_g(lasvm_t *self, double *g); /* --- lasvm_get_b Returns the value of the bias term. */ double lasvm_get_b(lasvm_t *self); /* --- lasvm_get_w2 Returns the value of the dual objective function. */ double lasvm_get_w2(lasvm_t *self); /* --- lasvm_predict Computes the kernel expansion on example with index and returns the result. */ double lasvm_predict(lasvm_t *self, int xi); /* --- lasvm_predict_nocache Same as but does not mark the corresponding kernel values as recently used. */ double lasvm_predict_nocache(lasvm_t *self, int xi); /* --- lasvm_init Resets the state of lasvm to known values. The gradients are optional. Passing a null pointer will cause them to be recomputed on the fly. KNOWN BUG: this function uses the sign of the coefficient to determine the class of each example. That does not work if is zero. Such support vectors are eliminated... */ void lasvm_init( lasvm_t *self, int l, const int *sv, const double *alpha, const double *g ); #endif lasvm-source/kernel.h0000640000400500003220000000576210336653214013425 0ustar leonbCSI/*********************************************************************** * * 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: kernel.h,v 1.4 2005/11/16 00:10:01 agbs Exp $ **********************************************************************/ #ifndef KERNEL_H #define KERNEL_H #include #include #include "vector.h" #ifdef __cplusplus__ extern "C" { #if 0 } #endif #endif /* ------------------------------------- */ /* GENERIC KERNEL TYPE */ /* --- lasvm_kernel_t This is the type for user defined symmetric kernel functions. It returns the Gram matrix element at position ,. Argument represents arbitrary additional information. */ #ifndef LASVM_KERNEL_T_DEFINED #define LASVM_KERNEL_T_DEFINED typedef double (*lasvm_kernel_t)(int i, int j, void* closure); #endif /* ------------------------------------- */ /* USEFUL KERNELS */ typedef struct lasvm_vectorproblem_s { int l; /* number of examples */ int n; /* dimension of examples */ lasvm_vector_t **x; /* x[0]...x[l-1] */ double *y; /* category */ double *xnorm; /* for rbf kernel: l2-norm of the x[i] */ double rbfgamma; /* for rbf kernel: gamma */ } lasvm_vectorproblem_t; double lasvm_vectorproblem_lin_kernel(int i, int j, void *problem); double lasvm_vectorproblem_rbf_kernel(int i, int j, void *problem); /* ------------------------------------- */ /* MORE USEFUL KERNELS */ typedef struct lasvm_sparsevectorproblem_s { int l; /* number of examples */ int n; /* dimension of examples */ lasvm_sparsevector_t **x; /* x[0]...x[l-1] */ double *y; /* category */ double *xnorm; /* for rbf kernel: l2-norm of the x[i] */ double rbfgamma; /* for rbf kernel: gamma */ } lasvm_sparsevectorproblem_t; double lasvm_sparsevectorproblem_lin_kernel(int i, int j, void *problem); double lasvm_sparsevectorproblem_rbf_kernel(int i, int j, void *problem); #ifdef __cplusplus__ } #endif #endif lasvm-source/messages.h0000640000400500003220000000526210336653214013747 0ustar leonbCSI/*********************************************************************** * * 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.4 2005/11/16 00:10:01 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 lasvm-source/kcache.c0000640000400500003220000002317510336653214013354 0ustar leonbCSI/*********************************************************************** * * 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: kcache.c,v 1.4 2005/11/16 00:10:01 agbs Exp $ **********************************************************************/ #include #include #include #include #include "messages.h" #include "kcache.h" #ifndef min # define min(a,b) (((a)<(b))?(a):(b)) #endif #ifndef max # define max(a,b) (((a)>(b))?(a):(b)) #endif struct lasvm_kcache_s { lasvm_kernel_t func; void *closure; long maxsize; long cursize; int l; int *i2r; int *r2i; /* Rows */ int *rsize; float *rdiag; float **rdata; int *rnext; int *rprev; int *qnext; int *qprev; }; static void * xmalloc(int n) { void *p = malloc(n); if (! p) lasvm_error("Function malloc() has returned zero\n"); return p; } static void * xrealloc(void *ptr, int n) { if (! ptr) ptr = malloc(n); else ptr = realloc(ptr, n); if (! ptr) lasvm_error("Function realloc has returned zero\n"); return ptr; } static void xminsize(lasvm_kcache_t *self, int n) { int ol = self->l; if (n > ol) { int i; int nl = max(256,ol); while (nl < n) nl = nl + nl; self->i2r = (int*)xrealloc(self->i2r, nl*sizeof(int)); self->r2i = (int*)xrealloc(self->r2i, nl*sizeof(int)); self->rsize = (int*)xrealloc(self->rsize, nl*sizeof(int)); self->qnext = (int*)xrealloc(self->qnext, (1+nl)*sizeof(int)); self->qprev = (int*)xrealloc(self->qprev, (1+nl)*sizeof(int)); self->rdiag = (float*)xrealloc(self->rdiag, nl*sizeof(float)); self->rdata = (float**)xrealloc(self->rdata, nl*sizeof(float*)); self->rnext = self->qnext + 1; self->rprev = self->qprev + 1; for (i=ol; ii2r[i] = i; self->r2i[i] = i; self->rsize[i] = -1; self->rnext[i] = i; self->rprev[i] = i; self->rdata[i] = 0; } self->l = nl; } } lasvm_kcache_t* lasvm_kcache_create(lasvm_kernel_t kernelfunc, void *closure) { lasvm_kcache_t *self; self = (lasvm_kcache_t*)xmalloc(sizeof(lasvm_kcache_t)); memset(self, 0, sizeof(lasvm_kcache_t)); self->l = 0; self->func = kernelfunc; self->closure = closure; self->cursize = sizeof(lasvm_kcache_t); self->maxsize = 256*1024*1024; self->qprev = (int*)xmalloc(sizeof(int)); self->qnext = (int*)xmalloc(sizeof(int)); self->rnext = self->qnext + 1; self->rprev = self->qprev + 1; self->rprev[-1] = -1; self->rnext[-1] = -1; return self; } void lasvm_kcache_destroy(lasvm_kcache_t *self) { if (self) { int i; if (self->i2r) free(self->i2r); if (self->r2i) free(self->r2i); if (self->rdata) for (i=0; il; i++) if (self->rdata[i]) free(self->rdata[i]); if (self->rdata) free(self->rdata); if (self->rsize) free(self->rsize); if (self->rdiag) free(self->rdiag); if (self->qnext) free(self->qnext); if (self->qprev) free(self->qprev); memset(self, 0, sizeof(lasvm_kcache_t)); free(self); } } int * lasvm_kcache_i2r(lasvm_kcache_t *self, int n) { xminsize(self, n); return self->i2r; } int * lasvm_kcache_r2i(lasvm_kcache_t *self, int n) { xminsize(self, n); return self->r2i; } static void xextend(lasvm_kcache_t *self, int k, int nlen) { int olen = self->rsize[k]; if (nlen > olen) { float *ndata = (float*)xmalloc(nlen*sizeof(float)); if (olen > 0) { float *odata = self->rdata[k]; memcpy(ndata, odata, olen * sizeof(float)); free(odata); } self->rdata[k] = ndata; self->rsize[k] = nlen; self->cursize += (long)(nlen - olen) * sizeof(float); } } static void xtruncate(lasvm_kcache_t *self, int k, int nlen) { int olen = self->rsize[k]; if (nlen < olen) { float *ndata; float *odata = self->rdata[k]; if (nlen > 0) { ndata = (float*)xmalloc(nlen*sizeof(float)); memcpy(ndata, odata, nlen * sizeof(float)); } else { ndata = 0; self->rnext[self->rprev[k]] = self->rnext[k]; self->rprev[self->rnext[k]] = self->rprev[k]; self->rnext[k] = self->rprev[k] = k; } free(odata); self->rdata[k] = ndata; self->rsize[k] = nlen; self->cursize += (long)(nlen - olen) * sizeof(float); } } static void xswap(lasvm_kcache_t *self, int i1, int i2, int r1, int r2) { int k = self->rnext[-1]; while (k >= 0) { int nk = self->rnext[k]; int n = self->rsize[k]; int rr = self->i2r[k]; float *d = self->rdata[k]; if (r1 < n) { if (r2 < n) { float t1 = d[r1]; float t2 = d[r2]; d[r1] = t2; d[r2] = t1; } else if (rr == r2) { d[r1] = self->rdiag[k]; } else { int arsize = self->rsize[i2]; if (rr < arsize && rr != r1) d[r1] = self->rdata[i2][rr]; else xtruncate(self, k, r1); } } else if (r2 < n) { if (rr == r1) { d[r2] = self->rdiag[k]; } else { int arsize = self->rsize[i1]; if (rr < arsize && rr != r2) d[r2] = self->rdata[i1][rr]; else xtruncate(self, k, r2); } } k = nk; } self->r2i[r1] = i2; self->r2i[r2] = i1; self->i2r[i1] = r2; self->i2r[i2] = r1; } void lasvm_kcache_swap_rr(lasvm_kcache_t *self, int r1, int r2) { xminsize(self, 1+max(r1,r2)); xswap(self, self->r2i[r1], self->r2i[r2], r1, r2); } void lasvm_kcache_swap_ii(lasvm_kcache_t *self, int i1, int i2) { xminsize(self, 1+max(i1,i2)); xswap(self, i1, i2, self->i2r[i1], self->i2r[i2]); } void lasvm_kcache_swap_ri(lasvm_kcache_t *self, int r1, int i2) { xminsize(self, 1+max(r1,i2)); xswap(self, self->r2i[r1], i2, r1, self->i2r[i2]); } double lasvm_kcache_query(lasvm_kcache_t *self, int i, int j) { int l = self->l; ASSERT(i>=0); ASSERT(j>=0); if (irsize[i]; int p = self->i2r[j]; if (p < s) return self->rdata[i][p]; else if (i == j && s >= 0) return self->rdiag[i]; p = self->i2r[i]; s = self->rsize[j]; if (p < s) return self->rdata[j][p]; } /* compute */ return (*self->func)(i, j, self->closure); } static void xpurge(lasvm_kcache_t *self) { if (self->cursize>self->maxsize) { int k = self->rprev[-1]; while (self->cursize>self->maxsize && k!=self->rnext[-1]) { int pk = self->rprev[k]; xtruncate(self, k, 0); k = pk; } } } float * lasvm_kcache_query_row(lasvm_kcache_t *self, int i, int len) { ASSERT(i>=0); if (il && len<=self->rsize[i]) { self->rnext[self->rprev[i]] = self->rnext[i]; self->rprev[self->rnext[i]] = self->rprev[i]; } else { int olen, p, q; float *d; if (i >= self->l || len >= self->l) xminsize(self, max(1+i,len)); olen = self->rsize[i]; if (olen < 0) { self->rdiag[i] = (*self->func)(i, i, self->closure); olen = self->rsize[i] = 0; } xextend(self, i, len); q = self->i2r[i]; d = self->rdata[i]; for (p=olen; pr2i[p]; if (i == j) d[p] = self->rdiag[i]; else if (q < self->rsize[j]) d[p] = self->rdata[j][q]; else d[p] = (*self->func)(i, j, self->closure); } self->rnext[self->rprev[i]] = self->rnext[i]; self->rprev[self->rnext[i]] = self->rprev[i]; xpurge(self); } self->rprev[i] = -1; self->rnext[i] = self->rnext[-1]; self->rnext[self->rprev[i]] = i; self->rprev[self->rnext[i]] = i; return self->rdata[i]; } int lasvm_kcache_status_row(lasvm_kcache_t *self, int i) { ASSERT(self); ASSERT(i>=0); if (i < self->l) return max(0,self->rsize[i]); return 0; } void lasvm_kcache_discard_row(lasvm_kcache_t *self, int i) { ASSERT(self); ASSERT(i>=0); if (il && self->rsize[i]>0) { self->rnext[self->rprev[i]] = self->rnext[i]; self->rprev[self->rnext[i]] = self->rprev[i]; self->rprev[i] = self->rprev[-1]; self->rnext[i] = -1; self->rnext[self->rprev[i]] = i; self->rprev[self->rnext[i]] = i; } } void lasvm_kcache_set_maximum_size(lasvm_kcache_t *self, long entries) { ASSERT(self); ASSERT(entries>0); self->maxsize = entries; xpurge(self); } long lasvm_kcache_get_maximum_size(lasvm_kcache_t *self) { ASSERT(self); return self->maxsize; } long lasvm_kcache_get_current_size(lasvm_kcache_t *self) { ASSERT(self); return self->cursize; } lasvm-source/kernel.c0000640000400500003220000000527010336653214013412 0ustar leonbCSI/*********************************************************************** * * 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: kernel.c,v 1.4 2005/11/16 00:10:01 agbs Exp $ **********************************************************************/ #include #include #include #include #include #include "messages.h" #include "kernel.h" #ifdef __cplusplus__ #define this mythis #define or myor #define and myand #endif double lasvm_vectorproblem_lin_kernel(int i, int j, void *problem) { lasvm_vectorproblem_t *p = (lasvm_vectorproblem_t*)problem; ASSERT(i>=0 && il); ASSERT(j>=0 && jl); return lasvm_vector_dot_product(p->x[i], p->x[j]); } double lasvm_vectorproblem_rbf_kernel(int i, int j, void *problem) { double d; lasvm_vectorproblem_t *p = (lasvm_vectorproblem_t*)problem; ASSERT(i>=0 && il); ASSERT(j>=0 && jl); d = lasvm_vector_dot_product(p->x[i], p->x[j]); return exp( - p->rbfgamma * ( p->xnorm[i] + p->xnorm[j] - 2 * d )); } double lasvm_sparsevectorproblem_lin_kernel(int i, int j, void *problem) { lasvm_sparsevectorproblem_t *p = (lasvm_sparsevectorproblem_t*)problem; ASSERT(i>=0 && il); ASSERT(j>=0 && jl); return lasvm_sparsevector_dot_product(p->x[i], p->x[j]); } double lasvm_sparsevectorproblem_rbf_kernel(int i, int j, void *problem) { double d; lasvm_sparsevectorproblem_t *p = (lasvm_sparsevectorproblem_t*)problem; ASSERT(i>=0 && il); ASSERT(j>=0 && jl); d = lasvm_sparsevector_dot_product(p->x[i], p->x[j]); return exp( - p->rbfgamma * ( p->xnorm[i] + p->xnorm[j] - 2 * d )); }