Polyhedral Outer Approximations
with Application to Natural Language Parsing

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

Abstract
Recent approaches to learning structured
predictors often require approximate inference for tractability; yet its effects on thelearned model are unclear. Meanwhile, mostlearning algorithms act as if computational
cost was constant within the model class.
This paper sheds some light on the first issue
by establishing risk bounds for max-marginlearning with LP relaxed inference and addresses the second issue by proposing a newparadigm that attempts to penalize “timeconsuming” hypotheses. Our analysis relies
on a geometric characterization of the outerpolyhedra associated with the LP relaxation.
We then apply these techniques to the problem of dependency parsing, for which a concise LP formulation is provided that handles
non-local output features. A significant improvement is shown over arc-factored models.

1. Introduction
Structured classification tackles problems characterized by strong interdependence among the output variables, often with a sequential, graphical, or combinatorial structure. Problems of this kind arise in natural
language processing (NLP), computer vision, robotics,
and computational biology. Considerable progress has
been made lately toward a unified view of these problems (Lafferty et al., 2001; Collins, 2002; Taskar et al.,
2003; Tsochantaridis et al., 2004).
A typical approach is to capture the problem structure
via a Markov network. Unfortunately, exact inferenceAppearing in Proceedings of the 26 th International Conference on Machine Learning, Montreal, Canada, 2009. Copyright 2009 by the author(s)/owner(s).

afm@cs.cmu.edu
nasmith@cs.cmu.edu
epxing@cs.cmu.edu

and learning are only tractable for a small class of network topologies. While discriminative learning is able
to handle features that depend globally on the input
variables, the analogous property on the output side ismore difficult to obtain. For tractability, assumptions
about the locality of output variable dependence areoften made at the expense of expressive power. Exploring non-local output dependencies is not just an
empiricist attempt to produce more accurate models:
indeed, there are instances of structured problems inwhich the output variables are known to interact globally, e.g., by definition of the output space. An example is natural language parsing, where the output
variables must “agree” to ensure that they jointly encode a valid parse tree. While dynamic programming
sometimes offers a solution to this problem (albeit under locality assumptions), the same does not happen
in many combinatorial problems of interest, like those
involving matchings, permutations, or spanning trees.
When exact inference is intractable, one has to resort
to approximate algorithms; typically, the same algorithms are called as subroutines to train the model.
This has been done, e.g., by Taskar et al. (2004)
and Daumé and Marcu (2005); recently, Kulesza andPereira (2007) and Finley and Joachims (2008) provided some learning approximation guarantees andempirical analyses. However, a theoretical study of
the actual impact of these approximations in thelearning procedure—when compared with the exact
formulation—is still missing.
This paper aims to fill this gap for the case of outerapproximations when learning large margin classifiers.
Often, the problem of inference can be represented as
an integer linear program (ILP); this is common in
NLP applications like semantic role labeling (Roth &Yih, 2005), summarization (Clarke & Lapata, 2008),
coreference resolution (Denis & Baldridge, 2007), anddependency parsing (Riedel & Clarke, 2006; Martins

Polyhedral Outer Approximations with Application to Natural Language Parsing

et al., 2009). While solving an ILP is NP-hard ingeneral, fast solvers are available today that makethis a practical solution in some cases. We study
approximate techniques based on LP relaxations applied to the problem of dependency parsing; our formulation effectively handles global features and constraints. The techniques discussed here are also relevant to other applications; in particular, they are able
to exploit expert knowledge in the form of soft or hardfirst-order constraints (Richardson & Domingos, 2006;
Chang et al., 2008).
The contributions of this paper are:
• We provide risk bounds for approximate learners, ina large margin framework, that arise from an LP relaxation of the inference problem. We characterizethese bounds in terms of geometric and algorithmic
properties. In particular, we provide sufficient conditions for algorithmic separability.
• We propose a new learning paradigm for approximate inference that balances accuracy and runtime,
where an additional loss term is included in thelearner objective function to penalize models withlong expected runtime. We formulate and analyze a
new algorithm based on this paradigm.
• We empirically evaluate the performance of suchapproximate learners on dependency parsing tasks.
Our parsers are able to handle sibling and grandparent interactions, word valency, and to softly favornearly projective parses.
The paper is organized as follows. Sec. 2 introduces theframework of ILP formulations for large margin structured classification; Sec. 3 provides a theoretical analysis of outer approximations through LP relaxations;Sec. 4 presents the task; experiments are discussed inSec. 5. We conclude in Sec. 6.

2. Structured Classification and LP
Let X and Y denote the input and output sets, respectively, and assume a supervised setting, where weare given labeled data L , {(x1 , y1 ), . . . , (xm , ym )} ⊆X × Y, drawn according to a fixed, unknown distribution P (X, Y ), and aim to learn a function h : X → Y
with small expected loss E`(h(X); Y ) on unseen data;
here, ` : Y × Y → R+ denotes the loss function.
We are interested in the case where Y is exponentiallylarge but finite. We assume that there is a bijection ζ
between Y and the set of vertices of a polytope Z ,{z ∈ Rn | Az ≤ b}, where A is a p-by-n matrix andb is a vector in Rp , for some integers p and n. In
that case, to carry out structured classification (theinference problem), one may transform the problem

of optimizing over Y into that of optimizing a linear
function over Z (guaranteed to attain the optimum ata vertex of Z) and then invert, y ∗ = ζ −1 (z∗ ). This
framework was first studied by Taskar et al. (2004) inthe context of associative Markov networks.
Denote by V (Z) the set of vertices of Z. A map
ζ : Y → V (Z) arises naturally whenever the elementsof Y can be represented as collections of “parts” ina finite set R (i.e., each y ∈ Y satisfies y ⊆ R).1
Indeed, let us consider linear classifiers of the formhw (x) = arg maxy∈Y w> f (x, y) (here, f (x, y) is a vector of features and w is the corresponding weight vector). If the features decompose over the parts throughXX
f (x, y) ,fr (x) =zr fr (x),
(1)
r∈y

r∈R

where zr , I(r ∈ y), then, by defining the indicator
vector z , (zr )r∈R and the matrix F , (fr (x))r∈R :hw (x) = arg max w> f (x, y) = ζ −1 arg max w> Fz ,
y∈Y

z∈Z

(2)
where Z is the convex hull of the set of indicator vectors that correspond to elements of Y. Therefore, inthis situation, inference can be cast as an LP; this automatically enables learning using any algorithm that
only needs to perform inference steps, like the structured perceptron (Collins, 2002). Furthermore, whenever the loss function can be expressed as a linear function of z—which turns out to be the case in many casesof interest, e.g. in Hamming-like losses,
X`(y 0 ; y) ,(I(r ∈ y 0 )I(r ∈/ y) + I(r ∈/ y 0 )I(r ∈ y))
r∈R

=

X

zr0 (1 − zr ) + (1 − zr0 )zrr∈R= p> z0 + q,(3)

where p , 1 − 2z, q , 1> z, and we made the variablechanges z , ζ(y) and z0 , ζ(y 0 )—then this setting
also allows learning the model parameters w using a
max-margin criterion. To see how, define, for eachdata point (xt , yt ) ∈ L, the non-negative quantity
max w> f (xt , yt0 ) − w> f (xt , yt ) + `(yt0 ; yt )


>
> 0
>
>
=
max
(F
w
+
p
)
z
t
t − (Ft w) zt + qt ,t0

rt (w) ,yt0 ∈Yzt ∈Z(4)
where zt , ζ(yt ); the problem of finding the arg max
in (4) is often referred to as the loss-augmented inference (LAI) problem; observe that it can also be
1
The set of parts R can be, e.g., the set of all possible
clique assignments in a Markov network.

Polyhedral Outer Approximations with Application to Natural Language Parsing

Figure 1. Left: Schematic representation of the outer polytope Z̄ associated with the relaxation (6). Right: The
carved polytope Z̃η implicit in the problem (13).

cast as an LP. The complete learning problem ism
λ1 X
min kwk2 +rt (w),
w 2
m t=1

(5)

where λ ≥ 0 is a regularization parameter. This isa convex problem for which several algorithms havebeen proposed (Taskar et al., 2004; Taskar et al., 2006;
Tsochantaridis et al., 2004; Ratliff et al., 2006).
In what follows, we denote U , [0, 1], and B , {0, 1} =U ∩ Z. Although in some special cases there exists a
concise polyhedral representation of Z (in terms of thematrix A and vector b) that does not happen in general. Often, what we have is a concise representationof an outer polytope Z̄ ⊇ Z such thatmin c> z =
z∈Z

min

c> z ≥ min c> zz∈Z̄,z∈Bn(6)

Let H , {hw | w ∈ W} be our hypothesis class, whereW ⊆ Rd is a convex set, and hw is the maximum(over Z) of linear discriminant functions, as in (2).
We consider approximate inference algorithms A, that
accept as input a parameter w ∈ W and a data pointx ∈ X , and output a value A(x; w) in Z̄. Following
Kulesza and Pereira (2007), we say that the dataset
L is P
separable (w.r.t. H) if there is w ∈ W suchmthat t=1 `(hw (xt ); zt ) = 0; we say that L is algorithmicallyseparable (w.r.t. A) if there is w ∈ W
Pmsuch thatt=1 `(A(xt ; w); zt ) = 0. In both cases,
we say that “L is separated (resp. algorithmically separated) by w” when w is a “witness” in the above
definitions. In our setting, where we consider algorithms induced by the outer approximation Z̄ ⊇ Z,
algorithmic separability w.r.t. A is equivalent to separability w.r.t. H̄ , {h̄w | w ∈ W}, where h̄w takes theform h̄w (x) = arg maxz̄∈Z̄ w> Fz̄. Observe also that,in this setting, algorithmic separability implies separability; this was pointed out by Kulesza and Pereira(2007) and Finley and Joachims (2008). Essentially,
their theoretical analyses for structured learning withouter approximate (or “overgenerating”) inference algorithms are extensions of known results for the exact
formulations, obtained by replacing Z with Z̄ in theformulas. While these theoretical guarantees are helpful (constrasting with undergenerating predictors, forwhich no guarantees exist), they do not provide sufficient conditions for algorithmic separability, neither
do they bound the risk of an outer approximation compared with the exact formulation.

z∈Z̄

holds for any c with a fairly tight bound. Notice that,
if we assume that Z̄ ⊆ Un , then there are no integer
points in the relative interior of Z̄; consequently, (6)implies that any vertex of Z is also a vertex of Z̄. The
two polytopes are represented schematically in Fig. 1.

3. Learning with LP Relaxed Inference
We now study the impact of relaxations like (6) in thelearning problem.

Lemma 1 Assume that the feature function satisfies
kfr (x)k∞ ≤ 1,2 and let Nf , maxx∈X ,r∈R kfr (x)k1 .
Then, for any w ∈ W, z̄ ∈ Z̄ and z ∈ V (Z):p|w> F(z̄ − z)| ≤ kwk2 Nf `(z̄; z).
(7)
Proof: By using Hölder’s inequality, |w> F(z̄ − z)| ≤>kF> wkp∞ · kz̄ − zk1 = maxr∈R w fr (x) · `(z̄; z) ≤kwk2 Nf `(z̄; z).
Note that Lemma 1 implies
ˆ z, w) , w> F(z̄ − z) + `(z̄; z)`(z̄;p≤ (1 + kwk2 Nf )`(z̄, z).

3.1. Approximation Bounds
To cope with our approximate learning setting, we
identify Y ' V (Z) through the map ζ; with someabuse of notation, we write `(z0 ; z) for the loss function(3) instead of `(ζ −1 (z0 ); ζ −1 (z)). Also, we extend its
domain by defining `(z̄0 ; z) = p> z̄0 + q for any z̄0 ∈ Z̄.
Observe that, whenever z ∈ V (Z), `(z̄0 ; z) = kz̄0 − zk1 .
As a consequence, ` has the triangle inequality property, i.e., `(z̄0 ; z) ≤ `(z̄0 ; z0 ) + `(z0 ; z), for any z̄0 ∈ Z̄and z, z0 ∈ V (Z). This fact will be exploited below.

(8)

We can now provide a sufficient condition foralgorithmic separability.
Recall that rt (w) ,ˆ 0 ; zt , w); defining analogously r̄t (w) ,maxz0t ∈Z `(ztˆ 0 ; zt , w), we have:maxz̄0t ∈Z̄ `(z̄t2This is guaranteed if the features are binary-valued, inwhich case Nf is the maximum possible number of active
features at a single part.

Polyhedral Outer Approximations with Application to Natural Language Parsing

Proposition 2 Let L be such that, for any z̄ ∈ Z̄ \ Z,there exists z ∈ V (Z) such that `(z̄; z) ≤ L. Then:prt (w) ≤ r̄t (w) ≤ rt (w) + (1 + kwk2 Nf )L. (9)of Z have constant `1 -norm (say K), and any z̄ ∈ Z̄satisfies 1> z̄ ≤ K, then:prt (w) ≤ r̄t (w) ≤ rt (w) + 2K(1 + kwk2 Nf ). (12)Furthermore, let L0 ≥ L be such that, for any z̄ ∈Z̄ \ Z, there exist z, z0 ∈ V (Z) such that `(z̄; z) ≤`(z̄; z0 ) ≤ L0 . If P
L is separated by w∗ with a largem∗∗margin(i.e. if
t=1 rt (w ) = 0) and kw k2 <p0
1/(L Nf ), then L is algorithmically separated by w∗ .

Proof: Since A is outer -approximate, it underestimates minz∈Z c> z by at most c> z∗ , provided c ≥ 0.
In the general case for LAI, however, c = −F>t w−pt 0; but since the vertices of Z have constant norm,
the problem of optimizing over Z is unchanged byadding any constant to the cost vector. Thus, defining
c0 = c + kck∞ ≥ 0:

Proof: The fact that rt (w) ≤ r̄t (w) is trivial, sinceZ ⊆ Z̄. As for the upper bound, we choose z0t ∈ V (Z)such that `(z̄0t , z0t ) ≤ L and apply triangle inequality:r̄t (w) ≤max w

z̄0t ∈Z̄

>Ft (z̄0t − z0t ) + w> Ft (z0t − zt )z̄0t ∈Z̄≤ −(1 − ) minc0> z0t + Kkck∞ − w> Ft zt + qt
0zt ∈Z+`(z̄0t ; z0t ) + `(z0t , zt )
ˆ 0 ; zt , w)
ˆ 0 ; z0 , w) + `(z= max `(z̄tt t

c0> z0t≤ rt (w) +  min0zt ∈Zz̄0t ∈Z̄

≤ rt (w) + (1 + kwk2r̄t (w) = − min (c0 − kck∞ · 1)> z̄0t − w> Ft zt + qt

pNf )L,≤ rt (w) + 2K(1 + kwk
(10)

p
Nf ),

again due to Hölder’s inequality.

As for the second part, we have for all t and z̄0t ∈ Z̄:w∗ >Ft(zt − z̄0t ) = w∗ > Ft (zt − z0t ) + w∗ > Ft (z0t − z̄0t )p≥ w∗ >Ft(zt − z0t ) − kw∗ k2 Nf `(z0t ; z̄0t )p≥ `(zt ; z0t ) − kw∗ k2 Nf L0≥ 1 − 1 = 0,

(11)where we chose z0t 6= zt such that `(z̄0t ; z0t ) ≤ L0 , andused Lemma 1, together with the fact that any two
distinct points in V (Z) have at least unit loss (since
they belong to Bn ).
Corollary 3 Under the conditions stated in the second part of Prop. 2, the perceptron algorithm runningapproximate inference will make a finite number of
mistakes.
Proof: (Sketch) Use Prop. 2 and the mistake boundfor the structured perceptron (Collins, 2002).
The bound (9) relies on a geometric characterizationof the approximating polytope Z̄ (through the parameters L and L0 ). However, in some cases one has algorithmic approximation guarantees instead (see, e.g.,
Vazirani, 2001). The following establishes a boundsimilar to the one in Prop. 2 that relies on an algorithmic characterization (we define A(x, w) , h̄w (x)):
Proposition 4 If A is outer -approximate3 for theclass of problems minz∈Z c> z with c ≥ 0, the vertices
3
Given a class F of nonnegative functions and a minimization problem minx∈X f (x) , f ∗ , an algorithm is said
to be outer -approximate if it retrieves a lower bound of
the optimum, f , such that (f ∗ − f )/f ∗ ≤ .

Props. 2–4 will be used in Sec. 3.3 to establish empirical risk and generalization bounds.
3.2. Balancing Accuracy and Runtime
We now propose a new learning strategy that balances
accuracy and algorithmic cost. We argue that, when
the computational cost of performing inference at test
time is something that we worry about, then this costshould be taken into account in the learning problem.
Let `c : H × X → R be a cost function that, given ahypothesis h ∈ H and a data point x ∈ X , expresses
the cost of computing h(x). Most existing learningalgorithms concern minimizing the expected loss on
unseen data, E`(h(X), Y ); yet, it may happen thatthe model that minimizes this quantity (call it h∗ )has an impractically high average computational cost.
On the other hand, there may well exist another hypothesis h0 ∈ H performing similarly to h∗ that yields
much faster runtimes. Hence, our target should be tominimize E (`(h(X), Y ) + η`c (h, X)), where η ≥ 0 is atrade-off parameter.
Traditional algorithmic complexity theory, which looks
at the worst possible problem configurations, is notuseful here, as we are interested in average complexities (Levin, 1986) under the unknown distribution
P (X, Y ). As an example, consider the ILP formulation(6), where the cost vector c , F> w is affected both by
the model parameters w and by the input data, represented in the matrix F (that we can see as a randomvariable). Although solving an ILP is an NP-complete
problem, for some “nice” distributions P (c) (peakedPolyhedral Outer Approximations with Application to Natural Language Parsing

over values of c that hit integer vertices of the constraint polyhedron) the average computational cost is
low. Therefore, it is desirable to obtain model parameters w that, besides having small expected loss, yield
nice cost vectors c ∼ P (F> w) with high probability.
When the constraint polytope does not contain integer points in its relative interior (which is our case,cf. (6)), the runtime of many off-the-shelf ILP solvers(like those based on branch-and-bounding or Gomory’scuts) decreases as the solution of the relaxed problem is closer to the exact solution; therefore, it may
be reasonable to approximate the expected computational cost E`c (hw , X) by the expected relaxation gap
E`(hw (X), h̄w (X)). Led by this thought, we add a“empirical relaxation
term to our learning objecPgap”
m1
tive of the form m(r̄
t=1 t (w) − rt (w)) ≥ 0. Rearranging terms, the overall learning problem becomes:
m
m
λ
1−η X
η X
min kwk2 +rt (w) +r̄t (w).
w 2
m t=1
m t=1

(13)

By defining Z̃η , (1 − η)Z + η Z̄ and due to linearityof the loss function, observe that each LAI problem
in (13) can be written as (1 − η)rt (w) + ηr̄t (w) =maxz̃0 ∈Z̃η w> Ft (z̃0t − zt ) + `(z̃0t , zt ). As a consequence,t
the formulation (13) is isomorphic to the one in (5),with the sole difference that the polytope Z is replacedby Z̃η ; unfortunately, Z̃η is, in general, as hard to represent as Z. Notice that Z ⊆ Z̃η ⊆ Z̄ for any η ∈ [0, 1];geometrically, Z̃η is obtained from Z̄ by intersecting
the latter with cutting half-spaces that “carve out” thefractional vertices (see Fig. 1). Therefore, optimizing
over Z̃η has the effect of providing approximate solutions that lie near the integer vertices.
Rather than optimizing over the carved polytope, we
propose a simple stochastic online strategy (see Algorithm 1) to tackle (13); we also allow the trade-off parameter to vary over time (i.e., we replace η by hηt it ).
This algorithm is similar to the subgradient algorithmof Ratliff et al. (2006), except that, at each step, it
randomly decides whether it will perform exact or approximate LAI; we analyze this algorithm in Sec. 3.3.4

Algorithm 1 Modified Online Subgradient
Input: L, hηt it , learning rate sequence hαt it
Initialize w1 ← 0
for t = 1 to m = |L| do
Pick σt ∼ Bernoulli(ηt )if σt = 1 thenˆ 0 ; zt , wt )Solve relaxed LAI, ẑt←arg maxz̄0t ∈Z̄ `(z̄telse
ˆ 0 ; zt , wt )Solve exact LAI, ẑt ← arg maxz0t ∈Z `(zt
end ifCompute the subgradient gt ← λwt + Ft (ẑt − zt )Project and update wt+1 ← ProjW (wt − αt gt )end forPm
1
Return the averaged model ŵ ← m
t=1 wt .

can be adapted to the case of LP relaxed inference(by invoking the fact that relaxed inference essentiallyaugments the output set). Here, we go farther and provide a generalization bound for approximate learning
w.r.t. the empirical risk minimizer in the exact setting.
Proposition 5 Let ŵ be the solution returned by Algorithm 1 with learning rate chosen as αt = 1/(λt).
ˆ zt , wt ) is upper bounded by Λ and that
Assume that `(.;
the subgradient norm is bounded by G.5 Then, the following bound holds with probability at least 1 − δ:m

1 X
E`(hŵ (X); Y ) ≤ minrt (w) + M (w, m) +
w∈W m
t=1
p
8Λ2 /m ln(2/δ), (14)where M (w,· kwk2 + G2 (1 + log m)/(2λm) +p m) ,Pλ/2m(1 + kwk Nf )L t=1 ηt /m.
Proof: (Sketch.) We adapt a result from Cesa-Bianchi
et al. (2004) for convex and bounded loss functions toget (for any 0 < δ 0 ≤ 1)m

1 X
Er(ŵ) ≥rt (wt ) +
m t=1

P

r

2Λ2
1
ln 0
m
δ

!
≤ δ 0 . (15)3.3. Generalization Bounds
Kulesza and Pereira (2007) observed that a PAC-Bayes
generalization bound for empirical risk minimization
4

Note that Algorithm 1 with fixed η and fixed sample
size indeed optimizes (13). The law of large numbers implies that after enough iterations, the fraction of time thateach datum is used to solve exact LAI (resp. relaxed LAI)
is arbitrarily close, in probability, to 1 − η (resp. η); hence,
one just needs to adapt the convergence proofs of the subgradient algorithm.

Since `(hŵ (X); Y ) ≤ r(ŵ), it suffices to bound the
RHS. Noting that rt (wt ) ≤ r̄t (wt ), and adapting a
regret bound from Ratliff et al. (2006) for the subgradient algorithm we get, for any w ∈ W:
The function `ˆ can be made bounded if we define W to
be a convex body, e.g. by constraining kwk ≤ ρ, which enˆ zt , wt ) ≤ (1+ρN 1/2 )K ,sures, through Lemma 1, that `(.;f
Λ, where K ≥ kzk1 . As for G, assuming feature vectors
whose norm is bounded by R/2, we may take G = R + λρ2 .
5Polyhedral Outer Approximations with Application to Natural Language Parsing

m
1 X

m t=1

rt (wt ) ≤

m
1 X

m t=1

rt (w) +λkwk2 +
2

G2 (1 + log m)
+
2λm
m
1 X
σt (r̄t (w) − rt (w)); (16)m t=1Now, applying Hoeffding’s inequality to the random
00
sequence hσt it=1,...,m , wep get (for any 0 < δ00 ≤ 1)Pm
Pm
P ( t=1 σt ≥ t=1 ηt + 2/m · log(1/δ 00 )) ≤ δ . Substituting in (16), invoking Prop. 2, and plugging theresult in (15) (noting that Λ upper bounds the approximation gap), we get the desired result (by taking
δ , 2δ 00 = 2δ 0 ).
p
Corollary 6 If we set λ = Θ( (1 + log m)/m) and√a.s. 1 Pm∗
ηt = Θ(1/ t), then Er(ŵ) −→ m
t=1 rt (w ).
Proof: The choice of λ was proposed√by RatliffPm√et al.,2006. As for hηt i, we have t=1 1/ t = O( m) =o(m); therefore limm→∞ M (w, m) = 0.

4. Dependency Parsing
We next show how approximate learning using LP relaxed inference can be used in an important NLP task
involving non-local interactions among output variables: dependency parsing. We merely sketch the
problem; see Martins et al. (2009) for a full discussionof dependency parsing and its ILP representations.
Dependency trees are a lightweight syntactic representation that attempts to capture functional relationships between words. Given a sentence x =hw0 , . . . , wn i (where wi denotes the word at the i-th
position, and w0 = $ is a wall symbol), consider the
digraph D = (V, A), with vertices in V = {0, . . . , n}(the i-th vertex corresponding to the i-th word) andarcs in A = V 2 . A (legal) dependency parse tree of x
is any 0-arborescence6 of D; we denote the set of legal
dependency parse trees of x by Y(x).7 If a = (i, j) ∈ y
we refer to i as the parent of j and j as the child of i.
A
S parser is a function h : X → Y, where Y =x∈X Y(x). The fact that Y(x) is exponentially large
makes this a structured classification problem. We
want to learn an h with small expected loss—here, theHamming loss function `(y 0 ; y) , |{(i, j) ∈ y 0 : (i, j) ∈/y}|, which, if R = A, is proportional to (3).
6

An r-arborescence of D is a subset B of A such that
(V, B) is a (directed) tree rooted at r.
7
In this paper, we consider unlabeled dependency parsing, where only the backbone structure is predicted.

An arc-factored model for dependency parsing is one
in which the feature vector decomposes as a sum overarcs (i.e., R = A in (1)); such models can captureeach word’s preferences for particular properties of its
children or parents. McDonald et al. (2005) showedthat arc-factored inference among trees is an instanceof the minimum arborescence problem, which enables
efficient algorithms for exact inference (Chu & Liu,
1965; Edmonds, 1967).
Riedel and Clarke (2006) added hard linguistic constraints to an arc-factored model, representing the inference problem as an ILP with exponentially many
constraints. They used a cutting plane algorithm for
inference, in which constraints are only invoked when
violated; further, they trained with an arc-factoredmodel since the cutting plane algorithm was slow. In
Martins et al. (2009), we formulate dependency parsing as an ILP with a polynomial number of constraints,
by adapting a single-commodity directed flow modeldue to Magnanti and Wolsey (1994). Our representation allows constraints to be made soft, so that theirstrengths are learned as features of the model. Thispermits us to include non-arc-factored features, described next.
Siblings and grandparents It was shown by McDonald et al. (2006) and Smith and Eisner (2008) thatmodeling interactions among words who share a parent or among a word’s children and its parent can bebeneficial. To incorporate these features, we employ a
linearization trick (Boros & Hammer, 2002). This canbe done with O(n3 ) variables and constraints.
Valency Words in a language have preferences not
only for which words will be their children, but also
how many children they will have (valency or arity).
Our model includes valency indicator features. An extra O(n2 ) variables and constraints are necessary.
Projectivity If y ∈ Y(x), we say that an arc a =(i, j) ∈ y is projective if for any vertex k in the
span of a (i.e. satisfying min(i, j) < k < max(i, j)),there exists a path in y from i to k (Kahane et al.,1998). A dependency tree is called projective if it only
contains projective arcs.8 Although non-projectivity
is arguably necessary for correctly capturing dependency structure in some languages, parse trees tend
to be nearly projective. We encode this preference ina learned, language-specific way, as a feature. Indicator variables for projective arcs can be added with an
extra O(n3 ) variables and constraints.
8
When the arc-factored assumption is weakened andnon-projectivity is permitted, exact inference becomes NPhard (McDonald & Satta, 2007), cf. parsing with nonprojectivity disallowed (Eisner, 1996).

Polyhedral Outer Approximations with Application to Natural Language Parsing
Table 1. Results for dependency parsing. We have reproduced the system of McDonald et al. (2006) for the sake ofcomparison (MLP’06). For each language and model setting, we report the unlabeled attachment scores (UAS, %) using
exact and approximate inference at test time. For the arc-factored model, we report the results obtained by learning withexact LAI. Bold indicates significantly best results (statistical significance is measured by Dan Bikel’s randomized parsing
evaluation comparator, http://www.cis.upenn.edu/∼dbikel/software.html).
MLP’06
Learning →Inference →DanishDutch
Portuguese
Slovene

90.60
84.11
91.40
83.67

Arc-Factored Model
Exact (η = 0)
Approx. (η = 1)
Exact Approx. Exact Approx.
89.86
89.68
89.80
89.78
83.15
83.17
83.55
83.61
90.66
90.66
90.66
90.70
84.05
83.87
83.93
83.95

5. Experiments
We demonstrate the effectiveness of our polyhedral
approximations for dependency parsing, with experiments on four languages from the CoNLL-X sharedtask (Buchholz & Marsi, 2006): Danish, Dutch, Portuguese and Slovene. We used the same arc-factored
features as McDonald et al. (2005) and optional nonarc-factored features as described in Sec. 4. All our
experiments were conducted on a PC with a Intel dualcore processor with 2.66 GHz and 2 Gb RAM memory.
We used CPLEX to solve the ILPs.
For scalability, we first prune the base graph by running a simple algorithm that ranks the k-best candidate parents for each word in the sentence, setting
k = 10; this reduces the number of variables andconstraints in the arc-factored model to O(nk), andin the full model to O(n2 k).9 The ranker is a local
model trained using a max-margin criterion; it is arcfactored and not subject to any structural constraints,
so it is fast. Pruning was employed in both training
and testing. To learn the actual parser, we implemented Alg. 1 with passive-aggressive updates (Crammer et al., 2006).10 At test time, we experimented
with exact and approximate inference. The approximate decoder was implemented as follows to obtain atrue parse: first, solve the LP relaxation; then, if thesolution z∗ is fractional, project its arc componentsz∗A , (z∗a )a∈A onto the feasible set Y(x). The Euclidean projection can be computed by finding a maximalarborescence in the digraph whose weights are definedby z∗A (proof omitted); as seen in Sec. 4, the Chu-LiuEdmonds algorithm can do this in polynomial time.
Tab. 1 summarizes the results. As expected, adding
non-arc-factored features makes the models more accurate. We also observe that approximate training did
not hurt the arc-factored model, compared with ex9
The oracle constrained to pick parents from these lists
achieves > 98% in every case.
10
Without regularization, this can be seen as a variantof the online subgradient algorithm of Ratliff et al. (2006).

Full Model
Approx. (η = 1)
Exact Approx.
91.18
91.04
85.57
85.41
91.42
91.44
85.61
85.41

Table 2. Runtimes for Slovene, as a function of η. Learning the full model was intractable as η → 0; the valency
and non-projectivity features were excluded in this analysis. The reported values (collected at test time) are: thepercentage of words for which a fractional parent (FP) was
assigned in the LP-relaxed problem, and average runtimes
per sentence, using exact and approximate inference.
η
0.00
0.25
0.50
0.75
1.00

FP (%)
16.53
10.42
8.29
7.76
7.12

Exact (sec.)
19.33
4.16
2.20
1.62
1.11

Approx. (sec.)
0.17
0.13
0.13
0.13
0.12

act training. Moreover, approximate decoding at test
time did not considerably affect accuracy for any of themodels. For 3 out of 4 languages, the full model yields
substantially better results than the approximate nonarc-factored parser of McDonald et al. (2006).
To see whether the parameter η is effectively penalizing computational cost, according to the paradigm
sketched in Sec. 3.2, we did an additional experiment
for the Slovene dataset (Tab. 2). We observe that, as η
approaches 0 (i.e., as training becomes close to exact),
the learned model tends to assign more fractional solutions in the LP relaxed problem (a subroutine for boththe approximate and exact decoders), which results ina dramatic increase in runtime for the exact decoder.
In contrast, when trained with η = 1, the model learns
to avoid fractional solutions, and ILP solvers will converge faster to the optimum (on average). Yet theapproximate decoder is still significantly faster.

6. Conclusions
We studied the impact of LP relaxed inference in maxmargin learning. Based on a geometric characterization, we established conditions that guarantee algorithmic separability and derived risk bounds w.r.t. theexact formulations. As a by-product, we put forth a
new learning paradigm that takes computational cost
into consideration. We demonstrated the effectivenessPolyhedral Outer Approximations with Application to Natural Language Parsingof these techniques on a structured prediction problem.
As future work, we will look for polyhedral characterizations that guarantee tighter risk bounds; in particular, we aim to obtain conditions under which theapproximation gap decreases with the sample size.

Acknowledgments
The authors thank the reviewers for their comments
and Nathan Ratliff for discussions. A.M. was supported by a grant from FCT/ICTI through the CMUPortugal Program, and also by Priberam Informática.
N.S. was supported by NSF IIS-0836431 and an IBM
Faculty Award. E.X. was supported by NSF DBI0546594, DBI-0640543, IIS-0713379, and an Alfred
Sloan Foundation Fellowship in Computer Science.

References
Boros, E., & Hammer, P. (2002). Pseudo-Boolean optimization. Discrete Applied Mathematics, 123, 155–
225.
Buchholz, S., & Marsi, E. (2006). CoNLL-X sharedtask on multilingual dependency parsing. Proc. of
CoNLL.
Cesa-Bianchi, N., Conconi, A., & Gentile, C. (2004).
On the generalization ability of on-line learning algorithms. IEEE Trans. on Inf. Theory, 50, 2050–2057.
Chang, M., Ratinov, L., & Roth, D. (2008). Constraints as prior knowledge. ICML Workshop on
Prior Knowledge for Text and Language Processing.
Chu, Y. J., & Liu, T. H. (1965). On the shortest
arborescence of a directed graph. Science Sinica,
14, 1396–1400.
Clarke, J., & Lapata, M. (2008). Global Inference for
Sentence Compression An Integer Linear Programming Approach. JAIR, 31, 399–429.
Collins, M. (2002). Discriminative training methods
for hidden Markov models: theory and experimentswith perceptron algorithms. Proc. of EMNLP.
Crammer, K., Dekel, O., Keshet, J., Shalev-Shwartz,
S., & Singer, Y. (2006). Online Passive-Aggressive
Algorithms. JMLR, 7, 551–585.
Daumé, H., & Marcu, D. (2005). Learning as search
optimization: Approximate large margin methods
for structured prediction. ICML. Bonn, Germany.
Denis, P., & Baldridge, J. (2007). Joint Determinationof Anaphoricity and Coreference Resolution using
Integer Programming. Proc. of NAACL HLT.
Edmonds, J. (1967). Optimum branchings. Journal of
Research of the National Bureau of Standards, 71B,
233–240.
Eisner, J. (1996). Three new probabilistic models for
dependency parsing: An exploration. COLING.

Finley, T., & Joachims, T. (2008). Training structural
SVMs when exact inference is intractable. ICML.
Kahane, S., Nasr, A., & Rambow, O. (1998). Pseudoprojectivity: a polynomially parsable non-projective
dependency grammar. Proc. of COLING.
Kulesza, A., & Pereira, F. (2007). Structured Learningwith Approximate Inference. NIPS.
Lafferty, J., McCallum, A., & Pereira, F. (2001). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. Proc. of ICML.
Levin, L. (1986). Average Case Complete Problems.
SIAM Journal on Computing, 15, 285.
Magnanti, T., & Wolsey, L. (1994). Optimal Trees(Technical Report 290-94). Massachusetts Instituteof Technology, Operations Research Center.
Martins, A. F. T., Smith, N. A., & Xing, E. P. (2009).
Concise integer linear programming formulations for
dependency parsing. Proc. of ACL-IJCNLP.
McDonald, R., Lerman, K., & Pereira, F. (2006). Multilingual dependency analysis with a two-stage discriminative parser. Proc. of CoNLL.
McDonald, R., & Satta, G. (2007). On the complexityof non-projective data-driven dependency parsing.
Proc. of IWPT.
McDonald, R. T., Pereira, F., Ribarov, K., & Hajic,J. (2005). Non-projective dependency parsing using
spanning tree algorithms. Proc. of HLT-EMNLP.
Ratliff, N., Bagnell, J., & Zinkevich, M. (2006). Subgradient methods for maximum margin structured
learning. ICML Workshop on Learning in Structured Outputs Spaces.
Richardson, M., & Domingos, P. (2006). Markov logic
networks. Machine Learning, 62, 107–136.
Riedel, S., & Clarke, J. (2006). Incremental integer
linear programming for non-projective dependency
parsing. Proc. of EMNLP.
Roth, D., & Yih, W. (2005). Integer linear programming inference for conditional random fields. ICML.
Smith, D. A., & Eisner, J. (2008). Dependency parsing
by belief propagation. Proc. of EMNLP.
Taskar, B., Chatalbashev, V., & Koller, D. (2004).
Learning associative Markov networks. ICML.
Taskar, B., Guestrin, C., & Koller, D. (2003). Maxmargin markov networks. NIPS.
Taskar, B., Lacoste-Julien, S., & Jordan, M.
(2006). Structured Prediction via the Extragradient Method. NIPS.
Tsochantaridis, I., Hofmann, T., Joachims, T., & Altun, Y. (2004). Support vector machine learningfor interdependent and structured output spaces.
ICML.
Vazirani, V. (2001).
Approximation Algorithms.
Springer.