SHOGUN  4.2.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
MulticlassOCAS.cpp
Go to the documentation of this file.
1 /*
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 3 of the License, or
5  * (at your option) any later version.
6  *
7  * Written (W) 2009-2012 Vojtech Franc and Soeren Sonnenburg
8  * Written (W) 2012 Sergey Lisitsyn
9  * Copyright (C) 2009-2012 Vojtech Franc and Soeren Sonnenburg
10  */
11 
12 
14 #ifdef USE_GPL_SHOGUN
18 
19 using namespace shogun;
20 
21 struct mocas_data
22 {
23  CDotFeatures* features;
24  float64_t* W;
25  float64_t* oldW;
26  float64_t* full_A;
27  float64_t* data_y;
28  float64_t* output_values;
29  uint32_t nY;
30  uint32_t nData;
31  uint32_t nDim;
32  float64_t* new_a;
33 };
34 
35 CMulticlassOCAS::CMulticlassOCAS() :
37 {
38  register_parameters();
39  set_C(1.0);
40  set_epsilon(1e-2);
41  set_max_iter(1000000);
42  set_method(1);
43  set_buf_size(5000);
44 }
45 
46 CMulticlassOCAS::CMulticlassOCAS(float64_t C, CDotFeatures* train_features, CLabels* train_labels) :
47  CLinearMulticlassMachine(new CMulticlassOneVsRestStrategy(), train_features, NULL, train_labels), m_C(C)
48 {
49  register_parameters();
50  set_epsilon(1e-2);
51  set_max_iter(1000000);
52  set_method(1);
53  set_buf_size(5000);
54 }
55 
56 void CMulticlassOCAS::register_parameters()
57 {
58  SG_ADD(&m_C, "m_C", "regularization constant", MS_AVAILABLE);
59  SG_ADD(&m_epsilon, "m_epsilon", "solver relative tolerance", MS_NOT_AVAILABLE);
60  SG_ADD(&m_max_iter, "m_max_iter", "max number of iterations", MS_NOT_AVAILABLE);
61  SG_ADD(&m_method, "m_method", "used solver method", MS_NOT_AVAILABLE);
62  SG_ADD(&m_buf_size, "m_buf_size", "buffer size", MS_NOT_AVAILABLE);
63 }
64 
65 CMulticlassOCAS::~CMulticlassOCAS()
66 {
67 }
68 
69 bool CMulticlassOCAS::train_machine(CFeatures* data)
70 {
71  if (data)
72  set_features((CDotFeatures*)data);
73 
74  ASSERT(m_features)
75  ASSERT(m_labels)
76  ASSERT(m_multiclass_strategy)
77 
78  int32_t num_vectors = m_features->get_num_vectors();
79  int32_t num_classes = m_multiclass_strategy->get_num_classes();
80  int32_t num_features = m_features->get_dim_feature_space();
81 
82  float64_t C = m_C;
83  SGVector<float64_t> labels = ((CMulticlassLabels*) m_labels)->get_labels();
84  uint32_t nY = num_classes;
85  uint32_t nData = num_vectors;
86  float64_t TolRel = m_epsilon;
87  float64_t TolAbs = 0.0;
88  float64_t QPBound = 0.0;
89  float64_t MaxTime = m_max_train_time;
90  uint32_t BufSize = m_buf_size;
91  uint8_t Method = m_method;
92 
93  mocas_data user_data;
94  user_data.features = m_features;
95  user_data.W = SG_CALLOC(float64_t, (int64_t)num_features*num_classes);
96  user_data.oldW = SG_CALLOC(float64_t, (int64_t)num_features*num_classes);
97  user_data.new_a = SG_CALLOC(float64_t, (int64_t)num_features*num_classes);
98  user_data.full_A = SG_CALLOC(float64_t, (int64_t)num_features*num_classes*m_buf_size);
99  user_data.output_values = SG_CALLOC(float64_t, num_vectors);
100  user_data.data_y = labels.vector;
101  user_data.nY = num_classes;
102  user_data.nDim = num_features;
103  user_data.nData = num_vectors;
104 
105  ocas_return_value_T value =
106  msvm_ocas_solver(C, labels.vector, nY, nData, TolRel, TolAbs,
107  QPBound, MaxTime, BufSize, Method,
108  &CMulticlassOCAS::msvm_full_compute_W,
109  &CMulticlassOCAS::msvm_update_W,
110  &CMulticlassOCAS::msvm_full_add_new_cut,
111  &CMulticlassOCAS::msvm_full_compute_output,
112  &CMulticlassOCAS::msvm_sort_data,
113  &CMulticlassOCAS::msvm_print,
114  &user_data);
115 
116  SG_DEBUG("Number of iterations [nIter] = %d \n",value.nIter)
117  SG_DEBUG("Number of cutting planes [nCutPlanes] = %d \n",value.nCutPlanes)
118  SG_DEBUG("Number of non-zero alphas [nNZAlpha] = %d \n",value.nNZAlpha)
119  SG_DEBUG("Number of training errors [trn_err] = %d \n",value.trn_err)
120  SG_DEBUG("Primal objective value [Q_P] = %f \n",value.Q_P)
121  SG_DEBUG("Dual objective value [Q_D] = %f \n",value.Q_D)
122  SG_DEBUG("Output time [output_time] = %f \n",value.output_time)
123  SG_DEBUG("Sort time [sort_time] = %f \n",value.sort_time)
124  SG_DEBUG("Add time [add_time] = %f \n",value.add_time)
125  SG_DEBUG("W time [w_time] = %f \n",value.w_time)
126  SG_DEBUG("QP solver time [qp_solver_time] = %f \n",value.qp_solver_time)
127  SG_DEBUG("OCAS time [ocas_time] = %f \n",value.ocas_time)
128  SG_DEBUG("Print time [print_time] = %f \n",value.print_time)
129  SG_DEBUG("QP exit flag [qp_exitflag] = %d \n",value.qp_exitflag)
130  SG_DEBUG("Exit flag [exitflag] = %d \n",value.exitflag)
131 
132  m_machines->reset_array();
133  for (int32_t i=0; i<num_classes; i++)
134  {
135  CLinearMachine* machine = new CLinearMachine();
136  machine->set_w(SGVector<float64_t>(&user_data.W[i*num_features],num_features,false).clone());
137 
138  m_machines->push_back(machine);
139  }
140 
141  SG_FREE(user_data.W);
142  SG_FREE(user_data.oldW);
143  SG_FREE(user_data.new_a);
144  SG_FREE(user_data.full_A);
145  SG_FREE(user_data.output_values);
146 
147  return true;
148 }
149 
150 float64_t CMulticlassOCAS::msvm_update_W(float64_t t, void* user_data)
151 {
152  float64_t* W = ((mocas_data*)user_data)->W;
153  float64_t* oldW = ((mocas_data*)user_data)->oldW;
154  uint32_t nY = ((mocas_data*)user_data)->nY;
155  uint32_t nDim = ((mocas_data*)user_data)->nDim;
156 
157  for(uint32_t j=0; j < nY*nDim; j++)
158  W[j] = oldW[j]*(1-t) + t*W[j];
159 
160  float64_t sq_norm_W = CMath::dot(W,W,nDim*nY);
161 
162  return sq_norm_W;
163 }
164 
165 void CMulticlassOCAS::msvm_full_compute_W(float64_t *sq_norm_W, float64_t *dp_WoldW,
166  float64_t *alpha, uint32_t nSel, void* user_data)
167 {
168  float64_t* W = ((mocas_data*)user_data)->W;
169  float64_t* oldW = ((mocas_data*)user_data)->oldW;
170  float64_t* full_A = ((mocas_data*)user_data)->full_A;
171  uint32_t nY = ((mocas_data*)user_data)->nY;
172  uint32_t nDim = ((mocas_data*)user_data)->nDim;
173 
174  uint32_t i,j;
175 
176  memcpy(oldW, W, sizeof(float64_t)*nDim*nY);
177  memset(W, 0, sizeof(float64_t)*nDim*nY);
178 
179  for(i=0; i<nSel; i++)
180  {
181  if(alpha[i] > 0)
182  {
183  for(j=0; j<nDim*nY; j++)
184  W[j] += alpha[i]*full_A[LIBOCAS_INDEX(j,i,nDim*nY)];
185  }
186  }
187 
188  *sq_norm_W = CMath::dot(W,W,nDim*nY);
189  *dp_WoldW = CMath::dot(W,oldW,nDim*nY);
190 
191  return;
192 }
193 
194 int CMulticlassOCAS::msvm_full_add_new_cut(float64_t *new_col_H, uint32_t *new_cut,
195  uint32_t nSel, void* user_data)
196 {
197  float64_t* full_A = ((mocas_data*)user_data)->full_A;
198  float64_t* new_a = ((mocas_data*)user_data)->new_a;
199  float64_t* data_y = ((mocas_data*)user_data)->data_y;
200  uint32_t nY = ((mocas_data*)user_data)->nY;
201  uint32_t nDim = ((mocas_data*)user_data)->nDim;
202  uint32_t nData = ((mocas_data*)user_data)->nData;
203  CDotFeatures* features = ((mocas_data*)user_data)->features;
204 
205  float64_t sq_norm_a;
206  uint32_t i, j, y, y2;
207 
208  memset(new_a, 0, sizeof(float64_t)*nDim*nY);
209 
210  for(i=0; i < nData; i++)
211  {
212  y = (uint32_t)(data_y[i]);
213  y2 = (uint32_t)new_cut[i];
214  if(y2 != y)
215  {
216  features->add_to_dense_vec(1.0,i,&new_a[nDim*y],nDim);
217  features->add_to_dense_vec(-1.0,i,&new_a[nDim*y2],nDim);
218  }
219  }
220 
221  // compute new_a'*new_a and insert new_a to the last column of full_A
222  sq_norm_a = CMath::dot(new_a,new_a,nDim*nY);
223  for(j=0; j < nDim*nY; j++ )
224  full_A[LIBOCAS_INDEX(j,nSel,nDim*nY)] = new_a[j];
225 
226  new_col_H[nSel] = sq_norm_a;
227  for(i=0; i < nSel; i++)
228  {
229  float64_t tmp = 0;
230 
231  for(j=0; j < nDim*nY; j++ )
232  tmp += new_a[j]*full_A[LIBOCAS_INDEX(j,i,nDim*nY)];
233 
234  new_col_H[i] = tmp;
235  }
236 
237  return 0;
238 }
239 
240 int CMulticlassOCAS::msvm_full_compute_output(float64_t *output, void* user_data)
241 {
242  float64_t* W = ((mocas_data*)user_data)->W;
243  uint32_t nY = ((mocas_data*)user_data)->nY;
244  uint32_t nDim = ((mocas_data*)user_data)->nDim;
245  uint32_t nData = ((mocas_data*)user_data)->nData;
246  float64_t* output_values = ((mocas_data*)user_data)->output_values;
247  CDotFeatures* features = ((mocas_data*)user_data)->features;
248 
249  uint32_t i, y;
250 
251  for(y=0; y<nY; y++)
252  {
253  features->dense_dot_range(output_values,0,nData,NULL,&W[nDim*y],nDim,0.0);
254  for (i=0; i<nData; i++)
255  output[LIBOCAS_INDEX(y,i,nY)] = output_values[i];
256  }
257 
258  return 0;
259 }
260 
261 int CMulticlassOCAS::msvm_sort_data(float64_t* vals, float64_t* data, uint32_t size)
262 {
263  CMath::qsort_index(vals, data, size);
264  return 0;
265 }
266 
267 void CMulticlassOCAS::msvm_print(ocas_return_value_T value)
268 {
269 }
270 
271 #endif //USE_GPL_SHOGUN
virtual void dense_dot_range(float64_t *output, int32_t start, int32_t stop, float64_t *alphas, float64_t *vec, int32_t dim, float64_t b)
Definition: DotFeatures.cpp:67
virtual void set_w(const SGVector< float64_t > src_w)
The class Labels models labels, i.e. class assignments of objects.
Definition: Labels.h:43
static void qsort_index(T1 *output, T2 *index, uint32_t size)
Definition: Math.h:2202
virtual void add_to_dense_vec(float64_t alpha, int32_t vec_idx1, float64_t *vec2, int32_t vec2_len, bool abs_val=false)=0
Features that support dot products among other operations.
Definition: DotFeatures.h:44
Multiclass Labels for multi-class classification.
generic linear multiclass machine
#define ASSERT(x)
Definition: SGIO.h:201
shogun vector
double float64_t
Definition: common.h:50
Class LinearMachine is a generic interface for all kinds of linear machines like classifiers.
Definition: LinearMachine.h:63
static float64_t dot(const bool *v1, const bool *v2, int32_t n)
Compute dot product between v1 and v2 (blas optimized)
Definition: Math.h:627
#define SG_DEBUG(...)
Definition: SGIO.h:107
all of classes and functions are contained in the shogun namespace
Definition: class_list.h:18
The class Features is the base class of all feature objects.
Definition: Features.h:68
SGVector< T > clone() const
Definition: SGVector.cpp:207
void set_epsilon(float *begin, float max)
Definition: JLCoverTree.h:513
multiclass one vs rest strategy used to train generic multiclass machines for K-class problems with b...
#define SG_ADD(...)
Definition: SGObject.h:81

SHOGUN Machine Learning Toolbox - Documentation