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.
