37 #ifndef SHARK_ALGORITHMS_QP_QPBOXLINEAR_H 38 #define SHARK_ALGORITHMS_QP_QPBOXLINEAR_H 53 #define CHANGE_RATE 0.2 72 template <
class InputT>
93 for (std::size_t i=0; i<
m_data.size(); i++)
95 ElementType x_i =
m_data[i];
112 bool verbose =
false)
122 std::size_t ell =
m_data.size();
123 RealVector alpha(ell, 0.0);
125 RealVector pref(ell, 1.0);
126 double prefsum = ell;
127 std::vector<std::size_t> schedule(ell);
130 std::size_t epoch = 0;
131 std::size_t steps = 0;
134 double max_violation = 0.0;
135 const double gain_learning_rate = 1.0 / ell;
136 double average_gain = 0.0;
143 double psum = prefsum;
146 for (std::size_t i=0; i<ell; i++)
149 double num = (psum < 1e-6) ? ell - pos :
std::min((
double)(ell - pos), (ell - pos) * p / psum);
150 std::size_t n = (std::size_t)std::floor(num);
151 double prob = num - n;
152 if (Rng::uni() < prob) n++;
153 for (std::size_t j=0; j<n; j++)
162 for (std::size_t i=0; i<ell; i++)
std::swap(schedule[i], schedule[Rng::discrete(0, ell - 1)]);
166 for (std::size_t j=0; j<ell; j++)
169 std::size_t i = schedule[j];
170 ElementType e_i =
m_data[i];
171 double y_i = (e_i.label > 0) ? +1.0 : -1.0;
176 double g = 1.0 - wyx;
177 double pg = (a == 0.0 && g < 0.0) ? 0.0 : (a == C && g > 0.0 ? 0.0 : g);
180 max_violation =
std::max(max_violation, std::abs(pg));
189 double new_a = a + mu;
205 w += (mu * y_i) * e_i.input;
206 gain = mu * (g - 0.5 * q * mu);
213 if (epoch == 0) average_gain += gain / (double)ell;
216 double change =
CHANGE_RATE * (gain / average_gain - 1.0);
218 prefsum += newpref - pref(i);
220 average_gain = (1.0 - gain_learning_rate) * average_gain + gain_learning_rate * gain;
236 if (prop != NULL) prop->type =
QpTimeout;
242 if (verbose) std::cout <<
"#" << std::flush;
252 for (std::size_t i=0; i<ell; i++) pref[i] = 1.0;
258 if (verbose) std::cout <<
"." << std::flush;
266 std::size_t free_SV = 0;
267 std::size_t bounded_SV = 0;
269 for (std::size_t i=0; i<ell; i++)
275 if (a == C) bounded_SV++;
283 prop->accuracy = max_violation;
284 prop->iterations = ell * epoch;
285 prop->value = objective;
286 prop->seconds = timer.
lastLap();
292 std::cout << std::endl;
293 std::cout <<
"training time (seconds): " << timer.
lastLap() << std::endl;
294 std::cout <<
"number of epochs: " << epoch << std::endl;
295 std::cout <<
"number of iterations: " << (ell * epoch) << std::endl;
296 std::cout <<
"number of non-zero steps: " << steps << std::endl;
297 std::cout <<
"dual accuracy: " << max_violation << std::endl;
298 std::cout <<
"dual objective value: " << objective << std::endl;
299 std::cout <<
"number of free support vectors: " << free_SV << std::endl;
300 std::cout <<
"number of bounded support vectors: " << bounded_SV << std::endl;
327 : x(dataset.numberOfElements())
328 , y(dataset.numberOfElements())
329 , diagonal(dataset.numberOfElements())
341 for (std::size_t i=0; i<batch.size(); i++)
343 CompressedRealVector x_i =
shark::get(batch, i).input;
344 if (x_i.nnz() == 0)
continue;
346 unsigned int y_i =
shark::get(batch, i).label;
347 y[j] = 2.0 * y_i - 1.0;
349 for (CompressedRealVector::const_iterator it=x_i.begin(); it != x_i.end(); ++it)
352 sparse.index = it.index();
354 storage.push_back(sparse);
357 sparse.index = (std::size_t)-1;
358 storage.push_back(sparse);
363 for (std::size_t i=0, j=0, k=0; i<x.size(); i++)
365 CompressedRealVector x_i = dataset.
element(i).input;
366 if (x_i.nnz() == 0)
continue;
369 for (; storage[k].index != (std::size_t)-1; k++);
387 bool verbose =
false)
397 std::size_t ell = x.size();
398 RealVector alpha(ell, 0.0);
400 RealVector pref(ell, 1.0);
401 double prefsum = ell;
402 std::vector<std::size_t> schedule(ell);
405 std::size_t epoch = 0;
406 std::size_t steps = 0;
409 double max_violation = 0.0;
410 const double gain_learning_rate = 1.0 / ell;
411 double average_gain = 0.0;
418 double psum = prefsum;
421 for (std::size_t i=0; i<ell; i++)
424 double num = (psum < 1e-6) ? ell - pos :
std::min((
double)(ell - pos), (ell - pos) * p / psum);
425 std::size_t n = (std::size_t)std::floor(num);
426 double prob = num - n;
427 if (Rng::uni() < prob) n++;
428 for (std::size_t j=0; j<n; j++)
437 for (std::size_t i=0; i<ell; i++)
std::swap(schedule[i], schedule[Rng::discrete(0, ell - 1)]);
441 for (std::size_t j=0; j<ell; j++)
444 std::size_t i = schedule[j];
445 const SparseVector* x_i = x[i];
450 double g = 1.0 - wyx;
451 double pg = (a == 0.0 && g < 0.0) ? 0.0 : (a == C && g > 0.0 ? 0.0 : g);
454 max_violation =
std::max(max_violation, std::abs(pg));
461 double q = diagonal(i);
463 double new_a = a + mu;
480 axpy(w, mu * y(i), x_i);
481 gain = mu * (g - 0.5 * q * mu);
488 if (epoch == 0) average_gain += gain / (double)ell;
491 double change =
CHANGE_RATE * (gain / average_gain - 1.0);
493 prefsum += newpref - pref(i);
495 average_gain = (1.0 - gain_learning_rate) * average_gain + gain_learning_rate * gain;
511 if (prop != NULL) prop->type =
QpTimeout;
517 if (verbose) std::cout <<
"#" << std::flush;
527 for (std::size_t i=0; i<ell; i++) pref[i] = 1.0;
533 if (verbose) std::cout <<
"." << std::flush;
541 std::size_t free_SV = 0;
542 std::size_t bounded_SV = 0;
544 for (std::size_t i=0; i<ell; i++)
550 if (a == C) bounded_SV++;
558 prop->accuracy = max_violation;
559 prop->iterations = ell * epoch;
560 prop->value = objective;
561 prop->seconds = timer.
lastLap();
567 std::cout << std::endl;
568 std::cout <<
"training time (seconds): " << timer.
lastLap() << std::endl;
569 std::cout <<
"number of epochs: " << epoch << std::endl;
570 std::cout <<
"number of iterations: " << (ell * epoch) << std::endl;
571 std::cout <<
"number of non-zero steps: " << steps << std::endl;
572 std::cout <<
"dual accuracy: " << max_violation << std::endl;
573 std::cout <<
"dual objective value: " << objective << std::endl;
574 std::cout <<
"number of free support vectors: " << free_SV << std::endl;
575 std::cout <<
"number of bounded support vectors: " << bounded_SV << std::endl;
591 static inline void axpy(RealVector&
w,
double alpha,
const SparseVector* xi)
595 if (xi->index == (std::size_t)-1)
return;
596 w[xi->index] += alpha * xi->value;
602 static inline double inner_prod(RealVector
const&
w,
const SparseVector* xi)
607 if (xi->index == (std::size_t)-1)
return ret;
608 ret += w[xi->index] * xi->value;
614 std::vector<SparseVector*>
x;