Online MKL for Structured Prediction∗

André F. T. Martins∗†
Noah A. Smith∗
Eric P. Xing∗
School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USAMário A. T. Figueiredo†
Instituto de Telecomunicações,
Instituto Superior Técnico, Lisboa, Portugal

Pedro M. Q. Aguiar‡
Instituto de Sistemas e Robótica,
Instituto Superior Técnico, Lisboa, Portugal

†

‡

1

Introduction

Structured prediction (SP) problems are characterized by strong interdependence among the output
variables, usually with sequential, graphical, or combinatorial structure [17, 7]. Obtaining goodpredictors often requires a large effort in feature/kernel design and tuning (usually done via crossvalidation). Because discriminative training of structured predictors can be quite slow, specially inlarge scale settings, it is appealing to learn the kernel function simultaneously.
In multiple kernel learning (MKL, [8]), the kernel is learned as a linear combination of prespecified
base kernels. This framework has been made scalable with the advent of wrapper-based methods,
in which a standard learning problem (e.g., an SVM) is repeatedly solved in an inner loop up toa prescribed accuracy [14, 11, 6]. Unfortunately, extending such methods to large-scale SP raises
practical hurdles: since the output space is large, so are the kernel matrices, and the number of
support vectors; moreover, it becomes prohibitive to tackle the inner problem in its batch form, andone usually resorts to online algorithms [12, 3, 13]. The latter are fast learners but slow optimizers[2]; using them in the inner loop with early stopping may misguide the overall MKL optimization.
We propose instead a stand-alone online MKL algorithm which exploits the large-scale tradeoffs
directly. The algorithm iterates between subgradient and proximal steps, and has important advantages: (i) it is simple, flexible, and compatible with sparse and non-sparse variants of MKL, (ii) it
is adequate for SP, (iii) it offers regret, convergence, and generalization guarantees. Experimentally,
the proposed algorithm yields near-optimal solutions faster than wrapper-based approaches (adapted
to SP). We use the two following SP experimental testbeds: sequence labeling for handwritten text
recognition, and natural language dependency parsing. The potential of our approach is shown inlearning combinations of kernels from tens of thousands of training instances, with encouraging
results in terms of speed, accuracy, and interpretability.

2

Structured Prediction (SP) and Multiple Kernel Learning (MKL)In SP, to each input x ∈ X corresponds a set of possible outputs, Y(x) ⊆ Y; e.g., in sequence labeling, x ∈ X is an observed sequence and y ∈ Y(x) is a sequence of labels. Let
U , {(x, y) | x ∈ X , y ∈ Y(x)}. Given a dataset D , {(x1 , y1 ), . . . , (xN , yN )} ⊆ U, the goal is tolearn a compatibility function fθ : U → R whose maximization yields accurate predictions on new
inputs, ŷ(x) = arg maxy∈Y(x) fθ (x, y), according to some cost function ` : Y × Y → R+ . In thispaper, we bring in the MKL framework [1, 8] and definePMfθ (x, y) , hθ, φ(x, y)iH = m=1 hθ m , φm (x, y)iHm ,(1)
LMwhere H = m=1 Hm is a direct sum of RKHS, and θ and φ are block-structured (parameter andfeature) vectors. Learning is carried out by minimizing the regularized empirical risk,
PN
minfθ ∈H λ Ω[fθ ] + N1 i=1 L(fθ ; xi , yi ),(2)where L is a convex loss (e.g., the structured SVM hinge loss, L(fθ ; x, y) , maxy0 ∈Y(x) fθ (x, y 0 )−fθ (x, y) + `(y 0 , y)), Ω : H → R+ is a regularizer, and λ ≥ 0. Some examples are:1

Algorithm 1 Online Proximal MKL
J
T
1: input: D, kernels {Km }M
m=1 , regularizers {λj Ωj }j=1 , number of rounds T , sequence (ηt )t=1
2: Initialize θ 1 = 0; set N = |D|
3: for t = 1 to T do
4:
Take a training pair (xt , yt ) and obtain a subgradient g θt = ∂L(fθt ; xt , yt )5:
Subgradient step: θ̃ t = θ t − ηt g θt
6:
for j = 1 to J do
7:
Proximal step: θ̃ t+j/J = proxηt λΩj (θ̃ t+(j−1)/J )8:
end for9:
Projection step (optional): θ t+1 = θ̃ t+1 · min{1, γ/kθ̃ t+1 k}
10: end for
11: output: the last model fθT +1 or the averaged model fPT θt /T
t=1

PM• `2 -regularization, Ω[fθ ] = kθk2 /2, recovers the standard SVM with kernel m=1 Km ;P
M
• block-norm `2,1 regularization, Ω[fθ ] = 12 kθk22,1 = 12 ( m=1 kθ m kHm )2 , yields sparse MKL,
PM
which is equivalent to learning a kernel of the form m=1 βm Km with β ≥ 0 and kβk1 ≤ 1;
PM
• block-norm `2,q regularization, Ω[fθ ] = 21 kθk22,q = 12 ( m=1 kθ m kqHm )2/q , generalizes the two
previous cases, and for 1 < q ≤ 2 yields non-sparse MKL [6], where the kernel coefficients areconstrained as β ≥ 0 and kβkp ≤ 1 with p = q/(2 − q). The algorithm we propose also tackles
the case q > 2, which cannot be handled with the procedure described in [6];PJ• sums of block-norm regularizers, Ω[fθ ] = 12 j=1 σj kθk22,qj , with σj ≥ 0, are a further generalization that subsume the elastic MKL of [18]. Our algorithm can also handle these.
Decomposition over parts. As usually in SP [17], features decompose over parts; e.g., if thestructure is expressed with a Markov network (V, E), then each part is associated with either avertex or an edge, and the feature vector is written as φ(x, y) = (φV (x, y), φE (x, y)), with:XX
φV (x, y) =
ψ X,V (x, i) ⊗ ζ Y,V (yi ) and φE (x, y) =
ψ X,E (x, ij) ⊗ ζ Y,E (yi , yj ). (3)
i∈V

ij∈E

We make the common simplifying assumption that ζ Y,V is the identity feature mapping, that
ψ X,E ≡ 1, and that ζ Y,E is the identity feature mapping scaled by a positive β0 . We then learn
the kernel KX,V ((x, i), (x0 , i0 )) = hφX,V (x, i), φX,V (x0 , i0 )i as a combination of basis kernels{KX,V,m }M
m=1 . This yields a kernel decomposition of the formPPM
K(u, u0 ) = i,i0 ∈V :yi =y00 m=1 βm KX,V,m ((x, i), (x0 , i0 )) + β0 · |{i, i0 : yi = yi00 , yj = yj0 0 }|.
i

In our sequence labeling experiments, vertices and edges correspond to label unigrams and bigrams.
We explore two strategies: learning β1 , . . . , βM , with β0 = 1 fixed, or also learning β0 .

3An Online Algorithm for MKL

To handle (2), we propose Alg. 1, which can be seen as extending FOBOS [5] by allowing multiple
PJ
proximal steps to deal with composite regularizers, Ω[fθ ] =j=1 Ωj [fθ ]. Like SGD, Alg. 1
is suitable for problems with large N ; the proximal steps make it effective for (non-differentiable)sparsity-inducing regularizers. As in PEGASOS [13], if a bound is known on the optimum, kθ ∗ k ≤ γ,
a projection step (line 9) is used. Naturally, Alg. 1 is entirely (or partially) kernelizable.
Subgradient step (line 4). First, local scores are computed for each part using the current parameters. Then, the highest score output, ŷt ∈ argmaxyt0 ∈Y(x) fθ (xt , yt0 ) + `(yt0 , yt ), is found (e.g., bydynamic programming). Finally, a subgradient is given as g θ = fθ (xt , ŷt ) − fθ (xt , yt ).
Proximal step (line 7). Given Ω : H → R, the Ω-proximity operator [4] is defined as proxΩ (θ̃) =arg minθ 12 kθ− θ̃k2 +Ω(θ). The block structure of the parameter vector makes this step particularly
efficient, thanks to the following result:
Proposition 1 Let Ω(θ) ≡ ω((kθ m k)Mm=1 ) depend on each block only through its `2 -norm. Then,[proxΩ (θ)]m = [proxω (kθ 1 k, . . . , kθ M k)]m (θ m /kθ m k).
2

KernelLinear (L)Quadratic (Q)Gaussian (G) (σ 2 = 5)
Average (L + Q + G)/3
MKL β1 L + β2 Q + β3 G
MKL β0 , β1 L + β2 Q + β3 G
B1 -Spline (B1 )Average (L + B1 )/2
MKL β1 L + β2 B1
MKL β0 , β1 L + β2 B1

Training
Runtimes
6 sec.
116 sec.
123 sec.
118 sec.
279 sec.
282 sec.
8 sec.
15 sec.
15 sec.
16 sec.

Test Acc.
(per char.)
71.8 ± 3.9%
85.5 ± 0.3%
84.1 ± 0.4%
84.3 ± 0.3%
87.5 ± 0.3%
87.5 ± 0.4%
75.4 ± 0.9%
83.0 ± 0.3%
85.2 ± 0.3%
85.2 ± 0.3%

Table 1: Results for handwriting recognition.
Averages over 10 runs on the same folds as in[17], training on one and testing on the others.
The linear and quadratic kernels are normalized to unit diagonal. In all cases, 20 epochs
were used. Results are for the best regularization coefficient C = 1/(λm) (chosen from
{0.1, 1, 10, 102 , 103 , 104 }).

Hence, any `r2,q -proximity operator can be reduced to an `rq one. For sparse MKL (q = 1, r = 2) thiscomputation can be carried out in time Õ(M ) [9] (Õ hides logarithmic terms). For non-sparse MKL,
we replace `22,q by `q2,q (equivalent up to a change in the regularization constant). The `q2,q -proximity
operator is separable, hence can be computed coordinatewise.
Kernelization. The computation of local scores, which precedes the gradient step, only involves
inner products. Hence, the whole algorithm can be kernelized. We only need to keep track of the`2 -norm of each block, which can be updated after each gradient step viakθ̃ t,m k2=kθ t,m k2 − 2ηt hθ t,m , φm (xt , yt )i + ηt2 kφm (xt , ŷt ) − φm (xt , yt )k2=kθ t,m k2 − 2ηt fm (ût ) + ηt2 (Km (ut , ut ) + Km (ût , ût ) − 2Km (ut , ût ))(4)

and rescaled after each proximal and projection steps.
Regret, Convergence and Generalization Bounds. Let the loss L be convex and G-Lipschitz on
the γ-radius `2 -ball (e.g., hinge or logistic), the regularizers Ωj be convex and satisfy additional mildqconditions (satisfied, e.g., by Ωj = λj kθkpjj , for pj , qj ≥ 1). We show [9] that Alg. 1 converges to 
precision, with high confidence, in O(1/2 ) iterations (as the best batch MKL algorithms). If L or Ω
are strongly convex (e.g., if at least one regularizer Ωj is a squared `2,q -norm, for q > 1), the boundimproves to Õ(1/). The generalization√ bounds are of the same order. This follows from the fact,
shown in [9], that using rateη√t = η0 / t yields cumulative regret (w.r.t. the best fixed hypothesis)
T ; in the presence of σ-strong convexity, a rate ηt = 1/(σt) yields
RegT ≤ (2γ 2 )/η0 + G2 η0
RegT ≤ G2 (1 + log T )/(2σ).

4Experiments

Handwriting recognition. We use an OCR dataset [17] with 6,877 words written by 150 people(52,152 characters). Each character is a 16 × 8 binary image with one of 26 labels (a-z). Our
first experiment (upper part of Tab. 1) compares linear, quadratic, and Gaussian kernels, used individually, combined via a simple average, or with MKL via Alg. 1. The results show that MKL
outperforms the others, and that learning the bigram weight β0 did not make any difference.
The second experiment shows that Alg. 1 handles both feature and kernel sparsity by learning a
combination of a linear kernel (explicit features) with a generalized B1 -spline kernel (K(x, x0 ) =max{0, 1 − kx − x0 k/h}, with h such that the kernel matrix has ∼ 95% zeros). The idea is tocombine a simple feature-based kernel with one depending only on a few nearest neighbors. The
results (Tab. 1, bottom part) show that MKL outperforms the individual kernels and the averaged
kernel. The runtime is much shorter than in the previous experiment, with a mild accuracy decrease.
The third experiment compares Alg. 1 with two wrapper-based schemes: a Gauss-Seidel method alternating between optimizing the SVM and the kernel weights, and a gradient method (SimpleMKL[11]). In both cases, the SVMs were tackled with structured PEGASOS. As shown in Fig. 1, Alg. 1
converges in a small number of epochs to a near-optimal region, suggesting its usefulness in settings
where each epoch is costly.
Dependency parsing. We train non-projective dependency parsers on the dataset of the CoNLL2008 shared task [15] (39,278 training, 2,399 test sentences). The output to be predicted from each
input sentence is the set of dependency arcs, which must define a directed spanning tree (example inFig. 2). We use arc-factored models, and define a total of 507 feature groups (our linear kernels to be
combined) conjoining words, lemmas, parts-of-speech, distance and direction of attachment. This3

rojective Dependency Parsing using Spanning Tree Algorithms
Ryan McDonald
Fernando Pereira
Department of Computer and Information Science
University of Pennsylvania{ryantm,pereira}@cis.upenn.edu

Figure 1: Comparison between Alg. 1
and two wrapper based methods in the
OCR dataset, with C = 100. With only
20–30 passes over the data, Alg. 1 approaches a region very close to the optimum; in contrast, the wrapper-based
methods need about 100 epochs.

Kiril Ribarov
Jan Hajič
Institute of Formal and Applied Linguistics
Charles University{ribarov,hajic}@ufal.ms.mff.cuni.cz
Abstract
root

John

hit

the

ball

with

the

Figure 2:Top:
a dependency
parse tree (see [10]).
Bottomleft:
group weights along theepochs of Alg. 1. Bottom right:
results of standard SVMs trainedon sets of feature templates of sizes{107, 207, 307, 407, 507},
eitherselected via a standard SVM or
by MKL (the UAS—unlabeled attachment score—is the fraction of
non-punctuation words whose head
was correctly assigned.)bat

alize weighted dependency parsarching for maximum spanning
Figure 1: An example dependency tree.
STs) in directed graphs. Using
Dependency representations, which link words tosentation, the parsing algorithm
their arguments, have a long history (Hudson, 1984).
(1996) is sufficient for searchFigure 1 shows a dependency tree for the sentencell projective trees in O(n3 ) time.
John hit the ball with the bat. We restrict ourselvesprisingly, the representation isto dependency tree analyses, in which each word denaturally to non-projective parspends on exactly one parent, either another word or ag Chu-Liu-Edmonds (Chu anddummy root symbol as shown in the figure. The tree
5; Edmonds, 1967) MST alin Figure 1 is projective, meaning that if we put theyielding an O(n2 ) parsing alwords in their linear order, preceded by the root, theWe evaluate these methods
edges can be drawn above the words without crossague Dependency Treebank usor, equivalently,
a wordand instantiatedits descendantsfeatures. The feature vectors associated with eacha problemwith > 50
millionne large-margin learning tech- yields ings,
formarc,a contiguous
substringof thesentence.
however,are verysparseand this is exploited in the implementation. We run Alg. 1
rammer et al., 2003; McDonald candidatefeatures.
AlthoughMKL
did not
outperform an SVM, it showed a good performance05) and show that MST parsing with explicit
In English,
projective
trees aresufficient
to anaefficiency and accuracy for lan- at pruning
irrelevant
featuretemplates(Fig.
2,bottomright). Besides interpretability, this pruning islyze most sentence types. In fact, the largest source
ith non-projective dependencies. also appealinginatwo-stagearchitecture,whereastandard
learner at a second stage will only needof English dependency trees is automatically gener-

to handlesmallof the groups
hypothesized, perhaps giving speedups in inference.
atedafromthefraction
Penn Treebank(Marcus initiallyet al., 1993)

and is by convention exclusively projective. However, there are certain examples in which a nonAcknowledgments
parsing has seen a surge of inter- projective tree is preferable. Consider the sentence
applications such as relation extrac- John saw a dog yesterday which was a Yorkshire TerA. M. wasby a grantthrough the CMU-Portugal Program, and also by Priberam
and Sorensen, 2004), machine transrier. supported
Here the relative
clausefrom
whichFCT/ICTI
was a Yorkshire
Informática.
E.
X.
was
supportedby
AFOSR
FA9550010247,
ONR N000140910758, NSF CAREER DBInd Palmer, 2005), synonym genera- Terrier and the object it modifies (the dog) are sep0546594,
NSFbyIIS-0713379,
and isannoAlfredSloana et al., 2002), and lexical resource
aratedan adverb. Thereway toP.draw
the Fellowship. M. F. and P. A. were supported by the
FET programme
under
the SIMBAD(Snow et al., 2004). The primarydependency(EUtreeFP7),
for thissentencein the planeprojectwith (contract 213250), and by a FCT grant PTDC/EEATEL/72572/2006.
ing dependency structures insteadof no crossing edges, as illustrated in Figure 2. In lantive lexicalized phrase structures is guages with more flexible word order than English,
Referencesmore efficient to learn and parse while
such as German, Dutch and Czech, non-projective
much of the predicate-argument infordependencies
are morefrequent.
inflectionMultiple kernel learning, conic duality, and the SMO[1] Bach,F., Lanckriet,
G., andJordan,Rich
M. (2004).
in applications.
systems
reducereliance
on
word
order
to
expressalgorithm. In ICML.

tion[2] Bottou, L. and Bousquet, O. (2007). The tradeoffs of large scale learning. NIPS, 20.
[3] Collins, M., Globerson, A., Koo, T., Carreras, X., and Bartlett, P. (2008). Exponentiated gradient algorithms for conditional random fields and max-margin Markov networks. JMLR.
[4] Combettes, P. and Wajs, V. (2006). Signal recovery by proximal forward-backward splitting. Multiscale
Modeling and Simulation, 4(4):1168–1200.
[5] Duchi, J. and Singer, Y. (2009). Efficient online and batch learning using forward backward splitting.
JMLR, 10:2873–2908.
[6] Kloft, M., Brefeld, U., Sonnenburg, S., and Zien, A. (2010). Non-Sparse Regularization and Efficient
Training with Multiple Kernels. Arxiv preprint arXiv:1003.0079.
[7] Lafferty, J., McCallum, A., and Pereira, F. (2001). Conditional random fields: Probabilistic models forsegmenting and labeling sequence data. In ICML.
[8] Lanckriet, G. R. G., Cristianini, N., Bartlett, P., Ghaoui, L. E., and Jordan, M. I. (2004). Learning thekernel matrix with semidefinite programming. JMLR, 5:27–72.
[9] Martins, A. F. T., Figueiredo, M. A. T., Aguiar, P. M. Q., Smith, N. A., and Xing, E. P. (2010). Online
MKL for Structured Prediction. Arxiv preprint arXiv:1010.2770.
[10] McDonald, R. T., Pereira, F., Ribarov, K., and Hajic, J. (2005). Non-projective dependency parsing using
spanning tree algorithms. In Proc. of HLT-EMNLP.
[11] Rakotomamonjy, A., Bach, F., Canu, S., and Grandvalet, Y. (2008). SimpleMKL. JMLR, 9:2491–2521.

4

[12] Ratliff, N., Bagnell, J., and Zinkevich, M. (2006). Subgradient methods for maximum margin structured
learning. In ICML Workshop on Learning in Structured Outputs Spaces.
[13] Shalev-Shwartz, S., Singer, Y., and Srebro, N. (2007). Pegasos: Primal estimated sub-gradient solver forsvm. In ICML.
[14] Sonnenburg, S., Rätsch, G., Schäfer, C., and Schölkopf, B. (2006). Large scale MKL. JMLR, 7:1565.
[15] Surdeanu, M., Johansson, R., Meyers, A., Màrquez, L., and Nivre, J. (2008). The CoNLL-2008 sharedtask on joint parsing of syntactic and semantic dependencies. Proc. of CoNLL.
[16] Suzuki, T. and Tomioka, R. (2009). SpicyMKL. Arxiv preprint arXiv:0909.5026.
[17] Taskar, B., Guestrin, C., and Koller, D. (2003). Max-margin Markov networks. In NIPS.
[18] Tomioka, R. and Suzuki, T. (2010). Sparsity-accuracy trade-off in MKL. Arxiv.

5