Guan-Ting Chen [Wed, 18 Jan 2023 06:37:03 +0000 (14:37 +0800)]
Some improvements/changes in the one-class SVM solver:
- use quickselect and quicksort instead of heap to shorten the running
time on finding violating pairs. See details in a new section in
supplementary materials of our linear one-class SVM paper.
- modify the comparison function so instances with the same gradient
values are ordered by their instance indices. This ensures the same
results by using different implementations (e.g.,
quickselect/quicksort vs. heap)
linear.cpp (check_parameter): only check value of p if L2R_L2LOSS_SVR.
The parameter `p` is only used by the L2R_L2LOSS_SVR solver so skip
checking its value unless using it. This is important because it has
no default value meaning that we are effectively forcing the user to
set it even if they don't use it.
Signed-off-by: Chih-Jen Lin <cjlin@csie.ntu.edu.tw>
Adjust eps parameter comment in README: "stopping tolerance"
The comment was changed in linear.h via https://github.com/cjlin1/liblinear/commit/7b0193baec9a443684e4a079ae4a2040971f67cf.
However, the code snippet in the README was not adjusted.
Signed-off-by: Chih-Jen Lin <cjlin@csie.ntu.edu.tw>
Chih-Jen Lin [Wed, 28 Oct 2020 09:01:51 +0000 (17:01 +0800)]
Stopping conditon of dual CD method for L1- and L2-loss SVM is changed
Currently the stopping condition is M-m <= \epsilon, where
M = max proj_gard(alpha) and m = min proj_grad(alpha).
This condition works well in practice, but we must ensure that the
following situation does not occur.
M, m >> 0 or M,m << 0
but
M - m <= \epsilon.
From the optimality condition, |M| and |m| must be close to zero.
For example, because
grad_i f(0) = -1, for all i.
M=m= -1 and they satisfy M-m <= \epsilon. Thus we add |M| <=\epsilon
and |m| <= \epsilon$ into the stopping condition. In fact we can use
only these two inequalities as the stopping condition, but for
historical reasons we keep M-m <= \epsilon as the main condition to
check.
Chih-Jen Lin [Tue, 20 Oct 2020 23:57:44 +0000 (07:57 +0800)]
Automatic switching from dual CD to primal Newton if slow convergence occurs.
For l2-regularized logistic regression and L2-loss linear SVM,
liblinear provides two types of solvers: dual CD and primal Newton.
They are respectively first-order and second-order methods,
and are suitable under different circumstances.
The default solver (dual CD) may be slow
in some situations (e.g., data not scaled). In the past,
if slow convergence occurs, liblinear
issues a warning message suggesting users to use the
primal Newton method. In this commit this switch becomes automatic
to ensure that a reasonably good approximate solution of the
optimization problem is directly returned to the user.
The main change is in train_one(). It checks if iter of dual CD >= max_iter
and then switch to call primal Newton. Stopping tolerance is also adjusted.
minor changes:
- in comments tabs replaced with spaces
- for calling dual solvers, instead of passing individual parameters, the structure param is now passed
Chih-Jen Lin [Fri, 16 Oct 2020 12:40:20 +0000 (20:40 +0800)]
Two changes in newton.cpp
- in the previous version, the output is like
init f 1.403e+07
iter 1 f 5.390e+06 |g| 6.197e+05 CG 2 step_size 1.00e+00
we indeed print
f(w_k) |g(w_{k-1})|
So |g| 6.197e+05 is the grad at f(0) = 1.403e+07.
The output is changed to
init f 1.403e+07 |g| 6.197e+05
iter 1 f 5.390e+06 |g| 2.118e+05 CG 2 step_size 1.00e+00
iter 2 f 1.925e+06 |g| 7.244e+04 CG 4 step_size 1.00e+00
Each line shows the new f and |g| after an iteration with
CG steps and line search step_size
- in pcg(), we calculate
alpha = zTr/ddot_(&n, d, &inc, Hd, &inc);
before the stopping condition based on quadratic approximations.
But after the previous CG step, the new zTr and dHd may both be zero
(or very close to zero). Then 0/0 may occur. In such a situation CG
should stop. Now a safeguard check is added:
Newton solver is changed from trust region to line search
Specific changes are as follows.
- file name change:
tron.cpp and tron.h are changed to newton.cpp and newton.h, respectively.
In newton.cpp, the subroutine trpcg is changed to pcg.
Some functions (in the class newton) used for trust region are removed.
- classes of functions in linear.cpp:
A new class of function l2r_erm_fun is added to cover lr and svm.
It assumes the following function form
min_w w^Tw/2 + \sum C_i \xi(w^Tx_i), where \xi() is the loss
Some common utilities in particular the line-search subroutine (see below) are
implemented here.
- line search subroutines:
A special line-search subroutine for l2r_erm_fun is implemented in linear.cpp
so for each step size the function value can be cheaply calculated.
A base implementation of line search is provided in newton.cpp, where it
calculates every function value from scratch.
We require that the line-search subroutine to update w and also maintain
the function value.
- CG stopping criterion
It's changed to check a quadratic approximation instead of the
residual. See the release notes of version 2.40.
- CG stopping tolerance
LIBLINEAR enlarged eps_cg if the initial primal solution is not
null. This was from Chu et al. (2015) to avoid too many CG steps
in warm start for parameter selection. We found that this setting
is no longer needed; see details in version 2.40 release notes.
Chou Hung-Yi [Sat, 23 May 2020 15:25:17 +0000 (23:25 +0800)]
solver for one-class SVM supported
-add new solver ONECLASS_SVM (-s 21)
-add function solve_oneclass_svm
-add new attribute rho to model
-add new attribute nu to parameter
-modify function check_parameter, get_decfun_bias
to reject one-class SVM from accessing bias
-modify/add function get_decfun_coef, get_decfun_rho, get_w_value
for one-class SVM to get its decision function
-add function check_oneclass_model
-modify python/MATLAB interface and train.c update
-REDME update
Chih-Jen Lin [Fri, 21 Feb 2020 22:37:36 +0000 (06:37 +0800)]
change SHVER from 3 to 4 due to the function name change or new functions
- TRON::trcg -> changed to TRON::trcpg (version 2.20)
- find_parameters_C -> changed to find_parameters (version 2.30)
- possibly a new solver for one-class SVM
fix a bug in README building windows binaries
update the directory in README to fit visual studio latest version
modify the explanation in matlab/README installation
johncreed [Mon, 18 Mar 2019 09:12:47 +0000 (17:12 +0800)]
L2R_L2LOSS_SVR warm start parameter search supported
-add function find_parameters for parameter search
-modify function find_parameter_C as subroutine of find_parameters
-add function calc_max_p for maximal p parameter for L2R_L2LOSS_SVR
-modify function calc_start_C for L2R_L2LOSS_SVR
-modify function train to support initial solution for L2R_L2LOSS_SVR
-change L2R_L2LOSS_SVR default -e to (0.0001)
-change parameter stopping condition from num_unchanged_w == 3 to 5
-modify python/MATLAB interface and train.c update
-REDME update
Chih-Jen Lin [Tue, 18 Dec 2018 12:41:46 +0000 (20:41 +0800)]
in solve_l1r_l2_svc, loss_old is initialized in a for loop over num_linesearch
by
if(num_linesearch == 0)
Some compiler think it's not initialized.. Hence this change add loss_old = 0 when it's declared.
Chih-Jen Lin [Tue, 18 Dec 2018 02:59:12 +0000 (10:59 +0800)]
a _cstr function to encode string to utf-8. Use it for file names in
loading and saving model. The _cstr implementations are different for
python 2.x and 3.x
This changes follows from the modification in libsvm
Chih-Jen Lin [Wed, 24 Oct 2018 10:52:49 +0000 (18:52 +0800)]
in README use an example to explain that -C returns only the best
parameter rather than a model. Users must use the selected parameter
to train a model.
projects / liblinear / log