This chapter focuses on the structures assigned by context-free grammars. Context-free grammars don’t specify how the parse tree for a given sentence should be computed. We therefore need to specify algorithms that employ these grammars to efficiently produce correct trees. They are useful in applications such as grammar checking, semantic analysis, question answering and information extraction.
Structural ambiguity arises from many commonly used rules in phrase-structure grammars which occurs when the grammar can assign more than one parse to a sentence.
Two common kinds of ambiguity are:
attachment ambiguity: a particular constituent can be attached to the parse tree at more than one place
coordination ambiguity: different sets of phrases can be conjoined by a conjunction like and
Syntactic disambiguation algorithms require statistical, semantic, and contextual knowledge sources that vary in how well they can ben integrated into parsing algorithms.
Cocke-Kasami-Younger (CKY) algorithm is the most widely used dynamic-programming based approach to parsing. Related approaches include the Earley algorithm and chart parsing.
Restricting a grammar to CNF does not lead to any loss in expressiveness, since any context-free grammar can be converted into a corresponding CNF grammar that accepts exactly the same set of strings as the
Rules with a single non-terminal on the right are called unit productions.
The entire conversation process is as follows:
- Copy all conforming rules to the new grammar unchanged
- Convert terminals within rules to dummy non-terminals
- Convert unit-productions
- Make all rules binary and add them to new grammar
In CNF, each non-terminal node above the part-of-speech level in a parse tree will have exactly two daughters. An Example:
function CKY-PARSE(words, grammar) returns table
The code can be found here. Honestly, I am not quite sure it’s right :)
Turn the above recognized algorithm into a parser algorithm which could return all possible parses:
- augment the entries in the table so that each non-terminal is paired with pointers to the table entries from which it was derived
- permit multiple versions of the same non-terminal to be entered into the table
Our parser isn’t returning trees that are consistent with the grammar given to us by our friendly syntacticians. In addition, the conversion to CNF will complicate any syntax-driven approach to semantic analysis.
- One approach to getting around these problems is to keep enough information around to transform our trees back to the original grammar as a post-processing step of the parse.
- Another solution is to adopt a more complex dynamic programming solution that simply accepts arbitrary CFGs.
For those task which do not require complex, complete parse trees for all inputs, a partial parse, or shallow parse, of input sentences may be sufficient.
Chunking is the process of identifying and classifying the flat, non-overlapping segments of a sentence that constitute the basic non-recursive phrases corresponding to the major content-word parts-of-speech: noun phrases, verb phrases, adjective phrases, and prepositional phrases.
What constitutes a syntactic base phrase depends on the application. First and foremost, base phrases of a given type do not recursively contain any constituents of the same type.
It’s common to model chunking as IOB tagging.
# The morning flight from Denver has arrvied
There is no explicit encoding of the end of a chunk in IOB tagging; the end of any chunk is implicit in any transition from an I or B to a B or O tag.
Sequence model in a training set, Viterbi decoding is commonly used.
Chunkers are evaluated according to the notions of precision, recall, and the F-measure borrowed from the field of information retrieval.
Precision: = Number of correct chunks given by system / Total numbers of chunks given by system
Recall: = Number of correct chunks given by system / Total number of actual chunks in the text
Correct here means that both the boundaries of the chunk and the chunk’s label are correct.
Also can be seen here
- Structural ambiguity is a significant problem for parsers. Common sources of structural ambiguity include PP-attachment, coordination ambiguity, and noun-phrase bracketing ambiguity.
- Dynamic programming parsing algorithms, such as CKY, use a table of partial parses to efficiently parse ambiguous sentences. CKY restricts the form of the grammar to Chomsky normal form (CNF).
- Many practical problems, including information extraction problems, can be solved without full parsing. Partial parsing and chunking are methods for identifying shallow syntactic constituents in a text. SOT methods use supervised machine learning with Viterbi decoder.