Configurable Dependency Tree Extraction from CCG Derivations (2020)

Abstract: We revisit the problem of extracting dependency structures from the derivation structures of Combinatory Categorial Grammar (CCG). Previous approaches are often restricted to a narrow subset of CCG or support only one flavor of dependency tree. Our approach is more general and easily configurable, so that multiple styles of dependency tree can be obtained. In an initial case study, we show promising results for converting English, German, Italian, and Dutch CCG derivations from the Parallel Meaning Bank into (unlabeled) UD-style dependency trees.

## introduction in a world of heterogeneous linguistically annotated resources, the need often arises to convert annotations from one format into another. the purpose may be to extract features, make data available as input for tools that were not designed for it, or to compare heterogeneous tool outputs on an equal footing. for example, sentences annotated with derivations of combinatory categorial grammar (ccg) @xcite must often be converted to dependency graphs or trees. figure 1 shows an example. anne np swims s[dcl]\ np in ((s \ np)\(s \ np))/ np rio np (s \ np)\(s \ np) > 0 s[dcl]\ @xmath0 figure 1 : a ccg derivation and corresponding unlabeled ud dependency tree @xcite define a conversion from derivations to dependency graphs (containing both local and long-range dependencies) by annotating every lexical category that occurs in the english ccgbank @xcite , specifying the bilexical dependency (or dependencies) that each argument category gives rise to. this annotated inventory of categories and variations thereof have since widely been used to train and evaluate ccg parsers, e.g., @xcite , @xcite , @xcite , @xcite . the obvious drawback of this approach is that each category has to be annotated manually, and adapting the scheme to other languages, other flavors of ccg, or other flavors of dependency graph, is thus labor-intensive. a simple alternative is to just extract a dependency for each argument category, with the word corresponding to the argument as the dependent, and the word corresponding to the result category as the head. this is, e.g., used for parser training and evaluation for english by @xcite and for english and japanese by @xcite . @xcite define a similar algorithm operating on derivations rather than lexical categories, which however only supports pure first-order ccgs. the main drawback is that only one flavor of dependency tree is supported, in which modifiers and function words such as determiners end up as heads of what they modify due to the way ccg uses functional categories for them. @xcite use a simple algorithm with some tricks to accomodate a variety of different dependency treebank formats, but it only supports a heavily simplified version of ccg with two basic categories, s and n. in this paper we present a novel approach to extracting dependencies from ccg derivations. it is similar to clark et al.'s approach in that the lexical categories, augmented with dependency information for each argument category, serve as the basis for the extraction. however, we do not annotate each possible lexical category manually, but rather define a limited and mostly language-independent set of rules to do so automatically, which can be adapted to different dependency flavors easily. like the other approaches mentioned, we limit ourselves to local dependencies. as a result, the resulting structures are guaranteed to be trees. as a case study, we experiment with converting english, german, italian, and dutch derivations from the parallel meaning bank @xcite to (unlabeled) dependency trees compatible with the annotation guidelines of basic universal dependencies (ud) @xcite . ## ccg-to-dependency conversion by argument category augmentation in a ccg derivation, each word is assigned a syntactic category that encodes its combinatory potential in terms of syntactic arguments. for example, an english transitive verb like sees in mary sees john has the category (s \ np)/ np, meaning that it combines with an (object) np to the right and then with a (subject) np on the left, and that the resulting constituent is a sentence (s): categories with slashes (i.e., with arguments) are called functional, others are called basic. we call the basic category that remains after stripping all arguments from a functional category its top category, e.g., s is the top category of (s \ np)/ np. the first step in our conversion algorithm is to augment each basic category with a pair of variables x, d, where x represents its identity and d will later be bound to a marker (f or a) that indicates the direction of the dependency: we then unify argument categories of functors with the categories of their arguments (this can be done by traversing the derivation): we now bind the identity variable of the top category of each word to its token number: in the next step, each argument category gets a dependency direction marker. in our example, there are two argument categories, np 1,v and np 3,y , both arguments of the functor category (s 2,w \ np 1,v )/ np 3,y . in this case, the functor-argument relation of ccg corresponds exactly to the head-dependent relation of most dependency grammars. we indicate this by binding the top category of every argument category to f, meaning that the functor is the head: but the functor is not always the head. consider the following example: ## identifying modifiers and function words which arguments to mark with f, and which with a, depends on the style of dependency tree one wishes to obtain. marking every argument with f would yield very modifier-centric and function-word-centric trees due to ccg's treatment of adjectives, adverbs, adpositions, conjunctions, etc., as functors. most dependency grammars, however, prefer a modifiee-centric, and to varying degrees also content-wordcentric, style. universal dependencies @xcite is an example of an especially content-wordcentric style, treating function words as dependents of content words whenever possible. sud @xcite is a variant of ud that differs mainly in being less content-word-centric. non-ud treebanks show considerable variation as to which function words they treat as heads and which as dependents, cf. @xcite . our solution is to mark arguments with f by default, but to define a list of rules that identify modifier and function word categories whose outermost argument category should be marked with a. we group the rules into different modules (one for modifiers, one for determiners, etc.) that can be turned on and off individually, so various dependency styles are supported. we base our rules on the ccg category inventory of the parallel meaning bank (pmb) @xcite , a large quadrilingual corpus of sentences annotated with ccg derivations. our rule inventory is shown in ## case study: converting the pmb to ud-style dependencies 1 to initially develop and test our conversion algorithm, we annotated parts 00 (for development) and 01 (for testing) of the parallel meaning bank, version 3.0.0. we only used sentences whose annotation status was marked "gold". one trained annotator annotated the sentences with dependency trees following the basic ud guidelines, but without labels, indicating only the head for each word. we then converted the pmb ccg derivations to dependency trees using the algorithm presented above, with all modules turned on, and computed the unlabeled attachment score when comparing to the manual annotation. the results, shown in we performed a manual error analysis to see what kinds of discrepancies were encountered. in a few cases, the discrepancies have nothing to do with our algorithm but are the result of plain annotation errors in the pmb or attachment ambiguity that the pmb's annotators and our annotator resolved differently. unlike ud, the pmb has no strict rules for attaching punctuation, so it sometimes ends up modifying a different constituent from the one that the ud guidelines mandate. there are various relatively rare there np[thr] is ((s[dcl]\ np)/(s[ng]\ np))/ np no np / n person n cutting (s[ng]\ np)/ np some np / n ginger n and here, the emphatic how mediates the dependency between slow and are [pmb 00/0778]: (9) how (s[dcl]/(s[dcl]/ s[adj]\ np))/ s[adj]\ np slow s[adj]\ np you np are (s[dcl]\ np)/(s[adj]\ np) ## conclusions we have presented a general and configurable algorithm to convert ccg derivations into dependency trees, together with a rule inventory for the parallel meaning bank, achieving promising accuracy for conversion to unlabeled basic ud on english, german, italian, and dutch. compared to the method of @xcite , the need for manually marking up all lexical category types in a ccg treebank is reduced because we only have to list the categories of modifiers and function words. however, if our approach was to be extended to dependency schemes with nonlocal dependencies, such as enhanced ud @xcite , or if labeled dependencies were desired, markup of content words would be required as well. and as our error analysis shows, at least in the pmb, there is a long tail of categories that cannot be discovered by looking at a small sample. still, the modularity of our approach enables it to support different dependency treebank formats. the work has many possible applications, including feature extraction from ccg parses and cross-framework and cross-language parser evaluation.