WIXLIB

Figure 3: A sentence from Wikipedia with the correct lexical category assignedto each word.material appearing in Section 3.2, which reports new state-of-the-art accuracyfigures for the CCGbank parsing task. It also acts as something of a surveyof the 20-year wide-coverage CCG parsing project that began in Edinburgh.3For a more detailed exposition of the linguistic theory of CCG, the reader isreferred to Steedman (1996), Steedman (2000) and Baldridge (2002). For anintroduction to wide-coverage CCG parsing, the reader is referred to Clark andCurran (2007b) and Hockenmaier and Steedman (2007).2CCG SupertaggingCCG supertagging is the task of assigning a single lexical category (or “supertag”) to each word in an input sentence. The term supertag originates fromthe seminal work of Bangalore and Joshi (1999) for lexicalised tree-adjoininggrammar (LTAG), and reflects the fact that CCG lexical categories (and elementary trees in LTAG) contain so much information. As an indication of howmuch information, note that the CCG grammar used in this report containsaround 1,300 lexical categories, compared with the 50 or so part-of-speech tagsin the original Penn Treebank (Marcus et al., 1993).Figure 3 shows a sentence from Wikipedia with the correct lexical categoryassigned to each word (Clark et al., 2009). The words highlighted in blue demonstrate why CCG supertagging is a difficult task. The lexical category assignedto by takes two arguments: an NP to the right and a verb phrase (S \NP ) tothe left. The lexical category assigned to in is similar, but takes an NP to theleft. In the Penn Treebank, both of these prepositions would be assigned thepart-of-speech tag IN . The point of the example is that, in order to assign thecorrect lexical category to these prepositions (or at least the second one), thesupertagger has to decide whether the preposition attaches to a noun or a verb;i.e. it effectively has to resolve a prepositional phrase attachment ambiguity,which is one of the more difficult, classical parsing ambiguities (Collins andBrooks, 1995). This led Bangalore and Joshi (1999) to describe supertagging asalmost parsing.3 https://groups.inf.ed.ac.uk/ccg/index.html5

The data most used for training and testing CCG supertaggers is from CCGbank (Hockenmaier and Steedman, 2007), which is a CCG version of the originalPenn Treebank (Marcus et al., 1993), a corpus of newswire sentences manuallyannotated with syntactic parse trees. A standard split is to take Sections 2-21(39,604 sentences) as training data, Section 00 (1,913 sentences) as developmentdata, and Section 23 (2,407 sentences) as test data. Extracting a grammar fromSections 2-21 results in 1,286 distinct lexical category types, with 439 of thosetypes occurring only once in the training data.The original CCG supertagger (Clark, 2002) was a maximum entropy (“maxent”) tagger (Ratnaparkhi, 1996), which was state-of-the-art for sequence labelling tasks at the time. The main difference with today’s neural taggers isthat the features were defined by hand, in terms of feature templates, based onlinguistic intuition. For example, the NLP researcher may have decided thata good feature for deciding the correct tag for a word is the previous word inthe sentence, which would then become a feature template which gets filled infor each particular word being tagged. Both types of tagger use iterative algorithms for training, typically maximising the likelihood of the (supervised)training data, with the neural models benefitting from specialised GPU hardware. Another difference is that the Transformer-based model described inSection 2.1 builds on a pre-trained model which has already been trained onlarge amounts of data to perform a fairly generic language modelling task. Itturns out that this pre-training stage—which has become available since themaxent taggers because of developments in neural networks, hardware, and theavailability of data—is crucial for the resulting performance of the supertagger,which is fine-tuned for the supertagging task.The per-word accuracy for the maxent supertagger was around 92% (seeTable 1), compared with over 96% for the Penn Treebank pos-tagging task(Ratnaparkhi, 1996, Curran and Clark, 2003). An accuracy of 92% may soundreasonable, given the difficulty of the task, but with an average sentence lengthin the treebank of around 20-25 words, this would result in approximately twoerrors every sentence. Given the amount of information in the lexical categories,it is crucial for the subsequent parsing stage that the supertagging is correct.Hence Clark and Curran (2004a) developed a “multitagging” approach in whichthe supertagger is allowed to dynamically assign more than one lexical categoryto a word, based on how certain the supertagger is of the category for that word.Allowing more than one lexical category increases the accuracy to almost 98%with only a small increase in the average per-word lexical category ambiguity(see the end of Section 2.1 below).Development of the maxent supertagger from 2007 mainly consisted of adapting it to other domains (Rimell and Clark, 2008) and using it to increase thespeed of CCG parsers (Kummerfeld et al., 2010). The first paper to use neuralmethods for CCG supertagging was Xu et al. (2015), which applies a vanillaRNN to the sequence labelling task. This resulted in substantial accuracy improvements (Table 1), and also produced a more robust supertagger that performed better on sentences from domains other than newswire (see the paper fordetails). Another improvement was that the maxent supertagger relied heav6

SupertaggerClark and Curran (2007b)Clark and Curran (2007b) (w/gold pos)Xu et al. (2015)Lewis et al. (2016)Lewis et al. (2016) ( tri-training)Tian et al. er-word acc91.592.693.194.194.996.2Table 1: Supertagger accuracy evolution on Section 00 of CCGbank.ily on part-of-speech (POS) tags to define effective feature templates, and theaccuracy degraded significantly when using automatically assigned, as opposedto gold-standard, POS tags (see the first two rows in Table 1). The RNN supertagger was able to surpass the accuracy of the maxent supertagger relyingon gold POS, but without using POS tags as input at all.Lewis et al. (2016) improved on the performance of the vanilla RNN byusing a bi-directional LSTM, and obtained additional gains by training on largeamounts of automatically parsed data. More specifically, the tri-training method(row 5 in the table) uses the lexical category sequences from parsed sentencesas additional training data, but only those supertagged sentences on which twodifferent CCG parsers agree. Finally, the last row of Table 1 shows the staggeringimprovements that can be had—over 50% reduction in error rate compared tothe original maxent model—when using a pre-trained neural language modelthat is fine-tuned for the supertagging task. This model is described in the nextsection.Other recent neural approaches to CCG supertagging include Clark et al.(2018) and Bhargava and Penn (2020). Bhargava and Penn (2020) is noteworthy because it uses neural sequence models to model the internal structureof lexical categories, which allows the supertagger to meaningfully assign nonzero probability mass to previously unseen lexical categories, as well as modelrare categories, which is important given the long tail in the lexical categorydistribution.2.1CCG Supertagging with a Transformer-based ModelThe field of NLP has experienced a period of rapid change in the last few years,due to the success of applying large-scale neural language models to a range ofNLP tasks. The new paradigm relies on taking a pre-trained neural languagemodel, which has been trained to carry out a fairly generic language modellingtask such as predicting a missing word in a sentence, and fine-tuning it throughadditional supervised training for the task at hand (Brown et al., 2020). Despitethe generic nature of the original language modelling task, the neural model isable to acquire large amounts of linguistic (and world) knowledge which canthen be exploited for the downstream task.7

Figure 4: The neural architecture of the supertagger from Tian et al. (2020).Another innovation which has been particularly influential is the development of the Transformer neural architecture, which consists of many selfattention layers, where every pair of words in a sentence is connected via anumber of attention “heads” (Vaswani et al., 2017, Devlin et al., 2019). Eachattention head calculates a similarity score between transformed representationsof the respective word embeddings, where one word acts as a “query” and theother as a “key”. These scores are then used by each word to derive a probabilistic mixture of all the other words in the sentence, where the mixture elements (“values”) are again transformed representations of the word embeddings.This mixture acts as a powerful word-in-context representation, and stackingthe attention layers a number of times, combined with some non-linear, fullyconnected layers, results in a highly non-linear contextualised representation ofeach word in the sentence.Tian et al. (2020) apply this method to the CCG supertagging task, withgreat success. Figure 4, which is an embellished version of Figure 1 from thepaper, shows the neural architecture. The first component is the BERT encoder(Devlin et al., 2019), which has already been pre-trained on large amounts oftext using a masked language modelling objective. The output of BERT isa word embedding for each word in the input sentence. Then, an additionalneural network takes the output of BERT, and also produces an embedding foreach word. This additional network has not been pre-trained, and so requiressupervised training data for its weights to be learned. In Tian et al. (2020)8

the additional network is a novel graph convolutional neural network (GCNN).Finally, there is an additional set of parameters which, for each output wordembedding, define a softmax over the set of lexical categories. The output of thesupertagger, for each input word, is the most probable lexical category accordingto the softmax distribution.Training proceeds in a standard fashion, using the lexical category sequencesfrom Sections 2-21 of CCGbank as supervised training data. The loss functionis the cross-entropy loss, the minimisation of which is equivalent to putting asmuch probability mass as possible on each correct lexical category, relative tothe incorrect lexical categories for each word (i.e. maximising the probabilityof the training data). A form of batch-based stochastic gradient descent isused to minimise the loss function, and dropout is used to prevent overfitting(Goodfellow et al., 2016). All of these techniques have now become standard inneural NLP. The implementation uses the neural network library PyTorch.One feature of the neural supertagger, compared with the maxent supertagger, is that it does not model the lexical category sequence at all. One ofthe challenges in developing taggers using sequence modelling methods, such asHMMs (Brants, 2000), CRFs (Lafferty et al., 2001), and maxent models, is thatthe number of possible tag sequences grows exponentially with sentence length,so modelling them explicitly requires either heuristic methods such as beamsearch, or dynamic programming techniques such as Viterbi. In contrast, theprobabilistic decision made by the neural supertagger of what lexical category toassign to each word is made independently of the decisions for the other words.The reason it performs so well is because of the highly contextualised natureof the output word embeddings, which already contain substantial amounts ofinformation about the other words in the sentence.There are a number of possibilities for the additional neural network inFigure 4. In fact, one possibility is not to add any additional layers at all, andsimply fine-tune BERT, which works almost as well as the GCNN (Table 5 inTian et al. (2020)). It is likely that adding in some additional attention layers,and training those with the supervised data, would work just as well.In order to replicate the results in Tian et al. (2020), and to use the supertagger as a front-end to an existing CCG parser, I downloaded and ran thecode from the github repository4 , retraining the supertagger on Sections 2-21 ofCCGbank. One difference compared to Tian et al. (2020) is that I used the fulllexical category set of 1,286 categories, rather than the 425 which result fromapplying a frequency cutoff. I also downloaded the 2019 05 30 BERT-LargeUncased model from the BERT repository5 to serve as the BERT encoder.If the NeST-CCG supertagger is to act as an effective front-end to a CCGparser, it would be useful for it to sometimes output more than one category for aword. In fact, NeST-CCG already has a hyperparameter—clipping threshold —which retains lexical categories based on their log-probabilities. Tuning thishyperparameter—let’s call it γ—turns out to be highly effective for producing4 https://github.com/cuhksz-nlp/NeST-CCG5 https://github.com/google-research/bert9

a multitagger. There is a trade-off between using a low γ value, which increasesthe chance of assigning the correct category, and a high γ which reduces theaverage number of categories per word. One of the motivations for supertaggingis that, if the average number of categories per word can be kept low, then thisgreatly increases the efficiency of the parser (Clark and Curran, 2007b).The optimal γ value depends on how “sharp” the lexical category distributions are, and this is affected by the number of training epochs for the NeSTCCG supertagger. NeST-CCG also has an additional hyperparameter—call itα—which sets a maximum number of lexical categories that can be assigned toa single word. I experimented with various combinations of γ, α, and numberof training epochs, and found a happy medium with γ 0.0005, α 10, and 10epochs, which resulted in a multitagging accuracy of 99.3% on the development data with 1.7 lexical categories per word on average.6 This comparesvery favourably with 97.6% at 1.7 categories per word from Clark and Curran (2007b). Hence the expectation is that this greatly improved multitaggerwill lead to improved parsing performance, which we turn to next.3CCG ParsingThe job of a CCG parser is to take the output of a CCG supertagger as input,combine the categories together using the CCG combinatory rules, and returnthe best analysis as the output. This process requires a parsing algorithm, whichdetermines the order in which the categories are put together; a parsing model,which scores each possible analysis; and a search algorithm, which efficientlyfinds the highest-scoring analysis. In addition, there are various options forwhat kind of analysis the parser returns as output.The most popular form of parsing algorithms for CCG have been bottom-up,in which the lexical categories are combined first, followed by combinations ofcategories with increasing spans, eventually resulting in a root category spanning the whole sentence (Steedman, 2000). The first parsing algorithms to besuccessfully applied to wide-coverage CCG parsing were chart-based (Hockenmaier and Steedman, 2002, Clark and Curran, 2004b), followed by shift-reduceparsers (Zhang and Clark, 2011, Xu et al., 2014, Ambati et al., 2016). In thisreport we will be using a chart-based parser (described in Section 3.1).The original CCG parsing models were based on lexicalised PCFGs andused relative frequency counts to estimate the model parameters, with backingoff techniques to deal with data sparsity (Hockenmaier and Steedman, 2002,Collins, 1997).7 These were superseded by discriminative, feature-based models, essentially applying the maxent models that had worked so well for tagging to the parsing problem (Clark and Curran, 2004b, Riezler et al., 2002,6 In order for a set of lexical categories assigned to a word to be “correct”, the set needsto contain the one correct category. Hence multitagging “accuracy” increases monotonicallywith smaller γ values, as does the per-word ambiguity, reflecting the trade-off described above.7 For a number of citation lists in this section, the first citations give the relevant CCGpapers, followed by the (non-CCG) work on which they were based.10

Miyao and Tsujii, 2008). Alternative estimation methods based on the structured perceptron framework—which provides a particularly simple estimationtechnique—were also applied successfully to CCG (Clark and Curran, 2007a,Collins and Roark, 2004). The more recent neural parsing models that havebeen applied to CCG are mentioned in Section 3.2.In terms of search, the choice is between optimal dynamic programming,heuristic beam search, or optimal A* search (Lee et al., 2016). The earlyCCG parsing work focused on dynamic programming algorithms (Hockenmaierand Steedman, 2002, Clark and Curran, 2004b), whereas the shift-reduce CCGparsers tended to use beam search, performing surprisingly well even with relatively small beam widths (Zhang and Clark, 2011). The CCG parser describedbelow also uses beam search, but applied to a chart.Finally, the main output formats have been either the CCG derivation itself, a dependency graph where the dependency types are defined in terms of theCCG lexical categories (Clark et al., 2002, Hockenmaier and Steedman, 2002), ora dependency graph using a fairly formalism-independent representation (Clarkand Curran, 2007b). It has been argued that dependency types are especiallyuseful for parser evaluation (Carroll et al., 1998), in particular for CCG (Clarkand Hockenmaier, 2002), as well as for downstream NLP tasks and applications.In this report the parser output will be CCG dependencies (used for evaluation),with a novel application of the derivations suggested in the Conclusion. Thereis also a large body of work on interpreting CCG derivations to produce semantic representations as logical forms, in particular for Discourse RepresentationTheory (Bos et al., 2004, 2017, Liu et al., 2021), Abstract Meaning Representation (Artzi et al., 2015), as well as for more general semantic parsing tasks(Zettlemoyer and Collins, 2005, Artzi et al., 2014).3.1CCG Parsing with a Neural Supertagger Front EndThis section describes the accuracy gains that can be obtained by simply usingthe neural supertagger described in Section 2.1 as a front-end to an existing CCGparser. These experiments further demonstrate the importance of supertaggingfor CCG (Clark and Curran, 2004a), and further realise the original vision ofBangalore and Joshi (1999) for supertagging as almost parsing.The CCG parser that we will use is the Java C&C parser described in Clarket al. (2015). This is essentially a Java reimplementation of the C&C parser,which was highly optimised C code designed for efficiency (Clark and Curran, 2007b, Curran et al., 2007); one of the aims of the reimplementation wasto make the code more readable and easier to modify. There were also someimprovements made to the grammar, by extending the lexical category set thatcan be handled by the parser from the 425 lexical categories in C&C to the fullset of 1,286 derived from Sections 2-21 of CCGbank.8 Also, Java C&C uses anew chart-based beam-search decoder, which removes any restrictions imposed8 Extending the grammar in this way required an extension of the so-called markedup file,which encodes how CCG dependencies are generated from the lexical categories.11

ParserC&CC&C (w/gold pos)Java C&C (w/gold pos)Java 4.396.3Cov.99.199.1100.0100.0Table 2: Par

ther used a CCG grammar which is context free by construction, being built entirely from rules instances observed in a nite CCG treebank (Hockenmaier and Steedman, 2002, Fowler and Penn, 2010), or a grammar which is context free in practice by limiti