Is there a well-established metric to measure the effectiveness of a parsing algorithm?

My understanding that 100% accurate parsing (analyzing a text and creating a syntactic tree) is an impossible task for computational linguistics at this moment. However, there are many heuristics or approximation algorithms that produces good enough results. Do we have some kind of metric to rate the effectiveness of these algorithms? How does it work? For example, I guess we can run the algorithm against a set of text whose syntactic tree we already know and then compare the program's output against the known sytactic tree? Or do we use other methods?

Are there already well-established metrics/scoring system to rate parsing? How do they work?

• Darn, just remembered that something similar was asked before. Can we close this as duplicate? Or we can let this be because there are probably other method than comparing against a known corpus May 4, 2012 at 3:28
• Is the question covering the same ground or are you looking for a different answer that is not covered in that question? May 4, 2012 at 11:05
• I guess my question is more generic than that one.. this one talks about any type of metric, that one is only from comparing against known corpus.. but I suspect the answer is probably the same May 4, 2012 at 13:31
• I agree, the previous answer is about where the golden parses come from, whereas your question pretty clearly seems to be about how the score is measured. Additionally, there are some metrics that don't presume knowledge of the solution for each tree, which is totally unaddressed by the other question. I'll take a shot at the least. May 4, 2012 at 19:15

The most common evaluation metrics examine the conceptual "distance" between the candidate parse generated by the parser, and the correctly annotated solution (the "gold standard"). Gold standards are sometimes annotated by hand, but more often they come from existing corpora (Is there a standard corpus against which to benchmark mechanical parsers? has related discussion). A common choice is the Wall Street Journal sections of the Penn Treebank.

Generally speaking, the current standard comparison is the PARSEVAL metric (Black, et al 1991). It defines a set of values that focus primarily on the constituency differences between the two trees. The main values are:

• Precision: The number of correct constituents out of the number of constituents in the candidate parse.

• Recall: The number of correct constituents out of the number of constituents in the gold standard.

• F-Score: The harmonic mean of precision and recall (see below).

To demonstrate the concept, consider the pair of trees given below.

The constituents for each are given below in form label:yield (yield is the span of the node/constituent).

``````Candidate  gold
X:a      X:a
Y:b      Z:b
Z:cd     V:cd
--       Y:bcd
W:abcd   W:abcd
``````

As you can see, all of the constituents in the candidate have correct yield, so we have 4/4 = 100% precision, but there is an extra node in the hierarchy of the gold, so we only have 4/5 = 80% recall. These values then give us an F-score of 2*1*0.8/(1+0.8) = 88.9%.

We may also want to consider the accuracy of the labels. In this case we can use the labelled precision and labelled recall (potentially introduced by Collins 1997). These metrics only count a node as correct if its yield AND label match the gold standard. Above, only 2 out of our 4 nodes with correct yield have the correct label (W & X), so we get:

``````P = 50%  R = 40%  F = 44.4%
``````

PARSEVAL also includes one last value—the number of crossing brackets. This is simply a count of how many constituent boundaries in the candidate cross over constituent boundaries in the gold. These errors might be considered more serious, because they often indicate an element is in the completely wrong grouping. In the above example there are no crossing brackets.

As you may have noticed, PARSEVAL is a rather coarse metric, and it certainly is not without conceptual flaws. Among the complaints:

• Rewards shallow/safe analyses better than those that make more claims but a few mistakes.
• Especially with corpora, punishes parsers that provide more information than necessary.
• Some "single" errors can hurt the score repeatedly, for example a single misplaced node may trigger multiple crossing brackets and incorrect yields.
• Weights all nodes evenly, rather than making crucial semantical relations more important.

There are several competing metrics to address some of these issues. One such is Sampson's leaf-ancestor metric. This method examines the lineage of each terminal node—the list of nodes that connect it to the root—and determines the edit distance from the lineage of that node in the gold standard. The creators argue that this is a much more intuitive sense of accuracy, mostly because the Parseval metric "lays excessive weight on locating the exact boundaries of constructions," (Sampson & Babarczy) which might not be as semantically important as the "ancestry" for each word.

Still, PARSEVAL remains in widespread use, most likely because it is simple and most of its flaws are "equally flawed" for different parsing approaches. ACL's state-of-the-art listing continues to use it (though this wiki link only has a few recent parsers included).

One should note that the above vision doesn't apply to all models of grammar. Dependency grammars in particular have become popular for parsing in the last decade. These do not intrinsically define constituents, so they cannot utilise the formulas as given above. Note: I cannot attest well enough to other models at the moment, so perhaps someone else can come along.

Lastly, consider that there are factors that one might evaluate that don't compare parses with a standard. Most statistical parsers assign a score to each parse for the purposes of ranking and choosing the best. One may want to adjust the values of this score without even knowing if the parse is correct. (e.g. in a parser whose top candidates all get very uncertain scores or one that responds poorly to unknown entities). There are plenty of other goal-dependent values too. For example, necessary training set size might be a big factor to a parser that aims to approach optimal output with minimal input.

In any case, these tools are only used for rough comparisons. Any fine-grained evaluations will consider many metrics, and when controlled for different factors—languages, training sets, tuning values, time/memory limitations, etc. Ultimately it comes down to the idea of success for the given problem, which is usually tough to quantify, and impossible to compare unilaterally.

• I don't currently have access to any of the "standard" NLP reference books (ie Jurafsky/Martin, Manning/Schutze). If anyone has nice references from those, they'd probably really improve the answer. ;) May 4, 2012 at 22:16
• How can I obtain a code or program to evaluate my trees? Jun 25, 2016 at 12:33
• Nice explanation. Unfortunately, the links (Black et. al, and Collins) to the paper are broken. Can you update them? Feb 17, 2017 at 8:34

The recall metric is ignored when evaluating syntactic trees because all tokens are being labeled in one way or another. There are 5 most common metrics for the evaluation of syntactic dependency parsing:

• Head Attachment Score (percent of nodes which are correctly attached to their parent)
• Label Precision (percent of nodes whose dependency labeled is predicted correctly)
• Labeled Attachment Score (percent of node for which both of the above are true)
• Branch Precision (percent of the Paths (from root to leaf) that are being classified correctly)
• Correct trees precision (percent of the sentences from the eval corpus which have been parsed flawlessly)