详细描述
Multiple Kernel Learning.
A support vector machine based method for use with multiple kernels. In Multiple Kernel Learning (MKL) in addition to the SVM
and bias term
the kernel weights
are estimated in training. The resulting kernel method can be stated as
where
is the number of training examples
are the weights assigned to each training example
are the weights assigned to each sub-kernel
are sub-kernels and
the bias.
Kernels have to be chosen a-priori. In MKL
and bias are determined by solving the following optimization program
here C is a pre-specified regularization parameter.
Within shogun this optimization problem is solved using semi-infinite programming. For 1-norm MKL using one of the two approaches described in
Soeren Sonnenburg, Gunnar Raetsch, Christin Schaefer, and Bernhard Schoelkopf. Large Scale Multiple Kernel Learning. Journal of Machine Learning Research, 7:1531-1565, July 2006.
The first approach (also called the wrapper algorithm) wraps around a single kernel SVMs, alternatingly solving for
and
. It is using a traditional SVM to generate new violated constraints and thus requires a single kernel SVM and any of the SVMs contained in shogun can be used. In the MKL step either a linear program is solved via glpk or cplex or analytically or a newton (for norms>1) step is performed.
The second much faster but also more memory demanding approach performing interleaved optimization, is integrated into the chunking-based SVMlight.
In addition sparsity of MKL can be controlled by the choice of the
-norm regularizing
as described in
Marius Kloft, Ulf Brefeld, Soeren Sonnenburg, and Alexander Zien. Efficient and accurate lp-norm multiple kernel learning. In Advances in Neural Information Processing Systems 21. MIT Press, Cambridge, MA, 2009.
An alternative way to control the sparsity is the elastic-net regularization, which can be formulated into the following optimization problem:
where
is a loss function. Here
controls the trade-off between the two regularization terms.
corresponds to
-MKL, whereas
corresponds to the uniform-weighted combination of kernels (
-MKL). This approach was studied by Shawe-Taylor (2008) "Kernel Learning for Novelty Detection" (NIPS MKL Workshop 2008) and Tomioka & Suzuki (2009) "Sparsity-accuracy trade-off in MKL" (NIPS MKL Workshop 2009).
在文件MKL.h第92行定义。
所有成员的列表。
公有成员 |
| CMKL (CSVM *s=NULL) |
virtual | ~CMKL () |
void | set_constraint_generator (CSVM *s) |
void | set_svm (CSVM *s) |
CSVM * | get_svm () |
virtual bool | train (CFeatures *data=NULL) |
void | set_C_mkl (float64_t C) |
void | set_mkl_norm (float64_t norm) |
void | set_elasticnet_lambda (float64_t lambda) |
void | set_interleaved_optimization_enabled (bool enable) |
bool | get_interleaved_optimization_enabled () |
float64_t | compute_mkl_primal_objective () |
virtual float64_t | compute_mkl_dual_objective () |
float64_t | compute_elasticnet_dual_objective () |
void | set_mkl_epsilon (float64_t eps) |
float64_t | get_mkl_epsilon () |
int32_t | get_mkl_iterations () |
virtual bool | perform_mkl_step (const float64_t *sumw, float64_t suma) |
virtual float64_t | compute_sum_alpha ()=0 |
virtual void | compute_sum_beta (float64_t *sumw) |
静态公有成员 |
static bool | perform_mkl_step_helper (CMKL *mkl, const float64_t *sumw, const float64_t suma) |
保护成员 |
virtual void | init_training ()=0 |
void | perform_mkl_step (float64_t *beta, float64_t *old_beta, int num_kernels, int32_t *label, int32_t *active2dnum, float64_t *a, float64_t *lin, float64_t *sumw, int32_t &inner_iters) |
float64_t | compute_optimal_betas_via_cplex (float64_t *beta, const float64_t *old_beta, int32_t num_kernels, const float64_t *sumw, float64_t suma, int32_t &inner_iters) |
float64_t | compute_optimal_betas_via_glpk (float64_t *beta, const float64_t *old_beta, int num_kernels, const float64_t *sumw, float64_t suma, int32_t &inner_iters) |
float64_t | compute_optimal_betas_elasticnet (float64_t *beta, const float64_t *old_beta, const int32_t num_kernels, const float64_t *sumw, const float64_t suma, const float64_t mkl_objective) |
void | elasticnet_transform (float64_t *beta, float64_t lmd, int32_t len) |
void | elasticnet_dual (float64_t *ff, float64_t *gg, float64_t *hh, const float64_t &del, const float64_t *nm, int32_t len, const float64_t &lambda) |
float64_t | compute_optimal_betas_directly (float64_t *beta, const float64_t *old_beta, const int32_t num_kernels, const float64_t *sumw, const float64_t suma, const float64_t mkl_objective) |
float64_t | compute_optimal_betas_newton (float64_t *beta, const float64_t *old_beta, int32_t num_kernels, const float64_t *sumw, float64_t suma, float64_t mkl_objective) |
virtual bool | converged () |
void | init_solver () |
bool | init_cplex () |
void | set_qnorm_constraints (float64_t *beta, int32_t num_kernels) |
bool | cleanup_cplex () |
bool | init_glpk () |
bool | cleanup_glpk () |
bool | check_lpx_status (LPX *lp) |
virtual const char * | get_name () const |
保护属性 |
CSVM * | svm |
float64_t | C_mkl |
float64_t | mkl_norm |
float64_t | ent_lambda |
float64_t * | beta_local |
int32_t | mkl_iterations |
float64_t | mkl_epsilon |
bool | interleaved_optimization |
float64_t * | W |
float64_t | w_gap |
float64_t | rho |
CPXENVptr | env |
CPXLPptr | lp_cplex |
LPX * | lp_glpk |
bool | lp_initialized |
构造及析构函数文档
Constructor
- 参数:
-
s | SVM to use as constraint generator in MKL SIP |
在文件MKL.cpp第21行定义。
成员函数文档
bool check_lpx_status |
( |
LPX * |
lp ) |
[protected] |
check glpk error status
- 返回:
- if in good status
在文件MKL.cpp第175行定义。
bool cleanup_cplex |
( |
) |
[protected] |
cleanup cplex
- 返回:
- if cleanup was successful
在文件MKL.cpp第119行定义。
bool cleanup_glpk |
( |
) |
[protected] |
cleanup glpk
- 返回:
- if cleanup was successful
在文件MKL.cpp第166行定义。
float64_t compute_elasticnet_dual_objective |
( |
) |
|
compute ElasticnetMKL dual objective
- 返回:
- computed dual objective
在文件MKL.cpp第536行定义。
float64_t compute_mkl_dual_objective |
( |
) |
[virtual] |
compute mkl primal objective
- 返回:
- computed mkl primal objective
在文件MKL.h第189行定义。
given the alphas, compute the corresponding optimal betas
- 参数:
-
beta | new betas (kernel weights) |
old_beta | old betas (previous kernel weights) |
num_kernels | number of kernels |
sumw | 1/2*alpha'*K_j*alpha for each kernel j |
suma | (sum over alphas) |
mkl_objective | the current mkl objective |
- 返回:
- new objective value
在文件MKL.cpp第612行定义。
given the alphas, compute the corresponding optimal betas
- 参数:
-
beta | new betas (kernel weights) |
old_beta | old betas (previous kernel weights) |
num_kernels | number of kernels |
sumw | 1/2*alpha'*K_j*alpha for each kernel j |
suma | (sum over alphas) |
mkl_objective | the current mkl objective |
- 返回:
- new objective value
在文件MKL.cpp第417行定义。
given the alphas, compute the corresponding optimal betas
- 参数:
-
beta | new betas (kernel weights) |
old_beta | old betas (previous kernel weights) |
num_kernels | number of kernels |
sumw | 1/2*alpha'*K_j*alpha for each kernel j |
suma | (sum over alphas) |
mkl_objective | the current mkl objective |
- 返回:
- new objective value
在文件MKL.cpp第701行定义。
given the alphas, compute the corresponding optimal betas using a lp for 1-norm mkl, a qcqp for 2-norm mkl and an iterated qcqp for general q-norm mkl.
- 参数:
-
beta | new betas (kernel weights) |
old_beta | old betas (previous kernel weights) |
num_kernels | number of kernels |
sumw | 1/2*alpha'*K_j*alpha for each kernel j |
suma | (sum over alphas) |
inner_iters | number of internal iterations (for statistics) |
- 返回:
- new objective value
在文件MKL.cpp第893行定义。
given the alphas, compute the corresponding optimal betas using a lp for 1-norm mkl
- 参数:
-
beta | new betas (kernel weights) |
old_beta | old betas (previous kernel weights) |
num_kernels | number of kernels |
sumw | 1/2*alpha'*K_j*alpha for each kernel j |
suma | (sum over alphas) |
inner_iters | number of internal iterations (for statistics) |
- 返回:
- new objective value
在文件MKL.cpp第1236行定义。
virtual float64_t compute_sum_alpha |
( |
) |
[pure virtual] |
void compute_sum_beta |
( |
float64_t * |
sumw ) |
[virtual] |
compute 1/2*alpha'*K_j*alpha for each kernel j (beta dependent term from objective)
- 参数:
-
sumw | vector of size num_kernels to hold the result |
在文件MKL.cpp第1386行定义。
virtual bool converged |
( |
) |
[protected, virtual] |
check if mkl converged, i.e. 'gap' is below epsilon
- 返回:
- whether mkl converged
在文件MKL.h第378行定义。
helper function to compute the elastic-net objective
在文件MKL.cpp第509行定义。
helper function to compute the elastic-net sub-kernel weights
在文件MKL.h第334行定义。
bool get_interleaved_optimization_enabled |
( |
) |
|
get state of optimization (interleaved or wrapper)
- 返回:
- true if interleaved optimization is used; wrapper otherwise
在文件MKL.h第180行定义。
get mkl epsilon for weights (optimization accuracy for kernel weights)
- 返回:
- epsilon for weights
在文件MKL.h第217行定义。
int32_t get_mkl_iterations |
( |
) |
|
get number of MKL iterations
- 返回:
- mkl_iterations
在文件MKL.h第223行定义。
virtual const char* get_name |
( |
) |
const [protected, virtual] |
get SVM that is used as constraint generator in MKL SIP
- 返回:
- svm
在文件MKL.h第129行定义。
bool init_cplex |
( |
) |
[protected] |
init cplex
- 返回:
- if init was successful
在文件MKL.cpp第70行定义。
bool init_glpk |
( |
) |
[protected] |
init glpk
- 返回:
- if init was successful
在文件MKL.cpp第155行定义。
void init_solver |
( |
) |
[protected] |
initialize solver such as glpk or cplex
在文件MKL.cpp第52行定义。
virtual void init_training |
( |
) |
[protected, pure virtual] |
perform single mkl iteration
given sum of alphas, objectives for current alphas for each kernel and current kernel weighting compute the corresponding optimal kernel weighting (all via get/set_subkernel_weights in CCombinedKernel)
- 参数:
-
sumw | vector of 1/2*alpha'*K_j*alpha for each kernel j |
suma | scalar sum_i alpha_i etc. |
在文件MKL.cpp第362行定义。
perform single mkl iteration
given the alphas, compute the corresponding optimal betas
- 参数:
-
beta | new betas (kernel weights) |
old_beta | old betas (previous kernel weights) |
num_kernels | number of kernels |
label | (from svmlight label) |
active2dnum | (from svmlight active2dnum) |
a | (from svmlight alphas) |
lin | (from svmlight linear components) |
sumw | 1/2*alpha'*K_j*alpha for each kernel j |
inner_iters | number of required internal iterations |
callback helper function calling perform_mkl_step
- 参数:
-
mkl | MKL object |
sumw | vector of 1/2*alpha'*K_j*alpha for each kernel j |
suma | scalar sum_i alpha_i etc. |
在文件MKL.h第243行定义。
void set_constraint_generator |
( |
CSVM * |
s ) |
|
SVM to use as constraint generator in MKL SIP
- 参数:
-
在文件MKL.h第109行定义。
void set_elasticnet_lambda |
( |
float64_t |
lambda ) |
|
set elasticnet lambda
- 参数:
-
lambda | new elastic net lambda (must be 0<=lambda<=1) lambda=0: L1-MKL lambda=1: Linfinity-MKL |
在文件MKL.cpp第349行定义。
void set_interleaved_optimization_enabled |
( |
bool |
enable ) |
|
set state of optimization (interleaved or wrapper)
- 参数:
-
enable | if true interleaved optimization is used; wrapper otherwise |
在文件MKL.h第171行定义。
set mkl epsilon (optimization accuracy for kernel weights)
- 参数:
-
在文件MKL.h第211行定义。
set mkl norm
- 参数:
-
norm | new mkl norm (must be greater equal 1) |
在文件MKL.cpp第340行定义。
void set_qnorm_constraints |
( |
float64_t * |
beta, |
|
|
int32_t |
num_kernels |
|
) |
| [protected] |
void set_svm |
( |
CSVM * |
s ) |
|
SVM to use as constraint generator in MKL SIP
- 参数:
-
在文件MKL.h第118行定义。
bool train |
( |
CFeatures * |
data = NULL ) |
[virtual] |
train MKL classifier
- 参数:
-
data | training data (parameter can be avoided if distance or kernel-based classifiers are used and distance/kernels are initialized with train data) |
- 返回:
- whether training was successful
重载CClassifier。
在文件MKL.cpp第193行定义。
成员数据文档
sub-kernel weights on the L1-term of ElasticnetMKL
在文件MKL.h第441行定义。
Sparsity trade-off parameter used in ElasticnetMKL must be 0<=lambda<=1 lambda=0: L1-MKL lambda=1: Linfinity-MKL
在文件MKL.h第438行定义。
CPXENVptr env [protected] |
whether to use mkl wrapper or interleaved opt.
在文件MKL.h第447行定义。
mkl_epsilon for multiple kernel learning
在文件MKL.h第445行定义。
norm used in mkl must be > 0
在文件MKL.h第432行定义。
objective after mkl iterations
在文件MKL.h第455行定义。
partial objectives (one per kernel)
在文件MKL.h第450行定义。
该类的文档由以下文件生成: