Algorithm-LBFGS
view release on metacpan or search on metacpan
Algorithm-LBFGS.xs view on Meta::CPAN
SV* r = &PL_sv_undef;
CODE:
if (strcmp(name, "m") == 0) {
if (SvIOK(val)) p->m = SvIV(val);
r = newSViv(p->m);
}
else if (strcmp(name, "epsilon") == 0) {
if (SvNOK(val)) p->epsilon = SvNV(val);
r = newSVnv(p->epsilon);
}
else if (strcmp(name, "max_iterations") == 0) {
if (SvIOK(val)) p->max_iterations = SvIV(val);
r = newSViv(p->max_iterations);
}
else if (strcmp(name, "max_linesearch") == 0) {
if (SvIOK(val)) p->max_linesearch = SvIV(val);
r = newSViv(p->max_linesearch);
}
else if (strcmp(name, "min_step") == 0) {
if (SvNOK(val)) p->min_step = SvNV(val);
r = newSVnv(p->min_step);
}
else if (strcmp(name, "max_step") == 0) {
The client program can also pass string values to "progress_cb", which
means it want to use a predefined progress callback subroutine. There
are two predefined progress callback subroutines, 'verbose' and
'logging'. 'verbose' just prints out all information of each iteration,
while 'logging' logs the same information in an array ref provided by
"user_data".
...
# print out the iterations
fmin($eval_cb, $x0, 'verbose');
# log iterations information in the array ref $log
my $log = [];
fmin($eval_cb, $x0, 'logging', $log);
use Data::Dumper;
print Dumper $log;
user_data
The extra user data. It will be sent to both "evaluation_cb" and
"progress_cb".
if ($o->fmin(...), $o->status_ok) {
...
}
List of Parameters
m
The number of corrections to approximate the inverse hessian matrix.
The L-BFGS algorithm stores the computation results of previous "m"
iterations to approximate the inverse hessian matrix of the current
iteration. This parameter controls the size of the limited memories
(corrections). The default value is 6. Values less than 3 are not
recommended. Large values will result in excessive computing time.
epsilon
Epsilon for convergence test.
This parameter determines the accuracy with which the solution is to be
found. A minimization terminates when
||grad f(x)|| < epsilon * max(1, ||x||)
where ||.|| denotes the Euclidean (L2) norm. The default value is 1e-5.
max_iterations
The maximum number of iterations.
The L-BFGS algorithm terminates an optimization process with
"LBFGSERR_MAXIMUMITERATION" status code when the iteration count
exceedes this parameter. Setting this parameter to zero continues an
optimization process until a convergence or error. The default value is
0.
max_linesearch
The maximum number of trials for the line search.
LBFGSERR_MINIMUMSTEP
The line-search step became smaller than "min_step".
LBFGSERR_MAXIMUMSTEP
The line-search step became larger than "max_step".
LBFGSERR_MAXIMUMLINESEARCH
The line-search routine reaches the maximum number of evaluations.
LBFGSERR_MAXIMUMITERATION
The algorithm routine reaches the maximum number of iterations.
LBFGSERR_WIDTHTOOSMALL
Relative width of the interval of uncertainty is at most "xtol".
LBFGSERR_INVALIDPARAMETERS
A logic error (negative line-search step) occurred.
LBFGSERR_INCREASEGRADIENT
The current search direction increases the objective function value.
The criterion is given by the following formula:
|g(x)| / \max(1, |x|) < \epsilon
*/
if (xnorm < 1.0) xnorm = 1.0;
if (gnorm / xnorm <= param->epsilon) {
/* Convergence. */
ret = 0;
break;
}
if (param->max_iterations != 0 && param->max_iterations < k+1) {
/* Maximum number of iterations. */
ret = LBFGSERR_MAXIMUMITERATION;
break;
}
/*
Update vectors s and y:
s_{k+1} = x_{k+1} - x_{k} = \step * d_{k}.
y_{k+1} = g_{k+1} - g_{k}.
*/
it = &lm[end];
LBFGSERR_INCORRECT_TMINMAX,
/** A rounding error occurred; alternatively, no line-search step
satisfies the sufficient decrease and curvature conditions. */
LBFGSERR_ROUNDING_ERROR,
/** The line-search step became smaller than lbfgs_parameter_t::min_step. */
LBFGSERR_MINIMUMSTEP,
/** The line-search step became larger than lbfgs_parameter_t::max_step. */
LBFGSERR_MAXIMUMSTEP,
/** The line-search routine reaches the maximum number of evaluations. */
LBFGSERR_MAXIMUMLINESEARCH,
/** The algorithm routine reaches the maximum number of iterations. */
LBFGSERR_MAXIMUMITERATION,
/** Relative width of the interval of uncertainty is at most
lbfgs_parameter_t::xtol. */
LBFGSERR_WIDTHTOOSMALL,
/** A logic error (negative line-search step) occurred. */
LBFGSERR_INVALIDPARAMETERS,
/** The current search direction increases the objective function value. */
LBFGSERR_INCREASEGRADIENT,
};
/**
* L-BFGS optimization parameters.
* Call lbfgs_parameter_init() function to initialize parameters to the
* default values.
*/
typedef struct {
/**
* The number of corrections to approximate the inverse hessian matrix.
* The L-BFGS routine stores the computation results of previous \ref m
* iterations to approximate the inverse hessian matrix of the current
* iteration. This parameter controls the size of the limited memories
* (corrections). The default value is \c 6. Values less than \c 3 are
* not recommended. Large values will result in excessive computing time.
*/
int m;
/**
* Epsilon for convergence test.
* This parameter determines the accuracy with which the solution is to
* be found. A minimization terminates when
* ||g|| < \ref epsilon * max(1, ||x||),
* where ||.|| denotes the Euclidean (L2) norm. The default value is
* \c 1e-5.
*/
lbfgsfloatval_t epsilon;
/**
* The maximum number of iterations.
* The lbfgs() function terminates an optimization process with
* ::LBFGSERR_MAXIMUMITERATION status code when the iteration count
* exceedes this parameter. Setting this parameter to zero continues an
* optimization process until a convergence or error. The default value
* is \c 0.
*/
int max_iterations;
/**
* The maximum number of trials for the line search.
* This parameter controls the number of function and gradients evaluations
* per iteration for the line search routine. The default value is \c 20.
*/
int max_linesearch;
/**
* The minimum step of the line search routine.
* value of the objective function for the variables.
* This argument can be set to \c NULL if the final
* value of the objective function is unnecessary.
* @param proc_evaluate The callback function to provide function and
* gradient evaluations given a current values of
* variables. A client program must implement a
* callback function compatible with \ref
* lbfgs_evaluate_t and pass the pointer to the
* callback function.
* @param proc_progress The callback function to receive the progress
* (the number of iterations, the current value of
* the objective function) of the minimization
* process. This argument can be set to \c NULL if
* a progress report is unnecessary.
* @param instance A user data for the client program. The callback
* functions will receive the value of this argument.
* @param param The pointer to a structure representing parameters for
* L-BFGS optimization. A client program can set this
* parameter to \c NULL to use the default parameters.
* Call lbfgs_parameter_init() function to fill a
* structure with the default values.
minimize F(x), x = (x1, x2, ..., xN),
</pre>
only if the objective function F(x) and its gradient G(x) are computable. The
Newton's method, which is a well-known algorithm for the optimization,
requires computation or approximation of the inverse of the hessian matrix of
the objective function in order to find the point where the gradient G(X) = 0.
The computational cost for the inverse hessian matrix is expensive especially
when the objective function takes a large number of variables. The L-BFGS
method approximates the inverse hessian matrix efficiently by using information
from last m iterations. This innovation saves the memory storage and
computational time a lot for large-scaled problems.
Among the various ports of L-BFGS, this library provides several features:
- <b>Optimization with L1-norm (orthant-wise L-BFGS)</b>:
In addition to standard minimization problems, the library can minimize
a function F(x) combined with L1-norm |x| of the variables,
{F(x) + C |x|}, where C is a constant scalar parameter. This feature is
useful for estimating parameters of log-linear models with L1-regularization.
- <b>Clean C code</b>:
Unlike C codes generated automatically by f2c (Fortran 77 into C converter),
lib/Algorithm/LBFGS.pm view on Meta::CPAN
terminates with status code L</"LBFGSERR_CANCELED">.
The client program can also pass string values to L</"progress_cb">, which
means it want to use a predefined progress callback subroutine. There are
two predefined progress callback subroutines, 'verbose' and 'logging'.
'verbose' just prints out all information of each iteration, while 'logging'
logs the same information in an array ref provided by L</"user_data">.
...
# print out the iterations
fmin($eval_cb, $x0, 'verbose');
# log iterations information in the array ref $log
my $log = [];
fmin($eval_cb, $x0, 'logging', $log);
use Data::Dumper;
print Dumper $log;
=head3 user_data
lib/Algorithm/LBFGS.pm view on Meta::CPAN
...
}
=head2 List of Parameters
=head3 m
The number of corrections to approximate the inverse hessian matrix.
The L-BFGS algorithm stores the computation results of previous L</"m">
iterations to approximate the inverse hessian matrix of the current
iteration. This parameter controls the size of the limited memories
(corrections). The default value is 6. Values less than 3 are not
recommended. Large values will result in excessive computing time.
=head3 epsilon
Epsilon for convergence test.
This parameter determines the accuracy with which the solution is to be
found. A minimization terminates when
||grad f(x)|| < epsilon * max(1, ||x||)
where ||.|| denotes the Euclidean (L2) norm. The default value is 1e-5.
=head3 max_iterations
The maximum number of iterations.
The L-BFGS algorithm terminates an optimization process with
L</"LBFGSERR_MAXIMUMITERATION"> status code when the iteration count
exceedes this parameter. Setting this parameter to zero continues an
optimization process until a convergence or error. The default value is 0.
=head3 max_linesearch
The maximum number of trials for the line search.
lib/Algorithm/LBFGS.pm view on Meta::CPAN
=head3 LBFGSERR_MAXIMUMSTEP
The line-search step became larger than L</"max_step">.
=head3 LBFGSERR_MAXIMUMLINESEARCH
The line-search routine reaches the maximum number of evaluations.
=head3 LBFGSERR_MAXIMUMITERATION
The algorithm routine reaches the maximum number of iterations.
=head3 LBFGSERR_WIDTHTOOSMALL
Relative width of the interval of uncertainty is at most L</"xtol">.
=head3 LBFGSERR_INVALIDPARAMETERS
A logic error (negative line-search step) occurred.
=head3 LBFGSERR_INCREASEGRADIENT
t/01-parameter.t view on Meta::CPAN
0.9,
0.0
],
$__;
###
NAME 'Default parameters - 2';
is_deeply
[
$o->get_param('m'),
$o->get_param('max_iterations'),
$o->get_param('max_linesearch')
],
[
6,
0,
20
],
$__;
###
( run in 0.599 second using v1.01-cache-2.11-cpan-71847e10f99 )