Parsing Algorithms and Metrics

Parsing Algorithms and Metrics Joshua Goodman Harvard University 33 Oxford St. Cambridge, MA 02138 goodman@das.harvard.edu Abstract Many different metrics exist for evaluating parsing results, including Viterbi, Cross- ing Brackets Rate, Zero Crossing Brackets Rate, and several others. However, most parsing algorithms, including the Viterbi algorithm, attempt to optimize the same metric, namely the probability of getting the correct labelled tree. By choosing a parsing algorithm appropriate for the evaluation metric, better performance can be achieved. We present two new algo- rithms: the "Labelled Recall Algorithm," which maximizes the expected Labelled Recall Rate, and the "Bracketed Recall Algorithm," which maximizes the Brack- eted Recall Rate. Experimental results are given, showing that the two new al- gorithms have improved performance over the Viterbi algorithm on many criteria, es- pecially the ones that they optimize. 1 Introduction In corpus-based approaches to parsing, one is given a treebank (a collection of text annotated with the "correct" parse tree) and attempts to find algo- rithms that, given unlabelled text from the treebank, produce as similar a parse as possible to the one in the treebank. Various methods can be used for finding these parses. Some of the most common involve induc- ing Probabilistic Context-Free Grammars (PCFGs), and then parsing with an algorithm such as the La- belled Tree (Viterbi) Algorithm, which maximizes the probability that the output of the parser (the "guessed" tree) is the one that the PCFG produced. This implicitly assumes that the induced PCFG does a good job modeling the corpus. There are many different ways to evaluate these parses. The most common include the Labelled Tree Rate (also called the Viterbi Criterion or Ex- act Match Rate), Consistent Brackets Recall Rate (also called the Crossing Brackets Rate), Consis- tent Brackets Tree Rate (also called the Zero Cross- ing Brackets Rate), and Precision and Recall. De- spite the variety of evaluation metrics, nearly all re- searchers use algorithms that maximize performance on the Labelled Tree Rate, even in domains where they are evaluating using other criteria. We propose that by creating algorithms that op- timize the evaluation criterion, rather than some related criterion, improved performance can be achieved. In Section 2, we define most of the evaluation metrics used in this paper and discuss previous ap- proaches. Then, in Section 3, we discuss the La- belled Recall Algorithm, a new algorithm that max- imizes performance on the Labelled Recall Rate. In Section 4, we discuss another new algorithm, the Bracketed Recall Algorithm, that maximizes perfor- mance on the Bracketed Recall Rate (closely related to the Consistent Brackets Recall Rate). Finally, we give experimental results in Section 5 using these two algorithms in appropriate domains, and com- pare them to the Labelled Tree (Viterbi) Algorithm, showing that each algorithm generally works best when evaluated on the criterion that it optimizes. 2 Evaluation Metrics In this section, we first define basic terms and sym- bols. Next, we define the different metrics used in evaluation. Finally, we discuss the relationship of these metrics to parsing …

Content truncated to 500 words