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];
114 bool verbose =
false)
125 std::size_t ell =
m_data.size();
126 RealVector alpha(ell, 0.0);
128 RealVector pref(ell, 1.0);
129 double prefsum = ell;
130 std::vector<std::size_t> schedule(ell);
133 std::size_t epoch = 0;
134 std::size_t steps = 0;
137 double max_violation = 0.0;
138 const double gain_learning_rate = 1.0 / ell;
139 double average_gain = 0.0;
146 double psum = prefsum;
149 for (std::size_t i=0; i<ell; i++)
152 double num = (psum < 1e-6) ? ell - pos :
std::min((
double)(ell - pos), (ell - pos) * p / psum);
153 std::size_t n = (std::size_t)std::floor(num);
154 double prob = num - n;
156 for (std::size_t j=0; j<n; j++)
169 for (std::size_t j=0; j<ell; j++)
172 std::size_t i = schedule[j];
173 ElementType e_i =
m_data[i];
174 double y_i = (e_i.label > 0) ? +1.0 : -1.0;
179 double g = 1.0 - wyx - reg * a;
180 double pg = (a == 0.0 && g < 0.0) ? 0.0 : (a == bound && g > 0.0 ? 0.0 : g);
183 max_violation =
std::max(max_violation, std::abs(pg));
192 double new_a = a + mu;
200 else if (new_a >= bound)
208 w += (mu * y_i) * e_i.input;
209 gain = mu * (g - 0.5 * q * mu);
216 if (epoch == 0) average_gain += gain / (double)ell;
219 double change =
CHANGE_RATE * (gain / average_gain - 1.0);
221 prefsum += newpref - pref(i);
223 average_gain = (1.0 - gain_learning_rate) * average_gain + gain_learning_rate * gain;
239 if (prop != NULL) prop->type =
QpTimeout;
245 if (verbose) std::cout <<
"#" << std::flush;
255 for (std::size_t i=0; i<ell; i++) pref[i] = 1.0;
261 if (verbose) std::cout <<
"." << std::flush;
269 std::size_t free_SV = 0;
270 std::size_t bounded_SV = 0;
272 for (std::size_t i=0; i<ell; i++)
278 objective -= reg/2.0 * a * a;
279 if (a == bound) bounded_SV++;
287 prop->accuracy = max_violation;
288 prop->iterations = ell * epoch;
289 prop->value = objective;
290 prop->seconds = timer.
lastLap();
296 std::cout << std::endl;
297 std::cout <<
"training time (seconds): " << timer.
lastLap() << std::endl;
298 std::cout <<
"number of epochs: " << epoch << std::endl;
299 std::cout <<
"number of iterations: " << (ell * epoch) << std::endl;
300 std::cout <<
"number of non-zero steps: " << steps << std::endl;
301 std::cout <<
"dual accuracy: " << max_violation << std::endl;
302 std::cout <<
"dual objective value: " << objective << std::endl;
303 std::cout <<
"number of free support vectors: " << free_SV << std::endl;
304 std::cout <<
"number of bounded support vectors: " << bounded_SV << std::endl;
331 : x(dataset.numberOfElements())
332 , y(dataset.numberOfElements())
333 , diagonal(dataset.numberOfElements())
345 for (std::size_t i=0; i<batch.size(); i++)
347 CompressedRealVector x_i =
shark::get(batch, i).input;
350 unsigned int y_i =
shark::get(batch, i).label;
351 y[j] = 2.0 * y_i - 1.0;
353 for (CompressedRealVector::const_iterator it=x_i.begin(); it != x_i.end(); ++it)
356 sparse.index = it.index();
358 storage.push_back(sparse);
361 sparse.index = (std::size_t)-1;
362 storage.push_back(sparse);
370 for (std::size_t i=0; i<batch.size(); i++)
372 CompressedRealVector x_i =
shark::get(batch, i).input;
376 for (; storage[k].index != (std::size_t)-1; k++);
397 bool verbose =
false)
408 std::size_t ell = x.size();
409 RealVector alpha(ell, 0.0);
411 RealVector pref(ell, 1.0);
412 double prefsum = ell;
413 std::vector<std::size_t> schedule(ell);
416 std::size_t epoch = 0;
417 std::size_t steps = 0;
420 double max_violation = 0.0;
421 const double gain_learning_rate = 1.0 / ell;
422 double average_gain = 0.0;
429 double psum = prefsum;
432 for (std::size_t i=0; i<ell; i++)
435 double num = (psum < 1e-6) ? ell - pos :
std::min((
double)(ell - pos), (ell - pos) * p / psum);
436 std::size_t n = (std::size_t)std::floor(num);
437 double prob = num - n;
439 for (std::size_t j=0; j<n; j++)
452 for (std::size_t j=0; j<ell; j++)
455 std::size_t i = schedule[j];
456 const SparseVector* x_i = x[i];
461 double g = 1.0 - wyx - reg * a;
462 double pg = (a == 0.0 && g < 0.0) ? 0.0 : (a == bound && g > 0.0 ? 0.0 : g);
465 max_violation =
std::max(max_violation, std::abs(pg));
472 double q = diagonal(i) + reg;
474 double new_a = a + mu;
482 else if (new_a >= bound)
491 axpy(w, mu * y(i), x_i);
492 gain = mu * (g - 0.5 * q * mu);
499 if (epoch == 0) average_gain += gain / (double)ell;
502 double change =
CHANGE_RATE * (gain / average_gain - 1.0);
504 prefsum += newpref - pref(i);
506 average_gain = (1.0 - gain_learning_rate) * average_gain + gain_learning_rate * gain;
522 if (prop != NULL) prop->type =
QpTimeout;
528 if (verbose) std::cout <<
"#" << std::flush;
538 for (std::size_t i=0; i<ell; i++) pref[i] = 1.0;
544 if (verbose) std::cout <<
"." << std::flush;
552 std::size_t free_SV = 0;
553 std::size_t bounded_SV = 0;
555 for (std::size_t i=0; i<ell; i++)
561 objective -= reg/2.0 * a * a;
562 if (a == bound) bounded_SV++;
570 prop->accuracy = max_violation;
571 prop->iterations = ell * epoch;
572 prop->value = objective;
573 prop->seconds = timer.
lastLap();
579 std::cout << std::endl;
580 std::cout <<
"training time (seconds): " << timer.
lastLap() << std::endl;
581 std::cout <<
"number of epochs: " << epoch << std::endl;
582 std::cout <<
"number of iterations: " << (ell * epoch) << std::endl;
583 std::cout <<
"number of non-zero steps: " << steps << std::endl;
584 std::cout <<
"dual accuracy: " << max_violation << std::endl;
585 std::cout <<
"dual objective value: " << objective << std::endl;
586 std::cout <<
"number of free support vectors: " << free_SV << std::endl;
587 std::cout <<
"number of bounded support vectors: " << bounded_SV << std::endl;
603 static inline void axpy(RealVector&
w,
double alpha,
const SparseVector* xi)
607 if (xi->index == (std::size_t)-1)
return;
608 w[xi->index] += alpha * xi->value;
614 static inline double inner_prod(RealVector
const&
w,
const SparseVector* xi)
619 if (xi->index == (std::size_t)-1)
return ret;
620 ret += w[xi->index] * xi->value;
626 std::vector<SparseVector*>
x;