00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #include "features/Labels.h"
00013 #include "lib/Mathematics.h"
00014 #include "lib/Time.h"
00015 #include "base/Parallel.h"
00016 #include "classifier/LinearClassifier.h"
00017 #include "classifier/svm/SVMOcas.h"
00018 #include "classifier/svm/libocas.h"
00019 #include "features/DotFeatures.h"
00020 #include "features/Labels.h"
00021
00022 using namespace shogun;
00023
00024 CSVMOcas::CSVMOcas(E_SVM_TYPE type)
00025 : CLinearClassifier(), use_bias(true), bufsize(3000), C1(1), C2(1),
00026 epsilon(1e-3), method(type)
00027 {
00028 w=NULL;
00029 old_w=NULL;
00030 }
00031
00032 CSVMOcas::CSVMOcas(
00033 float64_t C, CDotFeatures* traindat, CLabels* trainlab)
00034 : CLinearClassifier(), use_bias(true), bufsize(3000), C1(C), C2(C),
00035 epsilon(1e-3)
00036 {
00037 w=NULL;
00038 old_w=NULL;
00039 method=SVM_OCAS;
00040 set_features(traindat);
00041 set_labels(trainlab);
00042 }
00043
00044
00045 CSVMOcas::~CSVMOcas()
00046 {
00047 }
00048
00049 bool CSVMOcas::train(CFeatures* data)
00050 {
00051 SG_INFO("C=%f, epsilon=%f, bufsize=%d\n", get_C1(), get_epsilon(), bufsize);
00052 SG_DEBUG("use_bias = %i\n", get_bias_enabled()) ;
00053
00054 ASSERT(labels);
00055 if (data)
00056 {
00057 if (!data->has_property(FP_DOT))
00058 SG_ERROR("Specified features are not of type CDotFeatures\n");
00059 set_features((CDotFeatures*) data);
00060 }
00061 ASSERT(features);
00062 ASSERT(labels->is_two_class_labeling());
00063
00064 int32_t num_train_labels=0;
00065 lab=labels->get_labels(num_train_labels);
00066 w_dim=features->get_dim_feature_space();
00067 int32_t num_vec=features->get_num_vectors();
00068
00069 ASSERT(num_vec==num_train_labels);
00070 ASSERT(num_vec>0);
00071
00072 delete[] w;
00073 w=new float64_t[w_dim];
00074 memset(w, 0, w_dim*sizeof(float64_t));
00075
00076 delete[] old_w;
00077 old_w=new float64_t[w_dim];
00078 memset(old_w, 0, w_dim*sizeof(float64_t));
00079 bias=0;
00080 old_bias=0;
00081
00082 tmp_a_buf=new float64_t[w_dim];
00083 cp_value=new float64_t*[bufsize];
00084 cp_index=new uint32_t*[bufsize];
00085 cp_nz_dims=new uint32_t[bufsize];
00086 cp_bias=new float64_t[bufsize];
00087 memset(cp_bias, 0, sizeof(float64_t)*bufsize);
00088
00089 float64_t TolAbs=0;
00090 float64_t QPBound=0;
00091 int32_t Method=0;
00092 if (method == SVM_OCAS)
00093 Method = 1;
00094 ocas_return_value_T result = svm_ocas_solver( get_C1(), num_vec, get_epsilon(),
00095 TolAbs, QPBound, bufsize, Method,
00096 &CSVMOcas::compute_W,
00097 &CSVMOcas::update_W,
00098 &CSVMOcas::add_new_cut,
00099 &CSVMOcas::compute_output,
00100 &CSVMOcas::sort,
00101 this);
00102
00103 SG_INFO("Ocas Converged after %d iterations\n"
00104 "==================================\n"
00105 "timing statistics:\n"
00106 "output_time: %f s\n"
00107 "sort_time: %f s\n"
00108 "add_time: %f s\n"
00109 "w_time: %f s\n"
00110 "solver_time %f s\n"
00111 "ocas_time %f s\n\n", result.nIter, result.output_time, result.sort_time,
00112 result.add_time, result.w_time, result.solver_time, result.ocas_time);
00113
00114 delete[] tmp_a_buf;
00115
00116 uint32_t num_cut_planes = result.nCutPlanes;
00117
00118 for (uint32_t i=0; i<num_cut_planes; i++)
00119 {
00120 delete[] cp_value[i];
00121 delete[] cp_index[i];
00122 }
00123
00124 delete[] cp_value;
00125 cp_value=NULL;
00126 delete[] cp_index;
00127 cp_index=NULL;
00128 delete[] cp_nz_dims;
00129 cp_nz_dims=NULL;
00130 delete[] cp_bias;
00131 cp_bias=NULL;
00132
00133 delete[] lab;
00134 lab=NULL;
00135
00136 delete[] old_w;
00137 old_w=NULL;
00138
00139 return true;
00140 }
00141
00142
00143
00144
00145
00146
00147
00148
00149 float64_t CSVMOcas::update_W( float64_t t, void* ptr )
00150 {
00151 float64_t sq_norm_W = 0;
00152 CSVMOcas* o = (CSVMOcas*) ptr;
00153 uint32_t nDim = (uint32_t) o->w_dim;
00154 float64_t* W=o->w;
00155 float64_t* oldW=o->old_w;
00156
00157 for(uint32_t j=0; j <nDim; j++)
00158 {
00159 W[j] = oldW[j]*(1-t) + t*W[j];
00160 sq_norm_W += W[j]*W[j];
00161 }
00162 o->bias=o->old_bias*(1-t) + t*o->bias;
00163 sq_norm_W += CMath::sq(o->bias);
00164
00165 return( sq_norm_W );
00166 }
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176 void CSVMOcas::add_new_cut(
00177 float64_t *new_col_H, uint32_t *new_cut, uint32_t cut_length,
00178 uint32_t nSel, void* ptr)
00179 {
00180 CSVMOcas* o = (CSVMOcas*) ptr;
00181 CDotFeatures* f = o->features;
00182 uint32_t nDim=(uint32_t) o->w_dim;
00183 float64_t* y = o->lab;
00184
00185 float64_t** c_val = o->cp_value;
00186 uint32_t** c_idx = o->cp_index;
00187 uint32_t* c_nzd = o->cp_nz_dims;
00188 float64_t* c_bias = o->cp_bias;
00189
00190 float64_t sq_norm_a;
00191 uint32_t i, j, nz_dims;
00192
00193
00194 float64_t* new_a = o->tmp_a_buf;
00195 memset(new_a, 0, sizeof(float64_t)*nDim);
00196
00197 for(i=0; i < cut_length; i++)
00198 {
00199 f->add_to_dense_vec(y[new_cut[i]], new_cut[i], new_a, nDim);
00200
00201 if (o->use_bias)
00202 c_bias[nSel]+=y[new_cut[i]];
00203 }
00204
00205
00206 nz_dims = 0;
00207 sq_norm_a = CMath::sq(c_bias[nSel]);
00208 for(j=0; j < nDim; j++ ) {
00209 if(new_a[j] != 0) {
00210 nz_dims++;
00211 sq_norm_a += new_a[j]*new_a[j];
00212 }
00213 }
00214
00215
00216 c_nzd[nSel] = nz_dims;
00217 if(nz_dims > 0)
00218 {
00219 c_idx[nSel]=new uint32_t[nz_dims];
00220 c_val[nSel]=new float64_t[nz_dims];
00221
00222 uint32_t idx=0;
00223 for(j=0; j < nDim; j++ )
00224 {
00225 if(new_a[j] != 0)
00226 {
00227 c_idx[nSel][idx] = j;
00228 c_val[nSel][idx++] = new_a[j];
00229 }
00230 }
00231 }
00232
00233 new_col_H[nSel] = sq_norm_a;
00234
00235 for(i=0; i < nSel; i++)
00236 {
00237 float64_t tmp = c_bias[nSel]*c_bias[i];
00238 for(j=0; j < c_nzd[i]; j++)
00239 tmp += new_a[c_idx[i][j]]*c_val[i][j];
00240
00241 new_col_H[i] = tmp;
00242 }
00243
00244
00245
00246 }
00247
00248 void CSVMOcas::sort(float64_t* vals, uint32_t* idx, uint32_t size)
00249 {
00250 CMath::qsort_index(vals, idx, size);
00251 }
00252
00253
00254
00255
00256
00257
00258 void CSVMOcas::compute_output(float64_t *output, void* ptr)
00259 {
00260 CSVMOcas* o = (CSVMOcas*) ptr;
00261 CDotFeatures* f=o->features;
00262 int32_t nData=f->get_num_vectors();
00263
00264 float64_t* y = o->lab;
00265
00266 f->dense_dot_range(output, 0, nData, y, o->w, o->w_dim, 0.0);
00267
00268 for (int32_t i=0; i<nData; i++)
00269 output[i]+=y[i]*o->bias;
00270
00271
00272 }
00273
00274
00275
00276
00277
00278
00279
00280
00281
00282
00283 void CSVMOcas::compute_W(
00284 float64_t *sq_norm_W, float64_t *dp_WoldW, float64_t *alpha, uint32_t nSel,
00285 void* ptr )
00286 {
00287 CSVMOcas* o = (CSVMOcas*) ptr;
00288 uint32_t nDim= (uint32_t) o->w_dim;
00289 CMath::swap(o->w, o->old_w);
00290 float64_t* W=o->w;
00291 float64_t* oldW=o->old_w;
00292 memset(W, 0, sizeof(float64_t)*nDim);
00293 float64_t old_bias=o->bias;
00294 float64_t bias=0;
00295
00296 float64_t** c_val = o->cp_value;
00297 uint32_t** c_idx = o->cp_index;
00298 uint32_t* c_nzd = o->cp_nz_dims;
00299 float64_t* c_bias = o->cp_bias;
00300
00301 for(uint32_t i=0; i<nSel; i++)
00302 {
00303 uint32_t nz_dims = c_nzd[i];
00304
00305 if(nz_dims > 0 && alpha[i] > 0)
00306 {
00307 for(uint32_t j=0; j < nz_dims; j++)
00308 W[c_idx[i][j]] += alpha[i]*c_val[i][j];
00309 }
00310 bias += c_bias[i]*alpha[i];
00311 }
00312
00313 *sq_norm_W = CMath::dot(W,W, nDim) + CMath::sq(bias);
00314 *dp_WoldW = CMath::dot(W,oldW, nDim) + bias*old_bias;
00315
00316
00317 o->bias = bias;
00318 o->old_bias = old_bias;
00319 }