SHOGUN  3.2.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
MulticlassOneVsOneStrategy.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) 2012 Chiyuan Zhang
8  * Written (W) 2013 Shell Hu and Heiko Strathmann
9  * Copyright (C) 2012 Chiyuan Zhang
10  */
11 
15 
16 using namespace shogun;
17 
19  :CMulticlassStrategy(), m_num_machines(0), m_num_samples(SGVector<int32_t>())
20 {
21  register_parameters();
22 }
23 
25  :CMulticlassStrategy(prob_heuris), m_num_machines(0), m_num_samples(SGVector<int32_t>())
26 {
27  register_parameters();
28 }
29 
30 void CMulticlassOneVsOneStrategy::register_parameters()
31 {
32  //SG_ADD(&m_num_samples, "num_samples", "Number of samples in each training machine", MS_NOT_AVAILABLE);
33  SG_WARNING("%s::CMulticlassOneVsOneStrategy(): register parameters!\n", get_name());
34 }
35 
37 {
38  CMulticlassStrategy::train_start(orig_labels, train_labels);
40 
43 
45 }
46 
48 {
50 }
51 
53 {
55 
57  int32_t tot=0;
58  for (int32_t k=0; k < m_orig_labels->get_num_labels(); ++k)
59  {
60  if (((CMulticlassLabels*) m_orig_labels)->get_int_label(k)==m_train_pair_idx_1)
61  {
62  ((CBinaryLabels*) m_train_labels)->set_label(k, +1.0);
63  subset[tot]=k;
64  tot++;
65  }
66  else if (((CMulticlassLabels*) m_orig_labels)->get_int_label(k)==m_train_pair_idx_2)
67  {
68  ((CBinaryLabels*) m_train_labels)->set_label(k, -1.0);
69  subset[tot]=k;
70  tot++;
71  }
72  }
73 
76  {
79  }
80 
81  // collect num samples each machine
82  m_num_samples[m_train_iter-1] = tot;
83 
84  subset.resize_vector(tot);
85  return subset;
86 }
87 
89 {
90  // if OVO with prob outputs, find max posterior
91  if (outputs.vlen==m_num_classes)
92  return SGVector<float64_t>::arg_max(outputs.vector, 1, outputs.vlen);
93 
94  int32_t s=0;
97  votes.zero();
98  dec_vals.zero();
99 
100  for (int32_t i=0; i<m_num_classes; i++)
101  {
102  for (int32_t j=i+1; j<m_num_classes; j++)
103  {
104  if (outputs[s]>0)
105  {
106  votes[i]++;
107  dec_vals[i] += CMath::abs(outputs[s]);
108  }
109  else
110  {
111  votes[j]++;
112  dec_vals[j] += CMath::abs(outputs[s]);
113  }
114  s++;
115  }
116  }
117 
118  int32_t i_max=0;
119  int32_t vote_max=-1;
120  float64_t dec_val_max=-1;
121 
122  for (int32_t i=0; i < m_num_classes; ++i)
123  {
124  if (votes[i] > vote_max)
125  {
126  i_max = i;
127  vote_max = votes[i];
128  dec_val_max = dec_vals[i];
129  }
130  else if (votes[i] == vote_max)
131  {
132  if (dec_vals[i] > dec_val_max)
133  {
134  i_max = i;
135  dec_val_max = dec_vals[i];
136  }
137  }
138  }
139 
140  return i_max;
141 }
142 
144 {
145  if (m_num_machines < 1)
146  return;
147 
150 
151  int32_t tot = 0;
152  for (int32_t j=0; j<m_num_classes; j++)
153  {
154  for (int32_t k=j+1; k<m_num_classes; k++)
155  {
156  indx1[tot] = j;
157  indx2[tot] = k;
158  tot++;
159  }
160  }
161 
162  if(tot!=m_num_machines)
163  SG_ERROR("%s::rescale_output(): size(outputs) is not num_machines.\n", get_name());
164 
165  switch(get_prob_heuris_type())
166  {
167  case OVO_PRICE:
168  rescale_heuris_price(outputs,indx1,indx2);
169  break;
170  case OVO_HASTIE:
171  rescale_heuris_hastie(outputs,indx1,indx2);
172  break;
173  case OVO_HAMAMURA:
174  rescale_heuris_hamamura(outputs,indx1,indx2);
175  break;
176  case PROB_HEURIS_NONE:
177  break;
178  default:
179  SG_ERROR("%s::rescale_outputs(): Unknown OVO probability heuristic type!\n", get_name());
180  break;
181  }
182 }
183 
185  const SGVector<int32_t> indx1, const SGVector<int32_t> indx2)
186 {
187  if (m_num_machines != outputs.vlen)
188  {
189  SG_ERROR("%s::rescale_heuris_price(): size(outputs) = %d != m_num_machines = %d\n",
190  get_name(), outputs.vlen, m_num_machines);
191  }
192 
193  SGVector<float64_t> new_outputs(m_num_classes);
194  new_outputs.zero();
195 
196  for (int32_t j=0; j<m_num_classes; j++)
197  {
198  for (int32_t m=0; m<m_num_machines; m++)
199  {
200  if (indx1[m]==j)
201  new_outputs[j] += 1.0 / (outputs[m]+1E-12);
202  if (indx2[m]==j)
203  new_outputs[j] += 1.0 / (1.0-outputs[m]+1E-12);
204  }
205 
206  new_outputs[j] = 1.0 / (new_outputs[j] - m_num_classes + 2);
207  }
208 
209  //outputs.resize_vector(m_num_classes);
210 
211  float64_t norm = SGVector<float64_t>::sum(new_outputs);
212  for (int32_t i=0; i<new_outputs.vlen; i++)
213  outputs[i] = new_outputs[i] / norm;
214 }
215 
217  const SGVector<int32_t> indx1, const SGVector<int32_t> indx2)
218 {
219  if (m_num_machines != outputs.vlen)
220  {
221  SG_ERROR("%s::rescale_heuris_hastie(): size(outputs) = %d != m_num_machines = %d\n",
222  get_name(), outputs.vlen, m_num_machines);
223  }
224 
225  SGVector<float64_t> new_outputs(m_num_classes);
226  new_outputs.zero();
227 
228  for (int32_t j=0; j<m_num_classes; j++)
229  {
230  for (int32_t m=0; m<m_num_machines; m++)
231  {
232  if (indx1[m]==j)
233  new_outputs[j] += outputs[m];
234  if (indx2[m]==j)
235  new_outputs[j] += 1.0-outputs[m];
236  }
237 
238  new_outputs[j] *= 2.0 / (m_num_classes * (m_num_classes - 1));
239  new_outputs[j] += 1E-10;
240  }
241 
243  SGVector<float64_t> prev_outputs(m_num_classes);
244  float64_t gap = 1.0;
245 
246  while (gap > 1E-12)
247  {
248  prev_outputs = new_outputs.clone();
249 
250  for (int32_t m=0; m<m_num_machines; m++)
251  mu[m] = new_outputs[indx1[m]] / (new_outputs[indx1[m]] + new_outputs[indx2[m]]);
252 
253  for (int32_t j=0; j<m_num_classes; j++)
254  {
255  float64_t numerator = 0.0;
256  float64_t denominator = 0.0;
257  for (int32_t m=0; m<m_num_machines; m++)
258  {
259  if (indx1[m]==j)
260  {
261  numerator += m_num_samples[m] * outputs[m];
262  denominator += m_num_samples[m] * mu[m];
263  }
264 
265  if (indx2[m]==j)
266  {
267  numerator += m_num_samples[m] * (1.0-outputs[m]);
268  denominator += m_num_samples[m] * (1.0-mu[m]);
269  }
270  }
271 
272  // update posterior
273  new_outputs[j] *= numerator / denominator;
274  }
275 
276  float64_t norm = SGVector<float64_t>::sum(new_outputs);
277  for (int32_t i=0; i<new_outputs.vlen; i++)
278  new_outputs[i] /= norm;
279 
280  // gap is Euclidean distance
281  for (int32_t i=0; i<new_outputs.vlen; i++)
282  prev_outputs[i] -= new_outputs[i];
283 
284  gap = SGVector<float64_t>::qsq(prev_outputs.vector, prev_outputs.vlen, 2);
285  SG_DEBUG("[Hastie's heuristic] gap = %.12f\n", gap);
286  }
287 
288  for (int32_t i=0; i<new_outputs.vlen; i++)
289  outputs[i] = new_outputs[i];
290 }
291 
293  const SGVector<int32_t> indx1, const SGVector<int32_t> indx2)
294 {
295  if (m_num_machines != outputs.vlen)
296  {
297  SG_ERROR("%s::rescale_heuris_hamamura(): size(outputs) = %d != m_num_machines = %d\n",
298  get_name(), outputs.vlen, m_num_machines);
299  }
300 
301  SGVector<float64_t> new_outputs(m_num_classes);
302  SGVector<float64_t>::fill_vector(new_outputs.vector, new_outputs.vlen, 1.0);
303 
304  for (int32_t j=0; j<m_num_classes; j++)
305  {
306  for (int32_t m=0; m<m_num_machines; m++)
307  {
308  if (indx1[m]==j)
309  new_outputs[j] *= outputs[m];
310  if (indx2[m]==j)
311  new_outputs[j] *= 1-outputs[m];
312  }
313 
314  new_outputs[j] += 1E-10;
315  }
316 
317  float64_t norm = SGVector<float64_t>::sum(new_outputs);
318 
319  for (int32_t i=0; i<new_outputs.vlen; i++)
320  outputs[i] = new_outputs[i] / norm;
321 }
322 

SHOGUN Machine Learning Toolbox - Documentation