Is there a favoured data structure for storing ambiguous parse trees in Natural Language Processing?

Question

I know a bit about parsing computer languages. Generally they try to resolve all ambiguities when parsing or abort the parse and throw an error.

This means you either got nothing because there was an error, or you have a neat syntax tree / AST with no ambiguities.

Of course in natural languages ambiguity is rampant and has to be handled somehow.

Since the same kind of syntax tree used for computer languages could not work for natural languages ("can" in an ambiguous sentence might be part of a verb phrase or part of a noun phrase depending how you look at it) I'm wondering if there is some data structure which has gained wide acceptance among NLP practitioners.

A simplistic obvious approach is just to have one tree for each way of parsing a sentence, but the longer the sentence and the more ambiguities, they tend to compound and everything quickly gets out of hand.

I'm expecting there is some kind of multidimensional tree used which is "flat" in the unambiguous parts of a sentence but has extra layers for each variant parse just in the ambiguous sections. Or am I barking up the wrong tree?

Answer 1

Short answer

There is a favoured structure for storing ambiguous parse trees. It is usually called a shared forest, and it is simply a grammar that generates only the sentence parsed with exactly the same parse trees as the grammar of the language (up to a renaming homomorphisme for the non-terminal symbols). This applies to Context-Free grammars, but also to several other formalisms such as Tree-Adjoining Grammars. It can be used as a generator to enumerate the individual parse-trees.

Shared forests are often presented as a graphs, with various qualification, but these graphs are only representations of grammars. They appear in all general context-free parsers in the literature.

Longer answer

Your question is a good question. However, the sentence you emphasize in boldface is, in my opinion, the wrong way to worry about representing ambiguity, even though it is the usual way to state it.

When you ask for a data structure, you are asking for a device to do processing, but you forget to worry about the intrinsic nature of that device, about the meaning it may have in your model of language processing. In some sense you emphasize the doing over the understanding.

There is actually an abstract answer that applies to numerous cases, numerous formalisms, independently of the parsing algorithm used, such as the CKY algorithm, Earley's algorithm, and many others.

The relevant concept is that of a shared forest. It is a condensed form of all the correct parse trees for the sentence, However, though the concept of shared forest was widely used in the parsing literature, it did take some time to understand what it was, other than a convenient data structure. The understanding opened it to generalizations.

Here I am skipping several fine points, see my answer to another question, for more details.

The basic idea (described in a 1995 paper by Lang and in the Grune-Jacobs book) relies on the fact that context-free languages, and many other syntactic formalisms are closed under intersection with regular languages (Type-3 grammars in Chomsky hierarchy). Furthermore, this closure property is constructive, which means that given a grammar G (in some syntactic formalism, such as CF grammar, or tree adjoining grammar, or many others) generating all syntactically correct sentences of the language, and a formal specification R of the regular language, it is possible to exhibit another grammar F, that generates only the syntactically correct sentences that belong to the regular set, with exactly the same ambiguities as with the original grammar G. This grammar F is a shared forest (there are many equivalent ways of building such a grammar - see Billot & Lang, The structure of shared forests in ambiguous parsing). Basically, the relevant rules of the original grammar are homomorphique images of the rules of the shared forest, through a renaming homomorphism of the non terminals. The shared forest uses "specialized copies" of the non-terminals of the original grammar so as to control more tightly the generative power of its rules.

A set of one sentence is a regular set, and the construction applies. Then, the shared forest F can be used a a generative grammar that generates only a single sentence, but with differents parse-trees corresponding to all the parses with the original grammar G. So, for example, it can be used to enumerate all the correct parse-trees for the sentence.

This can generalize to many situations. For example, when there is phonological ambiguity, as in the question Phonological ambiguity that changes the syntactic structure, this ambiguity regarding the words actually uttered can be represented by a word lattice, which actually defines formally a regular set of (not necessarily syntactically correct) sentences. The same construction intersecting the regular set with the grammar G can be used, accounting at the same time for lexical/phonological ambiguity and for syntactic ambiguity.

Now, what about this construction of the intersection. For CF grammars, there is an old construction that was published some 50 years ago (Bar-Hillel, Perles, Shamir 1961). All later algorithms, such as CKY, Earley, chart parsing, etc, that produce a shared forest are actually only variants of that construction that may optimize some steps so as to avoid some useless construction steps while producing the shared forest F. Similar constructions exist for many other classes of grammar than the CF grammars.

The next issue is to develop techniques to choose the right tree in the forest. This can be achieved in various ways but remains a very open topic. For example it is possible to associate features or data with specific algebraic characteristics (semi-ring) to the lexicon and parts of speech, together with composition rules associated to the grammar rules, to identify the "better" parse-tree. The Viterbi techniques to chose a most-likely parse-tree according to some probabilities fall in this category. Alternatively, the choice of correct parse-trees may be postponed to later stages of analysis.

This is (the skeleton of) the whole story, afaik, regarding shared forest. Much is still being developped on that basis.

It may seem too abstract, but it gives a good and actually simple mathematical understanding for organizing the technology. But that does not mean that all is simple when you get into actual details, for example with sophisticated feature structures.

Another advantage of the approach is that it gives a cleaner view of issues by separating the operational from the denotational. What this means is that the relevant entities you may be interested in, such as trees or forests, are specified by abstract mathematical definitions, on the basis of desirable properties, without specifying any actual method to effectively compute them. The operational algorithms that will compute them (the parsing algorithms) are elaborated separately, and have to be proved correct with respect to the denotational definition. This separates the issues of conceptual perspicuity and computational correctness and effectiveness.

Another point is that the complexity of the relevant structures can be analyzed from the mathematical definitions, independently of the algorithms that computes them.

Finally, to come back to your question, shared forest have gained wide acceptance among NLP practitioners. The abstract view of it as the grammar of an intersection is less well known by those who are not mathematically oriented, though it is nearly 20 years old. This ignorance/rejection of mathematics is unfortunately the source of much waste of time and energy.

Of course, the grammar view of the shared forest is an abstraction, which may be implemented in various ways, some being more easily computed with than others. Hence the grammar is sometimes a bit harder to see when described an an implemented structure in some algorithm descriptions. It may also happen, as in the case of Earley's algorithm, that the parse forest grammar is derived from a binarized version of the original grammar.

Bibliography: search the web with the keywords: parsing intersection forest - many papers are open access somewhere.

Some references on stackexchange:

• answer to Algorithms or data structures for dealing with ambiguity

• Recovering a parse forest from an Earley parser? and my answer

• Complexity of a GLR parser on an ambiguous grammar

• How do I reconstruct the forest of syntax trees from the Earley vector?

Answer 2

As you correctly note, ambiguity is rampant in natural language and whatever data structure is used for parsing in ambiguous grammars must somehow represent a large number of possible derivations.

Despite this, it's not feasible to represent every possible derivation as an explicit parse tree, because the number of possible bracketings of a string is its Catalan number, exponential in its length.

Which data structure is used to compactly represent ambiguity depends on the parsing algorithm chosen.

I'll use the CKY algorithm as an example, as the way in which it packs ambiguity is simple to describe.

The CKY parsing algorithm implicitly represents ambiguity using a data structure called a chart.

To focus on your question, I'll leave the description of the algorithm out, only describing how the data structure represents ambiguity. I'll leave a description of the algorithm itself to any NLP text or the video from Chris Manning's Coursera course.

Suppose we're parsing a sentence with N words. The chart can be modelled as a two-dimensional array, in which each cell C[i,j] contains all non-terminals which words [i..j] of the input sentence can derive.

For instance, in the below chart, cell C[0,3] contains all the non-terminals derivable from the words Book the flight using a particular grammar.

The CKY algorithm builds up the chart bottom-up through dynamic programming, so that when the algorithm terminates, the cell C[0,N] contains all possible non-terminals with a yield of the words [0..N].

The key insight that allows the chart to implicitly represent all possible derivations is that any parse tree in which some constituent XP has the yield [i..j] is represented by the very same chart entry in the cell C[i,j].

In the above chart, for example, the chart entry NP in cell C[1,3] implicitly belongs to every parse tree in which the words the flight at positions 1 and 2 is interpreted as an NP.

If each production rule is associated with a probability (a probabilistic context-free grammar), then a decoding algorithm such as the Viterbi algorithm can be used to find the most likely parse given the chart.

Other parsing algorithms for CFGs, such as the Earley algorithm, have analogous ways of packing ambiguity — in an Earley parser, for instance, a data structure called the agenda contains all possible parsing states for a prefix of the input sentence.

It's also possible for a parsing algorithm to discard ambiguity. Since not every possible parse is a likely parse, massive efficiency gains can be realised by only preserving a number of likely parses at each step (a greedy algorithm).

Finally, some parsing algorithms, such as the Chu-Liu-Edmonds algorithm for MST (minimum spanning tree) parsing, do not really represent derivational ambiguity directly. In such algorithms, the set of all possible parses isn't actually stored and thus can't easily be recovered. Instead, the sentence is treated as a graph, with directed edges representing dependencies between words. A tree algorithm runs over this graph to find the maximum-scoring set of spanning dependency edges.

This is sufficient because most parsing applications in NLP focus not on enumerating all parses, but on finding the best parse with respect to some figure of merit.

Bibliography:

McDonald, Ryan, et al. "Non-projective dependency parsing using spanning tree algorithms." Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 2005.