SpicyMKL
Efficient multiple kernel learning
method using
dual augmented Lagrangian
Taiji Suzuki
Ryota Tomioka
The University of Tokyo
Graduate School of Information Science and Technology
Department of Mathematical Informatics

23rd Oct., 2009@ISM

1

Multiple Kernel Learning

Fast Algorithm

2Kernel Learning
Regression, Classification

Kernel Function3• Gaussian, polynomial, chi-square, $.
– Parameters：Gaussian width, polynomial degree

Thousands of kernels• Features– Computer Vision：color, gradient, sift (sift,hsvsift, huesift, scaling of sift), Geometric Blur,
image regions, ．．．

Multiple Kernel Learning(Lanckriet et al. 2004)
Select important kernels and combine them
4

Multiple Kernel Learning (MKL)
Single Kernel

Multiple Kernel

dm:convex combination,sparse (many 0 components)
5

Sparse learninggrouping

Lasso
Group Lassokernelize

Multiple Kernel Learning (MKL)：N samples：M kernels

L1-regularization→sparse：RKHS associated with km：Convex loss（hinge, square, logistic）

6

Representer theorem

Finite dimensional problem：Gram matrix of mth kernel

7SpicyMKL

Proposed:

SpicyMKL• Scales well against # of kernels.
• Formulated in a general framework.

8

Outline• Introduction• Details of Multiple Kernel Learning• Our method– Proximal minimization– Skipping inactive kernels• Numerical Experiments– Bench-mark datasets– Sparse or dense9Details ofMultiple Kernel Learning(MKL)

10

Generalized Formulation
MKL: sparse regularization
11

hinge loss

elastic net

logistic loss
L1regularization

hinge:

elastic net:logistic:

L1regularization:
12

Rank 1 decomposition
If g is monotonically increasing and fℓ is diff’ble at the optimum,
the solution of MKL is rank 1:
such thatconvex combination of kernels
Proof

Derivative w.r.t.

13

Existing approach 1
Constraints based formulation:[Lanckriet et al. 2004, JMLR] [Bach, Lanckriet & Jordan 2004, ICML]
primalDual• Lanckriet et al. 2004: SDP• Bach, Lanckriet & Jordan 2004: SOCP
14

Existing approach 2
Upper bound based formulation:[Sonnenburg et al. 2006, JMLR] [Rakotomamonjy et al. 2008, JMLR][Chapelle & Rakotomamonjy 2008, NIPS workshop]
primal(Jensen’s inequality)• Sonnenburg et al. 2006: Cutting plane (SILP)• Rakotomamonjy et al. 2008: Gradient descent (SimpleMKL)• Chapelle & Rakotomamonjy 2008: Newton method (HessianMKL)
15

Problem of existing methods• Do not make use of sparsity
during the optimization.
→ Do not perform efficiently when
# of kernels is large.

16

Outline• Introduction• Details of Multiple Kernel Learning• Our method– Proximal minimization– Skipping inactive kernels• Numerical Experiments– Bench-mark datasets– Sparse or dense17Our method
SpicyMKL

18

• DAL (Tomioka & Sugiyama 09)– Dual Augmented Lagrangian– Lasso, group Lasso, trace norm regularization• SpicyMKL = DAL + MKL– Kernelization of DAL

19

Difficulty of MKL（Lasso）

is non-diff’ble at 0.
0Relax by
Proximal Minimization(Rockafellar, 1976)20

Our algorithm
SpicyMKL: Proximal Minimization (Rockafellar, 1976)
1 Set some initial solution. Choose increasing sequence.

2 Iterate the following update rule until convergence:

Regularization toward the last update.
It can be shown that••super linearly !

Taking its dual, the update step can be solved efficiently

21Fenchel’s duality theorem

Split into two parts

22

Non-diff’ble

dual

dual

Non-diff’ble

Smooth !
Moreau envelope
23Inner optimization• Newton method is applicable.

Twice Differentiable Twice Differentiable (a.e.)

Even if
is not differentiable,
we can apply almost the same algorithm.

24

Rigorous Derivation ofConvolution and duality

25Moreau envelope

Moreau envelope (Moreau 65)
For a convex function, we define its Moreau envelope as26

Moreau envelope

L1-penalty

dual

Smooth !

27

What we have observed
We arrived at $Dual of update rule in proximal minimization• Differentiable• Only active kernels need to be calculated.
(next slide)28

Skipping inactive kernels
Soft threshold

Hard threshold

If(inactive),and its gradient also vanishes.

,29

Derivatives• We can apply Newton method for the dual optimization.
The objective function:

Its derivatives:

where• Only active kernels contributes their computations.
→ Efficient for large number of kernels.
30

Convergence result
Thm.

Thm.

For any proper convex functions andand any non-decreasing sequence ,,Ifis strongly convex and is sparse reg.,
for any increasing sequence ,the convergence rate is super linear.
linear31

Non-differentiable loss
• If loss is non-differentiable, almost the samealgorithm is available by utilizing Moreau
envelope of .
primaldual

Moreau envelope of dual

32

Dual of elastic net
primaldual

Smooth !

Naïve optimization in the dual is applicable.
But we applied prox. minimization method
for small to avoid numerical instability.

33

Why ‘Spicy’ ?
• SpicyMKL = DAL + MKL.
• DAL also means a major Indian cuisine.
→ hot, spicy“Dal”→ SpicyMKL

from Wikipedia

34

Outline• Introduction• Details of Multiple Kernel Learning• Our method– Proximal minimization– Skipping inactive kernels• Numerical Experiments– Bench-mark datasets– Sparse or dense35Numerical Experiments

36

IDA data set, L1 regularization.

CPU time against # of kernels

SpliceSpicyMKL

Ringnorm• Scales well against # of kernels.
37

IDA data set, L1 regularization.

CPU time against # of samples

SpliceSpicyMKL

Ringnorm• Scaling against # of samples isalmost the same as the existing methods. 38

UCI dataset# of kernels 189

243

918

891

1647

39Comparison in elastic net(Sparse v.s. Dense)40

Sparse or Dense ?
Elastic Net

where.

0Sparse1DenseCompare performances of sparse and dense solutions
in a computer vision task.
41

caltech101 dataset (Fei-Fei et al., 2004)• object recognition task
• anchor, ant, cannon, chair, cup• 10 classification problems (10=5×(5-1)/2)• # of kernels: 1760 = 4 (features)×22 (regions) ×
あああああ2 (kernel functions) × 10 (kernel parameters)– sift features [Lowe99]: colorDescriptor [van de Sande et al.10]
hsvsift, sift (scale = 4px, 8px, automatic scale)– regions: whole region, 4 division, 16 division, spatial
pyramid. (computed histogram of features on each region.)– kernel functions: Gaussian kernels, kernels with10 parameters.
42Performances are averaged over all classification problems.

Best

Performance of sparse solution iscomparable with dense solution.

dense
Medium density

43

Conclusion
and Future works
まとめと今後の課題
Conclusion• We proposed a new MKL algorithm that isefficient when # of kernels is large.
– proximal minimization– neglect ‘in-active’ kernels• Medium density showed the best
performance, but sparse solution also works
well.
Future work
• Second order update44• Technical report
T. Suzuki & R. Tomioka: SpicyMKL.
arXiv: http://arxiv.org/abs/0909.5026• DAL
R. Tomioka & M. Sugiyama: Dual Augmented Lagrangian
Method for Efficient Sparse Reconstruction. IEEE Signal
Proccesing Letters, 16 (12) pp. 1067--1070, 2009.

45

Thank you for your attention!

46

Some properties
Moreau envelope

proximal operator(Fenchel duality th.)(Fenchel duality th.)Differentiable !

047