Evaluation measures play an important role in IR experimental evaluation and their properties determine the kind of statistical analyses we can conduct. It has been previously shown that it is questionable that IR effectiveness measures are on an interval-scale and this implies that computing means and variances is not a permissible operation. In this paper, we investigate whether it is possible to relax a bit the denition of interval scale, introducing the notion of intervallike scale, and to what extent IR eectiveness measures comply with this relaxed denition.
•Information systems ! Retrieval eectiveness;
Evaluation plays a central role in Information Retrieval (IR) and a
lot of aention is devoted to improving our evaluation
methodologies and practices. For example, since many years, there is a
continued interest on how to properly apply statistical techniques
to the analysis of IR experimental data, e.g., on the appropriate use
of statistical testing [
However, all these studies rely on some, oen hidden and implicit,
assumptions on what IR eectiveness measures are. In particular,
measurement scales [
erefore, researchers started to study what IR eectiveness
measures are, not only from an empirical perspective, e.g., [
In this paper, we stem from the recent work of [
[
erefore, [
Strong top-heaviness provides us with a total ordering among
runs and, as discussed above, there is at least one case of IR
measure on an interval scale; however, the way in which strong
topheaviness orders runs may give raise to disagreement or corner
cases. For example, strong top-heaviness ranks the run ¹1; 0; 0; 0º
with just one top relevant document before the run ¹0; 1; 1; 1º with
all relevant documents except for the rst position; thus, there
might be disagreement on whether this is an appropriate ordering
for these runs. On the other hand, weak top-heaviness provides
us with a much more intuitive partial ordering based on two basic
operations – swapping two consecutive documents in a ranking
and replacing a not relevant document with a relevant one [
e problem with IR eectiveness measures emerging from [
In this paper, we take a dierent approach to the ordering of
intervals of runs, not based on single numbers, as the natural distance
of [
e paper is organized as follows: Section 2 recaps some basic concepts about the representational theory of measurement and posets; Section 3 deals with interval-like scales; nally, Section 4 wraps up the discussion and outlooks some future work. 2 2.1
A relational structure [
A relational structure E is called empirical if its domain set E spans over the entities under consideration in the real world, i.e. the system runs in our case; a relational structure S is called symbolic if its domain set S spans over a given set of numbers. A measurement (scale) is the homomorphism M = M; MR from the real world to the symbolic world and a measure is the number assigned to an entity by this mapping. 2.2
[
Given E, a weakly ordered empirical structure is a pair ¹E; º where, for every a; b; c 2 E, a a b or b b and b a; c ) a c.
Given ¹E; º, we have to dene a dierence Δab between two elements a; b 2 E, which is a kind of signed distance we exploit to compare intervals. en, we have to dene a weak order d between these Δab dierences. We can proceed as follows: if two elements a; b 2 E are such that a b, i.e. a b and b a, 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 .
Definition 1. Let E be a nite (not empty) set of objects. Let d be a binary relation on E E that satises, for each a; b; c; d; a0; b 0; c 0 2 E, the following axioms: i. d is weak order; ii. if Δab d Δcd , then Δdc d Δba ; iii. if Δab d Δa0b0 and Δbc d Δb0c0 then Δac d Δa0c0 ; iv. Solvability Condition: if Δaa d Δcd d Δab ; then there exists d 0; d 00 2 E such that Δad0 d Δcd d Δd00b : en ¹E; d º is a dierence structure.
Particular aention has to be paid to the Solvability Condition which ensures the existence of an equally spaced gradation between the elements of E, indispensable to construct an interval scale measurement.
e representation theorem for dierence structures states: Theorem 1. Let E be a nite (not empty) set of objects and let ¹E; d º be a dierence structure. en there exist a measurement scale M : E ! R such that for every a; b; c; d 2 E Δab d Δcd , M a ¹ º
M b ¹ º
M c ¹ º
M¹dº : is theorem ensures us that, if there is a dierence structure on the empirical set E, then there exists an interval scale M.
As anticipated in Section 1, we will introduce the notion of interval-like scale which corresponds to removing the solvability condition from the denition of dierence structure and obtaining a new partial ordering of the intervals of runs. 2.3
A partially ordered set P , poset for short, is a set with a partial order
dened on it [
A closed interval is a subset of P dened as »s; t ¼ B fu 2 P : s u t g, where s; t 2 P and s t . Moreover we say that t covers s if s t and »s; t ¼ = fs; t g; that is there does not exist u 2 P such that s u t :
We can represent a nite poset P by using the Hasse diagram which is a graph where vertices are the elements of P , edges represent the covers relations, and if s t then s is below t in the diagram.
A subset C of a poset P is a chain if any two elements of C are comparable: a chain is a totally ordered subset of a poset. If C is a nite chain, the length of C, `¹Cº, is dened by `¹Cº = jC j 1: A maximal chain of P is a chain that is not a proper subset of any other chain of P .
If every maximal chain of P has the same length n, we say that P is graded of rank n; in particular there exists a unique function ρ : P ! f0; 1; : : : ; ng, called the rank function, such that ρ¹sº = 0, if s is a minimal element of P , and ρ¹t º = ρ¹sº + 1, if t covers s.
Finally, since any interval on a graded poset is graded, the length of an interval »s; t ¼ is given by `¹s; t º B `¹»s; t ¼º = ρ¹t º ρ¹sº, also called the natural distance. 3 3.1
Given N , the length of the run, we dene the set of retrieved documents as D¹N º = f¹d1; : : : ; dN º : di 2 D; di , dj for any i , j g, i.e. the ranked list of retrieved documents without duplicates, and the universe set of retrieved documents as D := ÐNjD=j1 D¹N º. A run rt , retrieving a ranked list of documents D¹N º in response to a topic t 2 T , is a function from T into D
t 7! rt = ¹d1; : : : ; dN º We denote by rt »j¼ the j-th element of the vector rt , i.e. rt »j¼ = dj .
We dene the universe set of judged documents as R := ÐjD j RELN , where RELN is the set of the ranked lists of judged
N =1 retrieved documents with length xed to N . Since in our case REL = f0; 1g, RELN = f0; 1gN refers to the space of all N length vectors consisting of 0 and 1. As for the set-based case, we denote by RBt the recall base, i.e. the total number of relevant documents for a topic.
We call judged run the function rˆt from T D into R, which assigns a relevance degree to each retrieved document in the ranked list
¹t ; rt º 7! rˆt = GT ¹t ; d1º; : : : ; GT ¹t ; dN º We denote by rˆt »j¼ the j-th element of the vector rˆt , i.e. rˆt »j¼ = GT ¹t ; dj º.
As for the set-based case, we can simplify the notation omiing the dependence on topics, rˆ B rˆ»1¼; : : : ; rˆ»N ¼ , RB, and so on. 3.2
Let us start recalling the ordering between runs adopted in this
paper and based on the following two monotonicity-like properties
proposed by [
Replacement A measure of retrieval eectiveness should not decrease when replacing a document with another one in the same rank position with higher degree of relevance. Swap If we swap a less relevant document with a more relevant one in a lower rank position, the measure should not decrease.
ese two properties lead to the following partial ordering among system runs rˆ sˆ , k Õ rˆ»j¼ j=1 k Õ sˆ»j¼ 8k 2 f1; : : : ; N g : j=1 (1) is ordering considers a run bigger than another one when, for each rank position, it has more relevant documents than the other one up to that rank.
is is the same ordering of runs used by [
To dene the length of an interval we adopt the following strategy: given rˆ; sˆ 2 RELN with rˆ sˆ, we count how many replacements in the last position and how many forward single-step swaps at each depth are necessary to go from rˆ to sˆ following a maximal chain in RELN . In order to do this, it is useful to dene the cumulative sums of a vector v = ¹v»1¼; : : : ; v»N ¼º, denoted using the capital leer as V = ¹V »1¼; : : : ; V »N ¼º; where V »j¼ = Íj i=1 v»i¼.
Let us start with a simple example.
Since 0ˆ rˆ, in order to construct a chain from 0ˆ to rˆ with the two basic operators (replacement in last position and single-step forward swap) we get We have made two replacement in the fourth position, one swap in the second position and two in the third one. Recall that with swap at depth i we mean that a forward swap from position i 1 to position i was done. We can count how many of these basic operations in each position are needed to go from 0ˆ to rˆ just taking the cumulative sums of rˆ. Indeed we get
Rˆ = ¹0; 1; 2; 2º ; and each entry k < D of Rˆ, Rˆ»k¼, counts the number of swaps made in position k, while Rˆ»N ¼ counts the number of replacement, i.e. the total mass of rˆ, to go from 0ˆ to rˆ.
More generally, given two vectors rˆ; sˆ 2 RELN , with rˆ sˆ, in order to collect the number of basic operations made at each position to go from rˆ to sˆ, we can compute this vector of length N rst between 0ˆ and rˆ and between 0ˆ and sˆ, namely Rˆ and Sˆ, and then subtract the two vectors. Precisely Sˆ Rˆ leads to a new vector of length N , where each entry k equals the number of swaps or replacements (if k = N ) needed to go from rˆ to sˆ.
Example. In order to beer understand this mechanism, let us consider a second example. Consider the two judged runs in REL4 In order to construct a chain from rˆ to sˆ with the two basic operators (replacement in last position and single-step forward swap) we get rˆ = ¹0; 1; 0; 0º ; sˆ = ¹1; 0; 1; 0º : rˆ = ¹0; 1; 0; 0º ; vˆ = ¹1; 0; 0; 0º ; wˆ = ¹1; 0; 0; 1º ; sˆ = ¹1; 0; 1; 0º : We have made a swap in the rst and third position and a replacement in the fourth position, that we can collect in a vector as sˆ: Moreover
Sˆ Rˆ = ¹0; 1; 1; 1; 2; 1; 1; 1; 0; 1º: Let t = Sˆ Rˆ. For any i < 10, t »i¼ tells us how many swaps one needs to do at depth i to make the smallest run coincide with the biggest one. Moreover, if the total number of relevant relevancedegrees is not equal for both, as in this example, the last entry of t , t »N ¼, is exactly the number or replacements on rˆ one needs to make, and coincide with Íi sˆ¹iº Íi rˆ¹iº.
Given an interval »rˆ; sˆ¼; if we take the cumulative sums of t =
Sˆ Rˆ we obtain the vector T of the cumulative sums of t that
counts, for every i N , the total number of swaps (or replacements,
if i = N ) made from depth 1 to i between the endpoints of the
given interval. e vector T can be seen as a new and generalized
denition of the length of the interval »rˆ; sˆ¼, which replaces the
natural distance used by [
According to this new distance, we say that the interval »rˆ1; sˆ1¼ is smaller than or equal to the interval »rˆ2; sˆ2¼ if, for the vectors T1 and T2 of their cumulative sums, it holds that T1»i¼ T2»i¼ for any i n. It is worth noticing that, if we take as denition of length any convex linear combination of the values ¹T »i¼; : : : ; T »n¼º, the intervals comparable for the previous ordering remain comparable. Other intervals become comparable for any xed linear combination, but it is not possible to say in advance they are ordered in the same way by any two of these combinations.
We are now able to dene a dierence in this seing: Definition 2. Given rˆ; sˆ 2 RELN ; with rˆ is a vector of length N such that sˆ, the dierence Δ®sˆrˆ Õi j=1 Δ®sˆrˆ »i¼ B ¹i j + 1º sˆ»j¼ rˆ»j¼ ; for all i 2 f1; : : : ; N g:
It can be easily proved that Δ®sˆrˆ is exactly the vector T dened above. Indeed, by construction, given rˆ; sˆ 2 RELN with rˆ sˆ, t »j¼ = Ínj=1 ¹sˆ»n¼ rˆ»n¼º. erefore T »i¼ = Íij=1 t »j¼ = Íij=1 Ínj=1 ¹sˆ»n¼ rˆ»n¼º = Íij=1¹i j + 1º sˆ»j¼ rˆ»j¼ .
Moreover, when computing the dierence vector Δ® between two comparable runs rˆ; sˆ, in this work we write Δ®sˆrˆ whenever rˆ sˆ: if we instead consider Δ®rˆsˆ, then we are counting the backward swaps from sˆ to rˆ and Δ®rˆsˆ»i¼ 0 for all i 2 f1; : : : ; N g.
Since here Δ® is no more a scalar but a vector, we have to dene the partial order among intervals of runs d as follow:
RELN ; Δ®vˆuˆ d Δ®sˆrˆ if and only if Δ®vˆuˆ »i¼ Δ®sˆrˆ »i¼; 8i 2 f1; : : : ; N g: Example. With respect to the previous example, where t = Sˆ ¹0; 1; 1; 1; 2; 1; 1; 1; 0; 1º, the vector Δ®sˆrˆ is given by Rˆ = Δ®sˆrˆ = T = ¹0; 1; 2; 3; 5; 6; 7; 8; 8; 9º:
uˆ = ¹1; 0; 0; 1; 0; 1; 1; 1; 0; 0º ; vˆ = ¹1; 0; 1; 1; 1; 0; 1; 0; 0; 0º : Clearly uˆ vˆ and
Δ®vˆuˆ = ¹0; 0; 1; 2; 4; 5; 6; 6; 6; 6º : us we can conclude that the dierence between sˆ and rˆ is greater than the dierence between vˆ and uˆ.
Note that the last entry of Δ® always equals the natural distance
as dened in Section 2.3 and used by [
is denition of dierence vector solves some of the problems encountered with the dierence dened using the natural distance, as the following example shows.
Example. Let rˆ; sˆ; uˆ; vˆ be dened as follows: rˆ = ¹0; 1; 0; 0; 0; 0; 0; 0; 0; 0º ; sˆ = ¹1; 0; 0; 0; 0; 0; 0; 0; 0; 0º ; uˆ = ¹0; 0; 0; 0; 0; 0; 0; 0; 0; 1º ; vˆ = ¹0; 0; 0; 0; 0; 0; 0; 0; 1; 0º ; where rˆ sˆ and uˆ vˆ:
As already discussed, the natural distance induces a dierence between runs that does not keep track or the rank. In this case, the natural distance would that both the pairs rˆ; sˆ; and uˆ; vˆ; have both dierence equal to 1, even if these two pair diers a lot in terms of where dierences actually happen in the ranking.
Instead, Δ® shows a bigger dierence between rˆ and sˆ compared to the other two runs, because their dierences happen in higher and more important rank positions: Δ®sˆrˆ = ¹1; 1; 1; 1; 1; 1; 1; 1; 1; 1º Δ®vˆuˆ = ¹0; 0; 0; 0; 0; 0; 0; 0; 1; 1º ; and Δ®sˆrˆ »i¼ Δ®vˆuˆ »i¼ for every i 2 f1; : : : ; 10g.
erefore, this new and more expressive dierence matches beer with the intuition that the higher the rank position at which it happens, the more important the same dierence between two runs.
e vector Δ® is thus useful to compare, when possible, intervals on RELN , paying the necessary aention on the ranking. As a consequence, a measure that satisfy these relations among intervals, although not interval scale, could be viewed as something more powerful than a measure on ordinal scale. Indeed, when the above dierences between intervals are comparable, one direction of i on eorem 1 is still satised.
erefore we can say that a measure M of retrieval eectiveness is interval-like if, given a distance (potentially vector) Δ , an ordering d between distances, and given rˆ; sˆ; uˆ; vˆ 2 RELN , the following relation holds:
Δsˆrˆ d Δvˆuˆ ) M¹sˆº M¹rˆº M¹vˆº M¹uˆº: e next section is discusses whether some well-known IR measures are interval-like with respect to the dierence introduced in Denition 2.
We tested some measures of retrieval eectiveness – namely AP, RBPp , ERR, DCG – on intervals with comparable dierences according to the above denition.
ERR shows the strongest discordance with our denition of dierence, since oen it does not respect the relations between intervals induced by Δ® , as the next example shows.
Example. Let us consider the following four runs rˆ; sˆ; uˆ; vˆ 2 f0; 1g10: rˆ = ¹0; 0; 0; 0; 0; 0; 1; 1; 1; 0º ; sˆ = ¹0; 0; 0; 0; 0; 1; 0; 1; 1; 0º ; uˆ = ¹1; 1; 0; 1; 0; 1; 1; 0; 1; 1º ; vˆ = ¹1; 1; 1; 0; 0; 1; 1; 0; 1; 1º : Clearly rˆ sˆ uˆ vˆ. It seems fair to think that rˆ and sˆ give rise to a smaller interval compared to »uˆ; vˆ¼ – note that the endpoints of both intervals dier by a swap of length one, but made in dierent positions. Moreover it is easy to prove that Δ®sˆrˆ »i¼ Δ®vˆuˆ »i¼ 8i : But while the measures RBPp ; AP and DCG agree with the previous statement, ERR does not, since ERR¹sˆº ERR¹rˆº > ERR¹vˆº ERR¹uˆº.
Another measure that does not always respect the relations between distances is AP.
Example. Let us consider the following runs rˆ; sˆ; uˆ 2 f0; 1g10: rˆ = ¹0; 0; 0; 0; 0; 0; 0; 0; 0; 0º ; sˆ = ¹0; 1; 0; 0; 1; 0; 0; 0; 0; 1º ; uˆ = ¹0; 1; 0; 0; 1; 1; 1; 0; 0; 1º :
Clearly rˆ sˆ and sˆ uˆ. e readers can agree to consider the interval »rˆ; sˆ¼ strictly bigger than »sˆ; uˆ¼; since from uˆ to sˆ we have lost only two relevant documents, while from sˆ to rˆ the information lost seems to be higher. Moreover Δ®sˆrˆ »i¼ Δ®uˆsˆ»i¼ 8i; with strict inequality for some i : However while the measures RBPp ; ERR and DCG agree with this relation between the two intervals, AP does not, since AP ¹sˆº AP ¹rˆº < AP ¹uˆº AP ¹sˆº.
Instead, RBPp and DCG show a greater agreement with the inequalities between intervals induced by Δ® , even if sometimes they do not respect these relations: this happens when the endpoints of an interval do not have an equal number of relevant documents.
that is Δ®sˆrˆ »i¼ Δ®uˆsˆ»i¼ 8i; with strict inequality for some i : While uˆ and sˆ has the same number of relevant documents, rˆ has two relevant documents less than sˆ. In particular DCG¹sˆº DCG¹rˆº > DCG¹uˆº DCG¹sˆº and, for p > 0:85, RBPp ¹sˆº RBPp ¹rˆº > RBPp ¹uˆº RBPp ¹sˆº, against the inequality given by the dierence vectors.
erefore, we can say that RBPp and DCG are interval-like with respect to the dierence introduced in Denition 2 and considering only intervals where the endpoints have an equal number of relevant documents. While AP and ERR are not even interval-like since the relations between intervals oen fail to be complied with.
In this paper, we conducted a formal study to propose a new and
more expressive way of providing an empirical ordering of intervals
of runs in order to determine how close IR eectiveness measure
are to be on an interval scale. Indeed, previous work [
Future work will concern an empirical investigation of the different theoretical properties of evaluation measures we have found in order to determine the impact and severity of not complying with them when you compute descriptive statistics, like mean and variance, and when you conduct statistical signicance tests.