情報論的学習理論テクニカルレポート 2009
Technical Report on Information-Based Induction Sciences
2009 (IBIS2009)

Multiple Kernel Learning for Object Classification
Shinichi Nakajima ∗Marius Kloft ¶Alexander Binder †Christina Müller ‡Ulf Brefeld kKlaus-Robert Müller ∗∗Wojciech Wojcikiewicz §Motoaki Kawanabe ††Abstract: Combining information from various image descriptors has become a standard techniquefor image classification tasks. Multiple kernel learning (MKL) approaches allow to determine theoptimal combination of such similarity matrices and the optimal classifier simultaneously. Most
MKL approaches employ an `1 -regularization on the mixing coefficients to promote sparse solutions; an assumption that is often violated in image applications where descriptors hardly encode
orthogonal pieces of information. In this paper, we compare `1 -MKL with a recently developed
non-sparse MKL in object classification tasks. We show that the non-sparse MKL outperforms
both the standard MKL and SVMs with average kernel mixtures on the PASCAL VOC data sets.
Keywords: multiple kernel learning, support vector machine, image classification, sparsity.

1

Introduction

Data fusion is an important topic in computer vision. Images can be represented by a multiplicity of features capturing certain aspects, including color, textures, and shapes.
Unfortunately, the importance of different types of featuresvaries with the tasks; color information, for instance, substantially increases the detection of stop signs while coloring is almost irrelevant for finding cars in images. Techniques for appropriately combining relevant features for atask at hand are therefore crucial for state-of-the-art object
recognition systems.
From a machine learning view, different representations
give rise to different kernel functions. Kernels define (possibly nonlinear) similarities between data points and allow
to abstract learning algorithms from data. Thus, kernel machines have been successfully applied to many practicalproblems in various fields [19]. Given a task at hand, designing an appropriate kernel is essential for achieving good
generalizations, for instance by incorporating prior assumptions and domain knowledge [9, 28]. However, in the absence of prior knowledge one has to resort to alternatives.
For object recognition tasks, combining information from
∗ Nikon Corporation, nakajima.s@nikon.co.jp,† Fraunhofer Institute FIRST, binder@first.fhg.de,‡ Technische Universität Berlin, muechr@first.fraunhofer.de,§ Technische Universität Berlin, wojcikie@informatik.hu-berlin.de,¶ Technische Universität Berlin, mkloft@cs.tu-berlin.de,k Technische Universität Berlin, brefeld@cs.tu-berlin.de,∗∗ Technische Universität Berlin, klaus-robert.mueller@tu-berlin.de,†† Fraunhofer Institute FIRST, nabe@first.fhg.de,various image descriptors into several kernels K1 , . . . , Km
has become a standard technique. Unfortunately, the choiceof the right kernel mixture is often a matter of trial and error. As a remedy, uniform mixtures of normalized kernels[14, 26] or brute-force approaches [2] are employed frequently. However, the former approach may lead to suboptimal kernels and the latter is computationally infeasible
if many kernels are to be combined.
Recently, multiple kernel learning (MKL) [13, 1, 20, 18,27] was applied to object classification tasks involving various image descriptors [24]. Compared to uniform mixturesand brute-force approaches, MKL has the appealing property of always finding the optimal kernel combination andconverges quickly as it can be wrapped around a regularsupport vector machine (SVM) [20]. MKL aims at learning
the optimal kernel mixture and the model parameters simultaneously. More specifically, MKL approaches find a linearP
mixture of the kernels, that is K = j βj Kj . To support
the interpretability of the solution, many MKL approaches
promote sparse mixtures by incorporating an `1 -norm constraint on the mixing coefficients. However, it has often
been observed that `1 -norm MKL is outperformed by thePaverage-sum kernel K = j Kj . An explanation is thatenforcing sparse mixtures may lead to degenerate models if
the optimal kernel mixture is non-sparse. A remedy might
be recently developed non-sparse variants of MKL promoting non-sparse kernel mixtures [10].
In this contribution, we empirically compare sparse andnon-sparse MKL approaches to object classification tasks.
We employ candidate kernels obtained from many different
image descriptors including the 30 color SIFT features by
the VOC2008 winner [22]. Our empirical results on image data sets from the PASCAL visual object classification(VOC) challenge 2007 and 2008 [8] show that the nonsparse MKL significantly outperforms the uniform mixtureand `1 -norm MKL.

infinite-dimensional, however, translating the above formulation into the equivalent dual optimization problem prevents from dealing with features in H explicitly.

This paper is organized as follows. In Section 2, we
briefly review the underlying techniques, including sparseand non-sparse MKL. Section 3 discusses similarities between the prepared kernels. Based on this analysis, we precompute averages of similar kernels and apply MKL witha substantially reduced sets of kernels. We discuss our empirical results in Section 4 and Section 5 concludes.

The above dual depends only on inner products (similarities) of inputs which can be alternatively computed by meansof kernel functions k, given by

2

Preliminaries

2.1

Support Vector Machines

input space X to a reproducing kernel Hilbert space (RKHS)
H, linear classifiers in H of the form

w,b,ξ

s.t.

i=1

1 X
αi αl yi yl k(xi , xl )
2

(3)

i,l=1

0 ≤ αi ≤ C, ∀i;nXyi αi = 0.

i=1k(x, x̄) = hψ(x), ψ(x̄)iH .
Once, optimal parameters are found, these are used as plugin estimates and the final decision function can be written
asnXf (x) =
αi k(xi , x) + b.
Note that only a small fraction of the α’s usually take nonzero values which are often called support vectors. The
threshold b is determined by saturated support vectors with
α = C. Finally, we remark that we need to use different
regularization constants C+ and C− for the positive andnegative examples, respectively, to compensate the unbalanced sample sizes of the two classes [3].

2.2 Multiple Kernel Learning
Let K1 , . . . , Km be m kernel matrices with Kt =[kt (xi , xj )]i,j=1,...,n , obtained from different sources or features. The multiple kernel learning (MKL) framework extends the regular SVM formulation by additionally learninga linear mixture of the kernels, i.e.
Kβ =

m
X

βj Kj .

j=1

Thus, the model in Equation (1) is extended toters (w, b) are determined by solving the optimization problemnX1
kwk22 + C
ξi ,
2
i=1
©
ª
∀i, yi w> ψ(xi ) + b ≥ 1 − ξi ;

s.t.

n

αi −

(1)

provide a rich set of flexible classifiers in X . The parame-

min

α

n
X

i=1

In the supervised learning setting, we are given n training samples {(xi , yi )}ni=1 , where xi ∈ X is the input vector
and yi ⊆ Y . For instance, in object recognition, inputs x
are frequently histograms of some image features and Y isa discrete set of objects that are to be identified in the images. Inputs are often annotated with several labels as different objects can occur in the same image. To account forthese multi-label scenarios, we take a one-vs-all approachand focus on binary classification settings. That is, we haveyi ∈ {+1, −1}, where yi = +1 denotes that at least one
object from the actual category is included in the i-th image and yi = −1 otherwise.
Support vector machines (SVMs) originate from linear
classifiers and maximize the margin between sample cloudsof both classes. Introducing a feature mapping ψ from thef (x) = w> ψ(x) + b

min

(2)
ξi ≥ 0,where k · k2 denotes the `2 norm and C > 0 is a regularization constant. Notice that the spanned RKHS can be

f (x) =mX

βj w>
j ψj (x) + b.

j=1

A common approach is to rephrase the above expression
by incorporating the mixing coefficients into the parame√√
ter vector wβ = ( β1 w1 , . . . , βm wm )> and the feature√√
mapping ψβ (xi ) = ( β1 ψ1 (xi ), . . . , βm ψm (xi ))> . The
corresponding optimization problem maximizes the generalization performance by simultaneously optimizing the parameters w, b, ξ, and β. We obtain the common `1 -norm

MKL for p = 1 [1, 20, 18, 27], and non-sparse MKL forp > 1 [10].
nX
1kwβ k22 + C
ξi
2
i=1

min

β,w,b,ξ

s.t.

∀i :

β ≥ 0;

kβkp ≤ 1

m = 1. Irrespectively of the actual value of p, the above
optimization problem can be translated into a semi-infinite
program [20, 10] which can be interpreted as a dualized
variant of the optimization problem (4). We arrive at,
min λ
λ,β

n
X

αi −

i=1

n
m
X
1 X
αi αl yi yl
βj kj (xi , xl ),
2
j=1
i,l=1

∀α ∈ Rn0 ≤ αi ≤ C, ∀i;

(5)
n
X

yi αi = 0;i=1βj ≥ 0, ∀j;

≈

1−

X
p(3 − p)− (p2 − 2p)(βjold )p−1 βj2jp(p − 1) X old p−2 2(βj ) βj .
2jUsing the above approximation, one obtain a QCQP, which
can again be optimized with standard techniques [10].

Note that we resolve the regular SVM optimization problem in Equation (2) for learning with only a single kernels.t. λ ≥kβkpp+

yi (hwβ , ψβ (xi )i + b) ≥ 1 − ξi (4)ξ ≥ 0;

bykβkp ≤ 1

Initializing β with a uniform kernel mixture, the semi-infinite
program can be optimized efficiently by interleaving thefollowing two steps:
1. For the actual mixture β, the solution of the regular
SVM generates the most strongly violated constraint(Equation (5)).

2. With respect to set of active constraints, the optimalvalues of β and λ are identified by solving the corresponding optimization problem for β.
The actual optimization problems for the mixing coefficients, however, differ with varying values of p. For instance, for p = 1, one obtains a linear program that can besolved with standard techniques. For p = 2, the `2 -norm
gives rise to a quadratically constrained quadratic program(QCQP) that can also be optimized with off-the-shelf QPsolvers. For different values of p, things get a bit tricky be-

2.3 Kernel Alignment
In the remainder, we will need to analyze the similarity ofkernel matrices. For this purpose, we now introduce kernel
target alignment [5] as an adequate measure of similarity or
hyper kernel [17].
Let K1 = [k1 (xi , xj )]i,j=1,...,n andK2 = [k2 (xi , xj )]i,j=1,...,n be the Gram matrices of kernel
functions k1 and k2 for x1 , . . . , xn . The alignment between
k1 and k2 is defined as the cosine of the angle between thetwo matrices K1 and K2 given by
A(K1 , K2 ) :=hK1 , K2 iF,
kK1 kF kK2 kF(6)

where hK1 , K2 iF denotes the standard inner productPnhK1 , K2 iF := i,j=1 k1 (xi , xj )k2 (xi , xj ) and kK1 kF is
the Frobenius norm in matrix space defined as kK1 kF :=1/2
hK1 , K1 iF .
It is important to center the kernels before computing thealignment as many classifiers, including SVMs, are invariant against mean shifts in the RKHSs. The centering in
the respective feature spaces is achieved by multiplying thematrix H, given by
H := I −1 >11nto the kernels K1 and K2 from both sides, where I is theidentity matrix of size n and 1 is a column vector with allelements 1. Thus, the resulting alignment for centered kernels can be computed by
A(HK1 H, HK2 H) =hHK1 H, HK2 HiF,
kHK1 HkF kHK2 HkF(7)

where hHK1 H, HK2 HiF = tr(HK1 HK2 ), because H
is a projection matrix.

cause there is hardly an `p -norm solver. Nevertheless, one
can approximate the `p -norm constraint by a second-order

3 Experiments

Taylor expansion around the current estimates β old given

3.1 VOC data sets
In order to show the advantage of our procedure, we compare the performance of the different MKL procedures to1
SIFT_g1

0.5

0.9
0.8

SIFT_o0.7
0.6

SIFT_no0.5
SIFT_nrg

0

0.4
0.3

SIFT_rgb

0.2
0.1

PHoG
SIFT_g1

SIFT_oSIFT_no SIFT_nrg SIFT_rgb

PHoG

0

(a)

−0.5

0.5

1

(b)

図 1: Similarity between the 35 prepared kernels: (a) hyper kernel and (b) graphical representation of the similarities within

the first two eigen directions. In the panel (a), 6 groups are ’SIFT g1’, ’SIFT o’, ’SIFT no’, ’SIFT nrg’, ’SIFT rgb’, and’PHoG’, while 6 elements within SIFT color channel consists of 3 pyramid levels (level 0, 1, y3) for dense grid and interest
points. In the panel (b), the color channels are specified as black=’g1’, red=’o’, magenda=’no’, green=’nrg’ and blue=’rgb’,
while the markers discriminates the pyramid levels and sampling scheme for SIFT plus PHoG (triangle), i.e. circle=’denselevel0’, square=’dense level1’, diamond=’dense y3’, plus=’interest level0’, X-mark=’interest points level1’, star=’interest
points y3’.
SVMs using the average-sum kernel. We experiment on the
VOC 2007 and VOC 2008 classification data sets [8].
The VOC 2007 data set consists of 9963 images (2501
training, 2510 validation and 4952 test) annotated with 20
object classes. The VOC 2008 data set contains 8780 images categorized into the same 20 object classes as in the
VOC 2007 data. The latter is split into train, validation andtest sets by the organizers (2113 for train, 2227 for validation, and 4340 for test). The ground-truth of the test set isyet disclosed by the organizers who agreed to evaluate test
performance on request.
We split the multi-label problem into 20 binary classification problems using the one-vs-all strategy. That is, foreach class, we define an auxiliary label yi = +1 if at least
one object from the actual class is included in the i-th im-

p = ∞. Furthermore, we optimized the parameter p basedon the cross-validation score either jointly with all classes(`p -joint) or individually for each category (`p -single).
The final classifiers are obtained by re-training the respective approaches on all available data (i.e., training andholdout sets) using the previously determined optimal parameters. We report on average AP scores over 10 repetitions with different training, holdout, and test sets. The
baselines SVM and `1 -norm MKL are implemented using
the Shogun library [20].

age, and yi = −1 if there is no such object in the image.1
The evaluation is based on precision-recall (PR) curves and

SIFT descriptors [15] which are almost the same as those
applied by the winner of VOC 2008 [22]. As sampling

the principal quantitative measure is the average precision(AP) over all recall values.

schemes, we use a dense grid with 6 pitches and interest
points from gray-scale images by the scale invariant de-We employ model selection for the SVM/MKL tradeoff parameter C and for the parameter p which controls

tector [25]. For both cases, we calculated the base SIFT
descriptors in 10 color channels: g1 (grey), o1 (opponent

the sparseness of the MKL. We used p = 1 + 2λ , where
λ = {−∞, −5, −4, −3, −2, −1, 0, 1, ∞}. We resolve p =color 1), o2, no1 (normalized o1), no2, nr (normalized red),ng (normalized green), r, g, b. For prototype calculation and

1 for λ = −∞ and obtain the unweighted-sum kernel for

visual word assignment, the color SIFTs are combined into
the following 5 groups: g1, o=[o1,o2,g1], no=[no1,no2],

1 Hardly detectable objects are indicated by y = 0 by the organizers.
iSince these are omitted in the final evaluation we simply excluded themfrom the training process.

3.2 Image Features and Base Kernels
In our experiments, we employed the following two setsof image features. The first category contains 30 histogramsof visual words (HoW) representations [6] based on color

nrg=[nr,ng], rgb=[r,g,b]. For each case, we created 4000

visual words for the dense grid (800 for the interest points)
by using k-means clustering. 2 Finally, we also consider
three levels of the image pyramid representation [14]: foreach image, its visual words are summarized into histogramsfor the whole image (level 0), for 4 quarter images (level 1)
and for 3 horizontal stripes (y3). In total, we prepared 5(colors) ×2 (sampling) ×3 (pyramid levels) = 30 kernels.
The second category of our image features is the pyramid
histogram of oriented gradient (PHoG) [7, 2]. For each of
the 5 color channels, which are same as in the first category,
we compute the PHoG representations of level 2 where the3 pyramid levels are merged by a default scheme without
any adaptation. In sum, we computed 5 PHoG kernels. We
used the χ2 kernel, which has proved to be a robust similarity measure for bag of words histograms [26], where theband-width is set to the mean χ2 distances between all pairsof training samples [12].
Although our MKL implementations are throughout efficient, simply storing all 35 kernels exceeds 1.2GB. We
therefore pre-combine kernels based on a similarity analysis using kernel target alignment [5] before applying MKL.
Figure 1 (a) shows the kernel alignment score (7) between
the 30 SIFT + 5 PHoG kernels. We can see: (i) the kernels within the same colors are mostly similar, (ii) g1 andrgb kernels are also similar and (iii) the PHoG and SIFT
kernels are less similar. In order to assure our findings, weplotted the kernels in a 2-dimensional space spanned by the
first and second eigenvectors of the hyper kernel obtainedby a principal component analysis (PCA) and spectral clustering [16] (Figure. 1(b)). Based on this similarity analysis,
we averaged 6 SIFT kernels with uniform weights withineach color. By doing this, we reduced the number of basekernels to 10. We obtain 5 pre-combined SIFT and 5 PHoG
kernels which are plugged into the MKL.

3.3

Result 1: Significance Test for 10 Random Splits of VOC 2008

Before we use the official VOC 2008 data split to compare our outcomes to already published results in Section
3.4, we investigate statistical properties of the performancesof the different methods. We therefore draw 2111 training,
1111 validation, and 1110 test images randomly from thelabeled pool (i.e., official training and holdout split). We
report on APs and standard deviations over 10 repetitions
2 We use only 800 visual words for the interest points as about 1/5 ofthe descriptors are extracted per image.

with distinct training, holdout, test sets. To test on the significance of the differences in performance, we conduct a
Wilcoxon signed-ranks test for each method and class andadditionally for the average AP over all classes. Table 1
shows the results.3
The methods whose performance are not significantly worse
than the best score are marked in bold face. The `p -single
MKL is always among the best performing algorithms. Its
jointly-optimized counterpart `p -joint, performs similarly
and attains the second best performance. Uniform weights
and `1 -MKL are significantly outperformed by the two nonsparse MKL variants for several object classes. The result
is however not really surprising as `p -single is optimized
class-wise.
Figure 2 shows the resulting kernel weights, averaged
over the 10 repetitions. We see that the solutions of `p joint distribute some weight on each kernel, achieving nonsparse solutions. The average p for `p -joint is 1.075. Furthermore, Figure 2 implies that PHoW features carry more
relevant information than PHoG. Since the PHoG features
do not seem to play a great role in the classification, a natural question is whether PHoG do contribute to the accuracy
at all. Table 2 shows the average gain in accuracy for using
PHoW kernels alone and PHoG & PHoW kernels together,respectively. The result shows that the PHoG kernels absolutely contribute to the final decision. We observe a significant gain in accuracy by incorporating PHoG kernels into
the learning process for all but the average-sum kernel.
表 2: Average gain in accuracy by adding PHoG features.

PHoW
PHoW&G

uniform45.4±1.045.2±1.0`145.6±0.8
46.6±0.9`p -joint
45.5±0.8
46.9±1.0`p -single
45.5±1.0
46.9±1.0

3.4 Result 2: Results for the Official Splits of
VOC 2007 and VOC 2008
In our second experimental setup, we evaluated the performance of the approaches for the official splits of theVOC 2007 and 2008 challenges. The winners of VOC2008[21] reported an average AP of 60.5 on VOC 2007 andachieved an AP of 54.9 on VOC2008. Their result is based
3 Since creating a codebook and assigning descriptors to visual words
is computationally demanding, we apply the codebook created with thetraining images of the official split. This could result in slightly better
absolute test errors, since some information of the test images might becontained in the codebook. However, our focus in this Section lies ona relative comparison between different classification methods, and thiscomputational shortcut does not favor any of these approaches.

表 1: Average precisions on the test images of our 10 splits. For each column, the best method and comparable ones basedon a Wilcoxon signed-rank test at the significance level of 5% are marked in bold faces.
average45.2±1.0
46.6±0.946.9±1.0
46.9±1.0

uniform`1p` -joint`p -single
uniform`1`p -joint`p -single
uniform`1p` -joint`p -single
uniform`1p` -joint`p -single

aeroplane
70.4±5.372.8±4.772.6±5.071.2±4.9car53.0±3.454.0±3.554.7±3.554.4±3.1
horse
48.2±8.3
47.1±7.948.0±8.049.3±8.2
train
60.4±8.6
60.8±8.961.6±8.2
61.1±8.7

bicycle42.5±3.644.5±5.845.1±5.0
44.0±4.9cat52.6±3.0
55.3±2.655.7±2.555.7±2.6
motorbike
44.5±6.5
47.5±4.848.0±5.8
47.6±4.9
tvmonitor
53.4±5.9
57.0±5.656.2±6.4
56.0±7.3

0.7

boat
61.2±4.661.3±4.3
61.9±4.461.7±4.0cow
13.8±3.813.8±4.4
13.7±4.2
13.7±3.5
pottedplant22.2±3.723.2±5.1
24.8±6.3
24.9±6.1

bottle22.5±5.7
20.5±4.0
22.1±4.722.5±5.2
diningtable
33.1±9.436.7±5.1
37.8±5.537.2±5.0
sheep
23.7±6.6
26.6±8.6
25.9±9.3
24.7±6.8bus
50.5±10.851.5±10.0
50.5±11.2
52.3±9.3
dog
36.1±3.0
38.5±4.838.3±4.538.8±3.4sofa
39.6±7.439.5±8.540.6±9.0
40.6±9.0

0.7
aeroplane
bicyclebird
boat
bottle
bus
car
cat
chair
cow
diningtable
dog
horse
motorbikepersonpottedplant
sheep
sofa
train
tvmonitor

0.6

0.5

0.4

0.3

0.2

0.1

0

bird
47.8±6.0
49.3±5.449.7±5.449.0±5.9chair
42.8±3.645.9±4.444.9±4.745.6±4.1
person85.8±1.0
86.7±1.0
86.8±1.0
86.8±1.0

aeroplane
bicyclebird
boat
bottle
bus
car
cat
chair
cow
diningtable
dog
horse
motorbikepersonpottedplant
sheep
sofa
train
tvmonitor

0.6

0.5

0.4

0.3

0.2

0.1

1

2

3

4

5

6

7

8

9

10

0

1

2

3

4

5

6

7

8

9

10

図 2: Selected weights by MKL: `1 (left) and `p -joint (right)

on color descriptors [22], kernel codebook [23], and kernel
discriminant analysis [4].
Table 3 shows the resulting average APs for our MKL approaches.4 The non-sparse MKL increases the accuracy ofthe basic color descriptors (uniform only PHoW) of about
2%. Furthermore, [21] reports a loss in accuracy of lessthan 1% if a SVM is substituted for the kernel discriminant analysis. Taking the different code books into account,we conjecture that – except for the code book – non-sparse
multiple kernel learning is on par or better as the winner oflast years VOC challenge. We will address the validity of
our assumption in future work.

表 3: Average APs for VOC 2007/2008 using official splits.

uniform (only PHoW)
uniform`1p` -joint`p -single

VOC2007
55.0
55.0
56.8
57.3
57.1

VOC2008
49.0
—
—
51.5
50.9

4 Discussion
In contrast to anecdotal reports, we observed `1 -MKL tooutperform the average-sum kernel for PHoW and PHoG
kernels (see Table 1). Nevertheless, carefully adjusting thenorm p for boosts the performance of non-sparse MKL which

4 APs for VOC2008 have been kindly evaluated by the organizers.

performed best throughout all our experiments. The optimal choice of the norm p thereby depends on the actual setof kernels. As a rule of thumb, large values of p work out
in cases where all kernels encode a similar amount of independent information while smaller values of p are best if
some kernels are less informative or redundant.
As an illustrative example, consider a simple experimental setup where we deployed MKL together with the following 12 kernels: level-2 PHoW with grey and hue channels with 10 pixels pitch dense grid and 1200 vocabulary(3 pyramid levels × 2 colors), PHoG of grey channel (3pyramid levels), and the pyramid histograms of intensitywith hue channel (3 pyramid levels). Table 4 shows the results. The sparse `1 -MKL yields a similar accuracy as theaverage-sum kernel. As suspected, both approaches are significantly outperformed by non-sparse MKL.
表 4: A simple case where the performance of `1 -norm

MKL deteriorates.
mean AP

5

uniform40.8±1.0`140.8±0.9`p -joint
42.6±0.7`p -single
42.3±0.9

Conclusions

When measuring data with different measuring devices,
it is always a challenge to combine the respective device
uncertainties in order to fuse all available sensor information optimally. In this paper, we revisited this important
topic and discussed machine learning approaches to adaptively combine different image descriptors in a systematicand theoretically well founded manner. While MKL approaches in principle solve this problem, it has been observed that the standard `1 -norm based MKL can rarely
outperform SVMs that use an average of a large numberof kernels. One hypothesis why this seemingly unintuitive
results may occur, is that the sparsity prior may not be appropriate in many real world problems. A close inspection
reveals that most kernels contain useful structural information and should therefore not be omitted. A slightly lesssevere method of sparsification is to use another norm for
optimization, namely the `p -norm. We tested whether thishypothesis holds true for computer vision and applied therecently developed non-sparse `p -norm MKL algorithms toobject classification tasks. By choosing p as a hyperparameter which controls the degree of non-sparsity from a setof candidate values with the help of a validation data, we
showed that `p -MKL significantly improves SVMs with av-

eraged kernels and the standard sparse `1 -norm MKL. Similar accuracy gain has been observed by controlling p in
one-class MKL [11].
Future work will incorporate further modeling ideas of
the VOC 2008 winner, e.g. the kernel code book, which
we have so far not even employed. The test result with theofficial splits shown in this paper implied that our method
is highly competitive to the winners solution. Furthermore,
a combination of mid-level features by MKL will be an interesting research direction.

参考文献[1] F. Bach, G. Lanckriet, and M. Jordan. Multiple kernel
learning, conic duality, and the smo algorithm. International Conference on Machine Learning, 2004.
[2] Anna Bosch, Andrew Zisserman, and Xavier Muñoz.
Representing shape with a spatial pyramid kernel. In
Proceedings of the 6th ACM international conference
on Image and video retrieval (CIVR ’07), pages 401–
408, 2007.
[3] U. Brefeld, P. Geibel, and F. Wysotzki. Support vector
machines with example dependent costs. In Proceedings of the European Conference on Machine Learning, 2003.
[4] D. Cai, X. He, and J. Han. Efficient kernel discriminant analysis via spectral regression. In ICDM, 2008.
[5] N. Cristianini, J. Shawe-Taylor, A. Elisseeff, and
J. Kandola. On kernel-target alignment. In Advances in Neural Information Processing Systems,
volume 14, pages 367–373, 2002.
[6] G. Csurka, C. Bray, C. Dance, and L. Fan. Visual
categorization with bags of keypoints. In Workshop on
Statistical Learning in Computer Vision, ECCV, pages
1–22, Prague, Czech Republic, May 2004.
[7] N. Dalal and B. Triggs. Histograms of oriented gradientsfor human detection. In IEEE Computer Society
Conference on Computer Vision and Pattern Recognition, volume 1, pages 886–893, San Diego, USA,
June 2005.
[8] M. Everingham, L. Van Gool, C. K. I.
Williams, J. Winn, and A. Zisserman.
The
PASCAL

VisualObjectClasses

Challenge

2008 (VOC2008) Results.
http://www.pascalnetwork.org/challenges/VOC/voc2008/year = workshop/index.html, 2008.
[9] Tommi Jaakkola and David Haussler. Exploiting generative models in discriminative classifiers. In Advances in Neural Information Processing Systems,
volume 11, pages 487–493, 1998.
[10] M. Kloft, U. Brefeld, S. Sonnenburg, A. Zien,
P. Laskov, and K.-R. Müller. Efficient and Accurate`p -Norm MKL. In Advances in Neural Information
Processing Systems 22, 2009. to appear.
[11] M. Kloft, S. Nakajima, and U. Brefeld. Feature Selection for Density Level-Sets. In Proc. of ECML, 2009.
[12] C. Lampert and M. Blaschko. A multiple kernel learning approach to joint multi-class object detection. In
DAGM, pages 31–40, 2008.
[13] Gert R.G. Lanckriet, Nello Cristianini, Peter Bartlett,Laurent El Ghaoui, and Michael I. Jordan. Learning the kernel matrix with semidefinite programming.
Journal of Machine Learning Research, pages 27–72,
2004.
[14] S. Lazebnik, C. Schmid, and J. Ponce. Beyond bagsof features: Spatial pyramid matching for recognizing
natural scene categories. In IEEE Computer Society
Conference on Computer Vision and Pattern Recognition, volume 2, pages 2169–2178, New York, USA,
June 2006.
[15] D. Lowe. Distinctive image features from scale invariant keypoints. International Journal of Computer
Vision, 60(2):91–110, 2004.
[16] A.Y. Ng, M.I. Jordan, and Y.Weiss. On spectral clustering: Analysis and an algorithm. In NIPS, 2002.
[17] C. Ong, A. Smola, and R. Williamson. Hyperkernels.
In NIPS, volume 15, pages 495–502, 2002.
[18] A. Rakotomamonjy, F. Bach, S. Canu, and Y. Grandvalet. More efficiency in multiple kernel learning. In
ICML, pages 775–782, 2007.
[19] B. Schölkopf and A. J. Smola. Learning with Kernels.
MIT Press, Cambridge, MA, 2002.

[20] S. Sonnenburg, G. Rätsch, C. Schäfer, and
B. Schölkopf. Large scale multiple kernel learning.
Journal of Machine Learning Research, 7:1531–1565,
2006.

[21] M. Tahir, K. van de Sande, Jasper Uijlings, Fei Yan, Xirong Li, Krystian Mikolajczyk, Josef Kittler, Theo Gevers, andArnold Smeulders.
Surreyuva srkda method.
http://pascallin.ecs.soton.ac.uk/challenges/VOC/voc2008/worksho[22] Koen E. A. van de Sande, Theo Gevers, and Cees
G. M. Snoek. Evaluation of color descriptors for object and scene recognition. In IEEE Conference on
Computer Vision and Pattern Recognition, Anchorage, Alaska, USA, June 2008.
[23] J.C. van Gemert, J.M. Geusebroek, C.J. Veenman, and
A.W.M. Smeulders. Kernel codebooks for scene categorization. In ECCV, 2008.
[24] M. Varma and D. Ray. Learning the discriminative
power-invariance trade-off. In Proceedings of theIEEE 11th International Conference on Computer Vision (ICCV ’07), pages 1–8, 2007.
[25] J. Zhang, M. Marszalek, S.Lazebnik, and C. Schmid.
Scale and affine invariant interest point detectors. International Journal of Computer Vision, 60(1):63–86,
2004.
[26] J. Zhang, M. Marszalek, S.Lazebnik, and C. Schmid.
Local features and kernels for classification of texture
and object categories: A comprehensive study. International Journal of Computer Vision, 73(2):213–238,
2007.
[27] Alexander Zien and C. Ong. Multiclass multiple kernel learning. In ICML, pages 1191–1198, 2007.
[28] Alexander Zien, Gunnar Rätsch, Sebastian Mika,
Bernhard Schölkopf, Thomas Lengauer, and K.-R.
Müller. Engineering support vector machine kernels
that recognize translation initiation sites. Bioinformatics, 16(9):799–807, 2000.