Using information from a supertagger, an agenda and a parse table are initialized with states representing all the possible lexical categories for each word in the input, along with their f-costs. The main loop removes the lowest cost edge from the agenda and tests to see if it is a complete derivation. If it reflects a complete derivation it is selected as the best solution and the loop terminates. Otherwise, new states based on the applicable CCG rules are generated, assigned costs, and entered into the agenda to await further processing. The loop continues until a complete derivation is discovered, or the agenda is exhausted, indicating a failed parse.

Implementation algorithm

Given a sentence S and derivation D that contains supertag sequence T, we have:
P(D,S) = $\sum_{i=1}^n -logP(t_i|s_i)$
The f-cost of an edge is the sum of two components: g(n), the cost of the span represented by the edge, and h(n), the estimate of the cost to complete a derivation containing that edge (these are often referred to as the inside and outside costs). For h(n), we need a score that approximates but never overestimates the actual cost of the final derivation. A simple heuristic that meets this requirement assumes that each of the words in the outside span will be assigned its most probable supertag. Putting this all together, we arrive at the following definition of a suitable f-cost for an edge.


Heuristic Functions

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.



University of Michigan - Ann Arbor

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) 

The first pair of operators permit us to compose adjacent functions:
- $X/Y \; Y/Z \implies X/Z$
- $Y \setminus Z \; X \setminus Y \implies X \setminus Z$

The first rule, called forward composition, can be 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 allows us to compose these two functions into a single one with the type of the first constituent and the argument of the second. 

The second rule, backward composition is the same, except that we’re looking to the left instead of to the right for the relevant arguments.

CCG Operations

 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.

Learn Before

Related

Learn After