Supertagging with CCG primitives (2020)

Abstract: In CCG and other highly lexicalized grammars, supertagging a sentence’s words with their lexical categories is a critical step for efficient parsing. Because of the high degree of lexicalization in these grammars, the lexical categories can be very complex. Existing approaches to supervised CCG supertagging treat the categories as atomic units, even when the categories are not simple; when they encounter words with categories unseen during training, their guesses are accordingly unsophisticated. In this paper, we make use of the primitives and operators that constitute the lexical categories of categorial grammars. Instead of opaque labels, we treat lexical categories themselves as linear sequences. We present an LSTM-based model that replaces standard word-level classification with prediction of a sequence of primitives, similarly to LSTM decoders. Our model obtains state-of-the-art word accuracy for single-task English CCG supertagging, increases parser coverage and F1, and is able to produce novel categories. Analysis shows a synergistic effect between this decomposed view and incorporation of prediction history.

## introduction highly lexicalized grammars, such as lexicalized tree-adjoining grammar (ltag) and combinatory categorial grammar (ccg), have very large sets of possible lexical categories. where most phrasestructure and dependency grammars have lexical category sets numbering in the tens for english @xcite , ltag and ccg have sets numbering in the hundreds or thousands @xcite . the large number of possible labels for each word can make the search space for the syntactic tree of the sentence intractably large; narrowing the set of viable lexical categories per word is therefore an important step in efficient parsing for such grammars @xcite . as the tags are much more complex and informative than partof-speech (pos) tags, tagging the words with these more complex categories is called supertagging. the large number of lexical categories comes from the high degree of complexity that the categories can have. when grammars have small tag sets, the bulk of the work in developing or learning a grammar comes from deciding how to combine the tags and their words. categorial grammars instead have fewer combination rules, requiring the lexical categories to support much greater syntactic richness; see figure 1 for some sample categories. existing approaches to supervised supertagging operate in the same manner as pos taggers: as a word classifiers, predicting the correct tag from a fixed set. this is relatively straightforward for pos tags: there are relatively few possibilities as the tags are simple-e.g., it is not immediately apparent if or how vbd is more complex than nnp. by con-trast, ccg categories have varying complexities and are clearly not atomic units; they are composed from a much smaller vocabulary of primitives. in this paper, we challenge the usual treatment of ccg supertagging as large-tagset pos tagging, instead treating lexical categories as the complex units that they are. we present a model for ccg supertagging that replaces traditional whole-category prediction with the prediction of their composing primitives. in addition to addressing the incongruity between pos tags and ccg categories, this allows for the generation of new categories that do not occur in the training set, a necessary property for handling the long tail of syntactic phenomena. we treat supertags as linear sequences, enabling us to employ lstm decoders to autoregressively predict ccg primitives in sequence. on ccgbank, our model outperforms a bidirectional lstm classification baseline on word accuracy, parser f 1 , and parser coverage, establishing a new state-of-the-art for single-task english ccg supertagging. analysis of our model and results shows that our non-atomic view of ccg lexical categories enables more effective incorporation of model prediction history than is the case with atomic category classification. our model can also generate new categories that it has not seen during training, and even manages to correctly label some words with such out-of-vocabulary (oov) categories. to the best of our knowledge, our model is the first fullysupervised ccg supertagger that constructs lexical categories from primitive types, and the first to be able to produce oov categories. our work presents both a more appropriate view of the problem and establishes a strong baseline for ccg supertagging according to this view. ## background and motivation supertagging is quite different from pos tagging. ccg lexical categories are composed from a fixed set of more primitive units; as a result, ccg supertagging has a much larger set of possible tags than does pos tagging-an open set, in fact. where the penn treebank (ptb) has 48 1 pos tags @xcite , ccgbank has 1322 lexical categories @xcite . selecting from a much larger set is more difficult, of course, and therefore, pos tagging accuracy is substantially higher than for ccg supertagging. recent pos tagging work has reached up to 98% 1 twelve of which are for punctuation. given these substantial differences, the complex, structured nature of ccg lexical categories warrants further investigation for supertagging. we see two primary advantages in doing so. first, as noted by @xcite and @xcite , a compositional view of lexical categories can provide strong information about surrounding categories. for example, if a word has category s/np, then it is likely that there is a primitive np type somewhere else in the sentence, whether as a simple category or as part of a complex one. second, treating ccg categories as atomic makes it impossible to fully tag all new data, since new, rare categories may be encountered during inference. such rare categories are not necessarily spurious; over the whole ccgbank, @xcite note that while some of the once-occurring categories "are due to noise or annotation errors, most are in fact required for certain constructions." foot_0 admittedly, novel categories (i.e., those not occurring in the training set) are rare in ccgbank: in the standard splits, 0.06% of word tokens in the development set and 0.04% in the test set are tagged with a category that does not occur in the training set. but since an incorrect lexical category can impair the parsability of a full sentence, it is more appropriate to consider the number of affected sentences, which is 0.9% for both the development and test sets. 3 work on ccg parsers has noted their high sensitivity to supertagging accuracy (e.g., @xcite , so such cases should not be ignored. and unlike typical classification scenarios, out-of-vocabulary lexical categories are not different in kind from in-vocabulary ones; they are composed from the same units using the same rules, suggesting that oov categories can, in principle, be treated in a concordant manner. ## related work while our focus in this paper is on ccg supertagging, it is worth noting that the supertagging task originates in the context of ltag @xcite , which also has highly complex lexical categories. supertagging is important for efficient parsing in such grammars as it helps narrow the search space for the parse @xcite . despite the complexity captured in supertags, the vast majority of existing approaches treat ccg lexical categories as atomic units for prediction, ignoring their varying complexities and structured nature. effectively, at each time step of the input sentence, the model must decide which of a fixed set of ccg categories is the best choice. this category-classification approach is the same as for pos tagging, and indeed, existing supertagging models are very similar to (if not the same as) pos tagging models in structure. early work for ccg supertagging relied on maximum-entropy models with hand-specified features, a limited set of possible categories, and tag dictionaries that tracked allowed categories for frequent words based on the training data @xcite @xcite . recent work relies heavily on word embeddings: they allow better handling of out-of-vocabulary words and decrease reliance on part-of-speech tags, where imperfect accuracy can be a detriment for the supertagger. @xcite used externally-trained embeddings @xcite combined with suffix and capitalization features in a simple feed-forward neural network as well as a crf; they also allowed words to be tagged with categories with which they did not co-occur in the training data. @xcite applied the same embeddings and features in a standard elman rnn @xcite ; they later improved their model by making it bidirectional @xcite . @xcite replaced the elman rnns with twolayer bidirectional lstms, taking advantage of the lstm units' ability to retain information over time @xcite , and incorporated a data-augmentation technique as well. vaswani et al. ( 2016 ) used a single-layer bidirectional lstm but dropped all hand-specified features, removed the limit on the categories that the model could produce, used custom in-domain word embeddings, and included a language modelstyle lstm over the output lexical categories that allowed the model to condition its predicted tag at time t on the previously-predicted lexical category at time t -1. in addition to improving word accuracy, this latter addition drastically increased the number of tagged sentences that were parsable, even in variations that hurt word accuracy. the current state-of-the-art result in ccg supertagging was achieved by @xcite . their model consisted of a two-layer bidirectional lstm with glove word embeddings @xcite supplemented by the output of a character-level convolutional neural network. their approach involved training additional "auxiliary" prediction modules on top of the same lstm on an additional, unlabelled corpus @xcite . these auxiliary modules were given an incomplete view of the input (e.g., only words to the left) and trained to predict the same label that the primary prediction module predicted. if we consider other grammars, @xcite presented a type-logical grammar for dutch and a supertagging approach that relied on primitive units. while their approach yielded improvement in word accuracy, the overall accuracy was substantially lower than with ccg supertagging; furthermore, the grammar's type system was so different that it is difficult to draw conclusions about applicability to other grammars. 4 in order to see some consideration of the composed structure of ccg lexical categories, we must alter our task scope somewhat. @xcite , following earlier work @xcite , applied a bayesian model with grammar-informed priors for supertagging where only a tag dictionary and raw, unlabelled text was made available. their model included a generative model for categories as well as the notion of combinability, preferring tag sequences where adjacent words could be combined via ccg rules. similarly, work in ccg grammar induction has involved some basic consideration of how ccg categories are constructed so that that a grammar could be built using em @xcite or hierarchical dirichlet processes @xcite . despite these applications, consideration of ccg primitives has yet to make its way to supervised supertagging approaches; we aim to fill that gap. ## method and model despite the potential advantages discussed above in section 2, it is unclear a priori whether supertagging with primitive units is more or less difficult than standard, whole-category classification. while the output vocabulary becomes drastically smaller, the output sequences are longer and must be arranged correctly. one of our aims in this paper is to establish a baseline for this approach to supertagging and evaluate its difficulty as a task in comparison to the usual methods. ## results the cochran-mantel-haenszel (cmh) test indicates that the difference in test set word accuracy between our model and the baseline is statistically significant (p ≈ 1.6 × 10 -7 ); likewise for the difference in coverage (p ≈ 0). 11 f 1 scores over the 20 runs, the wilcoxon signedrank test indicates statistical significance for the difference in f 1 scores (p ≈ 6.7 × 10 -15 ). it is extremely rare for our model to produce malformed categories. over all 20 runs, our model produces only two instances of redundant parentheses, which are automatically repaired, and seven instances of malformed categories 12 , which are left as-is and therefore counted as incorrect predictions. the malformations consist entirely of missing closing parentheses or extraneous opening parentheses. @xcite in addition to besting the baseline, our model also yields a higher word accuracy than the single-task models reported by @xcite . the focus of their work was their novel cross-view training (cvt) approach, which allowed for efficient and effective augmentation of model performance using unlabelled data. they compared their approach to the alternative use of elmo over a variety of tasks, and ccg supertagging was the only one in which cvt underperformed the incorporation of elmo. their result with the elmo-based model set the state-of-the-art word accuracy for singletask ccg supertagging. ## conclusion and future work in this paper, we have presented an alternative view to classification-based ccg supertagging where lexical categories are constructed from ccg primitives. where ccg categories are traditionally predicted atomically, we instead found that breaking them down into their primitive types and operators provides a substantial increase in word accuracy, parser f 1 , and parser coverage for english ccg supertagging. even with a simple linearization scheme, our lstm decoder-based model outperformed the baseline in all respects, and was also able to generate correct categories during inference that were unseen during training. our analysis showed that there is a strong interplay between knowledge of prediction history and prediction of primitive units, with both aspects being necessary to obtain the full increases in performance that our model exhibits. we conclude that our novel consideration of ccg lexical categories as the complex units that they are is worthwhile and beneficial. our model demonstrates the benefit of a more careful, informed consideration of the structure of supertagging and, by extension, ccg parsing. we expect that further, more sophisticated incorporation of category structure will yield additional benefit, and are investigating such extensions in place of the straightforward linearization of the category strings we applied in this paper; this is somewhat similar to some work in ltag supertagging @xcite . at the same time, other categorial grammars, such as lambek categorial grammar, are likely to be amenable to such improvements as well, but their theoretical properties may allow for more principled methods of decomposing lexical categories, allowing the supertagger's role to be more tightly integrated in the parsing process.