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