Supertagging the Long Tail with Tree-Structured Decoding of Complex Categories (2021)

Abstract: Although current CCG supertaggers achieve high accuracy on the standard WSJ test set, few systems make use of the categories’ internal structure that will drive the syntactic derivation during parsing. The tagset is traditionally truncated, discarding the many rare and complex category types in the long tail. However, supertags are themselves trees. Rather than give up on rare tags, we investigate constructive models that account for their internal structure, including novel methods for tree-structured prediction. Our best tagger is capable of recovering a sizeable fraction of the long-tail supertags and even generates CCG categories that have never been seen in training, while approximating the prior state of the art in overall tag accuracy with fewer parameters. We further investigate how well different approaches generalize to out-of-domain evaluation sets.

## introduction combinatory categorial grammar (ccg; @xcite is a strongly lexicalized grammar formalism in which rich syntactic categories at the lexical level impose tight constraints on the constituents that can be formed. its syntax-semantics interface has been attractive for downstream tasks such as semantic parsing @xcite and machine translation @xcite . most ccg parsers operate as a pipeline whose first task is 'supertagging', i.e., sequence labeling with a large search space of complex 'supertags' @xcite @xcite . the complex categories specify valency information: expected arguments to the right are signaled with forward slashes, and expected arguments to the left with backward slashes. for example, transitive verbs in english (like ''saw'' in figure 1a ) are tagged (s\np)/np to indicate that they expect a subsequent object noun phrase (np) and a preceding subject np to form a clause (s). given the supertags, all that remains to parsing is applying general rules of (binary) combination between adjacent constituents until the entire input is covered. supertagging thus represents the crux of the overall parsing process. in contrast to the simpler task of partof-speech tagging, supertaggers are required to resolve most of the syntactic ambiguity in the input. one key challenge of ccg supertagging is that the tagset is large and open-ended to account for combinatorial possibilities of syntactic constructions. this results in a heavy-tailed distribution of supertags, which is visualized in figure 1b ; a large proportion of unique supertags are rare or unseen (out-of-vocabulary, oov) even in a training set as large as the penn treebank's. previous ccg supertaggers have surrendered in the face of this challenge: they treat categories as a fixed set of opaque labels, rather than modeling their compositional structure. following @xcite , the standard approach is to consider only supertags appearing at least 10 times in the training data, sacrificing the possibility of predicting two thirds of the supertag types in ccgbank. rare supertags may have little impact on overall token accuracy-but the cost of this compromise is a fundamental incapability in truly generalizing to the task. in this paper, we confront the long-tail problem head-on by proposing a constructive framework in which supertags are built from scratch rather than predicted as opaque labels @xcite . in contrast to prior constructive supertaggers @xcite , our model builds upon the observation that supertags are themselves tree-structured, and hence can be generated top-down. 1 our experiments on the english ccgbank and its rebanked version show that constructing supertags as trees improves our ability to predict rare and even unseen tags, without sacrificing performance on the more common ones. our contributions are threefold: ## tree-structured constructive supertagging given a sequence of words (a sentence), our goal is to predict each word's supertag. constructing a supertag from its components requires a scoring function for the parts that is cognizant of both surrounding words and categories. below we describe the decoding procedure ( §3.1) and scoring functions ( §3.2) we developed for this purpose, which, in line with §2, explicitly incorporate the categories' tree structure. ## experimental setup per our quest to supertag the long tail, we compare our treernn and addrmlp models to the following baselines: if not indicated otherwise, we train the models with a batch size of 8 for a maximum of 10 epochs, and use early stopping based on the best development set performance. 11 all reported results are averaged over 3 random restarts. for downstream parsing evaluation ( §6.3), we run the c&c parser @xcite with the pretrained ccgbank model and default hyperparameters, providing as input our supertaggers' 1-best predictions and pos tags automatically obtained using stanza @xcite . ## results we report our main results on rebank in regarding the long tail, we ask: can constructive models accurately predict rare and complex categories without sacrificing performance on the head of the distribution? to answer this question, we break down performance by the frequency of category types in the training data. the baseline is the thresholded classifier mlp 10, which performs well on frequent categories but cannot access rare categories occurring less than 10 times in training. the simplest way of resolving this main hurdle is to remove the threshold, and indeed we find that mlp 1 is able to predict about a quarter of long-tail categories correctly. can we do better? the sequence-to-sequence model by k+19 does a lot better on the tail and even retrieves some unseen categories, but at the cost of frequent ones. the per-tag recurrent and tree-recursive generators (rnn and treernn) come close to to the nonconstructive classifiers, but do not convincingly improve over them. the addrmlp model, finally, outperforms all others on the rare tail while matching nonconstructive taggers on frequent and simple ones. for comparison with existing work ( in both in-domain and out-of-domain data, the performance gap between the nonconstructive mlps and addrmlp on the most frequent categories is minimal and in fact lies within the standard deviation. given the trend we observe from tables 3 and 4 to tables 6 and 7 , the ability to generalize to the long tail may well outweigh any minor improvement on the most frequent categories when applied to even more diverse data, within other languages, and across languages. figure 5 : confusion matrices by category depth, based on the standard rebank evaluation set. rows (columns) correspond to gold (predicted) categories with the respective depth. thus, cells above (below) the diagonal refer to categories predicted too deep (shallow). all numbers are absolute differences between confusions made by addrmlp@ and mlp 10@ / k+19, respectively. thus, positive numbers (red) are more typical for addrmlp@ and negative numbers (blue) are more typical for one of the other systems. ## conclusion we introduced a novel, explicitly tree-structured ccg supertagging method, advancing the nascent paradigm of constructive supertagging. our analysis of complex and long-tail categories highlights the positive impact of different modeling and inference choices within this paradigm: structural inductive bias as well as adequate contextualization via, e.g., attention contribute to more efficient, robust, and self-consistent models. we hope that our proposed method can be instrumental in researching and applying not only ccg and related syntactic formalisms, but also other paradigms like morphological (de)composition of complex words in morphologically rich languages, or compositional semantic parsing.