Parsing with Traces: An O(n4) Algorithm and a Structural Representation

Parsing with Traces: An O(n4) Algorithm and a Structural Representation Jonathan K. Kummerfeld and Dan Klein Computer Science Division University of California, Berkeley Berkeley, CA 94720, USA {jkk,klein}@cs.berkeley.edu Abstract General treebank analyses are graph struc- tured, but parsers are typically restricted to tree structures for efficiency and modeling rea- sons. We propose a new representation and algorithm for a class of graph structures that is flexible enough to cover almost all treebank structures, while still admitting efficient learn- ing and inference. In particular, we consider directed, acyclic, one-endpoint-crossing graph structures, which cover most long-distance dislocation, shared argumentation, and similar tree-violating linguistic phenomena. We de- scribe how to convert phrase structure parses, including traces, to our new representation in a reversible manner. Our dynamic program uniquely decomposes structures, is sound and complete, and covers 97.3% of the Penn En- glish Treebank. We also implement a proof- of-concept parser that recovers a range of null elements and trace types. 1 Introduction Many syntactic representations use graphs and/or discontinuous structures, such as traces in Govern- ment and Binding theory and f-structure in Lexi- cal Functional Grammar (Chomsky 1981; Kaplan and Bresnan 1982). Sentences in the Penn Tree- bank (PTB, Marcus et al. 1993) have a core projec- tive tree structure and trace edges that represent con- trol structures, wh-movement and more. However, most parsers and the standard evaluation metric ig- nore these edges and all null elements. By leaving out parts of the structure, they fail to provide key relations to downstream tasks such as question an- swering. While there has been work on capturing some parts of this extra structure, it has generally ei- ther been through post-processing on trees (Johnson 2002; Jijkoun 2003; Campbell 2004; Levy and Man- ning 2004; Gabbard et al. 2006) or has only captured a limited set of phenomena via grammar augmenta- tion (Collins 1997; Dienes and Dubey 2003; Schmid 2006; Cai et al. 2011). We propose a new general-purpose parsing algo- rithm that can efficiently search over a wide range of syntactic phenomena. Our algorithm extends a non-projective tree parsing algorithm (Pitler et al. 2013; Pitler 2014) to graph structures, with improve- ments to avoid derivational ambiguity while main- taining an O(n4) runtime. Our algorithm also in- cludes an optional extension to ensure parses contain a directed projective tree of non-trace edges. Our algorithm cannot apply directly to con- stituency parses–it requires lexicalized structures similar to dependency parses. We extend and im- prove previous work on lexicalized constituent rep- resentations (Shen et al. 2007; Carreras et al. 2008; Hayashi and Nagata 2016) to handle traces. In this form, traces can create problematic structures such as directed cycles, but we show how careful choice of head rules can minimize such issues. We implement a proof-of-concept parser, scor- ing 88.1 on trees in section 23 and 70.6 on traces. Together, our representation and algorithm cover 97.3% of sentences, far above the coverage of pro- jective tree parsers (43.9%). 2 Background This work builds on two areas: non-projective tree …

Content truncated to 500 words