Transition-based Spinal Parsing

Proceedings of the 19th Conference on Computational Language Learning, pages 289–299, Beijing, China, July 30-31, 2015. c⃝2015 Association for Computational Linguistics Transition-based Spinal Parsing Miguel Ballesteros1,2 Xavier Carreras3 1NLP Group, Pompeu Fabra University 2Carnegie Mellon University 3Xerox Research Centre Europe miguel.ballesteros@upf.edu xavier.carreras@xrce.xerox.com Abstract We present a transition-based arc-eager model to parse spinal trees, a dependency- based representation that includes phrase- structure information in the form of con- stituent spines assigned to tokens. As a main advantage, the arc-eager model can use a rich set of features combining depen- dency and constituent information, while parsing in linear time. We describe a set of conditions for the arc-eager system to produce valid spinal structures. In experi- ments using beam search we show that the model obtains a good trade-off between speed and accuracy, and yields state of the art performance for both dependency and constituent parsing measures. 1 Introduction There are two main representations of the syntac- tic structure of sentences, namely constituent and dependency-based structures. In terms of statisti- cal modeling, an advantage of dependency repre- sentations is that they are naturally lexicalized, and this allows the statistical model to capture a rich set of lexico-syntactic features. The recent liter- ature has shown that such lexical features greatly favor the accuracy of statistical models for pars- ing (Collins, 1999; Nivre, 2003; McDonald et al., 2005). Constituent structure, on the other hand, might still provide valuable syntactic information that is not captured by standard dependencies. In this work we investigate transition-based sta- tistical models that produce spinal trees, a rep- resentation that combines dependency and con- stituent structures. Statistical models that use both representations jointly were pioneered by Collins (1999), who used constituent trees annotated with head-child information in order to define lexical- ized PCFG models, i.e. extensions of classic constituent-based PCFG that make a central use of lexical dependencies. An alternative approach is to view the com- bined representation as a dependency structure augmented with constituent information. This ap- proach was first explored by Collins (1996), who defined a dependency-based probabilistic model that associates a triple of constituents with each dependency. In our case, we follow the representa- tions proposed by Carreras et al. (2008), which we call spinal trees. In a spinal tree (see Figure 1 for an example), each token is associated with a spine of constituents, and head-modifier dependencies are attached to nodes in the spine, thus combin- ing the two sources of information in a tight man- ner. Since spinal trees are inherently dependency- based, it is possible to extend dependency mod- els for such representations, as shown by Carreras et al. (2008) using a so-called graph-based model. The main advantage of such models is that they allow a large family of rich features that include dependency features, constituent features and con- junctions of the two. However, the consequence is that the additional spinal structure greatly in- creases the number of dependency relations. Even though a graph-based model remains parseable in cubic time, it is impractical unless …

Content truncated to 500 words