=Paper=
{{Paper
|id=Vol-2400/paper-19
|storemode=property
|title=A Formal Theory to Determine Scale Properties of Evaluation Measures
|pdfUrl=https://ceur-ws.org/Vol-2400/paper-19.pdf
|volume=Vol-2400
|authors=Marco Ferrante,Nicola Ferro,Silvia Pontarollo
|dblpUrl=https://dblp.org/rec/conf/sebd/Ferrante0P19
}}
==A Formal Theory to Determine Scale Properties of Evaluation Measures==
https://ceur-ws.org/Vol-2400/paper-19.pdf
A formal theory to determine scale properties of
evaluation measures?
Marco Ferrante1 , Nicola Ferro2 , and Silvia Pontarollo1
1
Department of Mathematics, University of Padua, Italy
{ferrante, spontaro}@math.unipd.it
2
Department of Information Engineering, University of Padua, Italy
ferro@dei.unipd.it
Abstract. Evaluation measures are the basis for quantifying the perfor-
mance of information access systems and the way in which their values
can be processed to perform statistical analyses depends on the scales
on which these measures are defined. For example, mean and variance
should be computed only when relying on interval scales.
We define a formal theory of evaluation measures, based on the represen-
tational theory of measurement, which allows us to determine whether
and when measures are interval scales. 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 multi-graded relevance case. In the case of rank-based re-
trieval 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 measures
are not interval scales.
1 Introduction
Measurement scales play a central role [4,5] 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 [5] identifies four major types
of scales with increasing properties: (i) the nominal scale consists of discrete
unordered values, i.e. categories; (ii) the ordinal scale introduces a natural order
among the values; (iii) the interval scale preserves the equality of intervals or
differences; and (iv) the ratio scale preserves the equality of ratios.
In experimental evaluation we daily perform operations, such as computing
means and variances, which are also the basic “ingredients” of the more sophis-
ticated statistical significance tests we use to compare systems and assess their
differences [1]. However, all these operations can be performed only from interval
Copyright c 2019 for the individual papers by the papers’ authors. Copying per-
mitted for private and academic purposes. This volume is published and copyrighted
by its editors. SEBD 2019, June 16-19, 2019, Castiglione della Pescaia, Italy.
?
Extended abstract of [2]
scales onwards but, due to our limited knowledge of evaluation measures, we do
not actually know which scales they rely on.
This paper sets a theory of evaluation measures to formally investigate their
properties and to study whether and when they use an interval scale. We frame
our work within the representational theory of measurement [4], which is the
measurement theory adopted in both physical and social sciences. In particular,
we develop a fully comprehensive framework, comprising both set-based mea-
sures – namely Precision, Recall and F-measure – dealing with unordered result
lists, and rank-based measures – namely, Average Precision (AP), Discounted
Cumulated Gain (DCG), Rank-Biased Precision (RBP), and Expected Recipro-
cal Rank (ERR) – dealing with ranked result lists. Moreover, we consider both
binary relevance, i.e. when documents can be just relevant or not relevant, and
multi-graded relevance [3], i.e. when documents can have different degrees of
relevance, such as not relevant, partially relevant, and highly relevant.
The paper is organized as follows. Section 2 introduces how to determine
when a measure is an interval scale, according to the representational theory of
measurement; Section 3 introduces our basic formalisms; Sections 4 and 5 discuss
set-based and rank-based evaluation measures, respectively; finally, Section 6
wraps up the discussion and outlooks some future work.
2 Representational Theory of Measurement
Given E, a weakly ordered empirical structure is a pair (E, ) where, for every
a, b, c ∈ E,
• a b or b a;
• a b and b c ⇒ a c (transitivity).
Note that if a, b ∈ E are such that a b and b a, then we write a ∼ b and
we say that a and b are equivalent elements of E for . When the antisymmetric
relation holds, that is when a b and b a implies that a and b are the same
element (namely a = b), we talk about a total order.
An interval on the empirical structure is an element (a, b) ∈ E × E and we
introduce a notion of difference ∆ab over intervals, to act as a signed distance
we exploit to compare intervals. Once we have a notion of difference ∆ab , we can
define a weak order d between the ∆ab differences and, consequently, among
intervals. We can proceed as follows: if two elements a, b ∈ E are such that a ∼ b,
then the interval [a, b] is null and, consequently, we set ∆ab ∼d ∆ba ; if a ≺ b we
agree upon choosing ∆aa ≺d ∆ab which, in turn implies that ∆aa d ∆ba , that
is there exist a kind of “zero” and the inverse with respect to this “zero”.
Definition 1. Let E be a finite (not empty) set of objects. Let d be a binary
relation on E × E that satisfies, for each a, b, c, d, a0 , b0 , c0 ∈ E, the following
axioms:
i. d is weak order;
ii. if ∆ab d ∆cd , then ∆dc d ∆ba ;
iii. Weak Monotonicity: if ∆ab d ∆a0 b0 and ∆bc d ∆b0 c0 then ∆ac d ∆a0 c0 ;
iv. Solvability Condition: if ∆aa d ∆cd d ∆ab , then there exists d0 , d00 ∈ R
such that ∆ad0 ∼d ∆cd ∼d ∆d00 b .
Then (E, d ) is a difference structure.
The representation theorem for difference structures states:
Theorem 1. Let E be a finite (not empty) set of objects and let (E, d ) be a
difference structure. Then, there exist an interval scale measurement M : E → R
such that for every a, b, c, d ∈ E
∆ab d ∆cd ⇔ M(b) − M(a) ≤ M(d) − M(c) .
This theorem ensures us that, if there is a difference structure on the empir-
ical set E, then there exists an interval scale M over it.
Therefore, to study whether evaluation measures are interval scales or not, [2]
proceeded as follows:
1. Define a total ordering among system runs, which allows us also to introduce
the notion of interval among runs;
2. Since this set is graded of a given rank n, there exists a unique rank function
ρ which assigns a natural number to each run;
3. Define the length of an interval as the natural distance ∆ab := `(a, b) :=
`([a, b]) = ρ(b) − ρ(a);
4. Check whether the set with the above natural length is a difference structure
or not;
5. In this case we have a difference structure and we can define an interval scale
M as the rank function ρ itself;
6. We can eventually check whether evaluation measures are a linear positive
transformation of this interval scale M and determine whether they are an
interval scale.
3 Basic Formalism
Let (REL, ) be a finite and totally ordered set of relevance degrees. We set
REL = {a0 , a1 , . . . , ac } with ai ≺ ai+1 for all i ∈ {0, . . . , c − 1}; REL has a
minimum a0 , called the “not relevant” relevance degree. Let us consider a finite
set of documents D and a set of topics T . For each pair (t, d) ∈ T × D, the
ground-truth GT is a map which assigns a relevance degree rel ∈ REL to a
document d with respect to a topic t. Let N be a positive natural number called
the length of the run. We assume that all the runs have same length N , since this
is what typically happens in real evaluation settings when you compare systems.
We define D(N ) as the set of all the possible N retrieved documents.
A run r : T → D(N ) retrieves N documents belonging to D(N ) in response
to a topic t ∈ T.
Let R(N ) be the set of N judged documents, that is the set of all the N
possible combinations of relevance degrees.
We call judged run of length N the function r̂ from T × D(N ) into R(N )
which assigns a relevance degree to each retrieved document, i.e. a judged run r̂
is the application of the ground-truth GT function to each element of the run r.
We define the gain function g : REL → R+ as the map that assigns a
positive real number to any relevance degree. We set, without loss of generality,
g(a0 ) = 0 and we require g to be strictly increasing.
We define the indicator function for the relevance degrees as δa (aj ) =
j ∀j ∈ {0, . . . , c}. Note that δa is a particular gain function.
Given the gain function g, the recall base RB : T → R+ is the map defined
P|D|
as RB(t) = j=1 g(GT (t, dj )). In the binary relevance case when c = 1 and
REL = {a0 , a1 }, the gain function usually is g(a1 ) = δa (a1 ) = 1 and RB
counts the total number of relevant documents for a topic.
An evaluation measure is a function M : R(N ) → R+ which maps a judged
run r̂ into a positive real number which quantifies its effectiveness. Note that
most of the evaluation measures are normalized and thus the co-domain is the
[0, 1] interval.
4 Set-based Measures
Let us start by introducing an order relation on the set of judged runs. Let
r̂, ŝ ∈ R(N ) such that r̂ 6= ŝ, and let k be the biggest relevance degree at which
the two runs differ for the first time, i.e. k = max{j ≤ c : {i : r̂i = aj } 6= {i :
ŝi = aj } }. We strictly order any pair of distinct system runs as follows
r̂ ≺ ŝ ⇔ {i : r̂i = ak } < {i : ŝi = ak } . (1)
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 ) =
N +c
N 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 ρ(ŝ) = ρ(r̂) + 1 if ŝ covers r̂:
N
X δa (r̂j ) + N − j
ρ(r̂) = , (2)
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̂, ŝ) = ρ(ŝ) − ρ(r̂), for r̂, ŝ ∈ R(N )
such that r̂ ŝ, and we can define the difference as ∆r̂ŝ = `(r̂, ŝ) if r̂ ŝ,
otherwise ∆r̂ŝ = −`(ŝ, r̂). (R(N ), d ) is a difference structure. Thus the rank
function is an interval scale and we are able to define a new measure that follows:
Definition 2. The Set-Based Total Order (SBTO) measure on (R(N ), d ) is:
N
X δa (r̂j ) + N − j
SBTO(r̂) = ρ(r̂) = . (3)
j=1
N −j+1
This measure satisfies the condition imposed by Theorem 1. Thus, SBTO is an
interval scale on (R(N ), d ).
Let us explore more deeply how the SBTO measure works. The first rele-
vance degree immediately above not relevant, i.e. a1 , always gives a constant
contribution, independently from how many a1 documents are retrieved, since:
δa (a1 ) + N − j 1+N −j
= =1.
N −j+1 N −j+1
However, when we consider higher relevance degrees, i.e. ak with k > 1, the
binomial coefficient strictly depends and changes on the basis of how many of
them are retrieved. Indeed, δa (ak ) is constant for all the documents with the
same relevance degree ak , but the term N − j decreases as the number of ak
retrieved documents increases due to N being constant and j increasing, i.e. the
binomial coefficient is decreasing in the number of ak retrieved documents. In
other terms, each additional ak retrieved document gives a contribution smaller
than the previously retrieved ones by a discount factor j.
4.1 Binary Relevance Case
When c = 1, i.e. in the binary relevance case, the ordering (1) just orders judged
runs by how many relevant documents they retrieve, i.e. by their total mass of
relevance:
XN N
X
r̂ ŝ ⇔ δa (r̂i ) ≤ δa (ŝi ) ,
i=1 i=1
since there is only one relevant relevance degree a1 .
Therefore the rank function becomes
N
X
ρ(r̂) = δa (r̂i ) = M(r̂) .
i=1
This follows easily from (3), using the fact that δa (r̂i ) ∈ {0, 1} for any i ≤ N
when c = 1.
Let now g be the gain function, and let us consider Precision
N N
1 X g(r̂i ) 1 X M(r̂)
Precision (P)(r̂) = = δa (r̂i ) = ,
N i=1 g(a1 ) N i=1 N
since g(a0 ) = 0 = δa (a0 ) and c = 1. Thus Precision is an interval scale, as it is
a linear positive transformation of M.
Similarly, Recall
N N
1 X g(r̂i ) 1 X M(r̂)
Recall (R)(r̂) = = δa (r̂i ) =
RB i=1 g(a1 ) RB i=1 RB
is an interval scale.
The F-measure, that is the harmonic mean of Precision and Recall,
N
P(r̂) · R(r̂) 2 X 2M(r̂)
F(r̂) = 2 = δa (r̂i ) =
P(r̂) + R(r̂) N + RB i=1 N + RB
is an interval scale as well.
4.2 Multi-graded Relevance Case
Neither Generalized Precision nor Generalized Recall are a positive linear trans-
formation of M defined in (3). Indeed, in these measures, the individual contri-
bution of each retrieved document r̂j is independent from the contribution of any
other retrieved document r̂k . However, the previous discussion on the measure
defined in (3) pointed out that, for each relevance degree ak with k > 1, the
individual contribution of an ak retrieved document depends on how many ak
retrieved documents there are in the run. Therefore neither gP nor gR are an
interval scale, since they cannot be a linear transformation of M.
Moreover they are not even an ordinal scale which, again, implies they cannot
be an interval scale too. Indeed, a measure M0 is an ordinal scale on R(N ) if, for
every r̂, ŝ ∈ R(N ), the following statement is true:
r̂ ŝ ⇔ M0 (r̂) ≤ M0 (ŝ) .
Let us consider r̂ = {a1 , . . . , a1 } and ŝ = {a2 , a0 , . . . , a0 }, two runs of length
N . We have r̂ ≺ ŝ. Moreover, since Generalized Recall (gR) and Generalized
PN
Precision (gP) are both proportional to G(v̂) := i=1 g(v̂i )/g(ac ), for any v̂ ∈
R(N ), we can prove that G(·) is not on an ordinal scale with respect to the
order (1). Since g(a0 ) = 0, G(r̂) = N g(a1 )/g(ac ) while G(ŝ) = g(a2 )/g(ac ).
From the fact that the gain function g is a positive strictly increasing function
and it is defined independently from the length N of the runs, by choosing a N
big enough we can have G(r̂) > G(ŝ).
5 Rank-based Measures
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̂, ŝ ∈ R(N ) such that r̂ 6= ŝ, then there exists k = min{j ≤ N : r̂[j] 6=
ŝ[j]} < ∞, and we order system runs as follows
r̂ ≺ ŝ ⇔ r̂[k] ≺ ŝ[k] . (4)
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
(û[1], . . . , û[m], a0 , ac , . . . , ac ), ≺ (û[1], . . . , û[m], aj , a0 , . . . , a0 ) ,
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:
N
X
ρ(r̂) = δa (r̂[i])(c + 1)N −i , (5)
i=1
where δa is the indicator function.
Let us set δa (r̂) = (δa (r̂[1]), . . . , δa (r̂[N ])). If we look at δa (r̂) as a string,
the rank function is exactly the conversion in base 10 of the number in base c + 1
identified by δa (r̂) and the ordering among runs corresponds to the ordering
≤ among numbers in base c + 1.
The natural distance is then given by `(r̂, ŝ) = ρ(ŝ) − ρ(r̂), for r̂, ŝ ∈ R(N )
such that r̂ ŝ, and we can define the difference as ∆r̂ŝ = `(r̂, ŝ) if r̂ ŝ,
otherwise ∆r̂ŝ = −`(ŝ, r̂). (R(N ), d ) is a difference 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. The Rank-Based Total Order (RBTO) measure on (R(N ), d )
is:
N
X
RBTO(r̂) = ρ(r̂) = δa (r̂[i])(c + 1)N −i (6)
i=1
This measure satisfies the condition imposed by Theorem 1. Thus, RBTO is an
interval scale on (R(N ), d ).
Let G = minj∈{1,...,c} (g(aj )−g(aj−1 ))/g(ac ) > 0 be the normalized smallest
gap between the gain of two consecutive relevance degrees.
Graded Rank-Biased Precision (gRBP)p with p > G/(G + 1) and other IR
measures – namely AP, DCG, and ERR – are not even an ordinal scale on
R(N ), as the following example shows. Let r̂ = (a1 , a0 , a2 , a0 , a1 ) and ŝ =
(a1 , a1 , a0 , a0 , a0 ) be two runs on R(5) with c = 2 and let us use the indicator
function δ as gain function g. We have r̂ ŝ. Then DCG2 (r̂) = 1 + 2/ log2 3 +
1/ log2 5 > 1 + 1 = DCG2 (ŝ); ERR(r̂) = 1/4 + 3/16 + 3/320 > 1/4 + 3/32 =
ERR(ŝ); finally, since g(a2 ) = δa (a2 ) = 2, 2gRBPp (r̂) = (1 − p)(1 + 2p2 + p4 ) >
(1 − p)(1 + p) = 2gRBP(ŝ) for p & 0.454, and such an example can be found
for any other values of p > G/(G + 1), where G = 1/2. AP is a binary measure
and, just to stay with the same data above, we adopt a lenient mapping of
multi-graded to binary relevance degrees setting g(a1 ) = g(a2 ) = 1 and thus
RB·AP(r̂) = 1 + 2/3 + 3/5 > 1 + 1 = RB·AP(ŝ), where RB is the recall base.
As a consequence, being not an ordinal scale, gRBPp with p > G/(G+1), AP,
DCG, and ERR cannot be an interval scale too, since an interval scale measure
is also an ordinal scale. gRBPp with p ≤ G/(G + 1) is interval if and only if
p = G/(1 + G) = (c + 1)−1 and the gain function is equal to g(ai ) = Kδa (ai ),
for any i ∈ {0, . . . , N} and for any K > 0 fixed.
6 Conclusion and Future Works
We developed a theory of evaluation measures to explore whether and when both
set-based and rank-based IR measures are interval scales. This is a fundamental
question since the validity of the descriptive statistics, such as mean and variance,
and the statistical significance tests we daily use to compare IR systems depends
on its answer.
We summarize here the main findings of our framework:
– set-based evaluation measures:
• binary relevance: precision, recall, F-measure are interval scales;
• multi-graded relevance: gP and gR are neither ordinal nor interval scales;
– rank-based evaluation measures:
• binary relevance: RBP is an interval scale only for p = 1/2 and it is an
ordinal scale for p < 1/2; RBP for p > 1/2 and AP are neither ordinal
nor interval scales;
• multi-graded relevance: gRBP is an interval scale only for p = G/(G + 1)
and when the gain function is equal to g(ai ) = Kδa (ai ); gRBP is an
ordinal scale when p < G/(G + 1); gRBP for p > G/(G + 1), DCG, and
ERR are neither ordinal nor interval scales.
As future work, we will investigate these new interval scale measures from an
experimental point of view, e.g. by performing an analysis of their robustness to
pool downsampling or of their discriminative power, as well as the exploration of
how they behave in statistical significance testing with respect to the traditional
evaluation measures which, instead, violate the interval scale assumption.
References
1. Carterette, B.A.: Multiple Testing in Statistical Analysis of Systems-Based Infor-
mation Retrieval Experiments. ACM TOIS 30(1), 4:1–4:34 (2012)
2. Ferrante, M., Ferro, N., Pontarollo, S.: A General Theory of IR Evaluation Measures.
IEEE TKDE 31(3), 409–422 (March 2019)
3. Kekäläinen, J., Järvelin, K.: Using Graded Relevance Assessments in IR Evaluation.
JASIST 53(13), 1120–1129 (November 2002)
4. Krantz, D.H., Luce, R.D., Suppes, P., Tversky, A.: Foundations of Measurement.
Additive and Polynomial Representations, vol. 1. Academic Press, USA (1971)
5. Stevens, S.S.: On the Theory of Scales of Measurement. Science, New Series
103(2684), 677–680 (June 1946)