Evaluation measures are the basis for quantifying the performance
of IR systems and measurement scales play a central role since
they determine the operations that can be performed with the
measured values and, as a consequence, the statistical analyses that
can be applied. Stevens [
We present our formal theory of IR evaluation measures [
We found that common set- based retrieval measures – namely Precision, Recall, and F-measure – always are interval scales in the case of binary relevance while this does not happen in the multigraded relevance case. In the case of rank-based retrieval measures – namely AP, gRBP, DCG, and ERR – only gRBP is an interval scale when we choose a specific value of the parameter p and define a specific total order among systems while all the other IR measures are not interval scales. We also introduce some brand new set-based and rank-based IR evaluation measures which ensure to be interval scales.
Finally, we discuss the outcomes of an extensive evaluation [
Let us start by introducing an order relation ⪯ on the set of judged
runs R(N). Let rˆ, sˆ ∈ R(N ) such that rˆ , sˆ, and let k be the biggest
relevance degree at which the two runs difer for the first time, i.e.
∗Extended abstract of [
R(N ) is a totally ordered set with respect to the ordering ⪯ defined by (1). As for any totally order set, R(N ) is a poset consisting of only one maximal chain (the whole set); therefore it is graded of rank |R(N )| − 1, where R(N ) = NN+c since it consists of all the N combinations of c + 1 = |REL| objects with repetition. Since R(N ) is graded of rank |R(N )| − 1, there exists a unique rank function ρ(rˆ) : R(N ) −→ N such that ρ(0ˆ) = 0 and ρ(sˆ) = ρ(rˆ) + 1 if sˆ covers rˆ: ρ(rˆ) = ÕN δa(rˆj ) + N − j , j=1 N − j + 1 where rˆ = {rˆ1, . . . , rˆN } ∈ R(N ) with rˆi ⪯ rˆi+1 for any i < N .
The natural distance is then given by ℓ(rˆ, sˆ) = ρ(sˆ) − ρ(rˆ), for rˆ, sˆ ∈ R(N ) such that rˆ ⪯ sˆ, and we can define the diference as ∆ rˆsˆ = ℓ(rˆ, sˆ) if rˆ ⪯ sˆ, otherwise ∆ rˆsˆ = −ℓ(sˆ, rˆ). (R(N ), ⪯d ) is a diference structure. Thus the rank function is an interval scale and we are able to define a new interval-scale measure that follows:
(R(N ), ⪯d ) is: SBTO(rˆ) = ρ(rˆ) = ÕN δa(rˆj ) + N − j . j=1 N − j + 1 3
Top-heaviness is a central property in Information Retrieval (IR), stating that the higher a system ranks relevant documents the better it is. If we apply this property at each rank position and we take to extremes the importance of having a relevant document ranked higher, we can define a strong top-heaviness property which, in turn, will induce a total ordering among runs.
Let rˆ, sˆ ∈ R(N ) such that rˆ , sˆ, then there exists k = min{j ≤ N : rˆ[j] , sˆ[j]} < ∞, and we order system runs as follows rˆ ≺ sˆ ⇔ rˆ[k] ≺ sˆ[k] .
This order prefers a single relevant document ranked higher to
any number of relevant documents, with same relevance degree or
higher, ranked just below it
(uˆ[
Measure Pair Topic-by-Topic Precision vs SBTO 1.0000 Recall vs SBTO 1.0000 F-measure vs SBTO 1.0000 Precision vs Recall 1.0000 SBTO vs RBTO 0.4358
Measure Pair Topic-by-Topic Generalized Precision vs SBTO 0.7325 Generalized Recall vs SBTO 0.7325 Generalized Precision vs Generalized Recall 1.0000 SBTO vs RBTO 0.3895 for any 1 ≤ j ≤ c, for any length N ∈ N and any m ∈ {0, 1, . . . , N − 1}. This is why we call it strong top-heaviness.
R(N ) is totally ordered with respect to ⪯ and is graded of rank (c + 1)N − 1. Therefore, there is a unique rank function ρ : R(N ) −→ {0, 1, . . . , (c + 1)N − 1} which is given by: where δa is the indicator function.
Let us set δa (rˆ) = (δa(rˆ[
The natural distance is then given by ℓ(rˆ, sˆ) = ρ(sˆ) − ρ(rˆ), for rˆ, sˆ ∈ R(N ) such that rˆ ⪯ sˆ, and we can define the diference as ∆ rˆsˆ = ℓ(rˆ, sˆ) if rˆ ⪯ sˆ, otherwise ∆ rˆsˆ = −ℓ(sˆ, rˆ). (R(N ), ⪯d ) is a diference structure. As done before in the set-based case, an interval scale measure on (R(N ), ⪯d ) is given by the rank function itself.
Definition 3.1. The Rank-Based Total Order (RBTO) interval-scale measure on (R(N ), ⪯d ) is:
RBTO(rˆ) = ρ(rˆ) =
N Õ δa(rˆ[i])(c + 1)N −i i=1
We explore the following research question: “How to scales determine the relationship among evaluation measures?”, i.e. what is the relationship between measures which are interval scales, ordinal scale or which are not on any scale? To this end, we will perform Kendall’s τ correlation analysis on TREC 08 Ad-hoc (binary judgements) and TREC 26 Core (multi-graded judgments) collections.
Tables 1 and 2 report the correlation analysis in the case of set-based and rank-based evaluation measures for both binary and multi-graded relevance.
Note that two interval scale measures order systems in the same way on the same topic and their correlation must be 1.0. However, this may be no more true, if you first average performance across (5) (6)
Measure Pair Topic-by-Topic RBP p = 1/2 vs RBTO 1.0000 RBP p = 0.2 vs RBTO 0.9985 RBP p = 0.8 vs RBTO 0.8553 AP vs RBTO 0.6099
Measure Pair Topic-by-Topic
gRBP p = 1/3 vs RBTO 1.0000
gRBP p = 1/3, W3 = [
This can be, for example, observed in Table 1 where Precision, Recall, F-measure, and SBTO are all transformation of the same interval scale and thus their topic-by-topic correlation is 1; on the other hand, their overall correlation, i.e. the traditional one, is diferent from 1.0 because of the efect of the recall base when averaging across topics. This suggest that the diference between Precision and Recall (τ = 0.85) is not due to them ranking systems diferently but just to the fact that the recall base alters the scale properties from topic to topic.
Another interesting case is RBP. For p = 1/2 (p = 1/3 in the multigraded case) it is an interval-scale; for p < 1/2 it is an ordinal but not interval scale and its correlation starts departing from 1.0; the efect is much more pronounced for RBP with p > 1/2 which is neither an ordinal nor an interval scale, suggesting that simply acting on a parameter of a measure can completely alter its scale properties.
A final interesting case is RBTO with diferent weights for the
relevance degrees: W1 = [