Priberam: A Turbo Semantic Parser with Second Order Features
André F. T. Martins∗†
Mariana S. C. Almeida∗†∗
Priberam Labs, Alameda D. Afonso Henriques, 41, 2o , 1000-123 Lisboa, Portugal†
Instituto de Telecomunicações, Instituto Superior Técnico, 1049-001 Lisboa, Portugal{atm,mla}@priberam.pt

Abstract
This paper presents our contribution to
the SemEval-2014 shared task on BroadCoverage Semantic Dependency Parsing.
We employ a feature-rich linear model, including scores for first and second-orderdependencies (arcs, siblings, grandparents
and co-parents). Decoding is performed ina global manner by solving a linear relaxation with alternating directions dual decomposition (AD3 ). Our system achieved
the top score in the open challenge, and thesecond highest score in the closed track.

1

Introduction

The last decade saw a considerable progress in statistical modeling for dependency syntactic parsing (Kübler et al., 2009). Models that incorporaterich global features are typically more accurate,even if pruning is necessary or decoding needs tobe approximate (McDonald et al., 2006; Koo andCollins, 2010; Bohnet and Nivre, 2012; Martins etal., 2009, 2013). This paper applies the same rationale to semantic dependency parsing, in which
the output variable is a semantic graph, rather
than a syntactic tree. We extend a recently proposed dependency parser, TurboParser (Martins etal., 2010, 2013), to be able to perform semantic
parsing using any of the three formalisms considered in this shared task (DM, PAS, and PCEDT).
The result is TurboSemanticParser, which we release as open-source software.1
We describe here a second order model for semantic parsing (§2). We follow prior work in semantic role labeling (Toutanova et al., 2005; JoThis work is licensed under a Creative Commons Attribution 4.0 International Licence. Page numbers and proceedings footer are added by the organisers. Licence details:
http://creativecommons.org/licenses/by/4.0/
1
http://labs.priberam.com/Resources/
TurboSemanticParser

Figure 1: Example of a semantic graph in the DM
formalism (sentence #22006003). We treat top
nodes as a special semantic role TOP whose predicate is a dummy root symbol.
hansson and Nugues, 2008; Das et al., 2012; Flanigan et al., 2014), by adding constraints and modeling interactions among arguments within the same
frame; however, we go beyond such sibling interactions to consider more complex grandparent and co-parent structures, effectively correlating different predicates. We formulate parsing asa global optimization problem and solve a relaxation through AD3 , a fast dual decomposition algorithm in which several simple local subproblems are solved iteratively (§3). Through a rich
set of features (§4), we arrive at top accuracies atparsing speeds around 1,000 tokens per second, as
described in the experimental section (§5).

2

A Second Order Model for Parsing

Figure 1 depicts a sentence and its semantic graph.
We cast semantic parsing as a structured prediction problem. Let x be a sentence and Y(x) the
set of possible dependency graphs. We assume
each candidate graph y ∈ Y(x) can be represented as a set of substructures (called parts) inan underlying set S (e.g., predicates, arcs, pairsof adjacent arcs). We design a score function fwhich decomposes
Pas a sum over these substructures, f (x, y) := s∈S fs (x, ys ). We parametrize
this function using a weight vector w, and write
each atomic function as fs (x, ys ) := w·φs (x, ys ),where φs (x, ys ) is a vector of local features. The
decoding problem consists in obtaining the best-

Algorithm 1 Decoding in an Arc-Factored Model
1: input: Predicate scores σP (p), arc scores σA (p → a),rlabeled arc scores σLA (p → a).
2: Initialize semantic graph G ← ∅3: for p = 0 to L do
4:
Initialize σ ← σP (p), frame A(p) ← ∅5:for a = 1 to L dor
6:
Set r0 ← arg maxr σLA (p → a)r0

if σA (p → a) + σLA (p → a) > 0 thenA(p) ← A(p) ∪ {hp, a, r0 i}

7:
8:

r0

9:
σ ← σ + σA (p → a) + σLA (p → a)10:
end if
11:
end for12:
if σ > 0 then set G ← G ∪ {hp, A(p)i}13: end for
14: output: semantic graph G.

scored semantic graph yb given a sentence x:
yb = arg max f (x, y).
y∈Y(x)(1)

Our choice of parts is given in Figure 2. The second order parts are inspired by prior work in syntactic parsing, modeling interactions for pairs of(unlabeled) dependency arcs, such as grandparents (Carreras, 2007) and siblings (Smith and Eisner, 2008; Martins et al., 2009). The main novelty
is co-parent parts, which, to the best of our knowledge, were never considered before, as they only
make sense when multiple parents are allowed.
If all parts were basic, decoding could be done
independently for each predicate p, as illustrated
in Algorithm 1. The total runtime, for a sentencewith L words, is O(L2 |R|), where R is the setof semantic roles. Adding consecutive siblings
still permits independent decoding for each predicate, but dynamic programming is necessary to
decode the best argument frame, increasing theruntime to O(L3 |R|). The addition of consecutive co-parents, grandparents, and arbitrary siblings and co-parents breaks this independency andsets a demand for approximate decoding. Even
without second-order parts, the inclusion of hardconstraints (such as requiring some roles to be
unique, see §3) also makes the problem harder.2
Rather than looking for a model in which exact
decoding is tractable, which could be even more
stringent for parsing semantic graphs than for dependency trees, we embrace approximate decoding strategies. Namely, our approach is based on
2

Albeit the dynamic program could still incorporate constraints for unique roles (by appending a bit-string to the state
to mark semantic roles that have been filled), runtime becomes exponential in the number of unique roles, only being
feasible when this number is small.

Figure 2: Parts considered in this paper. The
top row illustrate the basic parts, representing theevent that a word is a predicate, or the existence ofan arc between a predicate and an argument, eventually labeled with a semantic role. Our secondorder model looks at some pairs of arcs: arcs bearing a grandparent relationship, arguments of thesame predicate, predicates sharing the same argument, and consecutive versions of these two.
dual decomposition, a class of optimization techniques that tackle the dual of combinatorial problems in a modular and extensible manner (Komodakis et al., 2007; Rush et al., 2010). We employ alternating directions dual decomposition(AD3 ; Martins et al., 2011). Like the subgradient algorithm of Rush et al. (2010), AD3 splits
the original problem into local subproblems, andseeks an agreement on the overlapping variables.
The difference is that the AD3 subproblems havean additional quadratic term to accelerate consensus, achieving a faster convergence rate bothin theory and in practice (Martins et al., 2012,2013). For several factors (such as logic factors
representing AND, OR and XOR constraints, budget constraints, and binary pairwise factors), thesequadratic subproblems can be solved efficiently.
For dense or structured factors, the quadratic subproblems can be solved as a sequence of local
Viterbi decoding steps, via an active set method(Martins, 2014); this local decoding operation is
the same that needs to be performed in the subgradient algorithm. We describe these subproblems
in detail in the next section.

3

Solving the Subproblems

Predicate and Arc-Factored Parts. We capture
all the basic parts with a single component. As
stated in §2, local decoding in this component has
a runtime of O(L2 |R|), by using Algorithm 1.
Unique Roles. We assume some roles are
unique, i.e., they can occur at most once for thesame predicate.3 To cope with unique roles, we
add hard constraints of the kindPr(2)
a I(p → a ∈ y) ≤ 1, ∀p, ∀r ∈ Runiq ,where Runiq is the set of unique roles. This set is
obtained from the training data by looking at theroles that never occur multiple times in the goldargument frames.4 The constraint above corresponds to a AT M OST O NE factor, which is built-in
in AD3 and can be decoded in linear time (rendering the runtime O(L2 |Runiq |) when aggregating all such factors). These have also been usedby Das et al. (2012) in frame-semantic parsing.
Grandparents, Arbitrary Siblings and Coparents. The second-order parts in the middle
row of Figure 2 all involve the simultaneous inclusion of a pair of arcs, without further dependency
on the remaining arcs. We handle each of theseparts using a simple pairwise factor (called PAIRin the AD3 toolkit). The total runtime to locallydecode these factors is O(L3 ).
Predicate Automata. To handle consecutive
siblings, we adapt the simple head automaton
model (Alshawi, 1996; Smith and Eisner, 2008;
Koo et al., 2010) to semantic parsing. We introduce one automaton for each predicate p andattachment direction (left or right). We describe
right-side predicate automata; their left-side counterparts are analogous. Let ha0 , a1 , . . . , ak+1 i be
the sequence of right modifiers of p, with a0 =START and ak+1 = END . Then, we have the following component capturing consecutive siblings:
CSIB
fp,→
(p → a1 , . . . , p → ak ) =Pk+1
j=1 σCSIB (p, aj−1 , aj ).

(3)

CSIB
via dynamic programming has
Maximizing fp,→2
a cost of O(L ), yielding O(L3 ) total runtime.

Argument Automata. For consecutive coparents, we introduce another automaton which isanalogous to the predicate automaton, but wherearrows are reversed. Let hp0 , p1 , . . . , pk+1 i be
the sequence of right predicates that take a asargument (the left-side case is analagous), with
p0 = START and pk+1 = END. We define:CCP
fa,←(a ← p1 , . . . , a ← pk ) =Pk+1
j=1 σCCP (a, pj−1 , pj ).

(4)3Such roles have been called “deterministic” by Flanigan
et al. (2014).
4
For PAS, all 43 roles were found unique; for DM, thisnumber is 40 out of 52, and for PCEDT only 3 out of 69.

The total runtime is also O(L3 ).

4

FeaturesWe define binary features for each part represented
in Figure 2. Most of the features are taken from
TurboParser (Martins et al., 2013), while others
are inspired by the semantic parser of Johansson
and Nugues (2008). Those features marked with †require information from the dependency syntactic
parser, and are only used in the open track.5
Predicate Features. Our predicate features are:
• P REDW ORD , P RED L EMMA , P RED POS. Lexical form, lemma, and POS tag of the predicate.
• P RED R EL .† Syntactic dependency relation between the predicate and its head.
• P RED H EADW ORD /POS.† Form and POS tagof the predicate syntactic head, conjoined withthe predicate word and POS tag.
• P RED M ODW ORD /POS/R EL .† Form, POS tag,and dependency relation of the predicate syntactic dependents, conjoined with the predicate
word and POS tag.
Arc Features. All features above, plus the following (conjoined with arc direction and label):• A RG W ORD , A RG L EMMA , A RG POS. The lexical form, lemma, and POS tag of the argument.
• A RG R EL .† Syntactic dependency relation between the argument and its head.
• L EFT W ORD /POS,†R IGHT W ORD /POS.†
Form/POS tag of the leftmost/rightmost dependent of the argument, conjoined with thepredicate word and POS tag.
• L EFT S IB W ORD /POS,† R IGHT S IB W ORD /POS.†
Form/POS tag of the left/right sibling of theargument, conjoined with the predicate tag.
• P RED C ONTEXT W ORD , P RED C ONTEXT POS,P RED C ONTEXT L EMMA .
Word, POS, andlemma on the left and right context of the predicate (context size is 2).
• P RED C ONTEXT POSB IGRAM /T RIGRAM . Bigram and trigram of POS tags on the left andright side of the predicate.
• P REDVOICE .† Predicate voice: active, passive,
or none. Determined from the syntactic dependency tree as in Johansson and Nugues (2008).
5
For the open track, the only external information used byour system were the provided automatic dependency trees.

• P REDW ORDA RG W ORD , P REDW ORDA RG POS, P RED POSA RG W ORD , P RED POSA RG POS. Predicate word/tag conjoined withargument word/tag.
• P REDA RG POSC ONTEXT.
Several features
conjoining the POS of words surrounding thepredicate and argument (similar to the contextual features in McDonald et al. (2005)).
• E XACTA RC L ENGTH , B INNEDA RC L ENGTH .
Exact and binned arc length (distance between
predicate and argument), conjoined with thepredicate and argument POS tags.
• POSI N B ETWEEN , W ORD I N B ETWEEN . POS
and forms between the predicate and argument,
conjoined with their own POS tags and forms.
• R EL PATH ,† POSPATH .† Path in the syntactic
dependency tree between the predicate and theargument. The path is formed either by dependency relations or by POS tags.
Second Order Features. These involve a predicate, an argument, and a “companion word”(which can be a second argument, in the case of
siblings, a second predicate, for co-parents, or theargument of another argument, for grandparents).
In all cases, features are of the following kind:• POST RIPLET. POS tags of the predicate, theargument, and the companion word.
• U NILEXICAL . One word form (for the predicate/argument/companion) and two POS tags.
• B ILEXICAL . One POS tag (for the predicate/argument/companion) and two word forms.
• PAIRWISE . Backed-off pair features for thecompanion word form/POS tag and the wordform/POS of the predicate/argument.

5

Experimental Results

To speed up decoding, we discard arcs whose
posterior probability is below 10−4 , according to aprobabilistic unlabeled first-order pruner. Table 1
shows a significant reduction of the search spacewith a very small drop in recall.
Table 2 shows our final results in the test set,
for a model trained in the train and development
partitions. Our system achieved the best score in
the open track (an LF score of 86.27%, averaged
over DM, PAS, and PCEDT), and the second best in
the closed track, after the Peking team. Overall,
we observe that the precision and recall in PCEDT
are far below the other two formalisms, but thisdifference is much smaller when looking at unlabeled scores. Comparing the results in the closed
and open tracks, we observe a consistent improvement in the three formalisms of around 1% in F1
from using syntactic information. While this confirms previous findings that syntactic features areimportant in semantic role labeling (Toutanova etal., 2005; Johansson and Nugues, 2008), these improvements are less striking than expected. We
conjecture this is due to the fact that our model inthe closed track already incorporates a variety ofcontextual features which are nearly as informative as those extracted from the dependency trees.
Finally, to assess the importance of the second
order features, Table 3 reports experiments in thedev-set that progressively add several groups offeatures, along with runtimes. We can see thatsiblings, co-parents, and grandparents all provide
valuable information that improves the final scores(with the exception of the PCEDT labeled scores,
where the difference is negligible). This comesat only a small cost in terms of runtime, which isaround 1,000 tokens per second for the full models.

DM
PAS

All models were trained by running 10 epochs of
max-loss MIRA with C = 0.01 (Crammer et al.,2006). The cost function takes into account mismatches between predicted and gold dependencies, with a cost cP on labeled arcs incorrectlypredicted (false positives) and a cost cR on goldlabeled arcs that were missed (false negatives).
These values were set through cross-validation in
the dev set, yielding cP = 0.4 and cR = 0.6 in allruns, except for the DM and PCEDT datasets in theclosed track, for which cP = 0.3 and cR = 0.7.

PCEDT

UR
# UA/tokLR# LA/tok
99.33 3.5 (13.4%) 99.22 34.4 (2.5%)
99.53 3.3 (12.5%) 99.49 20.8 (1.9%)
99.03 2.1 (8.2%) 98.77 54.5 (3.0%)

Table 1: Pruner statistics in the dev-set, for the
open track. Shown are oracle recall scores, considering both unlabeled (UR) and labeled arcs (LR);and the averaged number of unlabeled and labeled arcs per token that remained after the pruning stage (# UA/tok and # LA/tok). In brackets,
we show the fraction of unlabeled/labeled arcs thatsurvived the pruning.

LP
LR
LF
88.82 87.35 88.08
91.95 89.92 90.93
78.80 74.70 76.70–– 85.24
90.23 88.11 89.16
92.56 90.97 91.76
80.14 75.79 77.90–– 86.27

tially supported by the EU/FEDER programme,
QREN/POR Lisboa (Portugal), under the Intelligo
project (contract 2012/24803) and by a FCT grant
PTDC/EEI-SII/2312/2012.

Table 2: Submitted results for the closed and open
tracks. For comparison, the best-performing system in the closed track (Peking) obtained averaged
UF and LF scores of 91.03% and 85.91%, respectively.

Hiyan Alshawi. 1996. Head automata and bilingual
tiling: Translation with minimal representations. In
Proc. of Annual Meeting of the Association for Computational Linguistics, pages 167–176.

DM , closed
PAS , closed
PCEDT, closed

average, closed
DM , open
PAS , open
PCEDT, open
average, open

UP UR UF90.14 88.65 89.39
93.18 91.12 92.14
90.21 85.51 87.80–– 89.77
91.41 89.26 90.32
93.62 92.01 92.81
91.58 86.61 89.03–– 90.72

DM , arc-factored
DM , arc-factored, pruned+siblings+co-parents+grandparent (full)
PAS , arc-factored
PAS , arc-factored, pruned+siblings+co-parents+grandparent (full)
PCEDT, arc-factored
PCEDT, arc-factored, pruned+siblings+co-parents+grandparent (full)

UF
89.90
89.85
90.34
90.80
90.95
92.34
92.35
92.45
92.71
92.87
87.90
87.74
88.46
90.17
90.18

LF
88.96
88.90
89.34
89.76
89.90
91.40
91.40
91.45
91.71
91.87
79.90
79.83
79.98
79.90
80.03

Tok/sec
1,681
2,642
1,838
1,073
955
1,927
2,914
2,106
1,104
1,043
1,558
2,906
2,066
1,531
1,371

Table 3: Results in the dev-set for the open track,
progressively adding several groups of features,
until the full model is obtained. We report unlabeled/labeled F1 and parsing speeds in tokens
per second. Our speeds include the time necessary
for pruning, evaluating features, and decoding, as
measured on a Intel Core i7 processor @3.4 GHz.

6

Conclusions

We have described a system for broad-coverage
semantic dependency parsing. Our system, whichis inspired by prior work in syntactic parsing, implements a linear model with second-order features, being able to model interactions between
siblings, grandparents and co-parents. We haveshown empirically that second-order features havean impact in the final scores. Approximate decoding was performed via alternating directions
dual decomposition (AD3 ), yielding fast runtimesof around 1,000 tokens per second.

Acknowledgements
We would like to thank the reviewers fortheir helpful comments. This work was par-References

Bernd Bohnet and Joakim Nivre. 2012. A transitionbased system for joint part-of-speech tagging and labeled non-projective dependency parsing. In Proc.
of the Empirical Methods in Natural Language Processing, pages 1455–1465.
Xavier Carreras. 2007. Experiments with a higherorder projective dependency parser. In International
Conference on Natural Language Learning, pages
957–961.
Koby Crammer, Ofer Dekel, Joseph Keshet, Shai
Shalev-Shwartz, and Yoram Singer. 2006. Online Passive-Aggressive Algorithms. Journal of Machine Learning Research, 7:551–585.
Dipanjan Das, André F. T. Martins, and Noah A. Smith.
2012. An Exact Dual Decomposition Algorithm
for Shallow Semantic Parsing with Constraints. In
Proc. of First Joint Conference on Lexical and Computational Semantics (*SEM), pages 209–217.
Jeffrey Flanigan, Sam Thomson, Jaime Carbonell,
Chris Dyer, and Noah A. Smith. 2014. A discriminative graph-based parser for the abstract meaning representation. In Proc. of the Annual Meeting of the Association for Computational Linguistics, pages 1426–1436.
Richard Johansson and Pierre Nugues.
2008.
Dependency-based syntactic–semantic analysis with
PropBank and NomBank. International Conference
on Natural Language Learning, pages 183–187.
Nikos Komodakis, Nikos Paragios, and Georgios Tziritas. 2007. MRF optimization via dual decomposition: Message-passing revisited. In Proc. of International Conference on Computer Vision, pages
1–8.
Terry Koo and Michael Collins. 2010. Efficient thirdorder dependency parsers. In Proc. of Annual Meeting of the Association for Computational Linguistics, pages 1–11.
Terry Koo, Alexander M. Rush, Michael Collins,
Tommi Jaakkola, and David Sontag. 2010. Dualdecomposition for parsing with non-projective head
automata. In Proc. of Empirical Methods for Natural Language Processing, pages 1288–1298.

Sandra Kübler, Ryan McDonald, and Joakim Nivre.
2009. Dependency parsing. Morgan & Claypool
Publishers.
André F. T. Martins, Noah A. Smith, and Eric P. Xing.
2009. Concise Integer Linear Programming Formulations for Dependency Parsing. In Proc. of Annual
Meeting of the Association for Computational Linguistics, pages 342–350.
André F. T. Martins, Noah A. Smith, Eric P. Xing,
Pedro M. Q. Aguiar, and Mário A. T. Figueiredo.
2010. Turbo Parsers: Dependency Parsing by Approximate Variational Inference. In Proc. of Empirical Methods for Natural Language Processing,pages 34–44.
André F. T. Martins, Noah A. Smith, Pedro M. Q.
Aguiar, and Mário A. T. Figueiredo. 2011. Dual Decomposition with Many Overlapping Components.
In Proc. of Empirical Methods for Natural Language
Processing, pages 238–249.
André F. T. Martins, Mário A. T. Figueiredo, Pedro
M. Q. Aguiar, Noah A. Smith, and Eric P. Xing.
2012. Alternating directions dual decomposition.
Arxiv preprint arXiv:1212.6550.
André F. T. Martins, Miguel B. Almeida, and Noah A.
Smith. 2013. Turning on the turbo: Fast third-ordernon-projective turbo parsers. In Proc. of the Annual
Meeting of the Association for Computational Linguistics, pages 617–622.
André F. T. Martins. 2014. AD3 : A Fast Decoder
for Structured Prediction. In S. Nowozin, P. Gehler,
J. Jancsary, and C. Lampert, editors, Advanced
Structured Prediction. MIT Press, Cambridge, MA,
USA.
Ryan McDonald, Koby Crammer, and Fernando
Pereira. 2005. Online large-margin training of dependency parsers. In Proc. of Annual Meeting of the
Association for Computational Linguistics, pages
91–98.
Ryan McDonald, Kevin Lerman, and Fernando Pereira.
2006. Multilingual dependency analysis with a twostage discriminative parser. In Proc. of International
Conference on Natural Language Learning, pages
216–220.
Alexander M. Rush, David Sontag, Michael Collins,
and Tommi Jaakkola. 2010. On dual decomposition and linear programming relaxations for natural
language processing. In Proc. of Empirical Methods
for Natural Language Processing.
David A. Smith and Jason Eisner. 2008. Dependency
parsing by belief propagation. In Proc. of Empirical
Methods for Natural Language Processing, pages
145–156.
Kristina Toutanova, Aria Haghighi, and Christopher
Manning. 2005. Joint learning improves semanticrole labeling. In ACL, pages 589–596.