13.5.3 Evaluating Chunking Systems

As with the evaluation of part-of-speech taggers, the evaluation of chunkers proceeds by comparing the output of a chunker against gold-standard answers provided by human annotators. However, unlike part-of-speech tagging and speech recognition, word-by-word accuracy measures are not adequate. Instead, chunkers are evaluated using measures borrowed from the field of information retrieval. In particular, the notions of precision, recall and the F measure are employed.

Precision measures the percentage of chunks that were provided by a system that were correct. Correct here means that both the boundaries of the chunk and the chunk's label are correct. Precision is therefore defined as:

$$ Precision:=\frac{Number~of~correct~chunks~given~by~system}{Total~number~of~chunks~given~by~system} $$

Recall measures the percentage of chunks actually present in the input that were correctly identified by the system. Recall is defined as:

$$ Recall:={\frac{Number~of~correct~chunks~given~by~system}{Total~number~of~actual~chunks~in~the~text}} $$

The F-measure (van Rijsbergen, 1975) provides a way to combine these two measures into a single metric. The F-measure is defined as:

$$ F_{\beta}=\frac{(\beta^{2}+1)P R}{\beta^{2}P+R} $$

The $ \beta $ parameter is used to differentially weight the importance of recall and precision, based perhaps on the needs of an application. Values of $ \beta > 1 $ favor recall, while values of $ \beta < 1 $ favor precision. When $ \beta = 1 $, precision and recall are equally balanced; this is sometimes called $ F_{\beta=1} $ or just $ F_1 $:

$$ F_{1}=\frac{2PR}{P+R} $$

The F-measure derives from a weighted harmonic mean of precision and recall. The harmonic mean of a set of numbers is the reciprocal of the arithmetic mean of the reciprocals:

$$ Harmonic Mean(a_{1},a_{2},a_{3},a_{4},...,a_{n})=\frac{n}{\frac{1}{a_{1}}\frac{1}{a_{2}}\frac{1}{a_{3}}\cdots\frac{1}{a_{n}}} $$

and hence F-measure is

$$ F=\frac{1}{\frac{1}{\alpha P}\times\frac{1}{(1-\alpha)R}}\quad\text{or}\left(\operatorname{with}\beta^{2}=\frac{1-\alpha}{\alpha}\right)\quad F=\frac{(\beta^{2}+1)PR}{\beta^{2}P+R} $$

The best current systems achieve an F-measure of around .96 on the task of base-NP chunking. Learning-based systems designed to find a more complete set of base-phrases, such as the ones given in Fig. 13.20, achieve F-measures in the .92 to .94 range. The exact choice of learning approach seems to have little impact on these results; a wide-range of machine learning approaches achieve essentially the same results (Cardie et al., 2000). FST-based systems of the kind discussed in Sec. 13.5.1 achieved F-measures ranging from .85 to .92 on this task.

Factors limiting the performance of current systems include the accuracy of the part-of-speech taggers used to provide features for the system during testing, inconsistencies in the training data introduced by the process of extracting chunks from parse trees, and difficulty resolving ambiguities involving conjunctions. Consider the following examples that involve pre-nominal modifiers and conjunctions.

[NP Late arrivals and departures] are commonplace during winter.

[NP Late arrivals] and [NP cancellations] are commonplace during winter.

In the first example, late is shared by both arrivals and departures yielding a single long base-NP. In the second example, late is not shared and modifies arrivals alone, thus yielding two base-NPs. Distinguishing these two situations, and others like them, requires access to semantic and context information unavailable to current chunkers.

13.6 SUMMARY

The two major ideas introduced in this chapter are those of parsing and partial parsing. Here's a summary of the main points we covered about these ideas:

• Parsing can be viewed as a search problem.

• Two common architectural metaphors for this search are top-down (starting with the root S and growing trees down to the input words) and bottom-up (starting with the words and growing trees up toward the root S).

• Ambiguity combined with the repeated parsing of sub-trees pose problems for simple backtracking algorithms.

• A sentence is structurally ambiguous if the grammar assigns it more than one possible parse.

Common kinds of structural ambiguity include PP-attachment, coordination ambiguity and noun-phrase bracketing ambiguity.

• The dynamic programming parsing algorithms use a table of partial-parses to efficiently parse ambiguous sentences. The CKY, Earley, and Chart-Parsing algorithms all use dynamic-programming to solve the repeated parsing of sub-trees problem.

• The CKY algorithm restricts the form of its grammar to Chomsky-Normal Form; the Earley and Chart-parsers accept unrestricted context-free grammars.

• 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.

• High accuracy partial parsing can be achieved either through rule-based or machine learning-based methods.

BIBLIOGRAPHICAL AND HISTORICAL NOTES

Writing about the history of compilers, Knuth notes:

In this field there has been an unusual amount of parallel discovery of the same technique by people working independently.

Well, perhaps not unusual, if multiple discovery is the norm (see page ??). But there has certainly been enough parallel publication that this history will err on the side of succinctness in giving only a characteristic early mention of each algorithm; the interested reader should see Aho and Ullman (1972).

Bottom-up parsing seems to have been first described by Yngve (1955), who gave a breadth-first bottom-up parsing algorithm as part of an illustration of a machine translation procedure. Top-down approaches to parsing and translation were described (presumably independently) by at least Glennie (1960), Irons (1961), and Kuno and Oettinger (1963). Dynamic programming parsing, once again, has a history of independent discovery. According to Martin Kay (personal communication), a dynamic programming parser containing the roots of the CKY algorithm was first implemented by John Cocke in 1960. Later work extended and formalized the algorithm, as well as proving its time complexity (Kay, 1967; Younger, 1967; Kasami, 1965). The related well-formed substring table (WFST) seems to have been independently proposed by Kuno (1965), as a data structure which stores the results of all previous computations in the course of the parse. Based on a generalization of Cocke's work, a similar data-structure had been independently described by Kay (1967) and Kay (1973). The top-down application of dynamic programming to parsing was described in Earley's Ph.D. dissertation (Earley, 1968) and Earley (1970). Sheil (1976) showed the equivalence of the WFST and the Earley algorithm. Norvig (1991) shows that the efficiency offered by all of these dynamic programming algorithms can be captured in any language with a memoization function (such as LISP) simply by wrapping the memoization operation around a simple top-down parser.

While parsing via cascades of finite-state automata had been common in the early history of parsing (Harris, 1962), the focus shifted to full CFG parsing quite soon afterward. Church (1980) argued for a return to finite-state grammars as a processing model for natural language understanding; other early finite-state parsing models include Ejerhed (1988). Abney (1991) argued for the important practical role of shallow parsing. Much recent work on shallow parsing applies machine learning to the task of learning the patterns; see for example Ramshaw and Marcus (1995), Argamon et al. (1998), Munoz et al. (1999).

The classic reference for parsing algorithms is Aho and Ullman (1972); although the focus of that book is on computer languages, most of the algorithms have been applied to natural language. A good programming languages textbook such as Aho et al. (1986) is also useful.

EXERCISES

13.1 Implement the algorithm to convert arbitrary context-free grammars to CNF. Apply your program to the $ \mathcal{L}_{1} $ grammar.

13.2 Implement the CKY algorithm and test it using your converted $ L_{1} $ grammar.

13.3 Rewrite the CKY algorithm given on page 13.10 so that it can accept grammars that contain unit productions.

13.4 Augment the Earley algorithm of Fig. 13.13 to enable parse trees to be retrieved from the chart by modifying the pseudocode for the COMPLETER as described on page 22.

13.5 Implement the Earley algorithm as augmented in the previous exercise. Check it on a test sentence using the $ \mathcal{L}_1 $ grammar.

13.6 Alter the Earley algorithm so that it makes better use of bottom-up information to reduce the number of useless predictions.

13.7 Attempt to recast the CKY and Earley algorithms in the chart parsing paradigm.

13.8 Discuss the relative advantages and disadvantages of partial parsing versus full parsing.

13.9 Implement a more extensive finite-state grammar for noun-groups using the examples given in Sec. 13.5 and test it on some sample noun-phrases. If you have access to an on-line dictionary with part-of-speech information, start with that; if not, build a more restricted system by hand.

13.10 Discuss how you would augment a parser to deal with input that may be incorrect, such as spelling errors or misrecognitions from a speech recognition system.

Abney, S. (1996). Partial parsing via finite-state cascades. Natural Language Engineering, 2(4), 337–344.

Abney, S. P. (1991). Parsing by chunks. In Berwick, R. C., Abney, S. P., and Tenny, C. (Eds.), Principle-Based Parsing: Computation and Psycholinguistics, pp. 257–278. Kluwer, Dordrecht.

Aho, A. V., Sethi, R., and Ullman, J. D. (1986). Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, MA.

Aho, A. V. and Ullman, J. D. (1972). The Theory of Parsing, Translation, and Compiling, Vol. 1. Prentice-Hall, Englewood Cliffs, NJ.

Argamon, S., Dagan, I., and Krymolowski, Y. (1998). A memory-based approach to learning shallow natural language patterns. In COLING/ACL-98, Montreal, pp. 67–73. ACL.

Bacon, F. (1620). Novum Organum. Annotated edition edited by Thomas Fowler published by Clarendon Press, Oxford, 1889.

Cardie, C., Daelemans, W., Ndellec, C., and Sang, E. T. K. (Eds.). (2000). Proceedings of the Fourth Conference on Computational Language Learning, Lisbon, Portugal.

Church, K. W. and Patil, R. (1982). Coping with syntactic ambiguity. American Journal of Computational Linguistics, 8(3-4), 139–149.

Church, K. W. (1980). On memory limitations in natural language processing. Master's thesis, MIT. Distributed by the Indiana University Linguistics Club.

Earley, J. (1968). An Efficient Context-Free Parsing Algorithm. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA.

Earley, J. (1970). An efficient context-free parsing algorithm. Communications of the ACM, 6(8), 451–455. Reprinted in Grosz et al. (1986).

Ejerhed, E. I. (1988). Finding clauses in unrestricted text by finitary and stochastic methods. In Second Conference on Applied Natural Language Processing, pp. 219–227. ACL.

Glennie, A. (1960). On the syntax machine and the construction of a universal compiler. Tech. rep. No. 2, Contr. NR 049-141, Carnegie Mellon University (at the time Carnegie Institute of Technology), Pittsburgh, PA†.

Harris, Z. S. (1962). String Analysis of Sentence Structure. Mouton, The Hague.

Irons, E. T. (1961). A syntax directed compiler for ALGOL 60. Communications of the ACM, 4, 51–55.

Kaplan, R. M. (1973). A general syntactic processor. In Rustin, R. (Ed.), Natural Language Processing, pp. 193–241. Algorithmic Press, New York.

Kasami, T. (1965). An efficient recognition and syntax analysis algorithm for context-free languages. Tech. rep. AFCRL-65-758, Air Force Cambridge Research Laboratory, Bedford, MA†.

Kay, M. (1967). Experiments with a powerful parser. In Proc. 2eme Conference Internationale sur le Traitement Automatique des Langues, Grenoble.

Kay, M. (1973). The MIND system. In Rustin, R. (Ed.), Natural Language Processing, pp. 155–188. Algorithmic Press, New York.

Kay, M. (1986). Algorithm schemata and data structures in syntactic processing. In Readings in natural language processing, pp. 35–70. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.

Kuno, S. (1965). The predictive analyzer and a path elimination technique. Communications of the ACM, 8(7), 453–462.

Kuno, S. and Oettinger, A. G. (1963). Multiple-path syntactic analyzer. In Popplewell, C. M. (Ed.), Information Processing 1962: Proceedings of the IFIP Congress 1962, Munich, pp. 306–312. North-Holland. Reprinted in Grosz et al. (1986).

Munoz, M., Punyakanok, V., Roth, D., and Zimak, D. (1999). A learning approach to shallow parsing. In Proceedings of the 1999 Joint SIGDAT Conference on Empirical Methods in Natural Language Processing and Very Large Corpora (EMNLP/VLC-99), College Park, MD, pp. 168–178. ACL.

Norvig, P. (1991). Techniques for automatic memoization with applications to context-free parsing. Computational Linguistics, 17(1), 91–98.

Ramshaw, L. A. and Marcus, M. P. (1995). Text chunking using transformation-based learning. In Proceedings of the Third Annual Workshop on Very Large Corpora, pp. 82–94. ACL.

Sheil, B. A. (1976). Observations on context free parsing. SMIL: Statistical Methods in Linguistics, 1, 71–109.

Tjong Kim Sang, E. F. and Veenstra, J. (1999). Representing text chunks. In Proceedings of EACL 1999, pp. 173–179.

van Rijsbergen, C. J. (1975). Information Retrieval. Butterworths, London.

Yngve, V. H. (1955). Syntax and the problem of multiple meaning. In Locke, W. N. and Booth, A. D. (Eds.), Machine Translation of Languages, pp. 208–226. MIT Press, Cambridge, MA.

Younger, D. H. (1967). Recognition and parsing of context-free languages in time $ n^{3} $. Information and Control, 10, 189–208.

14 STATISTICAL PARSING

Two roads diverged in a wood, and I – I took the one less traveled by...

Robert Frost, The Road Not Taken

The characters in Damon Runyon's short stories are willing to bet "on any proposition whatever", as Runyon says about Sky Masterson in The Idyll of Miss Sarah Brown; from the probability of getting aces back-to-back to the odds against a man being able to throw a peanut from second base to home plate. There is a moral here for language processing: with enough knowledge we can figure the probability of just about anything. The last two chapters have introduced sophisticated models of syntactic structure and its parsing. In this chapter we show that it is possible to build probabilistic models of syntactic knowledge and use some of this probabilistic knowledge in efficient probabilistic parsers.

One crucial use of probabilistic parsing is to solve the problem of disambiguation. Recall from Ch. 13 that sentences on average tend to be very syntactically ambiguous, due to problems like coordination ambiguity and attachment ambiguity. The CKY and Earley parsing algorithms could represent these ambiguities in an efficient way, but were not equipped to resolve them. A probabilistic parser offers a solution to the problem: compute the probability of each interpretation, and choose the most-probable interpretation. Thus, due to the prevalence of ambiguity, most modern parsers used for natural language understanding tasks (thematic role labeling, summarization, question-answering, machine translation) are of necessity probabilistic.

Another important use of probabilistic grammars and parsers is in language modeling for speech recognition. We saw that N-gram grammars are used in speech recognizers to predict upcoming words, helping constrain the acoustic model search for words. Probabilistic versions of more sophisticated grammars can provide additional predictive power to a speech recognizer. Of course humans have to deal with the same problems of ambiguity as do speech recognizers, and it is interesting that psychological experiments suggest that people use something like these probabilistic grammars in human language-processing tasks (e.g., human reading or speech understanding).

The most commonly used probabilistic grammar is the probabilistic context-free grammar (PCFG), a probabilistic augmentation of context-free grammars in which

each rule is associated with a probability. We introduce PCFGs in the next section, showing how they can be trained on a hand-labeled Treebank grammar, and how they can be parsed. We present the most basic parsing algorithm for PCFGs, which is the probabilistic version of the CKY algorithm that we saw in Ch. 13.

We then show a number of ways that we can improve on this basic probability model (PCFGs trained on Treebank grammars). One method of improving a trained Treebank grammar is to change the names of the non-terminals. By making the non-terminals sometimes more specific and sometimes more general, we can come up with a grammar with a better probability model that leads to improved parsing scores. Another augmentation of the PCFG works by adding more sophisticated conditioning factors, extending PCFGs to handle probabilistic subcategorization information and probabilistic lexical dependencies.

Finally, we describe the standard PARSEVAL metrics for evaluating parsers, and discuss some psychological results on human parsing.

14.1 PROBABILISTIC CONTEXT-FREE GRAMMARS

The simplest augmentation of the context-free grammar is the Probabilistic Context-Free Grammar (PCFG), also known as the Stochastic Context-Free Grammar (SCFG), first proposed by Booth (1969). Recall that a context-free grammar $G$ is defined by four parameters $(N, \Sigma, P, S)$; a probabilistic context-free grammar augments each rule in $P$ with a conditional probability. A PCFG is thus defined by the following components:

N a set of non-terminal symbols (or variables)

$ \Sigma $ a set of terminal symbols (disjoint from N)

$ R $ a set of rules or productions, each of the form $ A \to \beta\,[p] $, where $ A $ is a non-terminal, $ \beta $ is a string of symbols from the infinite set of strings $ (\Sigma \cup N)^* $, and $ p $ is a number between 0 and 1 expressing $ P(\beta|A) $

S a designated start symbol

That is, a PCFG differs from a standard CFG by augmenting each rule in R with a conditional probability:

$$ A\to\beta\ [p] $$

Here $p$ expresses the probability that the given non-terminal $A$ will be expanded to the sequence $\beta$. That is, $p$ is the conditional probability of a given expansion $\beta$ given the left-hand-side (LHS) non-terminal $A$. We can represent this probability as

$$ P(A\to\beta) $$

or as

$$ P(A\to\beta|A) $$

| S $ \rightarrow $ NP VP | [.80] | Det $ \rightarrow $ that [.10] | a [.30] | the [.60] |

| --- | --- | --- |

| S $ \rightarrow $ Aux NP VP | [.15] | Noun $ \rightarrow $ book [.10] | flight [.30] |

| S $ \rightarrow $ VP | [.05] | | meal [.15] | money [.05] |

| NP $ \rightarrow $ Pronoun | [.35] | | flights [.40] | dinner [.10] |

| NP $ \rightarrow $ Proper-Noun | [.30] | Verb $ \rightarrow $ book [.30] | include [.30] |

| NP $ \rightarrow $ Det Nominal | [.20] | | prefer; [.40] |

| NP $ \rightarrow $ Nominal | [.15] | Pronoun $ \rightarrow $ I [.40] | she [.05] |

| Nominal $ \rightarrow $ Noun | [.75] | | me [.15] | you [.40] |

| Nominal $ \rightarrow $ Nominal Noun | [.20] | Proper-Noun $ \rightarrow $ Houston [.60] |

| Nominal $ \rightarrow $ Nominal PP | [.05] | | TWA [.40] |

| VP $ \rightarrow $ Verb | [.35] | Aux $ \rightarrow $ does [.60] | can [.40] |

| VP $ \rightarrow $ Verb NP | [.20] | Preposition $ \rightarrow $ from [.30] | to [.30] |

| VP $ \rightarrow $ Verb NP PP | [.10] | | on [.20] | near [.15] |

| VP $ \rightarrow $ Verb PP | [.15] | | through [.05] |

| VP $ \rightarrow $ Verb NP NP | [.05] | |

| VP $ \rightarrow $ VP PP | [.15] | |

| PP $ \rightarrow $ Preposition NP | [.10] | |

or as

$$ P(RHS|LHS) $$

Thus if we consider all the possible expansions of a non-terminal, the sum of their probabilities must be 1:

$$ \sum_{\beta}P(A\to\beta)=1 $$

Fig. 14.1 shows a PCFG: a probabilistic augmentation of the $ \mathcal{L}_1 $ miniature English CFG grammar and lexicon. Note that the probabilities of all of the expansions of each non-terminal sum to 1. Also note that these probabilities were made up for pedagogical purposes. In any real grammar there are a great many more rules for each non-terminal and hence the probabilities of any particular rule would tend to be much smaller.

A PCFG is said to be consistent if the sum of the probabilities of all sentences in the language equals 1. Certain kinds of recursive rules cause a grammar to be inconsistent by causing infinitely looping derivations for some sentences. For example a rule $ S \rightarrow S $ with probability 1 would lead to lost probability mass due to derivations that never terminate. See Booth and Thompson (1973) for more details on consistent and inconsistent grammars.

How are PCFGs used? A PCFG can be used to estimate a number of useful probabilities concerning a sentence and its parse tree(s), including the probability of a par-

particular parse tree (useful in disambiguation) and the probability of a sentence or a piece of a sentence (useful in language modeling). Let's see how this works.