In Combinatory Categorial Grammar (CCG) parsing using the A* algorithm, given a sentence S and derivation D that contains supertag sequence T, the probability is: 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 (inside cost), and h(n), the estimate of the cost to complete a derivation containing that edge (outside cost). For h(n) to be admissible, it must approximate but never overestimate 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.

University of Michigan - Ann Arbor

Google

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.



 CCG Parsing using the A* Algorithm

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

Speech and Language Processing (3rd ed. draft) 

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.

Learn Before

Related