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)