8. Wide-Coverage Parsing, Semantics, and Morphology

Lewis and Steedman (2014) describe what is at stake if we incorporate distributional semantics of content words but not compositional semantics coming out of such heads.

The notion of morpheme is controversial in linguistics. Matthews (1974), Stump (2001), and Aronoff and Fudeman (2011) provide some discussion. Without delving into morphological theory, we shall adopt the computational view summarized by Roark and Sproat (2007): morphology can be characterized by finite-state mechanisms. Models of morphological processing differ in the way they handle lexical access. For example, two-level morphology is finite-state and linear-time in its morphotactics, but it incurs an exponential cost to do surface form-lexical form pairings during morphological processing (see Koskenniemi 1983; Koskenniemi and Church 1988, and Barton et al. 1987 for extensive discussion). On the other hand, if we have lexical categories for sub-lexical items, then, given a string and its decomposition, we can check efficiently (in polynomial time) whether the category-string correspondences are parsable: the problem is in NP (nondeterministic polynomial time) not because of parsing but because of ambiguity. Lexical access could then use the same mechanism for words, morphemes, and morpholexical rules if it wants to.

For example: for the word el-ler-im-de-ki “the ones in my hands” with the morphological breakdown of el-plu-poss.1s-loc-rel, el for “hand,” the lexical ending is -plu-poss.1s-loc-rel.

Notice that, left unconstrained we face n × 2¹⁶⁴ ≈ n × 10^49.4 word-like forms in Turkish, from 164 morphemes and n lexemes. A much smaller search space is attested because of morphological, semantic, and lexical constraints, but 50,000 and counting is still an enormous search space.

Using complexity results in these aspects has been sometimes controversial; see, for example, Berwick and Weinberg (1982), Barton et al. (1987), and Koskenniemi and Church (1988). One view, which we do not follow, is to eliminate alternatives in the model, by insisting on using tractable algorithms, as in Tractable Cognition thesis (van Rooij 2008). The one we follow addresses complexity as a complex mixture of source and data that in the end allows efficient parsing, feasible and transparent training, and scalable performance. For example, Clark and Curran’s (2007) CCG parser is cubic time, whereas A^∗ CCG parser is exponential time in the worst case, but with training, it has a superlinear parsing performance on long sentences (Lewis and Steedman 2014). Another example of this view is PAC learnability of Valiant (2013).

Item-and-Arrangement (IA) morphology treats word structure as consisting of morphemes which are put one after another, like segments. Item-and-Process morphology (IP) uses lexemes and associated processes on them, which are not necessarily segmental. Another alternative is Word-and-Paradigm, which is similar to IP but with word as the basic unit. The terminology is due to Hockett (1959).

Nonconcatenative and nonsegmental morphological processes, which are not only characteristic of templatic languages but also abundant in diverse morphological typologies, such as German, Tagalog, and Alabama, are painful reminders that IA cannot be a universal model for all lexicons.

What this means is that, if “archer” in (4) were a quantified phrase, for example her okçu “every archer,” then the quantifier’s lexically value-raised category would lead to her okçu := NP ^↑∖(NP∕NP): λpλqλx.(∀x)pa′x → qx. Value-raising is distribution of type-raising to arguments, as shown in the logical form.

Here we pass over the mechanism that maintains lexical integrity, which has the effect of doing category combination of bound items before doing it across words. The idea was first stipulated in CCG by Bozşahin (2002) and revised for explanation in Steedman and Bozşahin (2018). In practical parser training the same effect has been achieved in various ways. For example, in a maximum entropy model of Turkish, a category feature for a word is decided based on whether it arises from a suffix of the word (Akkuş 2014). Wang et al. (2014) rely on a morphological analyzer before training, to keep category inference within a word. Ambati et al. (2013) rank intra-chunk (morphological) dependencies higher than inter-chunk (phrasal) dependencies in coming up with CCG categories, which has the same effect.

Notice that the adverb kolayca is necessarily a VP modifier, unlike kolay of (7b), which is underspecified. We avoid ungrammatical coordinations involving parts of words while allowing suspended affixation, by virtue of radically lexicalizing the conjunction category. For example, [target-ACC hit and bystander-ACC missed ]-REL archer is ungrammatical, and the coordination category has the constraint (ω), which says that phonological wordhood must be satisfied by all Xs. The left conjunct in this hypothetical example could not project an X _ω because its right periphery—which projects X—would not be a phonological word, as Kabak (2007) showed. It is a forced move in CCG that such constraints on formally available combinations must be derived from information available at the perceptual interfaces.

We note that another wide-coverage parser for Turkish, Eryiğit et al. (2008), which uses dependency parsing, achieves its highest results in terms equivalent to a subset of our sub-lexical training (inflectional groups, in their case). Their comparison includes word-trained lexicons. CCG adds to this perspective a richer inventory of types to train with, and the benefit of naturally extending the coverage to long-range dependencies that are abundant in large corpora, once heads of syntactic constructions bear combinatory categories in the lexicon. We say more about these aspects subsequently.

Honnibal and Curran (2009), Honnibal et al. (2010), and Honnibal (2010) have shown that English benefits in parsing performance from sub-lexical training as well, although parsing in their case is word-based. One key ingredient appears to be lexicalizing the unary rules as “hat categories,” which indeed makes such CCG categories truly supertags because they can be taken into account in training before the parser sees them, whereas the previous usage of supertag in CCG is equivalent to “combinatory lexical category.”

In linguistics the term “lexeme” could mean one base lexeme and all its paradigm forms receiving one and same part of speech.

The example is from Çakıcı (2008). The convention we follow in display of Turkish treebank data is: word|POS|Category–gloss.

Figures are from Çakıcı (2008).

In fact, both interpretations are possible, and type-shifting from NP to S would be preferable. For example, “Arabadaki Mehmet.” (car-loc-ki Mehmet) could mean “Mehmet, the one in the car” or “The one in the car is Mehmet,” with the given punctuation. Differences in the interpretations are clear in the following alternative continuations: Yarın gidiyormuş./Ahmet değil. “He is leaving tomorrow/Not Ahmet.” The first one requires NP reading for the example in the beginning, and the second one S (propositional) reading. Going the other way, i.e., from a lexically specified S for a nominal predicate to an NP, is much more restricted in Turkish. Such type-shifting is in fact headed by verbal inflection.

Although the gold-standard CCG categories (supertags) are used, this number is slightly less than 100%. This is possibly caused by an implementation discrepancy.