For example http://naacl2013.naacl.org/Documents/deep-learning-for-nlp-naacl-2013-tutorial.pdf says "+1.4% F1 Dependency Parsing". How is the F1 score computed when comparing dependency-based parse trees? (I know how to compute the F1 score when I have a confusion matrix in a classification problem)
The PARSEVAL metric does not work for dependency-based parse trees since they don't generate constituents.
Kübler, Sandra, Ryan McDonald, and Joakim Nivre. "Dependency parsing." Synthesis Lectures on Human Language Technologies 1.1 (2009): 1-127.
Chapter 6: Evaluation > Section 6.1: Evaluation metrics
The standard methodology for evaluating dependency parsers, as well as other kinds of parsers, is to apply them to a test set taken from a treebank and compare the output of the parser to the gold standard annotation found in the treebank. Dependency parsing has been evaluated with many different evaluation metrics. The most widely used metrics are listed here
- Exact match: This is the percentage of completely correctly parsed sentences. The same measure is also used for the evaluation of constituent parsers.
- Attachment score: This is the percentage of words that have the correct head. The use of a single accuracy metric is possible in dependency parsing thanks to the single-head property of dependency trees, which makes parsing resemble a tagging task, where every word is to be tagged with its correct head and dependency type. This is unlike the standard metrics in constituency-based parsing, which are based on precision and recall, since it is not possible to assume a one-to-one correspondence between constituents in the parser output and constituents in the treebank annotation.
- Precision/Recall: If we relax the single-head property or if we want to evaluate single dependency types, the following metrics can be used. They correspond more directly to the metrics used for constituent parsing.
- Precision: This is the percentage of dependencies with a specific type in the parser output that were correct.
- Recall: This is the percentage of dependencies with a specific type in the test set that were correctly parsed.
- F-measure (β=1): This is the harmonic mean of precision and recall.
All of these metrics can be unlabeled (only looking at heads) or labeled (looking at heads and labels). The most commonly used metrics are the labeled attachment score (LAS) and the unlabeled attachment score (UAS).
LAS, as we have presented it above, gives an evaluation of how many words were parsed correctly.However, this may not always be the point of interest. Another way of evaluating the quality of dependency parses is using sentences as the basic units. In this case,we calculate for each sentence what the percentage of correct dependencies is and then average over the sentences. The difference becomes clear when we look at a test set containing 2 sentences: Let us assume that for the first sentence, the parser assigned correct dependencies to 9 out of 10 words. For the second sentence, we have 15 out 45 words correct.
- The word-based LAS would be LAS_w = (9 + 15)/(10 + 45) = 0.436.
- The sentence-based LAS is calculated as LAS_s = (9/10 + 15/45)/2 = (0.9 + 0.333)/2 = 0.617.
In the light of this distinction, we can call the word-based LAS micro-average LAS and the sentence-based one a macro-average LAS. Another way of calculating a macro-average LAS is by averaging over all dependency types.
Just adding to Franck's answer: -Recall is not really used in dependency parsing evaluation, because every word is "recalled". Only if you were to measure the precision of a single label, it would make sense.
Another important metric for evaluating dependency parsing is the "branch precision". This metric measures the number of paths from root to nodes which contain only correctly annotated nodes. If the Root is identified incorrectly, the entire sentence is wrong. It considers the nodes closer to the root, in the dependency tree, more important, because they drive the logical structure of the sentence, the trunk.
