A Dependency-based Method for Evaluating Broad-Coverage Parsers
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Natural Language. Pages 1420-1426.
© 1995 International Joint Conferences on Artificial Intelligence
Abstract
With the emergence of broad-coverage parsers, quantitative evaluation of parsers becomes increasingly more important. We propose a dependency-based method for evaluating broad-coverage parsers. The method offers several advantages over previous methods that are based on phrase boundaries. The error count score we propose here is not only more intuitively meaningful than other scores, but also more relevant to semantic interpretation. We will also present an algorithm for transforming constituency trees into dependency trees so that the evaluation method is applicable to both dependency and constituency grammars . Finally, we discuss a set of operations for modifying dependency trees that can be used to eliminate inconsequential differences among different parse trees and allow us to selectively evalu ate different aspects of a parser.
- [Black et a/., 1991] E. Black, S. Abney, D . Flickenger, C. Gdaniec, R. Grishman , P. Harrison , D . Hindle, R . Ingria, F . Jelinek , J. Klavans , M. Liberman, M. Marcus, S. Roukos , B Santorini , and T. Strza- lkowski . A procedure for quantitatively comparing the syntactic coverage of english grammars . In Pro- ceedings of Speech and Natural Languag e Workshop, pages 306-311. DARPA , February 1991.
- [Black et a/., 1992] Ezra Black, John Lafferty, and Salim Roukos . Development and evaluation of a broad- coverage probabilistic grammar of English-language computer manuals . In Proceedings of ACL-92, pages 185-192, Newark, Delaware, 1992.
- [Magerman , 1994] David M. Magerman. Natural Lan- guage Parsing as Statistical Pattern R ecognition. PhD thesis , Stanford University, 1994.
- [Mel 'cuk , 1987] Igor A . Mel'cuk . D ependency syntax: theory and pra ctice. State University of New York Press, Albany, 1987.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. Introduction
With the emergence of broad-coverage parsers, quanti tative evaluation of parsers becomes increasingly more important . It is generally accepted that such evaluation should be conducted by comparing the parser-generated parse trees (we call them answers) with manually con structed parse trees (we call them keys) . However, how such comparison should be performed is still subject to debate. Several proposals have been put forward [Black et a/., 1991; 1992; Magerman, 1994], all of which are based on the comparison between phrase boundaries in answers and keys. We propose a dependency-based eval uation scheme in which the dependency relations, rather than phrase boundaries, are the focus in the compari son between answers and keys. We then show that the dependency-based scheme offers several advantages over previous proposals. Note that the use of dependency In a sentence-level evaluation, a sentence is considered to be correctly parsed if certain criteria have been met. In [Black et al., 1992], the correctness criterion is that the number of crossing-brackets is 0. In [Magerman, 1994], a sentence is correctly parsed if both precision and recall are 100%. The scores assigned to parsers are their percentages of correctly parsed sentences in the test corpus.
·The author wishes to thank IJCAI reviewers for point ing out several errors in the draft and Mr. Wei Xiao for im plementing the algorithms presented in the paper. The au thor is a member of the Institute for Robotics and Intelligent Systems (IRIS) and wishes to acknowledge the support of the Networks of Centres of Excellence Program of the Gov ernment of Canada, the Nat ural Sciences and Engineering Research Council (NSERC), and the participation of PRE CARN Associates Inc. This research has also been partially supported by NSERC Research Grant OGP121338.
A problem with the phrase-level scores is that they do not necessarily reflect the quality of parse trees, because a single error may be counted multiple times. For exam ple, suppose (3a) is the key and (3b), (3c) are answers returned by two parsers .
(3)
- [I [saw [[a man] [with [[a dog] and [a cat]]]] [in [the park]]]]
- [I [saw [[a man] [with [[a dog] and [[a cat] [in [the park]]]]]]]]
- [I [saw [a man] with [a dog] and [a cat] [in [the park]]]]
The only difference between (3a) and (3b) is that the prepositional phrase [in [the park]] is the sister of "saw" in (3a) , but the sister of "a cat" in (3b). However , be cause of this single attachment error, there are 3 pairs of crossing brackets:
- [a dog and a cat] vs. [a cat in the park]
- [with a dog and a cat] vs. [a dog and a cat in the park]
- [a man with a dog and a cat] vs. [with a dog and a cat in the park]
The recall of (3b) is 1 6 0 =60% and the precision is {r=63.6%. In contrast, (3c) is a very shallow parse of the sentence. It has no crossing brackets, perfect pre cision (100%) and a better recall {t 0 =70%) than (3b) . Intuitively, the structure (3b) has a lot more in common with (3a) than (3c) . Yet , (3b) scored much poorly than (3c) according to the precision, recall and the number of crossing-brackets.
In sentence-level evaluations, an error will not be counted more than once. However, the other extreme has to be adopted: no matter how many mistakes a parser makes in a parse tree, they are only counted as one er ror. Thus an answer with a single error is treated the same as an answer with many serious errors. Since how much a parse tree deviates from the correct one greatly influence the chance of the sentence being interpreted correctly, the evaluation scheme should take the degree of the deviation into account.
3. Desiderata
In this section, we motivate the dependency-based eval uation by pointing out several desirable properties that are missing from previous evaluation schemes.
3.1. Ignoring the inconsequential differences
An objective of an evaluation scheme is to identify the differences between answers and keys. However, certain types of differences are of no consequence to the interpre tation of a sentence. An ideal evaluation scheme should make provisions to ignore such differences.
For example, consider sentence structures in (4):
(4)
- [[Bellows [made [the request]]] [while [[the all-woman jury] [was [out [of [the courtroom]]]]]]]
- [Bellows [[made [the request]] [while [[the [[all-woman] jury]] [was [out of [the courtroom]]]]]]]
In ( 4a) , the clause [while ... ] is the sister of [Bellows made the request]. In (4b), it is the sister of [made the request] . Differences such as this are typically of no con sequence to the interpretation of the sentence. However, if (4b) is evaluated against (4a), its scores are as follows :
If a sentence-level evaluation is used, ( 4b) would be clas sified as incorrect, even though, from linguistic point of view, it may well be as reasonable as (4a) .
3.2. Selective evaluation
Previous evaluation schemes only assess the overall per formance of parsers. A more flexible scheme should be able to selectively evaluate parsers with respect to any given types of syntactic phenomena. It would be in teresting to know, for example, how well a parser han dles conjunctions or how well a parser would perform if prepositional attachments were ignored. Answers to these questions would help to determine the suitability of a parser for a particular purpose.
3.3. Facilitate the diagnosis of incorrect parses
Besides measuring the performance of parsers, another service that should be provided by a parser evaluation scheme is to help developers to improve their parsers by pin-pointing exactly where the errors are. As we have discussed earlier a single attachment error may cause several crossing brackets and several spurious/missing phrase boundaries. Given the list of crossing brackets or the sets of spurious/missing phrase boundaries, it is not obvious what caused them to occur.
4. Dependency-based Evaluation
In this section, we propose a dependency-based parser evaluation scheme that offers the desirable properties discussed in the previous section. Instead of phrase boundaries, the scheme is based on the comparison be tween the dependency relations in answers and keys.
4.1. Dependency trees
In a dependency tree, every word in the sentence is a modifier of exactly one other word (called its head), ex cept the head word of the sentence, which does not have a head [Mel'cuk, 1987] . We use a list of tuples to specify a dependency tree. A tuple has the following format:
(modifier cat position head [relationship]) where, modifier is a word in ~he sentence; cat is its lexical category; head is the word that modifier mod ifies; relationship is an optional specification of the type of the dependency relationship between head and modifier, such as subj (subject), adjn (adjunct), cmpl (complement), spec (specifier), etc.; position indicates the position of the head relative to the modifier. It can take one of the following values: { < , >, < < , > > , <<<, ... , *, ?}, where < (or >) means that the head of modifier is the first occurrence of the word head to the left (or right) of the modifier; < < (or > >) means head is the second occurrence of the word head to the left (or right) of the modifier. If position is '*', then the word is the head of the sentence. If position is'?', then the word's head is unknown (either to the parser or the human analyst who created the parse tree).
| Key: (5a) | Answer: (5b) | error | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| I | N | < | saw | subj | I | N | < | saw | subj | |
| saw | v | * | saw | v | * | |||||
| a | Det | < | man | spec | a | Det | < | man | spec | |
| man | N | > | saw | cmpl | man | N | > | saw | cmpl | |
| with | p | > | man | adjn | with | p | > | man | adjn | |
| a | Det | < | dog | spec | a | Det | < | dog | spec | |
| dog | N | < | and | dog | N | < | and | |||
| and | Conj | > | with | cmpl | and | Conj | > | with | cmpl | |
| a | Det | < | cat | spec | a | Det | < | cat | spec | |
| cat | N | > | and | cat | N | > | and | |||
| in | p | > | saw | adjn | in | p | > | cat | adjn | yes |
| the | Det | < | park | spec | the | Det | < | park | spec | |
| park | N | > | in | cmpl | park | N | > | in | cmpl | |
| Key: (5a) | Answer: (6a) | error | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| I | N | < | saw | subj | I | N | < | saw | subj | ||
| saw | v | * | saw | v | * | ||||||
| a | Det | < | man | spec | a | Det | < | man | spec | ||
| man | N | > | saw | cmpl | man | N | > | saw | cmpl | ||
| with | p | > | man | adjn | with | p | ? | yes | |||
| a b. | Det | < | dog | spec | a | Det | < | dog | spec | ||
| dog | N | < | and | dog | N | ? | yes | ||||
| and | Conj | > | with | cmpl | and | Conj | ? | yes | |||
| a | Det | < | cat | spec | a | Det | < | cat | spec | ||
| cat | N | > | and | cat | N | ? | yes | ||||
| in | p | > | saw | adjn | in | p | ? | yes | |||
| the | Det | < | park | spec | the | Det | < | park | spec | ||
| park | N | > | in | cmpl | park | N | > | in | cmpl | ||

The dependency trees of (3a) and (3b) (re-written as (5a) and (5b)) are shown in the first and second column in (5c) respectively.
4.2. Evaluation
Once the answer and the key are both represented as dependency trees, the answer can be scored on a word by-word basis. Since both the answer and the key assign a head to every word in the sentence, we define the error count of the answer to be the number of words that are assigned different heads in the answer than in the key. For example, there is one error in (5b). In contrast, the dependency tree corresponding to the shallow parse tree (3c) (re-written as (6a)) contains 5 unknown heads, each of which is counted as an error (see ( 6b)).
Given two dependency trees key and answer , the func tion evaluate (7) returns the error count of the answer.
The error count is a Hamming distance between the answer and the key, because it is the number of depen dency relationships that must be altered in order to make the answer identical to the key. Compared with scores such as precision, recall, and the number of crossing brackets, the error-count score is intuitively more mean ingful. Since the phrase boundaries themselves are not used directly in semantic interpretation, it is hard to predict how missing or spurious phrase boundaries af fect semantic interpretation. On the other hand, since the semantic dependencies are embedded in the syntactic dependencies, the semantic interpretation process should be more sensitive to the number of missing or spurious syntactic dependencies than the number of missing, spu rious or crossed phrase boundaries.
4.3. Converting constituency trees into depen dency trees
Since the procedure evaluate takes the dependency trees as inputs, whereas almost all the broad-coverage
(7) int evaluate (DepTree key , DepTree answer) { errorCount = 0; for each word in the sentence { if (the position of the key is not equal to '?' and the position or the head of the key is not equal to that of the answer) errorCount = errorCount + 1; } return errorCount; }
parsers and treebanks use constituency grammars, a cru cial issue that must be resolved is how to apply the method to constituency grammars.
In this section, we present an algorithm to transform the constituency trees into dependency trees. If one or both of the key and the answer are represented as con stituency trees, we first transform them into dependency trees and then evaluate the parser with the resulting de pendency trees.
The transformation algorithm is based on Magerman's method for determining heads (lexical representatives) in CFG parse trees [Magerman, 1994, p.64-66]. Following Magerman, the transformation is driven by a Tree Head Table, which contains an entry for every non-terminal symbol in the grammar . Given a node in a constituency tree, the corresponding entry in the Tree Head Table can be used to determine the head child of the node (the head child of a node is either its lexical head or a child that dominates its lexical head).
Entries in a tree head table are triples: (parent direction head-list), where parent is a grammat ical category; direction is either right-to-left or left-to-right; and head-list is a list of grammati cal categories. Three sample entries are shown in (8).
(8) (S right-to-left (Aux VP NP AP PP)) (VP left-to-right (V VP)) (NP right-to-left (Pron N NP))
The first entry means that the head child of an S node is the first Aux node from right to left or, if the S node does not have an Aux child, th·efirst VP node from right to left , .... For example, given the tree head table in (8) and the constituency tree in (9a), the lexical heads and the head children of the nodes in (9a) are listed in (9b).
(9)
a.
child of any given node in a constituency tree using the tree head table.
Unlike [Magerman, 1994], where lexical heads of phrases are identified from bottom up, we use a top-down recursive procedure makeDeps to construct dependency trees according to parse trees. The procedure returns the lexical head of the tree.
(11) Tree makeDeps(Tree root, DepTree deps) { } if (root is a leaf node) return root; Tree headChild = findHeadChild(root); Tree lexHead = makeDeps(headChild, deps); for each non-head child of root { } lexHeadOfChild = makeDeps(child, deps); addDepRel(lexHead, lexHeadOfChild, deps); return lexHead;
The function addDepRel(head, modifier, depTree) inserts the dependency between head and modifier into the dependency tree depTree . The main idea of the al gorithm is as follows :
- find the head child of the root.
- make a recursive call to construct the dependency tree according to the subtree rooted at the head child and return the lexical head of the head child (which is also the lexical head of the root node).
- for all other children of the root
- recursively construct a dependency tree accord ing to the subtree rooted at that child and re turn the lexical head of the child.
- add the dependency relationship between the lexical head of the root and the lexical head of the child.
5. Modifying dependency trees
In [Black et a/., 1991], certain nodes in the answers and keys are erased before they are compared. The erased el ements include, for instance, auxiliaries, "not", and pre infinitival "to". The reason for the removal is that there are many possible ways to analyze structures involving these elements, all of which are correct in their own way. A evaluation scheme should not prefer any one of the theories and penalize the others.
There are many other kinds of allowable differences that may not be eliminated by simply removing elements from parse trees. In this section, we propose a set of op erations for modifying dependency trees in a more flex ible and principled fashion . We then demonstrate, by
| node | lexical head | head child |
|---|---|---|
| s NP1 | v Pron v v | VP1 Pron VP2 v |
| VP1 | ||
| VP2 | ||
| NP2 | N2 | N2 |

(10) Tree findHeadChild(Tree node) I· node is assumed to be interior ·I { TreeHeadEntry entry= search_entry(label(node), treeHeadTable); for each h in headList(entry) { enumerate children of node according to direction(entry) { if (label(currentChild)==h) return currentChild; } } if (direction(entry)='left-to-right') return firstChild(node); else return lastChild(node); }
means of examples, how these operations can be used to eliminate inconsequential differences, and to allow selec tive evaluation.

The process of dependency-based parser evaluation is depicted in Figure 1. The modify module normalize the dependency trees before they are evaluated. The modify module consists of a sequence of operations. Each op eration specifies a possible alternation to a dependency relationship. It consists of a condition part and an action part. If a dependency relationship satisfy the condition , the corresponding action will be performed on the dependency. The algorithm for modify is shown in (12) .
A condition is a triple:
(head modifier [relationship])
where head and modifier are restrictions on the head and the modifier of a dependency relationship. The op tional relationship component is a restriction on the type of the dependency relationship. The first column in Table 1 contains several example conditions. The sec ond column contains the dependency relationships that satisfy the conditions.
The action part specifies the modifications to the dependency relationship. We have implemented three types of actions: {deletion, inversion and transfer}
Deletion: delete(head, modifier, depTree)
removes the dependency relationship between head and modifier from the dependency tree depTree .
Inversion: invert(head, modifier, depTree) reverses the direction of the dependency relationship between head and modifier. In the mean time, if head also has a head (called headOfHead) , then the dependency between the headOfHead and head is replaced with the dependency between headOfHead and modifier.
Transfer: transfer(head, modifier, depTree) transfers modifiers of modifier to head. In other words, all the modifiers of modifier now become modifiers of head.
Figure 2 shows an example of each of these actions.

In the remainder of this section , we demonstrate how these modifications can be used to eliminate inconse quential differences, and to allow selective evaluation.
5.1. Eliminating inconsequential differences
Different grammars often treat adverbs differently. For example, in "she will leave soon", the adverb "soon" can either be analyzed as the modifier of "will" (Figure 3a) or "leave" (Figure 3b ). If the operation:
(if ((cat Aux) (cat V)) (invert transfer)) is applied to both trees, they become identical (Figure 3c). In Figure 3a, the dependency link from "will" to "leave" is first inverted, so that "will" becomes a modifier of "leave". Then, the modifiers of "will" ("she" and "soon") are transferred to "leave", resulting in Figure 3c.
Conjunction is another syntactic phenomenon that tends to be treated differently in different theories. Fig ure 4 shows three alternative analyses of the dependency tree of "saw A and B." They can be transformed into an identical form by the operations shown in the figure. Note that such variations in the analyses of conjunctions cannot be normalized by simply removing elements from parse trees .
5.2. Selective evaluation
The modification to the dependency tree also allows us to selectively evaluate the performance of parsers with
{
for each operation (condition, action) in operations for each dependency relation dep in depTree if (dep satisfies condition) perform action on dep.
| Condition | Dependency relationship between: |
|---|---|
| ((cat N) (cat Det)) | a noun and its determiner |
| ((cat N) (or (string "a") (string "the"))) | a noun and "a" or " the" |
| ((cat Conj) t) | a connective (e.g., "and", "or") and any other word |
| (t (cat P) (type adjn)) | any word and its prepositional adjunct |


regard to various syntactic phenomena. For example, if we want to find out how successfully a parser deals with prepositional phrase attachments, we can use the following operation to delete all the other dependencies except those in which the modifier is a preposition:
(if (t _(not (cat P))) (delete)) On the other hand, evaluating the result of applying
(if (t (cat P)) (delete))
to dependency trees would tell us how a parser would fare if attachments of prepositional phrases are ignored.
6. Conclusion
We have presented a dependency-based method for eval uating broad-coverage parsers. The method offers sev eral advantages over previous methods that relied on the comparison of phrase boundaries. The error count score is not only more intuitively meaningful than other scores, but also more relevant to semantic interpreta tion. We also presented an algorithm that transforms constituency trees into dependency trees so that the eval uation method is applicable to both dependency and constituency grammars. Finally, we proposed a set of operations for modifying dependency trees that can be used to eliminate inconsequential differences among dif ferent parse trees and allow us to selectively evaluate different aspects of a parser.
@inproceedings{ijcai1995p183,
title = {A Dependency-based Method for Evaluating Broad-Coverage Parsers},
author = {Lin, Dekang},
booktitle = {Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, {IJCAI-95}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Chris S. Mellish},
pages = {1420--1426},
year = {1995},
note = {Natural Language},
url = {https://ijcai.org/proceedings/1995/183},
}
TY - CPAPER TI - A Dependency-based Method for Evaluating Broad-Coverage Parsers AU - Lin, Dekang T2 - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95 PB - International Joint Conferences on Artificial Intelligence PY - 1995 SP - 1420 EP - 1426 UR - https://ijcai.org/proceedings/1995/183 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: