In Combinatory Categorial Grammar (CCG), composition operators permit the composition of adjacent functions:

- **Forward composition** ($$X/Y \; Y/Z \implies X/Z$$): Applied to adjacent constituents where the first is a function seeking an argument of type $$Y$$ to its right, and the second is a function that provides $$Y$$ as a result. This rule composes the two functions into a single one with the type of the first constituent and the argument of the second.
- **Backward composition** ($$Y \setminus Z \; X \setminus Y \implies X \setminus Z$$): Functions similarly to forward composition, but looks to the left instead of to the right for the relevant arguments.

University of Michigan - Ann Arbor

Google

Unfortunately, the basic categorial approach does not give us any more expressive power than we had with traditional CFG rules; it just moves information from the grammar to the lexicon. To move beyond these limitations CCG is a modern extension of categorical grammar and includes operations that operate over functions.

Combinatory Categorical Grammar (CCG)

An on-going but a helpful book resource about NLP
https://web.stanford.edu/~jurafsky/slp3/

Speech and Language Processing (3rd ed. draft) 

 Supertagging is the corresponding task for highly lexicalized grammar frameworks, where the assigned tags often dictate much of the derivation for a sentence. As with traditional part-of-speech tagging, the standard approach to building a CCG supertagger is to use supervised machine learning to build a sequence labeler from hand-annotated training data. To find the most likely sequence of tags given a sentence, it is most common to use a neural sequence model, either RNN or Transformer. A probability distribution over the possible supertags for each word in the
input will be returned. 

The following table illustrates an example distribution for a simple sentence, in which each column represents the probability of each supertag for a given word in the context of the input sentence. To get the probability of each possible word/tag pair, we’ll need to sum the probabilities of all the supertag sequences that contain that tag at that location. This can be done with the forward-backward algorithm that is also used to train the CRF.

Supertagging

The A* cost function, f(n), is used to efficiently guide the search to a solution. The f-cost has two components: g(n), the exact cost of the partial solution represented by the state n, and h(n) a heuristic approximation of the cost of a solution that makes use of n. When h(n) satisfies the criteria of not overestimating the actual cost, A* will find an optimal solution. When applied to parsing, search states correspond to edges representing completed constituents. Each edge specifies a constituent’s start and end positions, its grammatical category, and its f-cost. Here, the g component represents the current cost of an edge and the h component represents an estimate of the cost to complete a derivation that makes use of that edge.



Learn Before

Related