Algorithm-LibLinear

 view release on metacpan or  search on metacpan

src/liblinear/linear.cpp  view on Meta::CPAN

				eps_shrink = max(eps_shrink/2, eps);
				start_from_all = true;
			}
		}
		else
			start_from_all = false;
	}

	info("\noptimization finished, #iter = %d\n",iter);
	if (iter >= max_iter)
		info("\nWARNING: reaching max number of iterations\n");

	// calculate objective value
	double v = 0;
	int nSV = 0;
	for(i=0;i<w_size*nr_class;i++)
		v += w[i]*w[i];
	v = 0.5*v;
	for(i=0;i<l*nr_class;i++)
	{
		v += alpha[i];

src/liblinear/linear.cpp  view on Meta::CPAN

//              upper_bound_i = INF
//              D_ii = 1/(2*Cp) if y_i = 1
//              D_ii = 1/(2*Cn) if y_i = -1
//
// Given:
// x, y, Cp, Cn
// eps is the stopping tolerance
//
// solution will be put in w
//
// this function returns the number of iterations
//
// See Algorithm 3 of Hsieh et al., ICML 2008

#undef GETI
#define GETI(i) (y[i]+1)
// To support weights for instances, use GETI(i) (i)

static int solve_l2r_l1l2_svc(const problem *prob, const parameter *param, double *w, double Cp, double Cn, int max_iter=300)
{
	int l = prob->l;

src/liblinear/linear.cpp  view on Meta::CPAN

// In L2-SVM case:
//              upper_bound_i = INF
//              lambda_i = 1/(2*C)
//
// Given:
// x, y, p, C
// eps is the stopping tolerance
//
// solution will be put in w
//
// this function returns the number of iterations
//
// See Algorithm 4 of Ho and Lin, 2012

#undef GETI
#define GETI(i) (0)
// To support weights for instances, use GETI(i) (i)

static int solve_l2r_l1l2_svr(const problem *prob, const parameter *param, double *w, int max_iter=300)
{
	const int solver_type = param->solver_type;

src/liblinear/linear.cpp  view on Meta::CPAN

//  where Qij = yi yj xi^T xj and
//  upper_bound_i = Cp if y_i = 1
//  upper_bound_i = Cn if y_i = -1
//
// Given:
// x, y, Cp, Cn
// eps is the stopping tolerance
//
// solution will be put in w
//
// this function returns the number of iterations
//
// See Algorithm 5 of Yu et al., MLJ 2010

#undef GETI
#define GETI(i) (y[i]+1)
// To support weights for instances, use GETI(i) (i)

static int solve_l2r_lr_dual(const problem *prob, const parameter *param, double *w, double Cp, double Cn, int max_iter=300)
{
	int l = prob->l;

src/liblinear/linear.cpp  view on Meta::CPAN

// L1-regularized L2-loss support vector classification
//
//  min_w \sum |wj| + C \sum max(0, 1-yi w^T xi)^2,
//
// Given:
// x, y, Cp, Cn
// eps is the stopping tolerance
//
// solution will be put in w
//
// this function returns the number of iterations
//
// See Yuan et al. (2010) and appendix of LIBLINEAR paper, Fan et al. (2008)
//
// To not regularize the bias (i.e., regularize_bias = 0), a constant feature = 1
// must have been added to the original data. (see -B and -R option)

#undef GETI
#define GETI(i) (y[i]+1)
// To support weights for instances, use GETI(i) (i)

src/liblinear/linear.cpp  view on Meta::CPAN

				Gmax_old = INF;
				continue;
			}
		}

		Gmax_old = Gmax_new;
	}

	info("\noptimization finished, #iter = %d\n", iter);
	if(iter >= max_iter)
		info("\nWARNING: reaching max number of iterations\n");

	// calculate objective value

	double v = 0;
	int nnz = 0;
	for(j=0; j<w_size; j++)
	{
		x = prob_col->x[j];
		while(x->index != -1)
		{

src/liblinear/linear.cpp  view on Meta::CPAN

// L1-regularized logistic regression problems
//
//  min_w \sum |wj| + C \sum log(1+exp(-yi w^T xi)),
//
// Given:
// x, y, Cp, Cn
// eps is the stopping tolerance
//
// solution will be put in w
//
// this function returns the number of iterations
//
// See Yuan et al. (2011) and appendix of LIBLINEAR paper, Fan et al. (2008)
//
// To not regularize the bias (i.e., regularize_bias = 0), a constant feature = 1
// must have been added to the original data. (see -B and -R option)

#undef GETI
#define GETI(i) (y[i]+1)
// To support weights for instances, use GETI(i) (i)

src/liblinear/linear.cpp  view on Meta::CPAN

					QP_active_size = active_size;
					QP_Gmax_old = INF;
					continue;
				}
			}

			QP_Gmax_old = QP_Gmax_new;
		}

		if(iter >= max_iter)
			info("WARNING: reaching max number of inner iterations\n");

		delta = 0;
		w_norm_new = 0;
		for(j=0; j<w_size; j++)
		{
			delta += Grad[j]*(wpd[j]-w[j]);
			if(wpd[j] != 0)
				w_norm_new += fabs(wpd[j]);
		}
		if (regularize_bias == 0)

src/liblinear/linear.cpp  view on Meta::CPAN

		newton_iter++;
		Gmax_old = Gmax_new;

		info("iter %3d  #CD cycles %d\n", newton_iter, iter);
	}

	info("=========================\n");
	info("optimization finished, #iter = %d\n", newton_iter);
	if(newton_iter >= max_newton_iter)
		info("WARNING: reaching max number of iterations\n");

	// calculate objective value

	double v = 0;
	int nnz = 0;
	for(j=0; j<w_size; j++)
		if(w[j] != 0)
		{
			v += fabs(w[j]);
			nnz++;

src/liblinear/linear.cpp  view on Meta::CPAN

//              e^T \alpha = \nu l
//
//  where Qij = xi^T xj
//
// Given:
// x, nu
// eps is the stopping tolerance
//
// solution will be put in w and rho
//
// this function returns the number of iterations
//
// See Algorithm 7 in supplementary materials of Chou et al., SDM 2020.

static int solve_oneclass_svm(const problem *prob, const parameter *param, double *w, double *rho)
{
	int l = prob->l;
	int w_size = prob->n;
	double eps = param->eps;
	double nu = param->nu;
	int i, j, s, iter = 0;

src/liblinear/linear.cpp  view on Meta::CPAN

			delta = alpha[i] - old_alpha_i;
			sparse_operator::axpy(delta, xi, w);
			sparse_operator::axpy(-delta, xj, w);
		}
		iter++;
		if (iter % 10 == 0)
			info(".");
	}
	info("\noptimization finished, #iter = %d\n",iter);
	if (iter >= max_iter)
		info("\nWARNING: reaching max number of iterations\n\n");

	// calculate object value
	double v = 0;
	for(i=0; i<w_size; i++)
		v += w[i]*w[i];
	int nSV = 0;
	for(i=0; i<l; i++)
	{
		if (alpha[i] > 0)
			++nSV;

src/liblinear/linear.cpp  view on Meta::CPAN

			NEWTON newton_obj(&fun_obj, primal_solver_tol);
			newton_obj.set_print_string(liblinear_print_string);
			newton_obj.newton(w);
			break;
		}
		case L2R_L2LOSS_SVC_DUAL:
		{
			iter = solve_l2r_l1l2_svc(prob, param, w, Cp, Cn, dual_solver_max_iter);
			if(iter >= dual_solver_max_iter)
			{
				info("\nWARNING: reaching max number of iterations\nSwitching to use -s 2\n\n");
				// primal_solver_tol obtained from eps for dual may be too loose
				primal_solver_tol *= 0.1;
				l2r_l2_svc_fun fun_obj(prob, param, C);
				NEWTON newton_obj(&fun_obj, primal_solver_tol);
				newton_obj.set_print_string(liblinear_print_string);
				newton_obj.newton(w);
			}
			break;
		}
		case L2R_L1LOSS_SVC_DUAL:
		{
			iter = solve_l2r_l1l2_svc(prob, param, w, Cp, Cn, dual_solver_max_iter);
			if(iter >= dual_solver_max_iter)
				info("\nWARNING: reaching max number of iterations\nUsing -s 2 may be faster (also see FAQ)\n\n");			
			break;
		}
		case L1R_L2LOSS_SVC:
		{
			problem prob_col;
			feature_node *x_space = NULL;
			transpose(prob, &x_space ,&prob_col);
			solve_l1r_l2_svc(&prob_col, param, w, Cp, Cn, primal_solver_tol);
			delete [] prob_col.y;
			delete [] prob_col.x;

src/liblinear/linear.cpp  view on Meta::CPAN

			delete [] prob_col.y;
			delete [] prob_col.x;
			delete [] x_space;
			break;
		}
		case L2R_LR_DUAL:
		{
			iter = solve_l2r_lr_dual(prob, param, w, Cp, Cn, dual_solver_max_iter);
			if(iter >= dual_solver_max_iter)
			{
				info("\nWARNING: reaching max number of iterations\nSwitching to use -s 0\n\n");
				// primal_solver_tol obtained from eps for dual may be too loose
				primal_solver_tol *= 0.1;
				l2r_lr_fun fun_obj(prob, param, C);
				NEWTON newton_obj(&fun_obj, primal_solver_tol);
				newton_obj.set_print_string(liblinear_print_string);
				newton_obj.newton(w);
			}
			break;
		}
		case L2R_L2LOSS_SVR:

src/liblinear/linear.cpp  view on Meta::CPAN

			l2r_l2_svr_fun fun_obj(prob, param, C);
			NEWTON newton_obj(&fun_obj, primal_solver_tol);
			newton_obj.set_print_string(liblinear_print_string);
			newton_obj.newton(w);
			break;
		}
		case L2R_L1LOSS_SVR_DUAL:
		{
			iter = solve_l2r_l1l2_svr(prob, param, w, dual_solver_max_iter);
			if(iter >= dual_solver_max_iter)
				info("\nWARNING: reaching max number of iterations\nUsing -s 11 may be faster (also see FAQ)\n\n");			

			break;
		}
		case L2R_L2LOSS_SVR_DUAL:
		{
			iter = solve_l2r_l1l2_svr(prob, param, w, dual_solver_max_iter);
			if(iter >= dual_solver_max_iter)
			{
				info("\nWARNING: reaching max number of iterations\nSwitching to use -s 11\n\n");
				// primal_solver_tol obtained from eps for dual may be too loose
				primal_solver_tol *= 0.001;
				l2r_l2_svr_fun fun_obj(prob, param, C);
				NEWTON newton_obj(&fun_obj, primal_solver_tol);
				newton_obj.set_print_string(liblinear_print_string);
				newton_obj.newton(w);
			}
			break;
		}
		default:

src/liblinear/newton.cpp  view on Meta::CPAN

		if (fabs(actred) <= 1.0e-12*fabs(f))
		{
			info("WARNING: actred too small\n");
			break;
		}

		iter++;
	}

	if(iter >= max_iter)
		info("\nWARNING: reaching max number of Newton iterations\n");

	delete[] g;
	delete[] r;
	delete[] s;
	delete[] M;
}

int NEWTON::pcg(double *g, double *M, double *s, double *r)
{
	int i, inc = 1;