The development of multilingual and multimedia information access systems calls for proper evaluation methodologies to ensure that they meet the expected user requirements and provide the desired e ectiveness. In this paper, we propose a new metric for ranking evaluation, the CRP.
The development of information access systems calls for proper evaluation methodologies in particular for what is concerned with the evaluation of rankings. A range of evaluation metrics, such as MAP and nDCG, are widely used and they are particularly suitable to the evaluation of Information Retrieval (IR) techniques in terms of the quality of the output ranked lists, and often to some degree suitable to the evaluation of user experience regarding retrieval. Unfortunately, the traditional metrics do not take deviations from optimal document ranking su ciently into account. We think that a proper evaluation metric for ranked result lists in IR should: (a) explicitly handle graded relevance including negative gains for unhelpful documents, and (b) explicitly take into account document misplacements in ranking either too early or too late given their degree of relevance and the optimal ranking. In the present paper, we propose such a new evaluation metric, the Cumulated Relative Position (CRP).
We start with the observation that a document of a given degree of relevance
may be ranked too early or too late regarding the ideal ranking of documents
for a query. Its relative position may be negative, indicating too early ranking,
zero indicating correct ranking, or positive, indicating too late ranking. By
cumulating these relative rankings we indicate, at each ranked position, the net
e ect of document displacements, the CRP. CRP explicitly handles: (a) graded
? The extended version of this abstract has been published in [
De nition of Cumulated Relative Position We de ne the set of relevance degrees as (REL; ) such that there is an order between the elements of REL. For example, for the set REL = fnr; pr; fr; hrg, nr stands for \non relevant", pr for \partially relevant", fr for \fairly relevant", hr stands for \highly relevant", and it holds nr pr fr hr.
We de ne a function RW : REL ! Z as a monotonic function which maps each relevance degree (rel 2 REL) into an relevance weight (wrel 2 Z), e.g. RW(hr) = 3. This function allows us to associate an integer number to a relevance degree.
We de ne with D the set of documents we take into account, with N 2 N a natural number, and with DN the set of all possible vectors of length N containing di erent orderings of the documents in D. We can also say that a vector in DN represents a ranking list of length N of the documents D retrieved by an IR system. Let us consider a vector v 2 DN , a natural number j 2 [1; N ], and a relevance degree rel 2 REL, then the ground truth function is de ned as: GT :DN
N ! REL v[j] 7! rel (1)
Equation 1 allows us to associate a relevance degree to the document d 2 D retrieved at position j of the vector v, i.e. it associates a relevance judgment to each retrieved document in a ranked list.
In the following, we de ne with r 2 DN the vector of documents retrieved and ranked by a run r, with i 2 DN the ideal vector containing the best ranking of the documents in the pool (e.g. all highly relevant documents are grouped together in the beginning of the vector followed by fairly relevant ones and so on and so forth), and with w 2 DN the worst-case vector containing the worst rank of the documents retrieved by the pool (e.g. all the relevant documents are put in the end of the vector in the inverse relevance order).
From function GT we can point out a set called relevance support de ned as: RS(v; rel) = fj 2 [1; N ] j GT(v; j) = relg (2) which, given a vector v 2 DN { it can be a run vector r, the ideal vector i, or the worst-case vector w { and a relevance degree rel, contains the indexes j of the documents of v with which the given relevance degree (rel) relevance is associated.
Given the ideal vector i and a relevance degree rel, we can de ne the minimum rank in i as the rst position in which we nd a document with relevance degree equal to rel. In the same way, we can de ne the maximum rank in i as the last position in which we nd a document with relevance degree equal to rel. In formulas, they become: mini(rel) = min RS(i; rel) maxi(rel) = max RS(i; rel)
Given a vector v and a document at position j 2 [1; N ], we can de ne the Relative Position (RP) as: (3) (4) (5) 80 > RP(v; j) = <j >:j if mini GT(v; j) j maxi GT(v; j) mini(GT v; j) maxi(GT v; j) if j < mini GT(v; j) if j > maxi GT(v; j)
RP allows for pointing out misplaced documents and understanding how much they are misplaced with respect to the ideal case i . Zero values denote documents which are within the ideal interval, positive values denote documents which are ranked below their ideal interval, and negative values denote documents which are above their ideal interval. Note that the greater the absolute value of RP(v; j) is, the bigger is the distance of the document at position j from its ideal interval. From equation 4, it follows that RP(i; j) = 0; 8j 2 [1; N ].
Given a vector v and a document at position j 2 [1; N ], we can de ne the Cumulated Relative Position (CRP) as: j CRP(v; j) = X RP(v; k)
k=1
For each position j, CRP sums the values of RP up to position j included. From equation 5, it follows that CRP(i; j) = 0; 8j 2 [1; N ].
We can point out the following properties for CRP: { CRP can only be zero or negative before reaching the rank of the recall base (R); { the faster the CRP curve goes down before R, the worse the run is; { after R the CRP curve is non-decreasing; { after that the last relevant document has been encountered, CRP remains constant; { the sooner we reach the x-axis (balance point: br), the better the run is.
In Figure 1 we can see a sketch of the CRP for a topic of a run. For a given topic there are two xed values which are the rank of recall base (R) and the min R br on iitsoP 0.5 vaeedR Rank ilte ltau 0 m uC −0.5 CRP(r, R) CRP(w, R) N = Number of Retrieved Documents (fixed) R = Rank of the Recall Base (fixed) br = Rank of the Balance Point of the run CRP(r, R)= Loss Value of the run (CRP@R) CRP(w, R) = Loss Value of the worst-case min = Rank of the Turn-Around Point of the run number of retrieved documents (N ); this allows us to compare systems on the R basis.
The principal indicator describing the CRP curve of a topic for a given run which is the recovery value ( ) de ned as the ratio between R and br: = bRr .
The recovery-value is always between 0 and 1 (0 < 1) where = 1 indicates a perfect ranking and ! 0 a progressively worse ranking. Please note that ! 0 when br ! 1. 3
Final Remarks We think that the CRP o ers several advantages in IR evaluation because (a) it is obvious to interpret and it gives an estimate of ranking performance as a single measure; (b) it is independent on outliers since it focuses on the ranking of the result list; (c) it directly reports the e ort wasted in examining suboptimal rankings; (d) it is based on graded relevance.
Acknowledgements The work reported in this paper has been supported by the PROMISE network of excellence (contract n. 258191) project as a part of the 7th Framework Program of the European commission (FP7/2007-2013).