Structured Sparsity in Structured Prediction
André F. T. Martins∗† Noah A. Smith∗ Pedro M. Q. Aguiar‡ Mário A. T. Figueiredo†∗
School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA‡
Instituto de Sistemas e Robótica, Instituto Superior Técnico, Lisboa, Portugal†
Instituto de Telecomunicações, Instituto Superior Técnico, Lisboa, Portugal{afm,nasmith}@cs.cmu.edu, aguiar@isr.ist.utl.pt, mtf@lx.it.pt

Abstract
Linear models have enjoyed great success in
structured prediction in NLP. While a lot ofprogress has been made on efficient training with several loss functions, the problem
of endowing learners with a mechanism forfeature selection is still unsolved. Common
approaches employ ad hoc filtering or L1 regularization; both ignore the structure of thefeature space, preventing practicioners fromencoding structural prior knowledge. We fillthis gap by adopting regularizers that promote
structured sparsity, along with efficient algorithms to handle them. Experiments on threetasks (chunking, entity recognition, and dependency parsing) show gains in performance,compactness, and model interpretability.

1

Introduction

Models for structured outputs are in demand acrossnatural language processing, with applications in information extraction, parsing, and machine translation. State-of-the-art models usually involve linear
combinations of features and are trained discriminatively; examples are conditional random fields(Lafferty et al., 2001), structured support vector
machines (Altun et al., 2003; Taskar et al., 2003;
Tsochantaridis et al., 2004), and the structured perceptron (Collins, 2002a). In all these cases, the underlying optimization problems differ only in the
choice of loss function; choosing among them has
usually a small impact on predictive performance.
In this paper, we are concerned with model selection: which features should be used to define theprediction score? The fact that models with few
features (“sparse” models) are desirable for several

reasons (compactness, interpretability, good generalization) has stimulated much research work whichhas produced a wide variety of methods (Della Pietra
et al., 1997; Guyon and Elisseeff, 2003; McCallum,2003). Our focus is on methods which embed thisselection into the learning problem via the regularization term. We depart from previous approaches
in that we seek to make decisions jointly about all
candidate features, and we want to promote sparsity
patterns that go beyond the mere cardinality of theset of features. For example, we want to be able toselect entire feature templates (rather than featuresindividually), or to make the inclusion of some features depend on the inclusion of other features.
We achieve the goal stated above by employing regularizers which promote structured sparsity.
Such regularizers are able to encode prior knowledge and guide the selection of features by modeling the structure of the feature space. Lately, thistype of regularizers has received a lot of attention
in computer vision, signal processing, and computational biology (Zhao et al., 2009; Kim and Xing,
2010; Jenatton et al., 2009; Obozinski et al., 2010;
Jenatton et al., 2010; Bach et al., 2011). Eisenstein
et al. (2011) employed structured sparsity in computational sociolinguistics. However, none of theseworks have addressed structured prediction. Here,we combine these two levels of structure: structure in the output space, and structure in the feature
space. The result is a framework that allows building structured predictors with high predictive power,
while reducing manual feature engineering. We obtain models that are interpretable, accurate, and often much more compact than L2 -regularized ones.
Compared with L1 -regularized models, ours are often more accurate and yield faster runtime.

2

Structured Prediction

We address structured prediction problems, which
involve an input set X (e.g., sentences) and an output set Y, assumed large and structured (e.g., tags orparse trees). We assume that each x ∈ X has a setof candidate outputs Y(x) ⊆ Y. We consider linear
models, in which predictions are made according to
yb = arg maxy∈Y(x) θ · φ(x, y),where Ω is a regularizer and L is a loss function.
Examples of losses are: the negative conditional loglikelihood used in CRFs (Lafferty et al., 2001),(3)

where Pθ (y|x) ∝ exp(θ · φ(x, y)) is a log-linear
model; the margin rescaled loss of structured SVMs
(Taskar et al., 2003; Tsochantaridis et al., 2004),
LSVM (θ, x, y) = max θ · δφ(y 0 ) + c(y 0 , y), (4)y 0 ∈Y(x)where δφ(y 0 ) = φ(x, y 0 ) − φ(x, y); and the loss underlying the structured perceptron (Collins, 2002a),
LSP (θ, x, y) = maxy0 ∈Y(x) θ · δφ(y 0 ).

• L2 -regularization (Chen and Rosenfeld, 2000):2ΩL
λ (θ) ,

(1)

where φ(x, y) ∈ RD is a vector of features, and θ ∈RD is the vector of corresponding weights. Let D ={hxi , yi i}N
i=1 be a training sample. We assume a costfunction is defined such that c(by , y) is the cost ofpredicting yb when the true output is y; our goal is tolearn θ with small expected cost on unseen data. To
achieve this goal, linear models are usually trainedby solving a problem of the formb = arg minθ Ω(θ) + 1 PN L(θ, xi , yi ), (2)θ
i=1N

LCRF (θ, x, y) = − log Pθ (y|x),

computational biology (Jenatton et al., 2009; Liuand Ye, 2010; Bach et al., 2011), it has not yet received much attention in the NLP community, where
the choice of regularization for supervised learning
has essentially been limited to the following:(5)

Empirical comparison among these loss functions
can be found in the literature (see, e.g., Martins et al.,2010, who also consider interpolations of the losses
above). In practice, it has been observed that the
choice of loss has far less impact than the model design and choice of features. Hence, in this paper,
we focus our attention on the regularization term in
Eq. 2. We specifically address ways in which thisterm can be used to help design the model by promoting structured sparsity. While this has been a
topic of intense research in signal processing andλ2
2 kθk2=λ PD
2d=1 θd ;2(6)• L1 -regularization (Kazama and Tsujii, 2003;
Goodman, 2004):1ΩLτ (θ) , τ kθk1 = τPD

d=1 |θd |.

(7)

The latter is known as “Lasso,” as popularized by
Tibshirani (1996) in the context of sparse regression. In the two cases above, λ and τ are nonnegative coefficients controlling the intensity of the reg2
ularization. ΩLλ usually leads to easier optimization1and robust performance; ΩLτ encourages sparser
models, where only a few features receive nonzero
weights; see Gao et al. (2007) for an empirical comparison. More recently, Petrov and Klein (2008b)
applied L1 regularization for structure learning inphrase-based parsing; a comparison with L2 appears
in Petrov and Klein (2008a). Elastic nets interpolate
between L1 and L2 , having been proposed by Zou
and Hastie (2005) and used by Lavergne et al. (2010)
to regularize CRFs.
Neither of the regularizers just described “looks”
at the structure of the feature space, since they alltreat each dimension independently—we call them
unstructured regularizers, as opposed to the structured ones that we next describe.

3

Structured Sparsity

1
We are interested in regularizers that share with ΩLτthe ability to promote sparsity, so that they can beused for selecting features. In addition, we want toendow the feature space RD with additional structure, so that features are not penalized individually(as in the L1 -case) but collectively, encouraging entire groups of features to be discarded. The choice ofgroups will allow encoding prior knowledge regarding the kind of sparsity patterns that are intended in
the model. This can be achieved with group-Lasso
regularization, which we next describe.

3.1

The Group Lasso

To capture the structure of the feature space, wegroup our D features into M groups G1 , . . . , GM ,where each Gm ⊆ {1, . . . , D}. Ahead, we discuss meaningful ways of choosing group decompositions; for now, let us assume a sensible choice isobvious to the model designer. Denote by θ m =hθd id∈Gm the subvector of those weights that correspond to the features in the m-th group, and let
d1 , . . . , dM be nonnegative scalars (one per group).
We consider the following group-Lasso regularizers:
PM
(8)
ΩGL
m=1 dm kθ m k2 .
d =These regularizers were first proposed by Bakin(1999) and Yuan and Lin (2006) in the context of regression. If d1 = . . . = dM , ΩGLd becomes the “L1norm of the L2 norms.” Interestingly, this is also
a norm, called the mixed L2,1 -norm.1 These regularizers subsume the L1 and L2 cases, which correspond to trivial choices of groups:• If each group is a singleton, i.e., M = D and
Gd = {θd }, and d1 = . . . = dM = τ , we recoverL1 -regularization (cf. Eqs. 7–8).
• If there is a single group spanning all the features,i.e., M = 1 and G1 = {1, . . . , D}, then the righthand side of Eq. 8 becomes d1 kθk2 . This is equivalent to L2 regularization.2
We next present some non-trivial examples concerning different topologies of G = {G1 , . . . , GM }.
Non-overlapping groups. Let us first consider
the case where G is a partition of the
S featurespace: the groups cover all the features ( m Gm ={1, . . . , D}), and they do not overlap (Ga ∩Gb = ∅,∀a 6= b). Then, ΩGLd is termed a non-overlappinggroup-Lasso regularizer. It encourages sparsity patterns in which entire groups are discarded. A judicious choice of groups can lead to very compact
1

In the statistics literature, such mixed-norm regularizers,
which group features and then apply a separate norm for eachgroup, are called composite absolute penalties (Zhao et al.,2009); other norms besides L2,1 can be used, such as L∞,1
(Quattoni et al., 2009; Wright et al., 2009; Eisenstein et al.,2011).
2
Note that Eqs. 8 and 6 do not become exactly the same: in
Eq. 6, the L2 norm is squared. However it can be shown thatboth regularizers lead to identical learning problems (Eq. 2) up
to a transformation of the regularization constant.

models and pinpoint relevant groups of features.
The following examples lie in this category:• The two cases above (L1 and L2 regularization).
• Label-based groups. In multi-label classification,
where Y = {1, . . . , L}, features are typically designed as conjunctions of input features with label indicators, i.e., they take the form φ(x, y) =ψ(x) ⊗ ey , where ψ(x) ∈ RDX , ey ∈ RL has all
entries zero except the y-th entry, which is 1, and⊗ denotes the Kronecker product. Hence φ(x, y)
can be reshaped as a DX -by-L matrix, and we canlet each group correspond to a row. In this case,all groups have the same size and we typically set
d1 = . . . = dM . A similar design can be madefor sequence labeling problems, by considering asimilar grouping for the unigram features.3• Template-based groups. In NLP, features are commonly designed via templates. For example, atemplate such as w0 ∧ p0 ∧ p−1 denotes the wordin the current position (w0 ) conjoined with its
part-of-speech (p0 ) and that of the previous word
(p−1 ). This template encloses many features corresponding to different instantiantions of w0 , p0 ,and p−1 . In §5, we learn feature templates fromthe data, by associating each group to a featuretemplate, and letting that group contain all features that are instantiations of this template. Sincegroups have different sizes, it is a good idea tolet dm increase with the group size, so that larger
groups pay a larger penalty for being included.
Tree-structured groups. More generally, we may
let the groups in G overlap but be nested, i.e., we may
want them to form a hierarchy (two distinct groups
either have empty intersection or one is contained in
the other). This induces a partial order on G (the set
inclusion relation ⊇), endowing it with the structureof a partially ordered set (poset).
A convenient graphical representation of the posethG, ⊇i is its Hasse diagram. Each group is a nodein the diagram, and an arc is drawn from group Ga
to group Gb if Gb ⊂ Ga and there is no b0 s.t.
Gb ⊂ Gb0 ⊂ Ga . When the groups are nested, thisdiagram is a forest (a union of directed trees). The
corresponding regularizer enforces sparsity patterns
3

The same idea is also used in multitask learning, wherelabels correspond to tasks (Caruana, 1997).

where a group of features is only selected if all its
ancestors are also selected.4 Hence, entire subtrees
in the diagram can be pruned away. Examples are:see Fig. 1). The result is a “coarse-to-fine” regularizer, which prefers to select feature templates thatare coarser before zooming into finer features.

• The elastic net. The diagram of G has a root nodefor G1 = {1, . . . , D} and D leaf nodes, one pereach singleton group (see Fig. 1).

3.2• The sparse group-Lasso. This regularizer was
proposed by Friedman et al. (2010):ΩSGLd,τ (θ) =PM 0

m=1 (dm kθ m k2 + τm kθ m k1 ) ,(9)where the total number of groups is M = M 0 +D, and the components θ 1 , . . . , θ M 0 are nonoverlapping. This regularizer promotes sparsity
at both group and feature levels (i.e., it eliminates
entire groups and sparsifies within each group).
Graph-structured groups. In general, the groups
in G may overlap without being nested. In this case,the Hasse diagram of G is a directed acyclic graph(DAG). As in the tree-structured case, a group offeatures is only selected if all its ancestors are also
selected. Based on this property, Jenatton et al.
(2009) suggested a way of reverse engineering thegroups from the desired sparsity pattern. We next
describe a strategy for coarse-to-fine feature template selection that directly builds on that idea.
Suppose that we are given M feature templates
T = {T1 , . . . , TM } which are partially ordered according to some criterion, such that if Ta  Tb wewould like to include Tb in our model only if Ta
is also included. This criterion could be a measureof coarseness: we may want to let coarser part-ofspeech features precede finer lexical features, e.g.,p0 ∧ p1  w0 ∧ w1 , or conjoined features come after their elementary parts, e.g., p0  p0 ∧ p1 . The
order does not need to be total, so some templates
may not be comparable (e.g., we may want p0 ∧ p−1
and p0 ∧ p1 not to be comparable). To achieve
the sparsity pattern encoded in hT, i, we choose
G = hG1 , . . . , GM i as follows: let I(Ta ) be theset of features that S
are instantiations of template Ta ;then define Ga = b:ab I(Tb ), for a = 1, . . . , M .
It is easy to see that hG, ⊇i and hT, i are isomorph
posets (their Hasse diagrams have the same shape;
4

We say that a group of features Gm is selected if some feature in Gm (but not necessarily all) has a nonzero weight.

Bayesian Interpretation

The prior knowledge encoded in the group-Lasso
regularizer (Eq. 8) comes with a Bayesian interpretation, as we next describe. In a probabilistic
model (e.g. in the CRF case, where L = LCRF ),the optimization problem in Eq. 2 can be seen as
maximum a posteriori estimation of θ, where theregularization term Ω(θ) corresponds to the negative log of a prior distribution (call it p(θ)). It
is well-known that L2 -regularization corresponds tochoosing independent zero-mean Gaussian priors,θd ∼ N(0, λ−1 ), and that L1 -regularization resultsfrom adopting zero-mean Laplacian priors, p(θd ) ∝exp(τ |θd |).
Figueiredo (2002) provided an alternative interpretation of L1 -regularization in terms of a twolevel hierarchical Bayes model, which happens togeneralize to the non-overlapping group-Lasso case,where Ω = ΩGL
d . As in the L2 -case, we also assume
that each parameter receives a zero-mean Gaussianprior, but now with a group-specific variance τm ,i.e., θ m ∼ N(0, τm I) for m = 1, . . . , M . This
reflects the fact that some groups should have theirfeature weights shrunk more towards zero than others. The variances τm ≥ 0 are not pre-specified but
rather generated by a one-sided exponential hyperprior p(τm |dm ) ∝ exp(−d2m τm /2). It can be shownthat after marginalizing out τm , we obtain
Z ∞p(θ m |dm ) =p(θ m |τm )p(τm |dm )dτm0

∝ exp (−dm kθ m k) .

(10)

Hence, the non-overlapping group-Lasso corresponds to the following two-level hierachical Bayesmodel: independently for each m = 1, . . . , M ,τm ∼ Exp(d2m /2),
3.3

θ m ∼ N(0, τm I).

(11)

Prox-operators

Before introducing our learning algorithm for handling group-Lasso regularization, we need to define
the concept of a Ω-proximity operator. This is thefunction proxΩ : RD → RD defined as follows:proxΩ (θ) = arg minθ0 12 kθ 0 − θk2 + Ω(θ 0 ). (12)Figure 1: Hasse diagrams of several groupbased regularizers. For all tree-structured
cases, we use the same plate notation thatis traditionally used in probabilistic graphicalmodels. The rightmost diagram represents acoarse-to-fine regularizer: each node is a template involving contiguous sequences of words(w) and POS tags (p); the symbol order ∅ 
p  w induces a template order (Ta  Tb
iff at each position i [Ta ]i  [Tb ]i ). Digits
below each node are the group indices where
each template belongs.

Proximity operators generalize Euclidean projections and have many interesting properties; see Bachet al. (2011) for an overview. By requiring zero to bea subgradient of the objective function in Eq. 12, we
obtain the following closed expression (called softthresholding) for the ΩτL1 -proximity operator: θd − τ if θd > τ0
if |θd | ≤ τ(13)[proxΩL1 (θ)]d =τθd + τ if θd < −τ .
For the non-overlapping group Lasso case, the proximity operator is given by(0
if kθ m k2 ≤ dm[proxΩGL (θ)]m =kθ m k2 −dmdkθ m k2 θ m otherwise.
(14)
which can be seen as a generalization of Eq. 13: if
the L2 -norm of the m-th group is less than dm , theentire group is discarded; otherwise it is scaled sothat its L2 -norm decreases by an amount of dm .
When groups overlap, the proximity operator
lacks a closed form. When G is tree-structured, it
can still be efficiently computed by a recursive procedure (Jenatton et al., 2010). When G is not treestructured, no specialized procedure is known, and aconvex optimizer is necessary to solve Eq. 12.

4

Online Prox-Grad Algorithm

We now turn our attention to efficient ways of handling group-Lasso regularizers. Several fast andscalable algorithms having been proposed for training L1 -regularized CRFs, based on quasi-Newton
optimization (Andrew and Gao, 2007), coordinate
descent (Sokolovska et al., 2010; Lavergne et al.,2010), and stochastic gradients (Carpenter, 2008;

Langford et al., 2009; Tsuruoka et al., 2009). The
algorithm that we use in this paper (Alg. 1) extends
the stochastic gradient methods for group-Lasso regularization; a similar algorithm was used by Martinset al. (2011) for multiple kernel learning.
Alg. 1 addresses the learning problem in Eq. 2 byalternating between online (sub-)gradient steps withrespect to the loss term, and proximal steps withrespect to the regularizer. Proximal-gradient methods are very popular in sparse modeling, both inbatch (Liu and Ye, 2010; Bach et al., 2011) and online (Duchi and Singer, 2009; Xiao, 2009) settings.
The reason we have chosen the algorithm of Martinset al. (2011) is that it effectively handles overlapping groups, without the need of evaluating proxΩ(which, as seen in §3.3, can be costly if G is not treestructured). To do so, it decomposes Ω asΩ(θ) =PJ

j=1 σj Ωj (θ)(15)

for some J ≥ 1, and nonnegative σ1 , . . . , σJ ; eachΩj -proximal operator is assumed easy to compute.
Such a decomposition always exists: if G does nothave overlapping groups, take J = 1. Otherwise,find
SJ J ≤ M disjoint sets G1 , . . . , GJ such thatj=1 Gj = G and the groups on each Gj are nonoverlapping. The proximal steps are then applied
sequentially, one per each Ωj . Overall, Alg. 1 satisfies the following important requirements:• Computational efficiency. Each gradient step atround t is linear in the number of features thatfire for that instance and independent of the total
number of features D. Each proximal step is linear in the number of groups M , and does not need
be to performed every round (as we will see later).

Algorithm 1 Online Sparse Prox-Grad AlgorithmD,T , gravity sequence
hhσjt iJj=1 iTt=1 , stepsize sequence hηt iTt=1
2: initialize θ = 0
3: for t = 1 to T do
4:take training pair hxt , yt i ∈ D
5:θ ← θ − ηt ∇L(θ; xt , yt ) (gradient step)
6:
for j = 1 to J do7:
θ = proxηt σjt Ωj (θ) (proximal step)
8:
end for
9: end for
10: output: θ
1: input:hΩj iJj=1 ,• Memory efficiency. Only a small active set of features (those that have nonzero weights) need tobe maintained. Entire groups of features can bedeleted after each proximal step. Furthermore,
only the features which correspond to nonzero entries in the gradient vector need to be inserted in
the active set; for some losses (LSVM and LSP )many irrelevant features are never instantianted.
• Convergence. With high probability, Alg. 1 produces an -accurate solution after T ≤ O(1/2 )rounds, for a suitable choice of stepsizes and holding σjt constant, σjt = σj (Martins et al., 2011).
This result can be generalized
to any sequence
1 PTThσjt it=1 such that σj = T t=1 σjt .
We next describe several algorithmic ingredientsthat make Alg. 1 effective in sparse modeling.
Budget-Driven Shrinkage. Alg. 1 requires the
choice of a “gravity sequence.” We follow Langford et al. (2009) and set hσjt iJj=1 to zero for all twhich is not a multiple of some prespecified integer
K; this way, proximal steps need only be performed
each K rounds, yielding a significant speed-up when
the number of groups M is large. A direct adoption of the method of Langford et al. (2009) wouldset σjt = Kσj for those rounds; however, we haveobserved that such a strategy makes the number ofgroups vary substantially in early epochs. We use a
different strategy: for each Gj , we specify a budgetof Bj ≥ 0 groups (this may take into consideration
practical limitations, such as the available memory).
If t is a multiple of K, we set σjt as follows:
1. If Gj does not have more than Bj nonzerogroups, set σjt = 0 and do nothing.

2. Otherwise, sort the groups in Gj by decreasingorder of their L2 -norms. Check the L2 -normsof the Bj -th and Bj+1 -th entries in the list andset σjt as the mean of these two divided by ηt .
3. Apply a ηt σjt Ωj -proximal step using Eq. 14.
At the end of this step, no more than Bj groups
will remain nonzero.5
If the averageof the gravity steps converge,
1 PT
limT →∞ T t=1 σjt → σj , then the limit points
σj implicitly define the regularizer, via Ω =PJ
6
j=1 σj Ωj . Hence, we have shifted the control of
the amount of regularization to the budget constants
Bj , which unlike the σj have a clear meaning andcan be chosen under practical considerations.
Space and Time Efficiency. The proximal steps
in Alg. 1 have a scaling effect on each group, which
affects all features belonging to that group (seeEq. 14). We want to avoid explicitly updating eachfeature in the active set, which could be time consuming. We mention two strategies that can be used
for the non-overlapping group Lasso case.
• The first strategy is suitable when M is large andonly a few groups ( M ) have features that firein each round; this is the case, e.g., of label-based
groups (see §3.1). It consists of making lazy updates (Carpenter, 2008), i.e., to delay the updateof all features in a group until at least one ofthem fires; then apply a cumulative penalty. The
amount of the penalty can be computed if one assigns a timestamp to each group.
• The second strategy is suitable when M is smalland some groups are very populated; this is the
typical case of template-based groups (§3.1). Two
operations need to be performed: updating eachfeature weight (in the gradient steps), and scaling
entire groups (in the proximal steps). We adapt
a trick due to Shalev-Shwartz et al. (2007): represent the weight vector of the m-th group, θ m , by a5

When overlaps exist (e.g. the coarse-to-fine case), we specify a total pseudo-budget B ignoring the overlaps, which induces budgets B1 , . . . , BJ which sum to B. The number ofactually selected groups may be less than B, however, since inthis case some groups can be shrunk more than once. Other
heuristics are possible.
6
The convergence assumption can be sidestepped by freezing the σj after a fixed number of iterations.

triple hξ m , cm , ρm i ∈ R|Gm | ×R+ ×R+ , such thatθ m = cm ξ m and kθ m k2 = ρm . This representation allows performing the two operations abovein constant time, and it keeps track of the group
L2 -norms, necessary in the proximal updates.
For sufficient amounts of regularization, our algorithm has a low memory footprint. Only features
that, at some point, intervene in the gradient computed in line 5 need to be instantiated; and all features that receive zero weights after some proximal
step can be deleted from the model (cf. Fig. 2).
Sparseptron and Debiasing. Although Alg. 1 allows to simultaneously select features and learn themodel parameters, it has been observed in the sparsemodeling literature that Lasso-like regularizers usually have a strong bias which may harm predictive
performance. A post-processing stage is usuallytaken (called debiasing), in which the model is refitted without any regularization and using only theselected features (Wright et al., 2009). If a final debiasing stage is to be performed, Alg. 1 only needs
to worry about feature selection, hence it is appealing to choose a loss function that makes this procedure as simple as possible. Examining the inputof Alg. 1, we see that both a gravity and a stepsizesequence need to be specified. The former can betaken care of by using budget-driven shrinkage, as
described above.
p The stepsize sequence can be set
as ηt = η0 / dt/N e, which ensures convergence,
however η0 requires tuning. Fortunately, for the
structured perceptron loss LSP (Eq. 5), Alg. 1 is independent of η0 , up to a scaling of θ, which does notaffect predictions (see Eq. 1).7 We call the instantiation of Alg. 1 with a group-Lasso regularizer andthe loss LSP the sparseptron. Overall, we propose
the following two-stage approach:
1. Run the sparsepton for a few epochs and discard the features with zero weights.
2. Refit the model without any regularization andusing the loss L which one wants to optimize.
7

To see why this is the case, note that both gradient andproximal updates come scaled by η0 ; and that the gradient of
the loss is ∇LSP (θ, xt , yt ) = φ(xt , ybt ) − φ(xt , yt ), where ybt
is the prediction under the current model, which is insensitive tothe scaling of θ. This independence on η0 does not hold when
the loss is LSVM or LCRF .

5

Experiments

We present experiments in three structured prediction tasks for several group choices.
Text Chunking. We use the English dataset provided in the CoNLL 2000 shared task (Sang andBuchholz, 2000), which consists of 8,936 training
and 2,012 testing sentences (sections 15–18 and 20of the WSJ.) The input observations are the token
words and their POS tags; we want to predict thesequences of IOB tags representing phrase chunks.
We built 96 contextual feature templates as follows:• Up to 5-grams of POS tags, in windows of 5 tokens on the left and 5 tokens on the right;• Up to 3-grams of words, in windows of 3 tokens
on the left and 3 tokens on the right;• Up to 2-grams of word shapes, in windows of
2 tokens on the left and 2 tokens on the right.
Each shape replaces characters by their types(case sensitive letters, digits, and punctuation),and deletes repeated types—e.g., Confidence
and 2,664,098 are respectively mapped to Aa
and 0,0+,0+ (Collins, 2002b).
We defined unigram features by conjoining thesetemplates with each of the 22 output labels. An additional template was defined to account for label
bigrams—features in this template do not look at the
input string, but only at consecutive pairs of labels.8
We evaluate the ability of group-Lasso regularization to perform feature template selection. To
do that, we ran 5 epochs of the sparseptron algorithm with template-based groups and budget-driven
shrinkage (budgets of 10, 20, 30, 40, and 50 templates were tried). For each group Gm , we set dm =log2 |Gm |, which is the average number of bits necessary to encode a feature in that group, if all features were equiprobable. We set K = 1000 (thenumber of instances between consecutive proximal
steps). Then, we refit the model with 10 iterationsof the max-loss 1-best MIRA algorithm (Crammer
et al., 2006).9 Table 1 compares the F1 scores and8State-of-the-art models use larger output contexts, such aslabel trigrams and 4-grams. We resort to bigram labels as weare mostly interested in identifying relevant unigram templates.
9
This variant optimizes the LSVM loss (Martins et al., 2010).
For the refitting, we used unregularized MIRA. For the baseline

Table 1: Results fortext chunking.

Spa. dev/test
Dut. dev/test
Eng. dev/test

MIRA
93.10
5,300,396

F1 (%)
model size (# features)

MIRA
70.38/74.09
8,598,246
69.15/71.54
5,727,004
83.95/79.81
8,376,901

Lasso C = 0.1
69.19/71.9
68,56564.07/66.35
164,960
80.92/76.95
232,865

C = 0.5
70.75/72.38
1,017,769
66.82/69.42
565,704
82.58/78.84
870,587

Group Lasso B = 10
92.99
71,075C=1
71.7/74.03
1,555,683
70.43/71.89
953,668
83.38/79.35
1,114,016

B = 2093.28
158,844

Group-Lasso B = 100
71.79/73.62
83,03669.48/72.83
128,32085.62/80.26
255,165

B = 3093.59
389,065

B = 4093.42
662,018

B = 200
72.08/75.05
354,872
71.03/73.33
447,19385.86/81.47
953,178

B = 5093.40
891,378

B = 300
71.48/73.3
600,646
71.2/72.59
889,660
85.03/80.91
1,719,229

Table 2: Results for named entity recognition. Each cell shows F1 (%) and the number of features.
6# Features

6

x 10

4
MIRA
Sparceptron + MIRA (B=30)

2
0
0

5

10

15

# Epochs

Figure 2: Memory footprints of the MIRA and sparseptron algorithms in text chunking. The oscillation in thefirst 5 epochs (bottom line) comes from the proximal
steps each K = 1000 rounds. The features are thenfrozen and 10 epochs of unregularized MIRA follow.
Overall, the sparseptron requires < 7.5% of the memory
as the MIRA baseline.

the model sizes obtained with the several budgets
against those obtained by running 15 iterations of
MIRA with the original set of features. Note thatthe total number of iterations is the same; yet, thegroup-Lasso approach has a much smaller memory
footprint (see Fig. 2) and yields much more compact models. The small memory footprint comesfrom the fact that Alg. 1 may entertain a large number of features without ever instantiating all of them.
The predictive power is comparable (although somechoices of budget yield slightly better scores for thegroup-Lasso approach).10
Named Entity Recognition. We experiment with
the Spanish, Dutch, and English datasets provided in the CoNLL 2002/2003 shared tasks (Sang,
2002; Sang and De Meulder, 2003). For Spanish, we use the POS tags provided by Car(described next), we used L2 -regularized MIRA and tuned theregularization constant with cross-validation.
10
We also tried label-based group-Lasso and sparse groupLasso (§3.1), with less impressive results (omitted for space).

reras (http://www.lsi.upc.es/˜nlp/tools/
nerc/nerc.html); for English, we ignore the syntactic chunk tags provided with the dataset. Hence,
all datasets have the same sort of input observations(words and POS) and all have 9 output labels. We
use the feature templates described above plus some
additional ones (yielding a total of 452 templates):• Up to 3-grams of shapes, in windows of size 3;• For prefix/suffix sizes of 1, 2, 3, up to 3-grams ofword prefixes/suffixes, in windows of size 3;• Up to 5-grams of case, punctuation, and digit indicators, in windows of size 5.
As before, an additional feature template was defined to account for label bigrams. We do featuretemplate selection (same setting as before) for budget sizes of 100, 200, and 300. We compare withboth MIRA (using all the features) and the sparsep1
tron with a standard Lasso regularizer ΩLτ , for several values of C = 1/(τ N ). Table 2 shows the results. We observe that template-based group-Lasso
wins both in terms of accuracy and compactness.
Note also that the ability to discard feature templates (rather than individual features) yields fastertest runtime than models regularized with the standard Lasso: fewer templates will need to be instantiated, with a speed-up in score computation.
Multilingual Dependency Parsing. We trained
non-projective dependency parsers for 6 languages
using the CoNLL-X shared task datasets (Buchholz
and Marsi, 2006): Arabic, Danish, Dutch, Japanese,
Slovene, and Spanish. We chose the languages withthe smallest datasets, because regularization is more
important when data is scarce. The output to be predicted from each input sentence is the set of dependency links, which jointly define a spanning tree.

DanishArabic

93.5

89.8

78
UAS (%)

Japanese

90

78.5

93

89.6
77.5
89.4

Group−Lasso
Group−Lasso (C2F)
Lasso
Filter−based (IG)

77
76.5
2

4

6
8
10
Number of Features

92.5

89.2
12

89
0

5

10

15

6

92
0

2

4

x 10

8
6

x 10

Slovenex 10

Spanish84

6

6

Turkish

84

76

83.5

75.5

83

75

82.5

74.5

83

82

81
0

2

4

6

8

10

82
0

0.5

1

6

1.5

2

74
0

7

x 10

x 10

5

10

15
6

x 10

Figure 3: Comparison between non-overlapping group-Lasso, coarse-to-fine group-Lasso (C2F), and a filter-based
method based on information gain for selecting feature templates in multilingual dependency parsing. The x-axis is
the total number of features at different regularization levels, and the y-axis is the unlabeled attachment score. The
plots illustrate how accurate the parsers are as a function of the model sparsity achieved, for each method. The standard
Lasso (which does not select templates, but individual features) is also shown for comparison.

We use arc-factored models, for which exact inference is tractable (McDonald et al., 2005). We defined M = 684 feature templates for each candidate arc by conjoining the words, shapes, lemmas,
and POS of the head and the modifier, as well as
the contextual POS, and the distance and directionof attachment. We followed the same two-stage
approach as before, and compared with a baseline
which selects feature templates by ranking them according to the information gain criterion. This baseline assigns a score to each template Tm which reflects an empirical estimate of the mutual information between Tm and the binary variable A that indicates the presence/absence of a dependency link:
IGm ,

X

X

f ∈Tm a∈{0,1}

P (f, a) log2

P (f, a),P (f )P (a)(16)

where P (f, a) is the joint probability of feature ffiring and an arc being active (a = 1) or innactive(a = 0), and P (f ) and P (a) are the corresponding
marginals. All probabilities are estimated from theempirical counts of events observed in the data.

The results are plotted in Fig. 3, for budget sizesof 200, 300, and 400. We observe that for all
but one language (Spanish is the exception), nonoverlapping group-Lasso regularization is more effective at selecting feature templates than the information gain criterion, and slightly better thancoarse-to-fine group-Lasso. For completeness, we
also display the results obtained with a standard
Lasso regularizer. Table 3 shows what kind offeature templates were most selected for each language. Some interesting patterns can be observed:
morphologically-rich languages with small datasets(such as Turkish and Slovene) seem to avoid lexical features, arguably due to potential for overfitting;in Japanese, contextual POS appear to be speciallyrelevant. It should be noted, however, that someof these patterns may be properties of the datasets
rather than of the languages themselves.

6

Related WorkA variant of the online proximal gradient algorithm
used in this paper was proposed by Martins et al.

Bilexical
Lex. → POS
POS → Lex.
POS → POS
Middle POS
Shape
Direction
Distance

Ara.
++
+
++
++
++
++

Dan.
+
+
++
++
+
+

Jap.

Slo.

+
+
++
++
++
+
+

+
++
++
+
+

Spa.
+

Tur.

+

+

++

++

+
+

+
+

Table 3: Variation of feature templates that were selected
accross languages. Each line groups together similar templates, involving lexical, contextual POS, word shape information, as well as attachment direction and length.
Empty cells denote that very few or none of the templates
in that category was selected; + denotes that some wereselected; ++ denotes that most or all were selected.

(2011), along with a theoretical analysis. The focus there, however, was multiple kernel learning,
hence overlapping groups were not considered intheir experiments. Budget-driven shrinkage and thesparseptron are novel techniques, at the best of ourknowledge. Apart from Martins et al. (2011), theonly work we are aware of which combines structured sparsity with structured prediction is Schmidt
and Murphy (2010); however, their goal is to predict the structure of graphical models, while weare mostly interested in the structure of the feature
space. Schmidt and Murphy (2010) used to generative models, while our approach emphasizes discriminative learning.
Mixed norm regularization has been used for awhile in statistics as a means to promote structured
sparsity. Group Lasso is due to Bakin (1999) andYuan and Lin (2006), after which a string of variants
and algorithms appeared (Bach, 2008; Zhao et al.,2009; Jenatton et al., 2009; Friedman et al., 2010;
Obozinski et al., 2010). The flat (non-overlapping)case has tight links with learning formalisms suchas multiple kernel learning (Lanckriet et al., 2004)
and multi-task learning (Caruana, 1997). The treestructured case has been addressed by Kim and Xing
(2010), Liu and Ye (2010) and Mairal et al. (2010),
along with L∞,1 and L2,1 regularization. Graphstructured groups are discussed in Jenatton et al.
(2010), along with a DAG representation. In NLP,
mixed norms have been used recently by Graça et al.
(2009) in posterior regularization, and by Eisenstein
et al. (2011) in a multi-task regression problem.

7

Conclusions

In this paper, we have explored two levels of structure in NLP problems: structure on the outputs, andstructure on the feature space. We have shown how
the latter can be useful in model design, through theuse of regularizers which promote structured sparsity. We propose an online algorithm with minimal memory requirements for exploring large feature spaces. Our algorithm, which specializes into
the sparseptron, yields a mechanism for selecting
entire groups of features. We apply sparseptron
for selecting feature templates in three structured
prediction tasks, with advantages over filter-based
methods, L1 , and L2 regularization in terms of performance, compactness, and model interpretability.

Acknowledgments
We would like to thank all reviewers for their comments,
Eric Xing for helpful discussions, and Slav Petrov for hiscomments on a draft version of this paper. A. M. was supported by a FCT/ICTI grant through the CMU-Portugal
Program, and also by Priberam. This work was partially
supported by the FET programme (EU FP7), under the
SIMBAD project (contract 213250). N. S. was supported
by NSF CAREER IIS-1054319.

References
Y. Altun, I. Tsochantaridis, and T. Hofmann. 2003. Hidden Markov support vector machines. In Proc. of
ICML.
G. Andrew and J. Gao. 2007. Scalable training of
L1-regularized log-linear models. In Proc. of ICML.
ACM.
F. Bach, R. Jenatton, J. Mairal, and G. Obozinski. 2011.
Convex optimization with sparsity-inducing norms. In
Optimization for Machine Learning. MIT Press.
F. Bach. 2008. Exploring large feature spaces with hierarchical multiple kernel learning. NIPS, 21.
S. Bakin. 1999. Adaptive regression and model selection in data mining problems. Ph.D. thesis, Australian
National University.
S. Buchholz and E. Marsi. 2006. CoNLL-X sharedtask on multilingual dependency parsing. In Proc. of
CoNLL.
B. Carpenter. 2008. Lazy sparse stochastic gradient descent for regularized multinomial logistic regression.
Technical report, Technical report, Alias-i.
R. Caruana. 1997. Multitask learning. Machine Learning, 28(1):41–75.

S. F. Chen and R. Rosenfeld. 2000. A survey ofsmoothing techniques for maximum entropy models.
IEEE Transactions on Speech and Audio Processing,8(1):37–50.
M. Collins. 2002a. Discriminative training methods for
hidden Markov models: theory and experiments withperceptron algorithms. In Proc. of EMNLP.
M. Collins. 2002b. Ranking algorithms for named-entity
extraction: Boosting and the voted perceptron. In
Proc. of ACL.
K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and
Y. Singer. 2006. Online Passive-Aggressive Algorithms. JMLR, 7:551–585.
S. Della Pietra, V. Della Pietra, and J. Lafferty. 1997.
Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence,
19:380–393.
J. Duchi and Y. Singer. 2009. Efficient online and batchlearning using forward backward splitting. JMLR,
10:2873–2908.
J. Eisenstein, N. A. Smith, and E. P. Xing. 2011. Discovering sociolinguistic associations with structured sparsity. In Proc. of ACL.
M.A.T. Figueiredo. 2002. Adaptive sparseness using Jeffreys’ prior. Advances in Neural Information Processing Systems.
J. Friedman, T. Hastie, and R. Tibshirani. 2010. A noteon the group lasso and a sparse group lasso. Unpublished manuscript.
J. Gao, G. Andrew, M. Johnson, and K. Toutanova. 2007.
A comparative study of parameter estimation methods
for statistical natural language processing. In Proc. of
ACL.
J. Goodman. 2004. Exponential priors for maximum entropy models. In Proc. of NAACL.
J. Graça, K. Ganchev, B. Taskar, and F. Pereira. 2009.
Posterior vs. parameter sparsity in latent variable models. Advances in Neural Information Processing Systems.
I. Guyon and A. Elisseeff. 2003. An introduction to variable and feature selection. Journal of Machine Learning Research, 3:1157–1182.
R. Jenatton, J.-Y. Audibert, and F. Bach. 2009. Structured variable selection with sparsity-inducing norms.
Technical report, arXiv:0904.3523.
R. Jenatton, J. Mairal, G. Obozinski, and F. Bach. 2010.
Proximal methods for sparse hierarchical dictionary
learning. In Proc. of ICML.
J. Kazama and J. Tsujii. 2003. Evaluation and extension of maximum entropy models with inequality constraints. In Proc. of EMNLP.
S. Kim and E.P. Xing. 2010. Tree-guided group lasso for
multi-task regression with structured sparsity. In Proc.
of ICML.

J. Lafferty, A. McCallum, and F. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. of ICML.
G. R. G. Lanckriet, N. Cristianini, P. Bartlett, L. El
Ghaoui, and M. I. Jordan. 2004. Learning the kernel
matrix with semidefinite programming. JMLR, 5:27–
72.
J. Langford, L. Li, and T. Zhang. 2009. Sparse online
learning via truncated gradient. JMLR, 10:777–801.
T. Lavergne, O. Cappé, and F. Yvon. 2010. Practicalvery large scale CRFs. In Proc. of ACL.
J. Liu and J. Ye. 2010. Moreau-Yosida regularization forgrouped tree structure learning. In Advances in Neural
Information Processing Systems.
J. Mairal, R. Jenatton, G. Obozinski, and F. Bach. 2010.
Network flow algorithms for structured sparsity. In
Advances in Neural Information Processing Systems.
A. F. T. Martins, N. A. Smith, E. P. Xing, P. M. Q. Aguiar,
and M. A. T. Figueiredo. 2010. Turbo parsers: Dependency parsing by approximate variational inference.
In Proc. of EMNLP.
A. F. T. Martins, M. A. T. Figueiredo, P. M. Q. Aguiar,
N. A. Smith, and E. P. Xing. 2011. Online learning ofstructured predictors with multiple kernels. In Proc. of
AISTATS.
A. McCallum. 2003. Efficiently inducing features ofconditional random fields. In Proc. of UAI.
R. T. McDonald, F. Pereira, K. Ribarov, and J. Hajic.
2005. Non-projective dependency parsing using spanning tree algorithms. In Proc. of HLT-EMNLP.
G. Obozinski, B. Taskar, and M.I. Jordan. 2010. Joint covariate selection and joint subspace selection for multiple classification problems. Statistics and Computing,20(2):231–252.
S. Petrov and D. Klein. 2008a. Discriminative log-linear
grammars with latent variables. Advances in Neural
Information Processing Systems, 20:1153–1160.
S. Petrov and D. Klein. 2008b. Sparse multi-scale grammars for discriminative latent variable parsing. In
Proc. of EMNLP.
A. Quattoni, X. Carreras, M. Collins, and T. Darrell.
2009. An efficient projection for l1,∞ regularization.
In Proc. of ICML.
E.F.T.K. Sang and S. Buchholz. 2000. Introduction to the
CoNLL-2000 shared task: Chunking. In Proceedingsof CoNLL-2000 and LLL-2000.
E.F.T.K. Sang and F. De Meulder. 2003. Introduction to
the CoNLL-2003 shared task: Language-independent
named entity recognition. In Proc. of CoNLL.
E.F.T.K. Sang. 2002. Introduction to the CoNLL2002 shared task: Language-independent named entity
recognition. In Proc. of CoNLL.

M. Schmidt and K. Murphy. 2010. Convex structurelearning in log-linear models: Beyond pairwise potentials. In Proc. of AISTATS.
S. Shalev-Shwartz, Y. Singer, and N. Srebro. 2007. Pegasos: Primal estimated sub-gradient solver for SVM.
In ICML.
N. Sokolovska, T. Lavergne, O. Cappé, and F. Yvon.
2010. Efficient learning of sparse conditional random
fields for supervised sequence labelling. IEEE Journalof Selected Topics in Signal Processing, 4(6):953–964.
B. Taskar, C. Guestrin, and D. Koller. 2003. Max-margin
Markov networks. In Advances in Neural Information
Processing Systems.
R. Tibshirani. 1996. Regression shrinkage and selection
via the lasso. Journal of the Royal Statistical Society
B., pages 267–288.
I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun.
2004. Support vector machine learning for interdependent and structured output spaces. In ICML.
Y. Tsuruoka, J. Tsujii, and S. Ananiadou. 2009. Stochastic gradient descent training for l1-regularized loglinear models with cumulative penalty. In Proc. of
ACL.
S.J. Wright, R. Nowak, and M.A.T. Figueiredo. 2009.
Sparse reconstruction by separable approximation.
IEEE Transactions on Signal Processing, 57(7):2479–
2493.
L. Xiao. 2009. Dual averaging methods for regularized stochastic learning and online optimization. In
Advances in Neural Information Processing Systems.
M. Yuan and Y. Lin. 2006. Model selection and estimation in regression with grouped variables. Journal of
the Royal Statistical Society (B), 68(1):49.
P. Zhao, G. Rocha, and B. Yu. 2009. Grouped and hierarchical model selection through composite absolute
penalties. Annals of Statistics, 37(6A):3468–3497.
H. Zou and T. Hastie. 2005. Regularization and variable selection via the elastic net. Journal of the Royal
Statistical Society Series B (Statistical Methodology),67(2):301–320.