51 void CLibLinear::init()
87 SG_ERROR(
"Specified features are not of type CDotFeatures\n")
101 if (num_feat!=num_train_labels)
103 SG_ERROR(
"L1 methods require the data to be transposed: "
104 "number of features %d does not match number of "
105 "training labels %d\n",
106 num_feat, num_train_labels);
113 if (num_vec!=num_train_labels)
115 SG_ERROR(
"number of vectors %d does not match "
116 "number of training labels %d\n",
117 num_vec, num_train_labels);
125 liblinear_problem prob;
141 prob.y=SG_MALLOC(
double, prob.l);
147 for (int32_t i=0; i<prob.l; i++)
152 else if (prob.y[i] == -1)
155 SG_ERROR(
"labels should be +1/-1 only\n")
160 for(
int i=0;i<prob.l;i++)
167 SG_INFO(
"%d training points %d dims\n", prob.l, prob.n)
169 function *fun_obj=NULL;
174 fun_obj=
new l2r_lr_fun(&prob, Cs);
176 SG_DEBUG(
"starting L2R_LR training via tron\n")
184 fun_obj=
new l2r_l2_svc_fun(&prob, Cs);
210 solve_l2r_lr_dual(&prob,
epsilon, Cp, Cn);
214 SG_ERROR(
"Error: unknown solver_type\n")
254 #define GETI(i) (y[i]+1)
257 void CLibLinear::solve_l2r_l1l2_svc(
261 int w_size = prob->n;
264 double *QD = SG_MALLOC(
double, l);
265 int *index = SG_MALLOC(
int, l);
266 double *alpha = SG_MALLOC(
double, l);
267 int32_t *y = SG_MALLOC(int32_t, l);
274 double PGmax_new, PGmin_new;
277 double diag[3] = {0.5/Cn, 0, 0.5/Cp};
292 for(i=0; i<w_size; i++)
306 QD[i] = diag[
GETI(i)];
308 QD[i] += prob->x->dot(i, prob->x,i);
322 for (i=0; i<active_size; i++)
328 for (s=0;s<active_size;s++)
333 G = prob->x->dense_dot(i,
w.
vector, n);
342 C = upper_bound[
GETI(i)];
343 G += alpha[i]*diag[
GETI(i)];
358 else if (alpha[i] == C)
376 if(fabs(PG) > 1.0e-12)
378 double alpha_old = alpha[i];
380 d = (alpha[i] - alpha_old)*yi;
382 prob->x->add_to_dense_vec(d, i,
w.
vector, n);
405 PGmax_old = PGmax_new;
406 PGmin_old = PGmin_new;
414 SG_INFO("optimization finished,
#iter = %d\n",iter)
417 SG_WARNING(
"reaching max number of iterations\nUsing -s 2 may be faster"
418 "(also see liblinear FAQ)\n\n");
425 for(i=0; i<w_size; i++)
429 v += alpha[i]*(alpha[i]*diag[
GETI(i)] - 2);
433 SG_INFO(
"Objective value = %lf\n",v/2)
454 #define GETI(i) (y[i]+1)
457 void CLibLinear::solve_l1r_l2_svc(
458 liblinear_problem *prob_col,
double eps,
double Cp,
double Cn)
461 int w_size = prob_col->n;
463 int active_size = w_size;
464 int max_num_linesearch = 20;
467 double d, G_loss, G, H;
471 double d_old, d_diff;
472 double loss_old=0, loss_new;
473 double appxcond, cond;
475 int *index = SG_MALLOC(
int, w_size);
476 int32_t *y = SG_MALLOC(int32_t, l);
477 double *b = SG_MALLOC(
double, l);
478 double *xj_sq = SG_MALLOC(
double, w_size);
485 double C[3] = {Cn,0,Cp};
488 if (prob_col->use_bias)
494 if(prob_col->y[j] > 0)
500 for(j=0; j<w_size; j++)
508 for (ind=0; ind<l; ind++)
509 xj_sq[n] += C[
GETI(ind)];
513 iterator=x->get_feature_iterator(j);
514 while (x->get_next_feature(ind, val, iterator))
515 xj_sq[j] += C[
GETI(ind)]*val*val;
516 x->free_feature_iterator(iterator);
529 for(j=0; j<active_size; j++)
535 for(s=0; s<active_size; s++)
543 for (ind=0; ind<l; ind++)
547 double tmp = C[
GETI(ind)]*y[ind];
548 G_loss -= tmp*b[ind];
555 iterator=x->get_feature_iterator(j);
557 while (x->get_next_feature(ind, val, iterator))
561 double tmp = C[
GETI(ind)]*val*y[ind];
562 G_loss -= tmp*b[ind];
566 x->free_feature_iterator(iterator);
577 double violation = 0;
584 else if(Gp>Gmax_old/l && Gn<-Gmax_old/l)
593 violation = fabs(Gp);
595 violation = fabs(Gn);
607 if(fabs(d) < 1.0e-12)
613 for(num_linesearch=0; num_linesearch < max_num_linesearch; num_linesearch++)
618 appxcond = xj_sq[j]*d*d + G_loss*d + cond;
623 for (ind=0; ind<l; ind++)
624 b[ind] += d_diff*y[ind];
629 iterator=x->get_feature_iterator(j);
630 while (x->get_next_feature(ind, val, iterator))
631 b[ind] += d_diff*val*y[ind];
633 x->free_feature_iterator(iterator);
638 if(num_linesearch == 0)
645 for (ind=0; ind<l; ind++)
648 loss_old += C[
GETI(ind)]*b[ind]*b[ind];
649 double b_new = b[ind] + d_diff*y[ind];
652 loss_new += C[
GETI(ind)]*b_new*b_new;
657 iterator=x->get_feature_iterator(j);
658 while (x->get_next_feature(ind, val, iterator))
661 loss_old += C[
GETI(ind)]*b[ind]*b[ind];
662 double b_new = b[ind] + d_diff*val*y[ind];
665 loss_new += C[
GETI(ind)]*b_new*b_new;
667 x->free_feature_iterator(iterator);
675 for (ind=0; ind<l; ind++)
677 double b_new = b[ind] + d_diff*y[ind];
680 loss_new += C[
GETI(ind)]*b_new*b_new;
685 iterator=x->get_feature_iterator(j);
686 while (x->get_next_feature(ind, val, iterator))
688 double b_new = b[ind] + d_diff*val*y[ind];
691 loss_new += C[
GETI(ind)]*b_new*b_new;
693 x->free_feature_iterator(iterator);
697 cond = cond + loss_new - loss_old;
711 if(num_linesearch >= max_num_linesearch)
714 for(
int i=0; i<l; i++)
717 for(
int i=0; i<n; i++)
722 iterator=x->get_feature_iterator(i);
723 while (x->get_next_feature(ind, val, iterator))
724 b[ind] -=
w.
vector[i]*val*y[ind];
725 x->free_feature_iterator(iterator);
730 for (ind=0; ind<l; ind++)
737 Gmax_init = Gmax_new;
743 if(Gmax_new <= eps*Gmax_init)
745 if(active_size == w_size)
749 active_size = w_size;
759 SG_INFO("optimization finished,
#iter = %d\n", iter)
761 SG_WARNING(
"\nWARNING: reaching max number of iterations\n")
767 for(j=0; j<w_size; j++)
777 v += C[
GETI(j)]*b[j]*b[j];
779 SG_INFO(
"Objective value = %lf\n", v)
780 SG_INFO("
#nonzeros/#features = %d/%d\n", nnz, w_size)
800 #define GETI(i) (y[i]+1)
803 void CLibLinear::solve_l1r_lr(
804 const liblinear_problem *prob_col,
double eps,
805 double Cp,
double Cn)
808 int w_size = prob_col->n;
810 int active_size = w_size;
811 int max_num_linesearch = 20;
819 double sum1, appxcond1;
820 double sum2, appxcond2;
823 int *index = SG_MALLOC(
int, w_size);
824 int32_t *y = SG_MALLOC(int32_t, l);
825 double *exp_wTx = SG_MALLOC(
double, l);
826 double *exp_wTx_new = SG_MALLOC(
double, l);
827 double *xj_max = SG_MALLOC(
double, w_size);
828 double *C_sum = SG_MALLOC(
double, w_size);
829 double *xjneg_sum = SG_MALLOC(
double, w_size);
830 double *xjpos_sum = SG_MALLOC(
double, w_size);
837 double C[3] = {Cn,0,Cp};
840 if (prob_col->use_bias)
846 if(prob_col->y[j] > 0)
851 for(j=0; j<w_size; j++)
862 for (ind=0; ind<l; ind++)
866 C_sum[j] += C[
GETI(ind)];
868 xjneg_sum[j] += C[
GETI(ind)];
870 xjpos_sum[j] += C[
GETI(ind)];
880 C_sum[j] += C[
GETI(ind)];
882 xjneg_sum[j] += C[
GETI(ind)]*val;
884 xjpos_sum[j] += C[
GETI(ind)]*val;
898 for(j=0; j<active_size; j++)
904 for(s=0; s<active_size; s++)
913 for (ind=0; ind<l; ind++)
915 double exp_wTxind = exp_wTx[ind];
916 double tmp1 = 1.0/(1+exp_wTxind);
917 double tmp2 = C[
GETI(ind)]*tmp1;
918 double tmp3 = tmp2*exp_wTxind;
929 double exp_wTxind = exp_wTx[ind];
930 double tmp1 = val/(1+exp_wTxind);
931 double tmp2 = C[
GETI(ind)]*tmp1;
932 double tmp3 = tmp2*exp_wTxind;
940 G = -sum2 + xjneg_sum[j];
944 double violation = 0;
951 else if(Gp>Gmax_old/l && Gn<-Gmax_old/l)
960 violation = fabs(Gp);
962 violation = fabs(Gn);
974 if(fabs(d) < 1.0e-12)
981 for(num_linesearch=0; num_linesearch < max_num_linesearch; num_linesearch++)
987 double tmp = exp(d*xj_max[j]);
988 appxcond1 = log(1+sum1*(tmp-1)/xj_max[j]/C_sum[j])*C_sum[j] + cond - d*xjpos_sum[j];
989 appxcond2 = log(1+sum2*(1/tmp-1)/xj_max[j]/C_sum[j])*C_sum[j] + cond + d*xjneg_sum[j];
994 for (ind=0; ind<l; ind++)
995 exp_wTx[ind] *= exp(d);
1002 exp_wTx[ind] *= exp(d*val);
1009 cond += d*xjneg_sum[j];
1015 for (ind=0; ind<l; ind++)
1017 double exp_dx = exp(d);
1018 exp_wTx_new[i] = exp_wTx[ind]*exp_dx;
1019 cond += C[
GETI(ind)]*log((1+exp_wTx_new[i])/(exp_dx+exp_wTx_new[i]));
1029 double exp_dx = exp(d*val);
1030 exp_wTx_new[i] = exp_wTx[ind]*exp_dx;
1031 cond += C[
GETI(ind)]*log((1+exp_wTx_new[i])/(exp_dx+exp_wTx_new[i]));
1042 for (ind=0; ind<l; ind++)
1044 exp_wTx[ind] = exp_wTx_new[i];
1053 exp_wTx[ind] = exp_wTx_new[i];
1070 if(num_linesearch >= max_num_linesearch)
1073 for(
int i=0; i<l; i++)
1076 for(
int i=0; i<w_size; i++)
1082 for (ind=0; ind<l; ind++)
1089 exp_wTx[ind] +=
w.
vector[i]*val;
1094 for(
int i=0; i<l; i++)
1095 exp_wTx[i] = exp(exp_wTx[i]);
1100 Gmax_init = Gmax_new;
1104 if(Gmax_new <= eps*Gmax_init)
1106 if(active_size == w_size)
1110 active_size = w_size;
1116 Gmax_old = Gmax_new;
1120 SG_INFO("optimization finished,
#iter = %d\n", iter)
1122 SG_WARNING(
"\nWARNING: reaching max number of iterations\n")
1128 for(j=0; j<w_size; j++)
1129 if(
w.vector[j] != 0)
1136 v += C[
GETI(j)]*log(1+1/exp_wTx[j]);
1138 v += C[
GETI(j)]*log(1+exp_wTx[j]);
1140 SG_INFO(
"Objective value = %lf\n", v)
1141 SG_INFO("
#nonzeros/#features = %d/%d\n", nnz, w_size)
1146 SG_FREE(exp_wTx_new);
1172 #define GETI(i) (y[i]+1)
1175 void CLibLinear::solve_l2r_lr_dual(
const liblinear_problem *prob,
double eps,
double Cp,
double Cn)
1178 int w_size = prob->n;
1180 double *xTx =
new double[l];
1181 int max_iter = 1000;
1182 int *index =
new int[l];
1183 double *alpha =
new double[2*l];
1184 int32_t *y =
new int32_t[l];
1185 int max_inner_iter = 100;
1186 double innereps = 1e-2;
1188 double upper_bound[3] = {Cn, 0, Cp};
1189 double Gmax_init = 0;
1209 alpha[2*i+1] = upper_bound[
GETI(i)] - alpha[2*i];
1212 for(i=0; i<w_size; i++)
1216 xTx[i] = prob->x->dot(i, prob->x,i);
1217 prob->x->add_to_dense_vec(y[i]*alpha[2*i], i,
w.
vector, w_size);
1221 w.
vector[w_size]+=y[i]*alpha[2*i];
1227 while (iter < max_iter)
1234 int newton_iter = 0;
1240 double C = upper_bound[
GETI(i)];
1241 double ywTx = 0, xisq = xTx[i];
1243 ywTx = prob->x->dense_dot(i,
w.
vector, w_size);
1248 double a = xisq, b = ywTx;
1251 int ind1 = 2*i, ind2 = 2*i+1, sign = 1;
1252 if(0.5*a*(alpha[ind2]-alpha[ind1])+b < 0)
1260 double alpha_old = alpha[ind1];
1261 double z = alpha_old;
1264 double gp = a*(z-alpha_old)+sign*b+
CMath::log(z/(C-z));
1268 const double eta = 0.1;
1270 while (inner_iter <= max_inner_iter)
1272 if(fabs(gp) < innereps)
1274 double gpp = a + C/(C-z)/z;
1275 double tmpz = z - gp/gpp;
1280 gp = a*(z-alpha_old)+sign*b+log(z/(C-z));
1290 prob->x->add_to_dense_vec(sign*(z-alpha_old)*yi, i,
w.
vector, w_size);
1293 w.
vector[w_size]+=sign*(z-alpha_old)*yi;
1306 if(newton_iter <= l/10)
1307 innereps =
CMath::max(innereps_min, 0.1*innereps);
1312 SG_INFO(
"optimization finished, #iter = %d\n",iter)
1313 if (iter >= max_iter)
1314 SG_WARNING(
"reaching max number of iterations\nUsing -s 0 may be faster (also see FAQ)\n\n")
1319 for(i=0; i<w_size; i++)
1323 v += alpha[2*i] * log(alpha[2*i]) + alpha[2*i+1] * log(alpha[2*i+1])
1324 - upper_bound[
GETI(i)] * log(upper_bound[
GETI(i)]);
1325 SG_INFO(
"Objective value = %lf\n", v)
1337 SG_ERROR(
"Please assign labels first!\n")
1341 if (num_labels!=linear_term.
vlen)
1343 SG_ERROR(
"Number of labels (%d) does not match number"
1344 " of entries (%d) in linear term \n", num_labels,
1354 SG_ERROR(
"Please assign linear term first!\n")
1362 SG_ERROR(
"Please assign labels first!\n")
Class Time that implements a stopwatch based on either cpu time or wall clock time.
static void fill_vector(T *vec, int32_t len, T value)
virtual ELabelType get_label_type() const =0
L2 regularized linear logistic regression via dual.
The class Labels models labels, i.e. class assignments of objects.
static const float64_t INFTY
infinity
virtual int32_t get_num_labels() const =0
static float64_t log10(float64_t v)
L2 regularized SVM with L2-loss using newton in the primal.
L1 regularized logistic regression.
virtual int32_t get_num_vectors() const =0
void tron(float64_t *w, float64_t max_train_time)
float64_t m_max_train_time
L1 regularized SVM with L2-loss using dual coordinate descent.
Features that support dot products among other operations.
SGVector< float64_t > get_linear_term()
virtual int32_t get_dim_feature_space() const =0
float64_t cur_time_diff(bool verbose=false)
void set_linear_term(const SGVector< float64_t > linear_term)
void set_max_iterations(int32_t max_iter=1000)
static void clear_cancel()
L2 regularized linear logistic regression.
virtual void free_feature_iterator(void *iterator)=0
L2 regularized SVM with L2-loss using dual coordinate descent.
virtual void set_features(CDotFeatures *feat)
Class LinearMachine is a generic interface for all kinds of linear machines like classifiers.
LIBLINEAR_SOLVER_TYPE liblinear_solver_type
static bool cancel_computations()
virtual void * get_feature_iterator(int32_t vector_index)=0
virtual void set_compute_bias(bool compute_bias)
virtual bool get_next_feature(int32_t &index, float64_t &value, void *iterator)=0
all of classes and functions are contained in the shogun namespace
The class Features is the base class of all feature objects.
static float64_t log(float64_t v)
virtual bool train_machine(CFeatures *data=NULL)
Binary Labels for binary classification.
static void swap(T &a, T &b)
virtual void set_bias(float64_t b)
L2 regularized linear SVM with L1-loss using dual coordinate descent.
bool has_property(EFeatureProperty p) const
virtual void set_labels(CLabels *lab)
#define SG_SABS_PROGRESS(...)
SGVector< float64_t > m_linear_term