Learning Structured Classifiers with Dual
Coordinate AscentAndre F. T. Martins†‡
Eric P. Xing†

Kevin Gimpel†

Mario A. T. Figueiredo‡

Noah A. Smith†Pedro M. Q. Aguiar]

June 2010
CMU-ML-10-109

School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213† School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA,
‡ Instituto de Telecomunicações / ] Instituto de Sistemas e Robótica, Instituto Superior Técnico,

Lisboa, Portugal

A. M. was supported by a grant from FCT/ICTI through the CMU-Portugal Program, and also by Priberam
Informática. K. G. was supported by NSF grant IIS-0844507. N. S. was supported in part by Qatar NRF NPRP-08485-1-083. E. X. was supported by AFOSR FA9550010247, ONR N000140910758, NSF CAREER DBI-0546594,
NSF IIS-0713379, and an Alfred P. Sloan Fellowship. M. F. and P. A. were supported by the FET programme (EUFP7), under the SIMBAD project (contract 213250).

Keywords: Structured prediction, online learning, dual coordinate ascentAbstract
We present a unified framework for online learning of structured classifiers that handles a widefamily of convex loss functions, properly including CRFs, structured SVMs, and the structured
perceptron. We introduce a new aggressive online algorithm that optimizes any loss in this family.
For the structured hinge loss, this algorithm reduces to 1-best MIRA; in general, it can be regarded
as a dual coordinate ascent algorithm. The approximate inference scenario is also addressed. Our
experiments on two NLP problems show that the algorithm converges to accurate models at leastas fast as stochastic gradient descent, without the need to specify any learning rate parameter.

1Introduction

Learning structured classifiers discriminatively typically involves the minimization of a regularized
loss function; the well-known cases of conditional random fields (CRFs, [Lafferty et al., 2001])
and structured support vector machines (SVMs, [Taskar et al., 2003, Tsochantaridis et al., 2004,
Altun et al., 2003]) correspond to different choices of loss functions. For large-scale settings, theunderlying optimization problem is often difficult to tackle in its batch form, increasing the popularity of online algorithms. Examples are the structured perceptron [Collins, 2002a], stochastic
gradient descent (SGD) [LeCun et al., 1998], and the margin infused relaxed algorithm (MIRA)[Crammer et al., 2006].
This paper presents a unified representation for several convex loss functions of interest in
structured classification (§2). In §3, we describe how all these losses can be expressed in variational
form as optimization problems over the marginal polytope [Wainwright and Jordan, 2008]. We
make use of convex duality to derive new online learning algorithms (§4) that share the “passiveaggressive” property of MIRA but can be applied to a wider variety of loss functions, including
the logistic loss that underlies CRFs. We show that these algorithms implicitly perform coordinate
ascent in the dual, generalizing the framework in Shalev-Shwartz and Singer [2006] for a larger
set of loss functions and for structured outputs.
The updates we derive in §4 share the remarkable simplicity of SGD, with an important advantage: they do not require tuning a learning rate parameter or specifying an annealing schedule.
Instead, the step sizes are a function of the loss and its gradient. The additional computation
required for loss evaluations is negligible since the methods used to compute the gradient also
provide the loss value.
Two important problems in NLP provide an experimental testbed (§5): named entity recognition and dependency parsing. We employ feature-rich models where exact inference is sometimes
intractable. To be as general as possible, we devise a framework that fits any structured classification problem representable as a factor graph with soft and hard constraints (§2); this includes
problems with loopy graphs, such as some variants of the dependency parsers of Smith and Eisner[2008].

2

Structured Classification and Loss Functions

2.1

Inference and Learning

Denote by X a set of input objects from which we want to infer some hidden structure conveyed in an output set Y. We assume a supervised setting, where we are given labeled data
D , {(x1 , y1 ), . . . , (xm , ym )} ⊆ X × Y. Each input x ∈ X (e.g., a sentence) is associated witha set of legal outputs Y(x) ⊆ Y (e.g., candidate parse trees); we are interested in the case whereY(x) is a structured set whose cardinality grows exponentially with the size of x. We consider
linear classifiers hθ : X → Y of the formhθ (x) , argmax θ > φ(x, y),y∈Y(x)

1(1)

where θ ∈ Rd is a vector of parameters and φ(x, y) ∈ Rd is a feature vector. Our goal is tolearn the parameters θ from the data D such that hθ has small generalization error. We assume acost function ` : Y × Y → R+ is given, where `(ŷ, y) is the cost of predicting ŷ when the trueP
output is y. Typically, direct minimization of the empirical risk, minθ∈Rd m1 m
i=1 `(hθ (xi ), yi ), is
intractable and hence a surrogate non-negative, convex loss L(θ; x, y) is used. To avoid overfitting,a regularizer R(θ) is added, yielding the learning problem
mind λR(θ) +

θ∈R

m
1 X
L(θ; xi , yi ),
m i=1

(2)

where λ ∈ R is the regularization coefficient. Throughout this paper we assume `2 -regularization,R(θ) , 12 kθk2 , and focus on loss functions of the form


X
1
log
exp β θ > φ(x, y 0 ) − φ(x, y) + γ`(y 0 , y)β
y 0 ∈Y(x) Lβ,γ (θ; x, y) ,



,

(3)

which subsumes some well-known cases:• The logistic loss (in CRFs), LCRF (θ; x, y) , − log Pθ (y|x), corresponds to β = 1 and γ = 0;
• The hinge loss of structured SVMs, LSVM (θ; x, y) , maxy0 ∈Y(x) θ > (φ(x, y 0 ) − φ(x, y)) +`(y 0 , y), corresponds to the limit case β → ∞ and any γ > 0;
• The loss underlying the structured perceptron is obtained for β → ∞ and γ = 0.
• The softmax-margin loss recently proposed in Gimpel and Smith [2010] is obtained with β =γ = 1.
For any choice of β > 0 and γ ≥ 0, the resulting loss function is convex in θ, since, up to a scale
factor, it is the composition of the (convex) log-sum-exp function with an affine map.1 In §4 we
present a dual coordinate ascent online algorithm to handle (2), for this family of losses.

2.2

A Framework for Structured Inference

Two important inference problems are: to obtain the most probable assignment (i.e., to solve (1))
and to compute marginals, when a distribution is defined on Y(x). Both problems can be challenging when the output set is structured. Typically, there is a natural representation of the elements ofY(x) as discrete-valued vectors y ≡ y = (y1 , . . . , yI ) ∈ Y1 × . . . × YI ≡ Ȳ, each Yi being a setof labels (I may depend on x). We consider subsets S ⊆ {1, . . . , I} and write partial assignment
vectors as yS = (yi )i∈S . We assume a one-to-one map (not necessarily onto) from Y(x) to Ȳ anddenote by S(x) ⊆ Ȳ the subset of representations that correspond to valid outputs.
The next step is to design how the feature vector φ(x, y) decomposes, which can be conveniently done via a factor graph [Kschischang et al., 2001, McCallum et al., 2009]. This is a1
Some important non-convex losses can also be written as differences of losses in this family. By defining δLβ,γ =Lβ,γ − Lβ,0 , the case β = 1 yields δLβ,γ (θ; x, y) = log Eθ exp `(Y, y), which is an upper bound on Eθ `(Y, y), usedin minimum risk training [Smith and Eisner, 2006]. For β = ∞, δLβ,γ becomes a structured ramp loss [Collobert
et al., 2006].

2

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

bat

ze weighted dependency pars1: Example of aFigure
dependency
treedependency(adapted fromching for maximum Figure
spanning
1: An parseexampletree.[McDonald et al., 2005]).
s) in directed graphs. Using
bipartite
graph with two Dependency
types of nodes:
variable nodes,
which
our case
representations,whichlinkinwords
to are the I components
ntation, the parsing
algorithm
of
y;
and
a
set
C
of
factornodes.
Eachfactornode
isassociatedwitha subset C ⊆ {1, . . . , I};
their arguments, have a long history (Hudson, 1984).
1996) is sufficient for searchan edge connects the ith
variablenode aanda factor nodei ∈sentence
C. Each factor has a potential
Figure1 shows
dependency
tree C
foriffthe
projective trees in O(n3 ) time.
ΨC , a function that maps
assignmentsofvariablesto
non-negative
real values. We distinguishJohn hit the ball with the bat. We restrict ourselvesisingly, the representation is
between two kinds of tofactors:
hard constraint
factors,which
areworduseddeto rule out forbidden pardependency
tree analyses,
in whicheachturally to non-projective parstial assignments by mappingthem
to zerovalues,and soft
pends onexactly
one potential
parent, either
another
wordfactors,
or a whose potentials are
Chu-Liu-Edmonds (Chu andstrictly positive. Thus,dummy
C = Chard∪C.
We
associate
with
each
soft
factor a local feature vector
softroot symbol
as shown in the figure. The tree
Edmonds, 1967) MST alφ (x, yC ) and define in Figure 1 is projective, X
meaning that if we put theelding an O(n2 )C parsing
alφ(x,y),φC (x, yby(4)C ).
words in their linear order, preceded
the root, theWe evaluate these methods
C∈C
edges can be drawn above softthe words without crossue Dependency Treebank us>
The potential
factoror,is definedas ΨC a(x,word
yC ) and= exp(θφC (x, yC )). In a log-linear probequivalently,
its descendants
large-margin learning
tech-of a soft ings,
abilistic
model,
thefeaturedecompositionin(4)
inducesthefollowing
factorization for the condiform a contiguous substring of the sentence.
mmer et al., 2003; McDonald
of Y :) and show thattional
MSTdistribution
parsing
In English, projective trees are sufficient to anaY
ficiency and accuracy for lan1lyze
ΨC (x,source
yC ),
(5)
Pθmost(Y =sentencey | X =types.
x) = In fact, the largest
non-projective dependencies.
Z(θ,x)
of English dependency trees is automaticallygenerC∈Cfrom the Penn Treebank (Marcus et al., 1993)
P ated Q
the partition
function.HowTwo examples follow.
where Z(θ, x) = y0 ∈S(x)ΨC (x, yC0 ) is
and is C∈C
by convention
exclusively
projective.
onever, there are certain examples in which a noni ∈ {1,. . .is, I}
is a positionin the sequence
and Yi is the set of possible
rsing has seen Sequencea surge labeling:of inter- Eachprojectivetree
preferable.
Considerthe sentenceat thatextracposition. John
If all saw
labela sequences
are whichallowed,no hard Terconstraint factors exist. In a
plications such labels
as relation
dog yesterday
wasthena Yorkshire
bigrammodel,transthe softrier.
factors
aretheof relative
the formclause
C = {i,i + was1}. Toobtain a k-gram model, redefined Sorensen, 2004),
machineHerewhich
a Yorkshire
Yi to begenerathe set ofTerrier
all contiguous(k − 1)-tuplesof labels.
d Palmer, 2005),eachsynonymand the object
it modifies(the dog) are sepet al., 2002), and lexical resource arated by an adverb. There is no way to draw the
now et al., 2004).
The primarytree forthis sentencein theplane
witheach input is a sentence
Dependency
parsing:dependency
In this parsing
formalism[Kübler
et al.,
2009],
g dependency structuresinstead of words),
no crossing
edges,
as illustrated
in Figurelan(i.e., a sequenceand theoutputs
to be predicted
are 2.
theIndependency
arcs, which linke lexicalized phrase
structures
is andguages
with
more
flexibleword orderheads tomodifiers,
overallmust
definea spanning
tree than(see English,
Fig. 1 for an example). We letre efficient to learn
and
parse
while
such
as
German,Dutch
andCzech,
non-projective
each i = (h, m) index a pair of words, and define Yi = {0, 1}, where 1 means that there is a linkuch of the predicate-argument
dependencies
moreisfrequent.
Rich inflection
from h to m, inforand 0 meansotherwise.areThere
one hard factor
connected to all variables (call it
n applications. TREE), its potential being
systems
on wordformordera toexpresstree and zero otherwise.
one ifreduce
the arcrelianceconfigurations
spanning
In the arc-factored model [Eisner, 1996, McDonald et al., 2005], all soft factors are unary and thegraph is a tree. More sophisticated models (e.g., with siblings and grandparents) include pairwise
factors, creating loops [Smith and Eisner, 2008].

3

3

Variational Inference

3.1

Polytopes and Duality

Let P = {Pθ (.|x) | θ ∈ Rd } be the family of all distributions of the form (5), and rewrite (4) as:
φ(x, y) =X

φC (x, yC ) = F(x) · χ(y),C∈Csoft

where F(x) is a d-by-k feature matrix, with k = C∈Csoft i∈C |Yi |, each column containing thevectors φC (x, yC ) for each factor C and configuration yC ; and χ(y) is a binary k-vector indicating
which configurations are active given Y = y. We then define the marginal polytope
P

Q

Z(x) , conv{z ∈ Rk | ∃y ∈ Y(x) s.t. z = χ(y)},where conv denotes the convex hull. Note that Z(x) only depends on the graph and on the specification of the hard constraints (i.e., it is independent of the parameters θ).2 The next proposition(illustrated in Fig. 2) goes farther by linking the points of Z(x) to the distributions in P. BeP
low, H(Pθ (.|x)) = − y∈Y(x) Pθ (y|x) log Pθ (y|x) denotes the entropy, Eθ the expectation underPθ (.|x), and zC (yC ) the component of z ∈ Z(x) indexed by the configuration yC of factor C.
Proposition 1 There is a map coupling each distribution Pθ (.|x) ∈ P to a unique z ∈ Z(x) suchthat Eθ [χ(Y )] = z. Define H(z) , H(Pθ (.|x)) if some Pθ (.|x) is coupled to z, and H(z) = −∞if no such Pθ (.|x) exists. Then:
1. The following variational representation for the log-partition function holds:
log Z(θ, x) = max θ > F(x)z + H(z).
z∈Z(x)(6)

2. The problem in (6) is convex and its solution is attained at the factor marginals, i.e., there is a
maximizer z̄ s.t. z̄C (yC ) = Prθ {YC = yC } for each C ∈ C. The gradient of the log-partition
function is ∇ log Z(θ, x) = F(x)z̄.
3. The MAP ŷ , argmaxy∈Y(x) Pθ (y|x) can be obtained by solving the linear programẑ , χ(ŷ) = argmax θ > F(x)z.

(7)

z∈Z(x)

Proof: [Wainwright and Jordan, 2008, Theorem 3.4] provide a proof for the canonical overcomplete representation where F(x) is the identity matrix, i.e., each feature is an indicator of theconfiguration of the factor. In that case, the map from the parameter space to the relative interior of the marginal polytope is surjective. In our model, arbitrary features are allowed and theparameters are tied, since they are shared by all factors. This can be expressed as a linear map
2

The marginal polytope can also be defined as the set of factor marginals realizable by distributions that factor according to the graph. Log-linear models with canonical overcomplete parametrization—i.e., whose sufficient statistics(features) at each factor are configuration indicators—are studied in Wainwright and Jordan [2008].

4

Parameter�space Factor�log-potentials� Marginal�polytope�
space�������

Figure 2: Dual parametrization of the distributions in P. The original parameter is linearly mapped
to the factor log-potentials, the canonical overcomplete parameter space Wainwright and Jordan[2008], which is mapped onto the relative interior of the marginal polytope Z(x). In general only
a subset of Z(x) is reachable from our parameter space.

θ 7→ s = F(x)> θ that “places” our parameters θ ∈ Rd onto a linear subspace of the canonicalovercomplete parameter space; therefore, our map θ 7→ z is not necessarily onto riZ(x), unlike in
Wainwright and Jordan [2008], and our H(z) is defined slightly differently: it can take the value−∞ if no θ maps to z. This does not affect the expression in (6), since the solution of this optimization problem with our H(z) replaced by theirs is also the feature expectation under Pθ (.|x)
and the associated z, by definition, always yields a finite H(z).

3.2

Loss Evaluation and Differentiation

We now invoke Prop. 1 to derive a variational expression for evaluating any loss Lβ,γ (θ; x, y) in(3), and compute its gradient as a by-product.3 This is crucial for the learning algorithms to be
introduced in §4. Our only assumption is that the cost function `(y 0 , y) can be written as a sum
over factor-local costs; letting z = χ(y) and z0 = χ(y 0 ), this implies `(y 0 , y) = p> z0 + q for somep and q which are constant with respect to z0 .4 Under this assumption, and letting s = F(x)> θ be
the vector of factor log-potentials, Lβ,γ (θ; x, y) becomes expressible in terms of the log-partition
function of a distribution whose log-potentials are set to β(s + γp). From (6), we obtain
Lβ,γ (θ; x, y) = 0max θ > F(x)(z0 − z) +z ∈Z(x)1
H(z0 ) + γ(p> z0 + q).
β(8)Let z̄ be a maximizer in (8); from the second statement of Prop. 1 we obtain the following expression for the gradient of Lβ,γ at θ:∇Lβ,γ (θ; x, y) = F(x)(z̄ − z).

(9)For concreteness, we revisit the examples discussed in the previous subsection.
3

Our description also applies to the (non-differentiable) hinge loss case, when β → ∞, if we replace all instancesof “the gradient” in the text by “a subgradient.”
4
For the Hamming loss, this holds with p = 1 − 2z and q = 1> z. See Taskar et al. [2006] for other examples.

5Sequence Labeling. Without hard constraints, the graphical model does not contain loops, andtherefore Lβ,γ (θ; x, y) and ∇Lβ,γ (θ; x, y) may be easily computed by setting the log-potentials as
described above and running the forward-backward algorithm.
Dependency Parsing. For the arc-factored model, Lβ,γ (θ; x, y) and ∇Lβ,γ (θ; x, y) may be computed exactly by modifying the log-potentials, invoking the matrix-tree theorem to compute thelog-partition function and the marginals [Smith and Smith, 2007, Koo et al., 2007, McDonald andSatta, 2007], and using the fact that H(z̄) = log Z(θ, x) − θ > F(x)z̄. The marginal polytope isthe same as the arborescence polytope in Martins et al. [2009]. For richer models where arc interactions are considered, exact inference is intractable. Both the marginal polytope and the entropy,
necessary in (6), lack concise closed form expressions. Two approximate approaches have been
recently proposed: a loopy belief propagation (BP) algorithm for computing pseudo-marginals[Smith and Eisner, 2008]; and an LP-relaxation method for approximating the most likely parsetree [Martins et al., 2009]. Although the two methods may look unrelated at first sight, both optimize over outer bounds of the marginal polytope. See [Martins et al., 2010] for further discussion.

4

Online Learning

We now propose a dual coordinate ascent approach to learn the model parameters θ. This approach
extends the primal-dual view of online algorithms put forth by Shalev-Shwartz and Singer [2006]
to structured classification; it handles any loss in (3). In the case of the hinge loss, we recover the
online passive-aggressive algorithm (also known as MIRA, [Crammer et al., 2006]) as well as its
k-best variants. With the logistic loss, we obtain a new passive-aggressive algorithm for CRFs.
Start by noting that the learning problem in (2) is not affected if we multiply the objective by
m. Consider a sequence of primal objectives P1 (θ), . . . , Pm+1 (θ) to be minimized, each of theform
Pt (θ) = λmR(θ) +t−1
XL(θ; xi , yi ).

i=1

Our goal is to minimize Pm+1 (θ); for simplicity we consider online algorithms with only one passover the data, but the analysis can be extended to the case where multiple epochs are allowed.
Below, we let R̄ , R ∪ {+∞} be the extended reals and, given a function f : Rn → R̄, wedenote by f ? : Rn → R̄ its convex conjugate, f ? (y) = supx x> y − f (x) (see Appendix A fora background of convex analysis). The next proposition, proved in [Kakade and Shalev-Shwartz,
2008], states a generalized form of Fenchel duality, which involves a dual vector µi ∈ Rd per each
instance.
Proposition 2 ([Kakade and Shalev-Shwartz, 2008]) The Lagrange dual of minθ Pt (θ) ismax Dt (µ1 , . . . , µt−1 ),µ1 ,...,µt−1

where

t−1
t−1
X
1 X
µi −
L? (µi ; xi , yi ).
−λm i=1i=1!

Dt (µ1 , . . . , µt−1 ) = −λmR

?

6

(10)

Algorithm 1 Dual coordinate ascent (DCA)
Input: D, λ, number of iterations K
Initialize θ 1 = 0; set m = |D| and T = mK
for t = 1 to T do
Receive an instance xt , yt
Update θ t+1 by solving (11) exactly or approximately (see Alg. 2)
end forP
Return the averaged model θ̄ ← T1 Tt=1 θ t .

Algorithm 2 Parameter updates
Input: current model θ t , instance (xt , yt ), λObtain zt from yt
Solve the variational problem in (8) to obtainz̄t and Lβ,γ (θ t , xt , yt )Compute ∇Lβ,γ (θ t , xt , yt ) = F(xt )(z̄t − zt )n

L(θ t ;xt ,yt )1, k∇L(θCompute ηt = min λm
2t ;xt ,yt )kReturn θ t+1 = θ t − ηt ∇L(θ t ; xt , yt )o

If R(θ) = 12 kθk2 , then R = R? , and strong duality holds for any convex L, i.e., Pt (θ ∗ ) =Dt (µ∗1 , . . . , µ∗t−1 ) where θ ∗ and µ∗1 , . . . , µ∗t−1 are respectively the primal and dual optima. More1 Pt−1 ∗over, the following primal-dual relation holds: θ ∗ = − λm
i=1 µi .
We can therefore transform our problem into that of maximizing Dm+1 (µ1 , . . . , µm ). Dual coordinate ascent (DCA) is an umbrella name for algorithms that manipulate a single dual coordinate at a time. In our setting, the largest such improvement at round t is achieved by µt ,argmaxµ Dt+1 (µ1 , . . . , µt−1 , µ). The next proposition, proved in Appendix B, characterizes the
mapping of this subproblem back into the primal space, shedding light on the connections withknown online algorithms.
1
Proposition 3 Let θ t , − λm

Pt−1

i=1 µi . The Lagrange dual of maxµ Dt+1 (µ1 , . . . , µt−1 , µ) is

min
θ

λm
kθ − θ t k2 + L(θ; xt , yt ).
2(11)

Assembling these pieces together yields Alg. 1, where the solution of (11) is carried out by
Alg. 2, as explained next.5 While the problem in (11) is easier than the batch problem in (2), an
exact solution may still be prohibitively expensive in large-scale settings, particularly because it has
to be solved repeatedly. We thus adopt a simpler strategy that still guarantees some improvementin the dual. Noting that L is non-negative, we may rewrite (11) as
minθ,ξ λmkθ − θ t k2 + ξ
2s.t. L(θ; xt , yt ) ≤ ξ,

ξ ≥ 0.

(12)

From the convexity of L, we may take its first-order Taylor approximation around θ t to obtain thelower bound L(θ; xt , yt ) ≥ L(θ t ; xt , yt ) + (θ − θ t )> ∇L(θ t ; xt , yt ). Therefore the true minimumin (11) is lower bounded by
min
θ,ξ

λm
kθ − θ t k2 + ξ
2s.t.

L(θ t ; xt , yt ) + (θ − θ t )> ∇L(θ t ; xt , yt ) ≤ ξ,5

ξ ≥ 0.

(13)

The final averaging step in Alg. 1 is an online-to-batch conversion with good generalization guarantees CesaBianchi et al. [2004].

7

This is a Euclidean projection problem (with slack) that admits the closed form solution θ t+1 =θ t − ηt ∇L(θ t ; xt , yt ), withnoL(θ t ;xt ,yt )1, k∇L(θηt = min λm.
(14)2
t ;xt ,yt )kExample: 1-best MIRA. If L is the hinge-loss, we obtain from (9) ∇LSVM (θ t ; xt , yt ) = F(xt )(z̄t −00zt ) = φ(xt , ŷt ) − φ(xt , yt ), where ŷt = argmaxyt0 ∈Y(xt ) θ >t (φ(xt , yt ) − φ(xt , yt )) + `(yt , yt ). The
update becomes θ t+1 = θ t − ηt (φ(xt , ŷt ) − φ(xt , yt )), with1 θ>
(φ(xt , ŷt ) − φ(xt , yt )) + `(ŷt , yt )
, t
.
= min
λm
kφ(xt , ŷt ) − φ(xt , yt )k2
)

(

ηt

(15)

This is precisely the max-loss variant of the 1-best MIRA algorithm [Crammer et al., 2006, §8].
Hence, while MIRA was originally motivated by a conservativeness-correctness tradeoff, it turns
out that it also performs coordinate ascent in the dual.
Example: CRFs. This framework immediately allows us to extend 1-best MIRA for CRFs,
which optimizes the logistic loss. In that case, the exact problem in (12) can be expressed asminθ,ξ λmkθ − θ t k2 + ξ
2− log Pθ (yt |xt ) ≤ ξ,s.t.

ξ ≥ 0.

In words: stay as close as possible to the previous parameter vector, but correct the model sothat the conditional probability Pθ (yt |xt ) becomes large enough. From (9), ∇LCRF (θ t ; xt , yt ) =F(xt )(z̄t − zt ) = Eθt φ(xt , Yt ) − φ(xt , yt ), where now z̄t is an expectation instead of a mode. The
update becomes θ t+1 = θ t − ηt (Eθt φ(xt , Yt ) − φ(xt , yt )), withηt = min>1 θ t (Eθt φ(xt ,Yt )−φ(xt ,yt ))+H(Pθt (.|xt )),λm
kEθt φ(xt ,Yt )−φ(xt ,yt )k2





= min

− log Pθt (yt |xt )1,
λm kEθt φ(xt ,Yt )−φ(xt ,yt )k2



.

(16)

Thus, the difference with respect to standard 1-best MIRA (15) consists of replacing the feature
vector of the loss-augmented mode φ(xt , ŷt ) by the expected feature vector Eθt φ(xt , Yt ) and thecost function `(ŷt , yt ) by the entropy function H(Pθt (.|xt )).
Example: k-best MIRA. Tighter approximations to the problem in (11) can be built by using thevariational representation machinery; see (8) for losses in the family Lβ,γ . Plugging this variational
representation into the constraint in (12) we obtain the following semi-infinite quadratic program:
min
θ,ξ

s.t.

λm
kθ − θ t k2 + ξ2θ ∈ H(z0t ; β, γ),∀z0t ∈ Z(x)(17)ξ ≥ 0.
where H(z0 ; z, β, γ) , {θ | a> θ ≤ b} is a half-space with a = F(x)(z0 − z) and b = ξ − γ(p> z0 +q) − β −1 H(z0 ). The constraint set in (17) is a convex set defined by the intersection of uncountably

8many half-spaces (indexed by the points in the marginal polytope).6 Our approximation consistedof relaxing the problem in (17) by discarding all half-spaces except the one indexed by z̄t , the dual
parameter of the current iterate θ t ; however, tigher relaxations are obtained by keeping some of theother half-spaces. For the hinge loss, rather than just using the mode z̄t , one may rank the k-best
outputs and add a half-space constraint for each. This procedure approximates the constraint set
by a polyhedron and the resulting problem can be addressed using row-action methods, such as
Hildreth’s algorithm [Censor and Zenios, 1997]. This corresponds precisely to k-best MIRA.7

5

Experiments

We report experiments on two tasks: named entity recognition and dependency parsing. For each,
we compare DCA (Alg. 1) with SGD. We report results for several values for the regularization
parameter C = 1/(λm). To choose the learning rate for SGD, we use the formula ηt = η/(1 +(t − 1)/m) [LeCun et al., 1998]. We choose η using dev-set validation after a single epoch [Collins
et al., 2008].
Named Entity Recognition. We use the English data from the CoNLL 2003 shared task [Tjong
Kim Sang and De Meulder, 2003], which consist of English news articles annotated with four
entity types: person, location, organization, and miscellaneous. We used a standard set of featuretemplates, as in [Kazama and Torisawa, 2007], with token shape features [Collins, 2002b] andsimple gazetteer features; a feature was included iff it occurs at least once in the training set (total
1,312,255 features). The task is evaluated using the F1 measure computed at the granularity ofentire entities. We set β = 1 and γ = 0 (the CRF case). In addition to SGD, we also compare with
L-BFGS [Liu and Nocedal, 1989], a common choice for optimizing conditional log-likelihood.
We used {10a , a = −3, . . . , 2} for the set of values considered for η in SGD. Fig. 3 shows that
DCA (which only requires tuning one hyperparameter) reaches better-performing models than thebaselines.
Dependency Parsing. We trained non-projective dependency parsers for three languages (Arabic, Danish, and English), using datasets from the CoNLL-X and CoNLL-2008 shared tasks [Buchholz and Marsi, 2006, Surdeanu et al., 2008]. Performance is assessed by the unlabeled attachmentscore (UAS), the fraction of non-punctuation words which were assigned the correct parent. We
adapted TurboParser8 to handle any loss function Lβ,γ via Alg. 1; for decoding, we used the loopy
BP algorithm of Smith and Eisner [2008] (see §3.2). We used the pruning strategy in [Martinset al., 2009] and tried two feature configurations: an arc-factored model, for which decoding isexact, and a model with second-order features (siblings and grandparents) for which it is approximate. The comparison with SGD for the CRF case is shown in Fig. 4. For the arc-factored models,
6Interestingly, when the hinge loss is used, only a finite (albeit exponentially many) of these half-spaces are necessary, those indexed by vertices of the marginal polytope. In this case, the constraint set is polyhedral.
7
The prediction-based variant of 1-best MIRA [Crammer et al., 2006] is also a particular case, where z̄t is theprediction under the current model θ t , rather than the mode of LSVM (θ t , xt , yt ).
8
Available at http://www.ark.cs.cmu.edu/TurboParser.

9

90

Test Set F1

Development Set F1

86

91

89

DCA, C = 10
DCA, C = 1
DCA, C = 0.1
SGD, η = 1, C = 10
SGD, η = 0.1, C = 1
SGD, η = 0.1, C = 0.1
L-BFGS, C = 1

85

84

88
87

0

10

20

30

40

50

83

0

10

No. Iterations

20

30

40

50

No. Iterations

Figure 3: Named entity recognition. Learning curves for DCA (Alg. 1), SGD, and L-BFGS. The
SGD curve for C = 10 is lower than the others because dev-set validation chose a suboptimal valueof η. DCA, by contrast, does not require choosing any hyperparameters other than C. L-BFGS
ultimately converges after 121 iterations to an F1 of 90.53 on the development data and 85.31 on
the test data.
βγ
NER
DEPENDENCYPARSING

BEST C

F1 (%)BEST CUAS (%)

1
0 (CRF)
1.0
85.48
0.1
90.76

1
1
10.0
85.54
0.01
90.95

1
3
1.0
85.65
0.01
91.04

1
5
1.0
85.72
0.01
91.01

3
1
1.0
85.55
0.01
90.94

5
1
1.0
85.48
0.01
90.91

∞
1 (SVM)
1.0
85.41
0.1
90.75

Table 1: Varying β and γ: neither the CRF nor the SVM are optimal. We report only the results forthe best C, chosen from {0.001, 0.01, 0.1, 1} with dev-set validation. For named entity recognition,
we show test set F1 after K = 50 iterations (empty cells will be filled in in the final version).
Dependency parsing experiments used the arc-factored model on English and K = 10.
the learning curve of DCA seems to lead faster to an accurate model. Notice that the plots do notaccount for the fact that SGD requires four extra iterations to choose the learning rate. For thesecond-order models of Danish and English, however, DCA did not perform as well.9
Finally, Table 1 shows results obtained for different settings of β and γ.10 Interestingly, weobserve that the higher scores are obtained for loss functions that are “between” SVMs and CRFs.

6

Conclusion

We presented a general framework for aggressive online learning of structured classifiers by optimizing any loss function in a wide family. The technique does not require a learning rate to be
specified. We derived an efficient technique for evaluating the loss function and its gradient. Exper9

Further analysis showed that for ∼15% of the training instances, loopy BP led to very poor variational approximations of log Z(θ, x), yielding estimates Pθt (yt |xt ) > 1, thus a negative learning rate (see (16)), that we truncate
to zero. Thus, no update occurs for those instances, explaining the slower convergence. A possible way to fix thisproblem is to use techniques that guarantee upper bounds on the log-partition function Wainwright and Jordan [2008].
10
Observe that there are only two degrees of freedom: indeed, (λ, β, γ) and (λ0 , β 0 , γ 0 ) lead to equivalent learning
problems if λ0 = λ/a, β 0 = β/a and γ 0 = aγ for any a > 0, with the solutions related via θ 0 = aθ.

10Figure 4: Learning curves for DCA (Alg. 1) and SGD, the latter with the learning rate η = 0.01
chosen from {0.001, 0.01, 0.1, 1} using the same procedure as before. The instability when training
the second-order models might be due to the fact that inference there is approximate.
iments in named entity recognition and dependency parsing showed that the algorithm converges
to accurate models at least as fast as stochastic gradient descent.

References
Y. Altun, I. Tsochantaridis, and T. Hofmann. Hidden Markov support vector machines. In ICML,
2003.
S. P. Boyd and L. Vandenberghe. Convex optimization. Cambridge University Press, 2004.
S. Buchholz and E. Marsi. CoNLL-X shared task on multilingual dependency parsing. In CoNLL,
2006.
Y. Censor and S. A. Zenios. Parallel Optimization: Theory, Algorithms, and Applications. Oxford
University Press, 1997.
N. Cesa-Bianchi, A. Conconi, and C. Gentile. On the generalization ability of on-line learningalgorithms. IEEE Trans. on Inf. Theory, 50(9):2050–2057, 2004.
M. Collins. Discriminative training methods for hidden Markov models: theory and experimentswith perceptron algorithms. In EMNLP, 2002a.
M. Collins. Ranking algorithms for named-entity extraction: Boosting and the voted perceptron.
In ACL, 2002b.

11

M. Collins, A. Globerson, T. Koo, X. Carreras, and P.L. Bartlett. Exponentiated gradient algorithms
for conditional random fields and max-margin Markov networks. JMLR, 2008.
R. Collobert, F. Sinz, J. Weston, and L. Bottou. Trading convexity for scalability. In ICML, 2006.
K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. Online passive-aggressivealgorithms. JMLR, 7:551–585, 2006.
J. Eisner. Three new probabilistic models for dependency parsing: An exploration. In COLING,
1996.
K. Gimpel and N. A. Smith. Softmax-margin CRFs: Training log-linear models with cost functions. In NAACL, 2010.
S. Kakade and S. Shalev-Shwartz. Mind the duality gap: Logarithmic regret algorithms for online
optimization. In NIPS, 2008.
J. Kazama and K. Torisawa. A new perceptron algorithm for sequence labeling with non-local
features. In Proc. of EMNLP-CoNLL, 2007.
T. Koo, A. Globerson, X. Carreras, and M. Collins. Structured prediction models via the matrixtree theorem. In EMNLP, 2007.
F. R. Kschischang, B. J. Frey, and H. A. Loeliger. Factor graphs and the sum-product algorithm.
IEEE Transactions on information theory, 47(2):498–519, 2001.
S. Kübler, R. McDonald, and J. Nivre. Dependency Parsing. Morgan & Claypool, 2009.
J. Lafferty, A. McCallum, and F. Pereira. Conditional random fields: Probabilistic models forsegmenting and labeling sequence data. In Proc. of ICML, 2001.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document
recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.
D. C. Liu and J. Nocedal. On the limited memory BFGS method for large scale optimization.
Math. Programming, 45:503–528, 1989.
A. F. T. Martins, N. A. Smith, and E. P. Xing. Concise integer linear programming formulations
for dependency parsing. In Proc. of ACL, 2009.
A. F. T. Martins, N. A. Smith, E. P. Xing, P. M. Q. Aguiar, and M. A. T. Figueiredo. Turbo parsers:
Dependency parsing by approximate variational inference. In Proc. of EMNLP, 2010.
A. McCallum, K. Schultz, and S. Singh. Factorie: Probabilistic programming via imperatively
defined factor graphs. In NIPS, 2009.
R. McDonald and G. Satta. On the complexity of non-projective data-driven dependency parsing.
In IWPT, 2007.
12

R. T. McDonald, F. Pereira, K. Ribarov, and J. Hajic. Non-projective dependency parsing using
spanning tree algorithms. In Proc. of HLT-EMNLP, 2005.
S. Shalev-Shwartz and Y. Singer. Online learning meets optimization in the dual. In COLT, 2006.
D. A. Smith and J. Eisner. Minimum risk annealing for training log-linear models. In ACL, 2006.
D. A. Smith and J. Eisner. Dependency parsing by belief propagation. In EMNLP, 2008.
D. A. Smith and N. A. Smith. Probabilistic models of nonprojective dependency trees. In EMNLP,
2007.
M. Surdeanu, R. Johansson, A. Meyers, L. Màrquez, and J. Nivre. The CoNLL-2008 shared task
on joint parsing of syntactic and semantic dependencies. Proc. of CoNLL, 2008.
B. Taskar, C. Guestrin, and D. Koller. Max-margin Markov networks. In NIPS, 2003.
B. Taskar, S. Lacoste-Julien, and M. I. Jordan. Structured prediction, dual extragradient and Bregman projections. JMLR, 7:1627–1653, 2006.
E. F. Tjong Kim Sang and F. De Meulder. Introduction to the CoNLL-2003 shared task: Languageindependent named entity recognition. In Proc. of CoNLL, 2003.
I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun. Support vector machine learning forinterdependent and structured output spaces. In Proc. of ICML, 2004.
M. J. Wainwright and M. I. Jordan. Graphical Models, Exponential Families, and Variational
Inference. Now Publishers, 2008.

13

A

Background on Convex Analysis

We briefly review some notions of convex analysis that are used throughout the paper. For moreP
details, see e.g. Boyd and Vandenberghe [2004]. Below, ∆d , {µ ∈ Rd | dj=1 µj = 1, µj ≥0 ∀j} is the probability simplex in Rd , and Bγ (x) = {y ∈ Rd | ky − xk ≤ γ} is the ball withradius γ centered at x.
A set C ⊆ Rd is convex if µx + (1 − µ)y ∈ C for all x, y ∈ C and µ ∈ [0, 1]. The convex hullof a set X ⊆ Rd is the set of all convex combinations of the elements of X ,conv X =

( p
X

)
p

µi xi µ ∈ ∆ , p ≥ 1 ;i=1

it is also the smallest convex set that contains X . The affine hull of X ⊆ Rd is the set of all affine
combinations of the elements of X ,pX

aff X = pXµi x i

i=1

j=1




µj = 1, p ≥ 1 ;it is also the smallest affine set that contains X . The relative interior of X is its interior relative tothe affine hull X ,relint X = {x ∈ X | ∃γ > 0 : Bγ (x) ∩ aff X ⊆ X }.
Let R̄ , R ∪ {+∞} be the extended reals. The effective domain of a function f : Rd → R̄ is
the set dom f = {x ∈ Rd | f (x) < +∞}. f is proper if dom f 6= ∅. The epigraph of f is the set
epif , {(x, t) ∈ Rd × R | f (x) ≤ t}. f is lower semicontinuous (lsc) if the epigraph is closed in
Rd ×R. f is convex if dom f is a convex set andf (µx + (1 − µ)y) ≤ µf (x) + (1 − µ)f (y),∀x, y ∈ dom f,µ ∈ [0, 1].

The (Fenchel) conjugate of f is the function f ? : Rd → R̄ defined asf ? (y) = sup x> y − f (x).
x∈Rdf ? is always convex, since it is the supremum of a family of affine functions. Some examples
follow:• If f is an affine function, f (x) = a> x + b, then f ? (y) = −b if y = a and −∞ otherwise.
• If f is the `p -norm, f (x) = kxkp , then f ? is the indicator of the unit ball induced by the dual
norm, f ? (y) = 0 if kykq ≤ 1 and +∞ otherwise, with p−1 + q −1 = 1.
• If f is half of the squared `p -norm, f (x) = kxk2p /2, then f ? is half of the squared dual norm,f ? (y) = kyk2q /2, with p−1 + q −1 = 1.
• If f is convex, lsc, and proper, then f ?? = f .
?
• If g(x) = tf (x − x0 ), with t ∈ R+ and x0 ∈ Rd , then g ? (y) = x>
0 y + tf (y/t).

14

B

Proof of Proposition 3

From (10),max
Dt+1 (µ1 , . . . , µt−1 , µ)
µ
2

=
=
=(i)
=(ii)
=
=(iii)

t−1
t−1
X
1 X
?
−
L
(µ;
x
,
y
)
−
L? (µi ; xi , yi )
max
−
µ
+
µ
t t
µ
2λm i=1 i
i=1
1
max −
k−λmθ t + µk2 − L? (µ; xt , yt ) + constantµ2λm
1k−λmθ t + µk2 − max(µ> θ − L(θ; xt , yt )) + constant
max
−
µ
θ
2λm
1
k−λmθ t + µk2 − µ> θ + L(θ; xt , yt ) + constant
min max
−
µ
θ
2λm


1
2
>
min maxµ (−θ) −kµ − λmθ t k + L(θ; xt , yt ) + constant
µ
θ
2λm
λm
kθ − θ t k2 + L(θ; xt , yt ) + constant,
min
θ
2

(18)

where in (i) we invoked the definition of convex conjugate; in (ii) we interchange min and max
since strong duality holds (as stated in [Kakade and Shalev-Shwartz, 2008], a sufficient conditionis that R is strongly convex, L is convex and dom L is polyhedral); and in (iii) we used the facts that?
R(θ) = kθk2 /2 is conjugate of itself, and that g(x) = tf (x−x0 ) implies g ? (y) = x>0 y+tf (y/t).

15