Significance tests for the evaluation of ranking methods

Significance tests for the evaluation of ranking methods Stefan Evert Institut f¨ur maschinelle Sprachverarbeitung Universit¨at Stuttgart Azenbergstr. 12, 70174 Stuttgart, Germany evert@ims.uni-stuttgart.de Abstract This paper presents a statistical model that in- terprets the evaluation of ranking methods as a random experiment. This model predicts the variability of evaluation results, so that appro- priate significance tests for the results can be derived. The paper concludes with an empirical validation of the model on a collocation extrac- tion task. 1 Introduction Many tools in the area of natural-language process- ing involve the application of ranking methods to sets of candidates, in order to select the most use- ful items from an all too often overwhelming list. Examples of such tools range from syntactic parsers (where alternative analyses are ranked by their plau- sibility) to the extraction of collocations from text corpora (where a ranking according to the scores as- signed by a lexical association measure is the essen- tial component of an extraction “pipeline”). To this end, a scoring function g is applied to the candidate set, which assigns a real number g(x) ∈ R to every candidate x.1 Conventionally, higher scores are assigned to candidates that the scoring function considers more “useful”. Candidates can then be selected in one of two ways: (i) by compar- ison with a pre-defined threshold γ ∈ R (i.e. x is accepted iff g(x) ≥ γ), resulting in a γ-acceptance set; (ii) by ranking the entire candidate set accord- ing to the scores g(x) and selecting the n highest- scoring candidates, resulting in an n-best list (where n is either determined by practical constraints or in- teractively by manual inspection). Note that an n- best list can also be interpreted as a γ-acceptance set with a suitably chosen cutoff threshold γg(n) (deter- mined from the scores of all candidates). Ranking methods usually involve various heuris- tics and statistical guesses, so that an empirical eval- 1Some systems may directly produce a sorted candidate list without assigning explicit scores. However, unless this opera- tion is (implicitly) based on an underlying scoring function, the result will in most cases be a partial ordering (where some pairs of candidates are incomparable) or lead to inconsistencies. uation of their performance is necessary. Even when there is a solid theoretical foundation, its predictions may not be borne out in practice. Often, the main goal of an evaluation experiment is the comparison of different ranking methods (i.e. scoring functions) in order to determine the most useful one. A widely-used evaluation strategy classifies the candidates accepted by a ranking method into “good” ones (true positives, TP) and “bad” ones (false positives, FP). This is sometimes achieved by comparison of the relevant γ-acceptance sets or n- best lists with a gold standard, but for certain ap- plications (such as collocation extraction), manual inspection of the candidates leads to more clear-cut and meaningful results. When TPs and FPs have been identified, the precision Π of a γ-acceptance set or an n-best list can be computed as …

Content truncated to 500 words