Template Kernels for Dependency Parsing

Human Language Technologies: The 2015 Annual Conference of the North American Chapter of the ACL, pages 1422–1427, Denver, Colorado, May 31 – June 5, 2015. c⃝2015 Association for Computational Linguistics Template Kernels for Dependency Parsing Hillel Taub-Tabib Hebrew University Jerusalem, Israel {hillel.t,yoav.goldberg}@gmail.com Yoav Goldberg Bar-Ilan University Ramat-Gan, Israel Amir Globerson Hebrew University Jerusalem, Israel gamir@cs.huji.ac.il Abstract A common approach to dependency parsing is scoring a parse via a linear function of a set of indicator features. These features are typically manually constructed from templates that are applied to parts of the parse tree. The templates define which properties of a part should combine to create features. Existing approaches consider only a small subset of the possible combinations, due to statistical and computational efficiency considerations. In this work we present a novel kernel which facilitates efficient parsing with feature rep- resentations corresponding to a much larger set of combinations. We integrate the kernel into a parse reranking system and demonstrate its effectiveness on four languages from the CoNLL-X shared task.1 1 Introduction Dependency parsing is the task of labeling a sen- tence x with a syntactic dependency tree y ∈ Y (x), where Y (x) denotes the space of valid trees over x. Each word in x is represented as a list of linguis- tic properties (e.g. word form, part of speech, base form, gender, number, etc.). In the graph based ap- proach (McDonald et al., 2005b) parsing is cast as a structured linear prediction problem: hv(x) = argmax y∈Y(x) vT · Φ (x, y) (1) where Φ (x, y) ∈ Rd is a feature representation de- fined over a sentence and its parse tree, and v ∈ Rd is a vector of parameters. To construct an effective representation, Φ (x, y) is typically decomposed into local representations 1See https://bitbucket.org/hillel/templatekernels for imple- mentation. over parts p of the tree y: Φ (x, y) = � p∈y φ (x, p) Standard decompositions include different types of parts: arcs, sibling arcs, grandparent arcs, etc. Fea- ture templates are then applied to the parts to con- struct the local representations. The templates de- termine how the linguistic properties of the words in each part should combine to create features (see Section 2). Substantial effort has been dedicated to the man- ual construction of feature templates (McDonald et al., 2005b; Carreras, 2007; Koo and Collins, 2010). Still, for both computational and statistical reasons, existing templates consider only a small subset of the possible combinations of properties. From a computational perspective, solving Eq. 1 involves applying the templates to y and calculating a dot product in the effective dimension of Φ. The use of many templates thus quickly leads to computa- tional infeasibility (the dimensionality of v, as well as the number of non-zero features in Φ, become very large). From a statistical perspective, the use of a large number of feature templates can lead to overfitting. Several recent works have proposed solutions to the above problem. Lei et al., (2014) represented the space of all …

Content truncated to 500 words