An Exact Dual Decomposition Algorithm
for Shallow Semantic Parsing with Constraints∗

Dipanjan Das∗
André F. T. Martins∗†
Noah A. Smith∗Language Technologies Institute, Carnegie Mellon University, Pittsburgh, PA 15213, USA†
Instituto de Telecomunicações, Instituto Superior Técnico, Lisboa, Portugal{dipanjan,afm,nasmith}@cs.cmu.edu
Abstract

We present a novel technique for jointly predicting semantic arguments for lexical predicates. The
task is to find the best matching between semantic roles and sentential spans, subject to structural constraints that come from expert linguisticknowledge (e.g., in the FrameNet lexicon). We
formulate this task as an integer linear program(ILP); instead of using an off-the-shelf tool tosolve the ILP, we employ a dual decomposition
algorithm, which we adapt for exact decoding via
a branch-and-bound technique. Compared to abaseline that makes local predictions, we achieve
better argument identification scores and avoid all
structural violations. Runtime is nine times fasterthan a proprietary ILP solver.

1

Introduction

Semantic knowledge is often represented declaratively in resources created by linguistic experts. In
this work, we strive to exploit such knowledge ina principled, unified, and intuitive way. An example resource where a wide variety of knowledge
has been encoded over a long period of time is the
FrameNet lexicon (Fillmore et al., 2003),1 whichsuggests an analysis based on frame semantics (Fillmore, 1982). This resource defines hundreds ofsemantic frames. Each frame represents a gestalt
event or scenario, and is associated with several semantic roles, which serve as participants in the eventthat the frame signifies (see Figure 1 for an example). Along with storing the above data, FrameNet
also provides a hierarchy of relationships between
frames, and semantic relationships between pairs ofroles. In prior NLP research using FrameNet, theseinteractions have been largely ignored, though they1

http://framenet.icsi.berkeley.edu

have the potential to improve the quality and consistency of semantic analysis.
In this paper, we present an algorithm that finds
the full collection of arguments of a predicate given
its semantic frame. Although we work within theconventions of FrameNet, our approach is generalizable to other semantic role labeling (SRL) frameworks. We model this argument identification task
as constrained optimization, where the constraints
come from expert knowledge encoded in a lexicon. Following prior work on PropBank-style SRL(Kingsbury and Palmer, 2002) that dealt with similar constrained problems (Punyakanok et al., 2004;
Punyakanok et al., 2008, inter alia), we incorporate
this declarative knowledge in an integer linear program (ILP).
Because general-purpose ILP solvers are proprietary and do not fully exploit the structure of the
problem, we turn to a class of optimization techniques called dual decomposition (Komodakis etal., 2007; Rush et al., 2010; Martins et al., 2011a).
We derive a modular, extensible, parallelizable approach in which semantic constraints map not justto declarative components of the algorithm, but also
to procedural ones, in the form of “workers.” While
dual decomposition algorithms only solve a relaxation of the original problem, we make a novel contribution by wrapping the algorithm in a branch-andbound search procedure, resulting in exact solutions.
We experimentally find that our algorithm
achieves accuracy comparable to a state-of-the-art
system, while respecting all imposed linguistic constraints. In comparison to inexact beam search that
violates many of these constraints, our exact decoder
has less than twice the runtime; furthermore, it decodes nine times faster than CPLEX, a state-of-theart, proprietary, general-purpose exact ILP solver.

Agent

SELF_MOTIONCOLLABORATION

Austria , once expected to waltz smoothly into the European Union , is elbowing its partners ,Self_mover

Manner

Goal
MannerCONDUCT

Partner_1 Partner_2

treading on toes and pogo-dancing in a most un-Viennese manner .
Figure 1: An example sentence from the annotations released as part of FrameNet 1.5 with three predicates marked inbold. Each predicate has its evoked semantic frame marked above it, in a distinct color. For each frame, its semanticroles are shown in the same color, and the spans fulfilling the roles are underlined. For example, manner evokes the
C ONDUCT frame, and has the Agent and Manner roles fulfilled by Austria and most un-Viennese respectively.

2

Collective Argument Identification

Here, we take a declarative approach to modelingargument identification using an ILP and relate ourformulation to prior work in shallow semantic parsing. We show how knowledge specified in a linguistic resource can be used to derive the constraints
used in our ILP. Finally, we draw connections of our
specification to graphical models, a popular formalism in AI, and describe how the constraints can betreated as factors in a factor graph.
2.1

Declarative Specification

Let us denote a predicate by t and the semantic
frame it evokes within a sentence x by f . In thiswork, we assume that the semantic frame f is given,
which is traditionally the case in controlled experiments used to evaluate SRL systems (Màrquez etal., 2008). Given the semantic frame of a predicate,
the semantic roles that might be filled are assumed
to be given by the lexicon (as in PropBank andFrameNet). Let the set of roles associated with theframe f be Rf . In sentence x, the set of candidate
spans of words that might fill each role is enumerated, usually following an overgenerating heuristic;2
let this set of spans be St . We include the null span ∅in St ; connecting it to a role r ∈ Rf denotes that therole is not overt. Our approach assumes a scoring
function that gives a strength of association between
roles and candidate spans. For each role r ∈ Rf andspan s ∈ St , this score is parameterized as:c(r, s) = ψ · h(t, f, x, r, s),(1)where ψ are model weights and h is a feature function that looks at the predicate t, the evoked frame
f , sentence x, and its syntactic analysis, along with
2

Here, as in most SRL literature, role fillers are assumed to be
expressed as contiguous spans, though such an assumption iseasy to relax in our framework.

r and s. The SRL literature provides many featurefunctions of this form and many ways to use machine learning to acquire ψ. Our presented method
does not make any assumptions about the score except that it has the form in Eq. 1.
We define a vector z of binary variables zr,s ∈{0, 1} for every role and span pair. We have that:z ∈ {0, 1}d , where d = |Rf | × |St |. zr,s = 1 meansthat role r is filled by span s. Given the binary z vector, it is straightforward to recover the collection ofarguments by checking which components zr,s havean assignment of 1; we use this strategy to find arguments, as described in §4.2 (strategies 4 and 6). The
joint argument identification task can be represented
as a constrained optimization problem:PP
maximizer∈Rfs∈St c(r, s) × zr,swith respect toz ∈ {0, 1}dsuch thatAz ≤ b.

(2)

The last line imposes constraints on the mapping between roles and spans; these are motivated on linguistic grounds and are described next.3
Uniqueness: Each role r is filled by at most one
span in St . This constraint can be expressed by:P∀r ∈ Rf , s∈St zr,s = 1.
(3)
There are O(|Rf |) such constraints. Note that since
St contains the null span ∅, non-overt roles are also
captured using the above constraints. Such a constraint is used extensively in prior literature (Punyakanok et al., 2008, §3.4.1).
Overlap: SRL systems commonly constrain roles
to be filled by non-overlapping spans. For example,
Toutanova et al. (2005) used dynamic programmingover a phrase structure tree to prevent overlaps between arguments, and Punyakanok et al. (2008) used3

Note that equality constraints a · z = b can be transformed into
double-side inequalities a · z ≤ b and −a · z ≤ −b.

constraints in an ILP to respect this requirement. Inspired by the latter, we require that each input sentence position of x be covered by at most one argument. For each role r ∈ Rf , we define:Gr (i) = {s | s ∈ St , s covers position i in x}. (4)We can define our overlap constraints in terms of Gr
as follows, for every sentence position i:PP∀i ∈ {1, . . . , |x|},r∈Rfs∈Gr (i) zr,s ≤ 1, (5)This gives us O(|x|) constraints.
Pairwise “Exclusions”: For many predicateclasses, there are pairs of roles forbidden to appear
together in the analysis of a single predicate token.
Consider the following two sentences:
A blackberry resembles a loganberry.
Entity 1(6)

Entity 2

Most berries resemble each other.

(7)

Entities

Consider the uninflected predicate resemble inboth sentences, evoking the same meaning. In example 6, two roles, which we call Entity 1 and Entity 2
describe two entities that are similar to each other.
In the second sentence, a phrase fulfills a third role,called Entities, that collectively denotes some objects that are similar. It is clear that the roles Entity 1
and Entities cannot be overt for the same predicate
at once, because the latter already captures the function of the former; a similar argument holds for the
Entity 2 and Entities roles. We call this phenomenon
the “excludes” relationship. Let us define a set ofpairs from Rf that have this relationship:
Excl f = {(ri , rj ) | ri and rj exclude each other}
Using the above set, we define the constraint:∀(ri , rj ) ∈ Excl f , zri ,∅ + zrj ,∅ ≥ 1(8)

In English: if both roles are overt in a parse, thisconstraint will be violated, and we will not respect
the “excludes” relationship between the pair. If neither or only one of the roles is overt, the constraint
is satisfied. The total number of such constraints isO(|Excl f |), which is the number of pairwise “excludes” relationships of a given frame.
Pairwise “Requirements”: The sentence in example 6 illustrates another kind of constraint. The predicate resemble cannot have only one of Entity 1 andEntity 2 as roles in text. For example,* A blackberry resembles.

(9)

Entity 1

Enforcing the overtness of two roles sharing this“requires” relationship is straightforward. We define
the following set for a frame f :Req f = {(ri , rj ) | ri and rj require each other}
This leads to constraints of the form∀(ri , rj ) ∈ Req f , zri ,∅ − zrj ,∅ = 0(10)

If one role is overt (or absent), so must the otherbe. A related constraint has been used previously
in the SRL literature, enforcing joint overtness relationships between core arguments and referential
arguments (Punyakanok et al., 2008, §3.4.1), which
are formally similar to the example above.4
Integer Linear Program and Relaxation: Plugging the constraints in Eqs. 3, 5, 8 and 10 into thelast line of Eq. 2, we have the argument identification problem expressed as an ILP, since the indicator variables z are binary. In this paper, apart fromthe ILP formulation, we will consider the following relaxation of Eq. 2, which replaces the binary
constraint z ∈ {0, 1}d by a unit interval constraintz ∈ [0, 1]d , yielding a linear program:PPmaximizer∈Rfs∈St c(r, s) × zr,swith respect toz ∈ [0, 1]dsuch thatAz ≤ b.

(11)

There are several LP and ILP solvers available,
and a great deal of effort has been spent by the
optimization community to devise efficient genericsolvers. An example is CPLEX, a state-of-the-art
solver for mixed integer programming that we employ as a baseline to solve the ILP in Eq. 2 as wellas its LP relaxation in Eq. 11. Like many of the best
implementations, CPLEX is proprietary.
4

We noticed in the annotated data, in some cases, the “requires”
constraint is violated by the FrameNet annotators. This happens mostly when one of the required roles is absent in thesentence containing the predicate, but is rather instantiated inan earlier sentence; see Gerber and Chai (2010). We apply the
hard constraint in Eq. 10, though extending our algorithm toseek arguments outside the sentence is straightforward (Chenet al., 2010).

2.2

Linguistic Constraints from FrameNeta pair of roles that share the “requires” relationship.

Although enforcing the four different sets of constraints above is intuitive from a general linguistic
perspective, we ground their use in definitive linguistic information present in the FrameNet lexicon(Fillmore et al., 2003). FrameNet, along with listsof semantic frames, associated semantic roles, andpredicates that could evoke the frames, gives us asmall number of annotated sentences with framesemantic analysis. From the annotated data, wegathered that only 3.6% of the time is a role instantiated multiple times by different spans in a sentence.
This justifies the uniqueness constraint enforced by
Eq. 3. Use of such a constraint is also consistent
with prior work in frame-semantic parsing (Johansson and Nugues, 2007; Das et al., 2010a). Similarly,
we found that in the annotations, no arguments overlapped with each other for a given predicate. Hence,
the overlap constraints in Eq. 5 are also justified.
Our third and fourth sets of constraints, presented
in Eqs. 8 and 10, come from FrameNet, too; moreover, they are explicitly mentioned in the lexicon.
Examples 6–7 are instances where the predicate resemble evokes the S IMILARITY frame, which is defined in FrameNet as: “Two or more distinct entities, which may be concrete or abstract objects
or types, are characterized as being similar to eachother. Depending on figure/ground relations, theentities may be expressed in two distinct frame elements and constituents, Entity 1 and Entity 2, or
jointly as a single frame element and constituent,
Entities.”
For this frame, the lexicon lists several roles otherthan the three roles we have already observed, suchas Dimension (the dimension along which the entities are similar), Differentiating fact (a fact that reveals how the concerned entities are similar or different), and so forth. Along with the roles, FrameNet
also declares the “excludes” and “requires” relationships noted in our discussion in Section 2.1. The
case of the S IMILARITY frame is not unique; in Fig. 1,
the frame C OLLABORATION, evoked by the predicate
partners, also has two roles Partner 1 and Partner 2that share the “requires” relationship. In fact, outof 877 frames in FrameNet 1.5, the lexicon’s latest
edition, 204 frames have at least a pair of roles thatshare the “excludes” relationship, and 54 list at least

2.3 Constraints as Factors in a Graphical Model
The LP in Eq. 11 can be represented as a maximum a posteriori (MAP) inference problem in an
undirected graphical model. In the factor graph,each component of z corresponds to a binary variable, and each instantiation of a constraint in
Eqs. 3, 5, 8 and 10 corresponds to a factor. Smithand Eisner (2008) and Martins et al. (2010) usedsuch a representation to impose constraints in a dependency parsing problem; the latter discussed theequivalence of linear programs and factor graphs forrepresenting discrete optimization problems. Eachof our constraints take standard factor forms we candescribe using the terminology of Smith and Eisner(2008) and Martins et al. (2010). The uniquenessconstraint in Eq. 3 corresponds to an X OR factor,
while the overlap constraint in Eq. 5 corresponds toan AT M OST O NE factor. The constraints in Eq. 8
enforcing the “excludes” relationship can be represented with an O R factor. Finally, each “requires”
constraints in Eq. 10 is equivalent to an X ORW ITH O UTPUT factor.
In the following section, we describe how we arrive at solutions for the LP in Eq. 11 using dual decomposition, and how we adapt it to efficiently recover the exact solution of the ILP (Eq. 2), without
the need of an off-the-shelf ILP solver.

3“Augmented” Dual Decomposition

Dual decomposition methods address complex optimization problems in the dual, by dividing theminto simple worker problems, which are repeatedly solved until a consensus is reached. The
most simple technique relies on the subgradientalgorithm (Komodakis et al., 2007; Rush et al.,2010); as an alternative, an augmented Lagrangian
technique was proposed by Martins et al. (2011a,
2011b), which is more suitable when there are manysmall components—commonly the case in declarative constrained problems, such as the one at hand.
Here, we present a brief overview of the latter, whichis called Dual Decomposition with the Alternating
Direction Method of Multipliers (AD3 ).
Let us start by establishing some notation. Letm ∈ {1, . . . , M } index a factor, and denote by i(m)the vector of indices of variables linked to that factor. (Recall that each factor represents the instantiation of a constraint.) We introduce a new set of variables, u ∈ Rd , called the “witness” vector. We split
the vector z into M overlapping pieces z1 , . . . , zM ,where each zm ∈ [0, 1]|i(m)| , and add M constraints
zm = ui(m) to impose that all the pieces must agreewith the witness (and therefore with each other).
Each of the M constraints described in §2 can be
encoded with its own matrix Am and vector bm(which jointly define A and b in Eq. 11). For convenience, we denote by c ∈ Rd the score vector, whose
components are c(r, s), for each r ∈ Rf and s ∈ St
(Eq. 1), and define the following scores for the mth
subproblem:−1

cm (r, s) = δ(r, s)c(r, s), ∀(r, s) ∈ i(m), (12)where δ(r, s) is the number of constraints that involve role r and span
P s. Note that according to thisdefinition, c · z = M
m=1 cm · zm . We can rewrite
the LP in Eq. 11 in the following equivalent form:MX

maximizecm · zmwith respect to u ∈ Rd , zm ∈ [0, 1]i(m) ,A m z m ≤ bm ,∀mzm = ui(m) ,

∀m.

∀m
(13)

We next augment
a quadratic
P the objective with
2 (for some ρ >penalty term ρ2 M
kz
−
u
k
m
i(m)
m=1
0). This does not affect the solution of the problem,since the equality constraints in the last line force
this penalty to vanish. However, as we will see, thispenalty will influence the workers and will lead tofaster consensus. Next, we introduce Lagrange multipliers λm for those equality constraints, so that theaugmented Lagrangian function becomes:Lρ (z, u, λ) =MX

1: input:• role-span matching scores c := hc(r, s)ir,s ,• structural constraints hAm , bm iM
m=1 ,• penalty ρ > 0
2: initialize u uniformly (i.e., u(r, s) = 0.5, ∀r, s)
3: initialize each λm = 0, ∀m ∈ {1, . . . , M }4: initialize t ← 1
5: repeat6:
for each m = 1, . . . , M do
7:make a zm -update by finding the best scoring
analysis for the mth constraint, with penalties
for deviating from the consensus u:ρt+1
zm ← arg max (cm +λm )·zm − kzm −ui(m) k2
2
Am zm ≤bm8:
9:

end formake a u-update by updating the consensus solution, averaging z1 , . . . , zm :
X
1
t+1
zm
(r, s)
ut+1 (r, s) ←δ(r, s)m:(r,s)∈i(m)10:make a λ-update:
(t+1)

t
(t+1)
− ui(m) ),λt+1
m ← λm − ρ(zmm=1

such that

Algorithm 1 AD3 for Argument Identification(cm + λm ) · zm − λm · ui(m)m=1

ρ− kzm − ui(m) k2 .
(14)
2
The AD3 algorithm seeks a saddle point of Lρ byperforming alternating maximization with respect toz and u, followed by a gradient update of λ. The result is shown as Algorithm 1. Like dual decomposition approaches, it repeatedly performs a broadcast
operation (the zm -updates, which can be done in pa-

∀m

11:
t←t+1
12: until convergence.
13: output: relaxed primal solution u∗ and dual solution

λ∗ . If u∗ is integer, it will encode an assignment ofspans to roles. Otherwise, it will provide an upperbound of the true optimum.

-rallel, one constraint per “worker”) and a gather operation (the u- and λ-updates). Each u-operation
can be seen as an averaged voting which takes into
consideration each worker’s results.
Like in the subgradient method, the λ-updates canbe regarded as price adjustments, which will affectthe next round of zm -updates. The only differencewith respect to the subgradient method (Rush et al.,2010) is that each subproblem involved in a zm update also has a quadratic penalty that penalizes deviations from the previous average voting; it is thisterm that accelerates consensus and therefore convergence. Martins et al. (2011b) also provide stopping criteria for the iterative updates using primaland dual residuals that measure convergence; we refer the reader to that paper for details.
A key attraction of this algorithm is all the components of the declarative specification remain intact

in the procedural form. Each worker corresponds
exactly to one constraint in the ILP, which corresponds to one linguistic constraint. There is no need
to work out when, during the procedure, each constraint might have an effect, as in beam search.
Solving the subproblems. In a different application, Martins et al. (2011b, §4) showed how
to solve each zm -subproblem associated with the
X OR, X ORW ITH O UTPUT and O R factors in runtime
O(|i(m)| log |i(m)|). The only subproblem that remains is that of the AT M OST O NE factor, to which
we now turn. The problem can be transformed intothat of projecting a point (a1 , . . . , ak ) onto the setno
P|i(m)|
Sm = zm ∈ [0, 1]|i(m)|j=1 zm,j ≤ 1 .
This projection can be computed as follows:
1. Clip each aj into the interval [0, 1] (i.e., set
a0j = min{max{aj , 0}, 1}). If the result satisfies
Pk000
j=1 aj ≤ 1, then return (a1 , . . . , ak ).
2. Otherwise project (a1 , . . . , ak ) onto the probability simplex:no
P|i(m)|
zm ∈ [0, 1]|i(m)|
z
=
1
.
m,j
j=1
This is precisely the XOR subproblem and can besolved in time O(|i(m)| log |i(m)|).
Caching. As mentioned by Martins et al. (2011b),
as the algorithm comes close to convergence, many
subproblems become unchanged and their solutions
can be cached. By caching the subproblems, wemanaged to reduce runtime by about 60%.
Exact decoding. Finally, it is worth recalling that
AD3 , like other dual decomposition algorithms,
solves a relaxation of the actual problem. Although
we have observed that the relaxation is often tight—
cf. §4—this is not always the case. Specifically, afractional solution may be obtained, which is not interpretable as an argument, and therefore it is desirable to have a strategy to recover the exact solution. Two observations are noteworthy. First, theoptimal value of the relaxed problem (Eq. 11) provides an upper bound to the original problem (Eq. 2).
This is because Eq. 2 has the additional integer constraint on the variables. In particular, any feasible
dual point provides an upper bound to the original

problem’s optimal value. Second, during executionof the AD3 algorithm, we always keep track of a sequence of feasible dual points. Therefore, each iteration constructs tighter and tighter upper bounds.
With this machinery, we have all that is necessary for
implementing a branch-and-bound search that finds
the exact solution of the ILP. The procedure works
recursively as follows:
1. Initialize L = −∞ (our best value so far).
2. Run Algorithm 1. If the solution u∗ is integer, return u∗ and set L to the objective value. If along
the execution we obtain an upper bound less thanL, then Algorithm 1 can be safely stopped andreturn “infeasible”—this is the bound part. Otherwise (if u∗ is fractional) go to step 3.
3. Find the “most fractional” component of u∗ (callit u∗j ) and branch: constrain uj = 0 and go tostep 2, eventually obtaining an integer solution u∗0or infeasibility; and then constrain uj = 1 and do
the same, obtaining u∗1 . Return the u∗ ∈ {u∗0 , u∗1 }that yields the largest objective value.
Although this procedure may have worst-case exponential runtime, we found it empirically to rapidly
obtain the exact solution in all test cases.

4

Experiments and Results

4.1

Dataset, Preprocessing, and Learning

In our experiments, we use FrameNet 1.5, whichcontains a lexicon of 877 frames and 1,068 rolelabels, and 78 documents with multiple predicateargument annotations (a superset of the SemEval
shared task dataset; Baker et al., 2007). We used thesame split as Das and Smith (2011), with 55 documents for training (containing 19,582 frame annotations) and 23 for testing (with 4,458 annotations).
We randomly selected 4,462 predicates in the training set as development data. The raw sentences in all
the training and test documents were preprocessedusing MXPOST (Ratnaparkhi, 1996) and the MST
dependency parser (McDonald et al., 2005).
The state-of-the-art system for this task is SEMAFOR, an open source tool (Das et al., 2010a)5that provides a baseline benchmark for our new algorithm. We use the components of SEMAFOR
as-is to define the features h and train the weights
ψ used in the scoring function c. We also use its
5

http://www.ark.cs.cmu.edu/SEMAFORheuristic mechanism to find potential spans St for agiven predicate t. SEMAFOR learns weights using`2 -penalized log-likelihood; we augmented its dev
set-tuning procedure to tune both the regularization
strength and the AD3 penalty strength ρ. We initialize ρ = 0.1 and follow Martins et al. (2011b)
in dynamically adjusting it. Note that we do not use
SEMAFOR’s automatic frame identification component in our presented experiments, as we assume that
we have gold frames on each predicate. This lets us
compare the different argument identification methods in a controlled fashion.
4.2

Decoding Strategies

We compare the following algorithms:
1. Local: this is a naı̈ve argument identification
strategy that selects the best span for each role r,
according to the score function c(r, s). It ignores
all constraints except “uniqueness.”
2. SEMAFOR: this strategy employs greedy beam
search to eliminate overlaps between predicted arguments (Das et al., 2010b, Algorithm 1). Notethat it does not try to respect the “excludes” and“requires” constraints between pairs of roles. The
default size of the beam in SEMAFOR was a safe
10,000; this resulted in extremely slow decoding
times. We also tried beam sizes of 100 and 2(the latter being the smallest size that achieves thesame F1 score on the dev set as beam width 100.)
3. CPLEX, LP: this uses CPLEX to solve the relaxed LP in Eq. 11. To handle fractional z, foreach role r, we choose the best span s∗ , such thats∗ = arg maxs∈Sr zr,s , solving ties arbitrarily.
4. CPLEX, exact: this tackles the actual ILP (Eq. 2)
with CPLEX.
5. AD3 , LP: this is the counterpart of the LP versionof CPLEX, where the relaxed problem is solved
using AD3 . We choose the spans for each role inthe same way as in strategy 3.
6. AD3 , exact: this couples AD3 with branch-andbound search to get the exact integer solution.
4.3

Resultsize structural violations, we also report the numberof overlap, “excludes,” and “requires” constraints
that were violated in the test set. Finally, we tabulate each setting’s decoding time in seconds on thewhole test set averaged over 5 runs.7 The Local
model is very fast but suffers degradation in precision and violates one constraint roughly per ninepredicates. SEMAFOR used a default beam size of
10,000, which is extremely slow; a faster version ofbeam size 100 results in the same precision and recall values, but is 15 times faster. Beam size 2 resultsin slightly worse precision and recall values, but iseven faster. All of these, however, result in many
constraint violations. Strategies involving CPLEX
and AD3 perform similarly to each other and SEMAFOR on precision and recall, but eliminate mostor all of the constraint violations. SEMAFOR withbeam size 2 is 11-16 times faster than the CPLEX
strategies, but is only twice as fast than AD3 , and results in significantly more structural violations. The
exact algorithms are slower than the LP versions, but
compared to CPLEX, AD3 is significantly faster andhas a narrower gap between its exact and LP versions. We found that relaxation was tight 99.8% of
the time on the test examples.
The example in Fig. 1 is taken from our test set,and shows an instance where two roles, Partner 1
and Partner 2 share the “requires” relationship; forthis example, the beam search decoder misses thePartner 2 role, which is a violation, while our AD3
decoder identifies both arguments correctly. Notethat beam search makes plenty of linguistic violations, but has precision and recall values that are
marginally better than AD3 . We found that beam
search, when violating many “requires” constraints,
often finds one role in the pair, which increases its
recall. AD3 is sometimes more conservative in suchcases, predicting neither role. A second issue, as
noted in footnote 4, is that the annotations sometimes violate these constraints. Overall, we foundit interesting that imposing the constraints did nothave much effect on standard measures of accuracy.
7

Table 1 shows performance of the different decoding
strategies on the test set. We report precision, recall,and F1 scores.6 Since these scores do not penal6

We use the evaluation script from SemEval 2007 shared task,
modified to evaluate only the argument identification output.

We used a 64-bit machine with 2 2.6GHz dual-core CPUs (i.e.,
4 processors in all) with a total of 8GB of RAM. The workers in AD3 were not parallelized, while CPLEX automaticallyparallelized execution.

Method
Local
SEMAFOR (beam = 2)
SEMAFOR (beam = 100)
SEMAFOR (beam = 10000)
CPLEX, LP
CPLEX, exact
AD3 , LP
AD3 , exact

P
67.69
70.18
70.43
70.43
70.34
70.31
70.30
70.31

R
59.76
59.54
59.64
59.64
59.43
59.45
59.45
59.45

F1
63.48
64.42
64.59
64.59
64.43
64.43
64.42
64.43

Overlap
441
0
0
0
0
0
2
0

Violations
Requires Excludes
45
15
49
0
50
1
50
1
1
0
0
0
2
0
0
0

Time in Secs.
1.26 ± 0.01
2.74 ± 0.10
29.00 ± 0.25
440.67 ± 5.53
32.67 ± 1.29
43.12 ± 1.26
4.17 ± 0.01
4.78 ± 0.04

Table 1: Comparison of decoding strategies in §4.2. We evaluate in terms of precision, recall and F1 score on a test
set containing 4,458 predicates. We also compute the number of structural violations each model makes: numberof overlapping arguments and violations of the “requires” and “excludes” constraints of §2. Finally decoding time(without feature computation steps) on the whole test set is shown in the last column averaged over 5 runs.

5

Related Work

Semantic role labeling: Most SRL systems use
conventions from PropBank (Kingsbury and Palmer,
2002) and NomBank (Meyers et al., 2004), which
store information about verbal and nominal predicates and corresponding symbolic and meaningspecific semantic roles. A separate line of work,
including this paper, investigates SRL systems thatuse FrameNet conventions; while less popular, thesesystems, pioneered by Gildea and Jurafsky (2002),
consider predicates of a wider variety of syntactic
categories, use semantic frame abstractions, and employ explicit role labels. A common trait in priorwork has been the use of a two-stage model that
identifies arguments first, then labels them. They aretreated jointly here, unlike what has typically been
done in PropBank-style SRL (Màrquez et al., 2008).
Dual decomposition: Rush et al. (2010) proposed
subgradient-based dual decomposition as a way of
combining models which are tractable individually,
but not jointly, by solving a relaxation of the original problem. This was followed by work adopting
this method for syntax and translation (Koo et al.,2010; Auli and Lopez, 2011; DeNero and Macherey,
2011; Rush and Collins, 2011; Chang and Collins,2011). Recently, Martins et al. (2011b) showed thatthe success of subgradient-based dual decomposition strongly relies on breaking down the original
problem into a “good” decomposition, i.e., one withfew overlapping components. This leaves out many
declarative constrained problems, for which such agood decomposition is not readily available. For
those, Martins et al. (2011b) proposed the AD3 al-

gorithm, which retains the modularity of previous
methods, but can handle thousands of small overlapping components.
Exact decoding: This paper contributes an exact
branch-and-bound technique wrapped around AD3 .
A related line of research is that of Rush and Collins(2011), who proposed a tightening procedure fordual decomposition, which can be seen as a cutting
plane method (another popular approach in combinatorial optimization).

6

Conclusion

We presented a novel algorithm for incorporating
declarative linguistic knowledge as constraints inshallow semantic parsing. It outperforms a naı̈ve
baseline that is oblivious to the constraints. Furthermore, it is significantly faster than a decoder employing a state-of-the-art proprietary solver, and lessthan twice as slow as beam search, which is inexact
and does not respect all linguistic constraints. Our
method is easily amenable to the inclusion of moreconstraints, which would require minimal programming effort. Our implementation of AD3 within
SEMAFOR will be publicly released at http://
www.ark.cs.cmu.edu/SEMAFOR.

Acknowledgments
We thank the three anonymous reviewers for their valuable feedback. This material is based upon work supported by NSF grant IIS-1054319, Google’s supportof the Wordly Knowledge Project, a FCT/ICTI grantthrough the CMU-Portugal Program, and by Priberam,through the Discooperio project, contract 2011/18501 of
the EU/FEDER program.

References
M. Auli and A. Lopez. 2011. A comparison of loopy belief propagation and dual decomposition for integrated
ccg supertagging and parsing. In Proc. of ACL.
C. Baker, M. Ellsworth, and K. Erk. 2007. SemEval2007 Task 19: Frame semantic structure extraction. In
Proc. of SemEval.
Y.-W. Chang and Michael Collins. 2011. Exact decodingof Phrase-Based translation models through lagrangian
relaxation. In Proc. of EMNLP. Association for Computational Linguistics.
D. Chen, N. Schneider, D. Das, and N. A. Smith.
2010. SEMAFOR: Frame argument resolution with
log-linear models. In Proc. of SemEval.
D. Das and N. A. Smith. 2011. Semi-supervised framesemantic parsing for unknown predicates. In Proc. of
ACL.
D. Das, N. Schneider, D. Chen, and N. A. Smith. 2010a.
Probabilistic frame-semantic parsing. In Proc. of
NAACL-HLT.
D. Das, N. Schneider, D. Chen, and N. A. Smith. 2010b.
SEMAFOR 1.0: a probabilistic frame-semantic parser.
Technical report, CMU-LTI-10-001.
J. DeNero and K. Macherey. 2011. Model-based aligner
combination using dual decomposition. In Proc. of
ACL.
C. J. Fillmore, C. R. Johnson, and M. R.L. Petruck. 2003.
Background to FrameNet. International Journal of
Lexicography, 16(3).
C. J. Fillmore. 1982. Frame Semantics. In Linguistics in
the Morning Calm. Hanshin.
M. Gerber and J. Y. Chai. 2010. Beyond nombank: A
study of implicit arguments for nominal predicates. In
ACL.
D. Gildea and D. Jurafsky. 2002. Automatic labeling of
semantic roles. Computational Linguistics, 28(3).
R. Johansson and P. Nugues. 2007. LTH: semantic structure extraction using nonprojective dependency trees.
In Proc. of SemEval.
P. Kingsbury and M. Palmer. 2002. From TreeBank to
PropBank. In Proc. of LREC.
N. Komodakis, N. Paragios, and G. Tziritas. 2007.
MRF optimization via dual decomposition: Messagepassing revisited. In ICCV.
T. Koo, A. M. Rush, M. Collins, T. Jaakkola, and D. Sontag. 2010. Dual decomposition for parsing with nonprojective head automata. In Proc. of EMNLP.
L. Màrquez, X. Carreras, K. C. Litkowski, and S. Stevenson. 2008. Semantic role labeling: an introduction to
the special issue. Computational Linguistics, 34(2).
A. F. T. Martins, N. A. Smith, E. P. Xing, M. A. T.
Figueiredo, and P. M. Q. Aguiar. 2010. Turbo parsers:

Dependency parsing by approximate variational inference. In EMNLP.
A. F. T. Martins, M. A. T. Figueiredo, P. M. Q. Aguiar,
N. A. Smith, and E. P. Xing. 2011a. An augmented
Lagrangian approach to constrained MAP inference.
In Proc. of ICML.
A F. T. Martins, N. A. Smith, P. M. Q. Aguiar, and
M. A. T. Figueiredo. 2011b. Dual decomposition withmany overlapping components. In Proc. of EMNLP.
R. McDonald, K. Crammer, and F. Pereira. 2005. Online
large-margin training of dependency parsers. In Proc.
of ACL.
A. Meyers, R. Reeves, C. Macleod, R. Szekely, V. Zielinska, B. Young, and R. Grishman. 2004. The
NomBank project: An interim report. In Proc. of
NAACL/HLT Workshop on Frontiers in Corpus Annotation.
V. Punyakanok, D. Roth, W.-T. Yih, and D. Zimak. 2004.
Semantic role labeling via integer linear programming
inference. In Proc. of COLING.
V. Punyakanok, D. Roth, and W Yih. 2008. The importance of syntactic parsing and inference in semanticrole labeling. Computational Linguistics, 34:257–287.
A. Ratnaparkhi. 1996. A maximum entropy model forpart-of-speech tagging. In Proc. of EMNLP.
A. M. Rush and M. Collins. 2011. Exact decoding ofsyntactic translation models through lagrangian relaxation. In Proc. of ACL.
A. M. Rush, D. Sontag, M. Collins, and T. Jaakkola.
2010. On dual decomposition and linear programming
relaxations for natural language processing. In Proceedings of EMNLP.
D. Smith and J. Eisner. 2008. Dependency parsing bybelief propagation. In EMNLP.
K. Toutanova, A. Haghighi, and C. Manning. 2005. Joint
learning improves semantic role labeling. In Proc. ofACL.