Geometry-Aware Supertagging with Heterogeneous Dynamic Convolutions (2023)

Abstract: The syntactic categories of categorial grammar formalisms are structured units made of smaller, indivisible primitives, bound together by the underlying grammar’s category formation rules. In the trending approach of constructive supertagging, neural models are increasingly made aware of the internal category structure. In turn, this enables them to more reliably predict rare and out-of-vocabulary categories. with significant implications for grammars previously deemed too complex to find practical use. In this work, we revisit constructive supertagging from a graph-theoretic perspective, and propose a framework based on heterogeneous dynamic graph convolutions, aimed at exploiting the distinctive structure of a supertagger’s output space. We test our approach on a number of categorial grammar datasets spanning different languages and grammar formalisms, achieving substantial improvements over previous state of the art scores.

## introduction their close affinity to logics and lambda calculi has made categorial grammars a standard tool of trade for the formally-inclined nlp practitioner. modern flavors of categorial grammar, despite their (sometimes striking) divergences, share a common architecture. at its core, a categorial grammar is a formal system consisting of two parts. first, there is a lexicon, a mapping that assigns to each word a set of categories. categories are quasi-logical formulas recursively built out of atomic categories by means of category forming operations. the inventory of category forming operations at the minimum has the ability to express linguistic functionargument structure. if so desired, the inventory can be extended with extra operations, e.g. to handle syntactic phenomena beyond simple concatenation, or to express additional layers of grammatical information. the second component of the grammar is a small set of inference rules, formulated in terms of the category forming operations. the inference rules dictate how categories interact and, through this interaction, how words combine to form larger phrases. parsing thus becomes a process of deduction comparable (or equatable, depending on the grammar's formal rigor) to program synthesis, providing a clean and elegant syntax-semantics interface. in the post-neural era, these two components allow differentiable implementations. the fixed lexicon is replaced by supertagging, a process that contextually decides on the most appropriate supertags (i.e. categories), whereas the choice of which rules of inference to apply is usually deferred to a parser further down the processing pipeline. the highly lexicalized nature of categorial grammars thus shifts the bulk of the weight of a parse to the supertagging component, as its assignments and their internal make-up inform and guide the parser's decisions. in this work, we revisit supertagging from a geometric angle. we first note that the supertagger's output space consists of a sequence of trees, which has as of yet found no explicit representational treatment. capitalizing on this insight, we employ a framework based on heterogeneous dynamic graph convolutions, and show that such an approach can yield substantial improvements in predictive accuracy across categories both frequently and rarely encountered during a supertagger's training phase. ## background the supertagging problem revolves around the design and training of a function tasked with mapping each word (in the context of a sentence) to a category, thus inducing a sequence of categories {c 1 , . . . , c n } from a sentence {w 1 , . . . , w n }. existing supertagging architectures differ in how they implement this mapping, with each implementation choice boiling down to (i) which of the temporal and structural dependencies within and between the input and output are taken into consideration, and (ii) how these dependencies are materialized. earlier work would utilize solely occurrence counts from a training corpus to independently map word n-grams to their most likely categories, and then attempt to filter out implausible sequences via rule-constrained probabilistic models @xcite . the shift from sparse feature vectors to distributed word representations facilitated integration with neural networks and improved generalization on the mapping domain, extending it to rare and previously unseen words @xcite . later, the advent of recurrent neural networks offered a natural means of incorporating temporal structure, widening the input receptive field through contextualized word representations on the one hand @xcite , but also permitting an autoregressive formulation of the output generation, whereby the effect of a category assignment could percolate through the remainder of the output sequence @xcite . regardless of implementation specifics, the discriminative paradigm employed by all above works fails to account for the skewness of the data; exceedingly rare categories are practically impossible to learn, and categories absent from the training data are completely ignored. as an alternative, the recently emerging constructive paradigm seeks to explore the structure hidden within categories. by inspecting their formation rules, @xcite equates categories to cfg derivations, viewing each category as a tiny compositional expression, and a category sequence as the concatenation of their flattened depth-first projections. the goal sequence is now incrementally generated on a symbol-by-symbol basis using a transformer-based seq2seq model; a twist which provides the decoder with the means to construct novel categories on demand, bolstering co-domain generalization. the decoder's global receptive field, however, comes at the heavy price of quadratic memory complexity, which also bodes poorly with the elongated output sequences, leading to a slowed down inference speed. expanding on the idea, @xcite explicates the categories' tree structure, embedding symbols based on their tree positions and propagating contextualized representations through tree edges, using either residual dense connections or a tree-structured gru. this adaptation completely eliminates the burden of learning how the categorial trees are constructed, instead allowing the model to focus on what trees to construct, leading to drastically improved performance. simultaneously, since the decoder is now token-separable, it permits construction of categories for the entire sentence in parallel, speeding up inference and reducing the network's memory footprint. in the process, however, it loses the ability to model interactions between autoregressed nodes belonging to different trees, morally reducing the task once more to sequence classification (albeit now with a dynamic classifier). despite their common goal of accounting for syntactic categories in the zipfian tail, there are tension points between the above two approaches. in flattening categories and concatenating them together, the first breaks the input-to-output alignment and obfuscates the categorial tree structure. in opting for a tree-wise bottom-up decoding, the second forgets about meaningful inter-tree outputto-output dependencies. in this paper, we seek to resolve these tension points with a novel, unified and grammar-agnostic supertagging framework based on heterogeneous dynamic graph convolutions. our architecture combines the merits of explicit tree structures, strong autoregressive properties, near-constant decoding time, and a memory complexity that scales with the input, boasting high performance across the full span of the frequency spectrum and surpassing previously established benchmarks on all datasets considered. ## experiments we employ our supertagging architecture in a range of diverse categorial grammar datasets spanning different languages and underlying grammar formalisms. in all our experiments, we bind our model to a monolingual bert-style language model used as an external encoder, fine-tuned during training @xcite . in order to homogenize the tokenization between the one directed by each dataset and the one required by the encoder, we make use of a simple localized attention aggregation scheme. the subword tokens together comprising a single word are independently projected to scalar values through a shallow feed-forward layer. scalar values are softmaxed within their local group to yield attention coefficients over their respective bert vectors, which are then summed together, in a process reminiscent of a cluster-wide attentive pooling @xcite . in cases of datalevel tokenization treating multiple words as a single unit (i.e. assigning one type to what bert perceives as many words), we mark all words following the first with a special [mwu] token, signifying they need to be merged to the left. this effectively adds an extra output symbol to the decoder, which is now forced to do double duty as a sequence chunker. to avoid sequence misalignments and metric shifts during evaluation, we follow the merges dictated by the ground truth labels, and consider the decoder's output as correct only if all participating predictions match, assuming no implicit chunking oracles. ## conclusion we have proposed a novel supertagging methodology, where both the linear order of the output sequence and the tree-like structure of its elements is made explicit. to represent the different information sources (sentential word order, subword contextualized vectors, tree-sequence order and intratree edges) and their disparate sizes and scales, we turned to heterogeneous graph attention networks. to capture the autoregressive dependencies between different trees, we formulated the task as a dynamic graph completion process, aligning each subsequent temporal step with a higher order tree node neighborhood and predicting them in parallel across the entire sequence. we tested our methodology on four different datasets spanning three languages and as many grammar formalisms, establishing new state of the art scores in the process. through our ablation studies, we showed the importance of incorporating both intraand inter-tree context flows, to which we attribute our system's performance. other than architectural adjustment and optimizations, several interesting ideas present themselves as promising research avenues. first, it is worthwhile to consider adaptations of our framework to either allow an efficient integration of more "exotic" context pathways, e.g. sibling node interactions, or alter the graph's decoding order altogether. on a related note, for formalisms faithful to the linear logic roots of categorial grammars, it seems reasonable to anticipate that the goal graph can be compactified by collapsing primitive nodes of opposite polarity according to their interactions, unifying the tasks of supertagging and parsing with a single end-to-end framework. practice aside, our results pose further evidence that lexical sparsity, historically deemed the categorial grammar's curse, might well just require a change of perspective to tame and deploy as the answer to the very problem it poses.