公有成员 | 静态公有成员 | 保护成员 | 保护属性

CMKL类参考


详细描述

Multiple Kernel Learning.

A support vector machine based method for use with multiple kernels. In Multiple Kernel Learning (MKL) in addition to the SVM $\bf\alpha$ and bias term $b$ the kernel weights $\bf\beta$ are estimated in training. The resulting kernel method can be stated as

\[ f({\bf x})=\sum_{i=0}^{N-1} \alpha_i \sum_{j=0}^M \beta_j k_j({\bf x}, {\bf x_i})+b . \]

where $N$ is the number of training examples $\alpha_i$ are the weights assigned to each training example $\beta_j$ are the weights assigned to each sub-kernel $k_j(x,x')$ are sub-kernels and $b$ the bias.

Kernels have to be chosen a-priori. In MKL $\alpha_i,\;\beta$ and bias are determined by solving the following optimization program

\begin{eqnarray*} \mbox{min} && \gamma-\sum_{i=1}^N\alpha_i\\ \mbox{w.r.t.} && \gamma\in R, \alpha\in R^N \nonumber\\ \mbox{s.t.} && {\bf 0}\leq\alpha\leq{\bf 1}C,\;\;\sum_{i=1}^N \alpha_i y_i=0 \nonumber\\ && \frac{1}{2}\sum_{i,j=1}^N \alpha_i \alpha_j y_i y_j k_k({\bf x}_i,{\bf x}_j)\leq \gamma,\;\; \forall k=1,\ldots,K\nonumber\\ \end{eqnarray*}

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 $\alpha$ and $\beta$. 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 $L_p$-norm regularizing $\beta$ 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:

\begin{eqnarray*} \mbox{min} && C\sum_{i=1}^N\ell\left(\sum_{k=1}^Kf_k(x_i)+b,y_i\right)+(1-\lambda)\left(\sum_{k=1}^K\|f_k\|_{\mathcal{H}_k}\right)^2+\lambda\sum_{k=1}^K\|f_k\|_{\mathcal{H}_k}^2\\ \mbox{w.r.t.} && f_1\in\mathcal{H}_1,f_2\in\mathcal{H}_2,\ldots,f_K\in\mathcal{H}_K,\,b\in R \nonumber\\ \end{eqnarray*}

where $\ell$ is a loss function. Here $\lambda$ controls the trade-off between the two regularization terms. $\lambda=0$ corresponds to $L_1$-MKL, whereas $\lambda=1$ corresponds to the uniform-weighted combination of kernels ( $L_\infty$-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.h92行定义。

继承图,类CMKL
Inheritance graph
[图例]

所有成员的列表。

公有成员

 CMKL (CSVM *s=NULL)
virtual ~CMKL ()
void set_constraint_generator (CSVM *s)
void set_svm (CSVM *s)
CSVMget_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

保护属性

CSVMsvm
float64_t C_mkl
float64_t mkl_norm
float64_t ent_lambda
float64_tbeta_local
int32_t mkl_iterations
float64_t mkl_epsilon
bool interleaved_optimization
float64_tW
float64_t w_gap
float64_t rho
CPXENVptr env
CPXLPptr lp_cplex
LPX * lp_glpk
bool lp_initialized

构造及析构函数文档

CMKL ( CSVM s = NULL  ) 

Constructor

参数:
s SVM to use as constraint generator in MKL SIP

在文件MKL.cpp21行定义。

~CMKL (  )  [virtual]

Destructor

在文件MKL.cpp40行定义。


成员函数文档

bool check_lpx_status ( LPX *  lp  )  [protected]

check glpk error status

返回:
if in good status

在文件MKL.cpp175行定义。

bool cleanup_cplex (  )  [protected]

cleanup cplex

返回:
if cleanup was successful

在文件MKL.cpp119行定义。

bool cleanup_glpk (  )  [protected]

cleanup glpk

返回:
if cleanup was successful

在文件MKL.cpp166行定义。

float64_t compute_elasticnet_dual_objective (  ) 

compute ElasticnetMKL dual objective

返回:
computed dual objective

在文件MKL.cpp536行定义。

float64_t compute_mkl_dual_objective (  )  [virtual]

compute mkl dual objective

返回:
computed dual objective

CMKLRegression重载。

在文件MKL.cpp1429行定义。

float64_t compute_mkl_primal_objective (  ) 

compute mkl primal objective

返回:
computed mkl primal objective

在文件MKL.h189行定义。

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 
) [protected]

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.cpp612行定义。

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 
) [protected]

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.cpp417行定义。

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 
) [protected]

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.cpp701行定义。

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 
) [protected]

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.cpp893行定义。

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 
) [protected]

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.cpp1236行定义。

virtual float64_t compute_sum_alpha (  )  [pure virtual]

compute beta independent term from objective, e.g., in 2-class MKL sum_i alpha_i etc

CMKLClassificationCMKLOneClassCMKLRegression内被实现。

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.cpp1386行定义。

virtual bool converged (  )  [protected, virtual]

check if mkl converged, i.e. 'gap' is below epsilon

返回:
whether mkl converged

在文件MKL.h378行定义。

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 
) [protected]

helper function to compute the elastic-net objective

在文件MKL.cpp509行定义。

void elasticnet_transform ( float64_t beta,
float64_t  lmd,
int32_t  len 
) [protected]

helper function to compute the elastic-net sub-kernel weights

在文件MKL.h334行定义。

bool get_interleaved_optimization_enabled (  ) 

get state of optimization (interleaved or wrapper)

返回:
true if interleaved optimization is used; wrapper otherwise

在文件MKL.h180行定义。

float64_t get_mkl_epsilon (  ) 

get mkl epsilon for weights (optimization accuracy for kernel weights)

返回:
epsilon for weights

在文件MKL.h217行定义。

int32_t get_mkl_iterations (  ) 

get number of MKL iterations

返回:
mkl_iterations

在文件MKL.h223行定义。

virtual const char* get_name (  )  const [protected, virtual]
返回:
object name

重载CSVM

在文件MKL.h424行定义。

CSVM* get_svm (  ) 

get SVM that is used as constraint generator in MKL SIP

返回:
svm

在文件MKL.h129行定义。

bool init_cplex (  )  [protected]

init cplex

返回:
if init was successful

在文件MKL.cpp70行定义。

bool init_glpk (  )  [protected]

init glpk

返回:
if init was successful

在文件MKL.cpp155行定义。

void init_solver (  )  [protected]

initialize solver such as glpk or cplex

在文件MKL.cpp52行定义。

virtual void init_training (  )  [protected, pure virtual]

check run before starting training (to e.g. check if labeling is two-class labeling in classification case

CMKLClassificationCMKLOneClassCMKLRegression内被实现。

bool perform_mkl_step ( const float64_t sumw,
float64_t  suma 
) [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.cpp362行定义。

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 
) [protected]

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
static bool perform_mkl_step_helper ( CMKL mkl,
const float64_t sumw,
const float64_t  suma 
) [static]

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.h243行定义。

void set_C_mkl ( float64_t  C  ) 

set C mkl

参数:
C new C_mkl

在文件MKL.h150行定义。

void set_constraint_generator ( CSVM s  ) 

SVM to use as constraint generator in MKL SIP

参数:
s svm

在文件MKL.h109行定义。

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.cpp349行定义。

void set_interleaved_optimization_enabled ( bool  enable  ) 

set state of optimization (interleaved or wrapper)

参数:
enable if true interleaved optimization is used; wrapper otherwise

在文件MKL.h171行定义。

void set_mkl_epsilon ( float64_t  eps  ) 

set mkl epsilon (optimization accuracy for kernel weights)

参数:
eps new weight_epsilon

在文件MKL.h211行定义。

void set_mkl_norm ( float64_t  norm  ) 

set mkl norm

参数:
norm new mkl norm (must be greater equal 1)

在文件MKL.cpp340行定义。

void set_qnorm_constraints ( float64_t beta,
int32_t  num_kernels 
) [protected]

set qnorm mkl constraints

在文件MKL.cpp1480行定义。

void set_svm ( CSVM s  ) 

SVM to use as constraint generator in MKL SIP

参数:
s svm

在文件MKL.h118行定义。

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.cpp193行定义。


成员数据文档

float64_t* beta_local [protected]

sub-kernel weights on the L1-term of ElasticnetMKL

在文件MKL.h441行定义。

float64_t C_mkl [protected]

C_mkl

在文件MKL.h430行定义。

float64_t ent_lambda [protected]

Sparsity trade-off parameter used in ElasticnetMKL must be 0<=lambda<=1 lambda=0: L1-MKL lambda=1: Linfinity-MKL

在文件MKL.h438行定义。

CPXENVptr env [protected]

env

在文件MKL.h459行定义。

bool interleaved_optimization [protected]

whether to use mkl wrapper or interleaved opt.

在文件MKL.h447行定义。

CPXLPptr lp_cplex [protected]

lp

在文件MKL.h461行定义。

LPX* lp_glpk [protected]

lp

在文件MKL.h466行定义。

bool lp_initialized [protected]

if lp is initialized

在文件MKL.h469行定义。

float64_t mkl_epsilon [protected]

mkl_epsilon for multiple kernel learning

在文件MKL.h445行定义。

int32_t mkl_iterations [protected]

number of mkl steps

在文件MKL.h443行定义。

float64_t mkl_norm [protected]

norm used in mkl must be > 0

在文件MKL.h432行定义。

float64_t rho [protected]

objective after mkl iterations

在文件MKL.h455行定义。

CSVM* svm [protected]

wrapper SVM

在文件MKL.h428行定义。

float64_t* W [protected]

partial objectives (one per kernel)

在文件MKL.h450行定义。

float64_t w_gap [protected]

gap between iterations

在文件MKL.h453行定义。


该类的文档由以下文件生成:

SHOGUN Machine Learning Toolbox - Documentation