The following example is a directed graph for "Book that flight" with the maximum spanning tree corresponding to the desired parse shown in blue. 

University of Texas at San Antonio

In graph-based parsing finding the max spanning tree given sentence (S) and graph (G) a spanning tree over a G is a subset of G that is a tree covering all the vertices in G, thus a spanning tree over G that starts from the root is a valid parse of S. Resultingly, the highest score is the maximum spanning tree.

Max spanning tree

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

Learn Before

Related