We extend performance measures commonly used in semantic web applications to be capable of handling multi-graded relevance data. Most of today's recommender social web applications oer the possibility to rate objects with dierent levels of relevance. Nevertheless most performance measures in Information Retrieval and recommender systems are based on the assumption that retrieved objects (e. g. entities or documents) are either relevant or irrelevant. Hence, thresholds have to be applied to convert multi-graded relevance labels to binary relevance labels. With regard to the necessity of evaluating information retrieval strategies on multi-graded data, we propose an extended version of the performance measure average precision that pays attention to levels of relevance without applying thresholds, but keeping and respecting the detailed relevance information. Furthermore we propose an improvement to the NDCG measure avoiding problems caused by dierent scales in dierent datasets.
Semantic information retrieval systems as well as recommender systems provide
documents or entities computed to be relevant according a user prole or an
explicit user query. Potentially relevant entities (e. g. users, items, or documents)
are generally ranked by the assumed relevance, simplifying user’s navigation
through presented results. Performance measures evaluate computed rankings
based on user-given feedback and thus allow comparing dierent ltering or
recommendation strategies [
tions are the Precision (P = number of relevant items in the result set ) and the Mean total number of items in the result set
result lists (rankings). The main advantage of these measures is that they are simple and very commonly used. The main disadvantage of these measures is, that they only take into account binary relevance ratings and are not able to cope with multi-graded relevance assignments.
One well accepted performance measure designed for handling
multigraded relevance assignments is the Normalized Discounted Cumulative Gain
(NDCG) [
the relevance of entities were used. As performance measure the Mean Scaled
scaling model and the properties of the queries, the SCU measure should not be
used for comparing dierent datasets [
Due to the fact, that binary relevance performance measures precision and
mean average precision are commonly used, a promising approach is to extend
these binary measures to be capable of handling multi-graded relevance
assignments. Keklinen et al. [
handling multiple relevance levels. The idea of looking at the performance of each level of relevance separately is carried on. An extension of MAP is proposed where strategies can be evaluated with user given feedback independent from the number of used relevance levels. We refer to this extension of MAP as
used for benchmarking our work. We explain the performance measure Average
Average Precision. In Section 3 we propose an extension to Average Precision allowing us to handle multi-graded relevance assignment without changing the original ratings. After introducing our approach we evaluate the proposed measures for several Retrieval algorithms and dierent datasets (Section 4). Finally we discuss the advantages and disadvantages of the new measures and give an outlook to future work. 2
reference ranking is expert dened or provided by the user. It can be retrieved
explicitly or implicitly [
For analyzing and comparing the properties the proposed evaluation measures, we deploy an articial data set and a real-world dataset, providing three relevance levels. We assume that the reference item ratings stand for ratings coming from human experts and that the test rankings stand for the item list coming from dierent prediction strategies. We discuss several dierent types of reference ratings: In each evaluation setting the optimal item list based on the reference ratings should achieve the performance value 1:0. 2.1
the measured result quality. For this purpose, we compute the performance of 100 dierent test item lists for each given reference ranking considering dierent performance measures.
item of an optimal item list (reference ranking), see Fig. 1. Swapping means that two rated items in the ranking change their positions. The best test ranking is the one for that no items have been swapped. The performance of the obtained item list decreases with increasing number of swapped item pairs.
the rst test ranking ( 0) we do not swap any item pair, in the last test ranking (99) we randomly swap 99 item pairs. How much the performance decreases per swap depends on the relevance levels’ distance of the swapped items. Hence, an evaluation run for each number of switches includes 100 test ranking evaluations to average the results.
Uniformly Distributed Reference Ratings There are four dierent kinds of reference rankings which dier in the number of relevance levels. Each reference reference ranking example test rankings 1 switch 2 switches 5 switches ranking contains 100 elements which are uniformly distributed among 2, 10, 20, or 50 levels of relevance (see Fig. 2).
ence rankings used in the previous paragraph, we consider reference rankings consisting of non-uniformly rated items making use of 2, 10, 20, or 50 levels of relevance (see Fig. 3). In other words, the probabilities (that a relevance level is used in the reference ranking) dier randomly between the relevance levels.
University [
5 6 49 50
strategies assigning relevance scores to each item in result set for a respective query. Due to the fact that some the provided strategies show a very similar behavior, we limit the number of evaluated strategies to eight (OHSUMED id 1,
based on a three level scale. Because there is no real distance between not relevant, possibly relevant and denitely relevant , we assume 1 as distance of successive levels of relevance as the assigned scores 0, 1, and 2 in the dataset imply. Approximated Virtual-User Ratings The OHSUMED dataset provides three relevance levels. Because ne-grained ratings enable a more precise evaluation, authors believe that soon there will be datasets available with higher number of relevance levels. Until these datasets are available a trick is applied, replacing user’s ratings with relevance scores calculated by computer-controlled strategies. The computer calculated relevance scores are treated as user-given reference ratings. In our evaluation we selected the OHSUMED strategies TF of the title (resulting in 9 dierent relevance levels) and TF-IDF of the title (resulting in 158 dierent relevance levels) as virtual reference users. Both rating strategies show a very strong correlation; the Pearson’s correlation coecient of the relevance assessments is 0:96. The availability of more than three relevance levels in the reference ranking allows us to evaluate ranking strategies with multi-graded relevance assignments. The two strategies treated as reference rating strategies are also considered in the evaluation. Thus, these strategies should reach an evaluation value of 1. 2.3
and recommender systems, such as precision, Area Under an ROC curve or rank of the rst relevant document (mean reciprocal rank). Additionally, the mean of each performance measure over all queries can be computed to overcome the unstable character of some performance measures.
sion (AP) [
for a query q is dened as
APq =
Rq
(1) where N denotes the number of the items in the evaluated list, P @p the precision at position p, and Rq the number of relevant items with respect to q. relq(p) is a binary function describing if the element at position p is relevant (1) or not (0). A higher AP value means that more relevant items are in the heading of the result list. Given a set of queries, the mean over the AP of all queries is referred to as MAP.
signed to either 0 or 1. A threshold must be applied, separating the relevant items from the irrelevant items. For later use, we denote APqt as the AP with threshold t applied. APqt is calculated by
APqt =
Rqt with relqt(p) = (1; relq(p)
t 0; relq(p) < t where Rqt denes the number of results so that relqt(p) is 1.
discounted cumulative gain at position n is computed
NDCG@n(q) = NqnDCG = Nnq Xn 2gainq(i) log(i + 1) where gainq(i) denotes the gain of the document at position i of the (sorted) result list. Nn is a normalization constant, scaling the optimal DCG@n to 1. The optimal DCG@n can be retrieved by calculating the DCG@n with the correctly sorted item list. 3
for multi-graded relevance data. NDCG supports multi-graded relevance data, but the sensitivity to the choice of relevance levels prevents the comparison of NDCG values computed based on dierent datasets. Hence, for a detailed evaluation based on datasets having multiple relevance levels, both MAP and
In the most commonly used evaluation scenarios, the relevance of items is a binary function (returning relevant or irrelevant). If the reference dataset provides more than two relevance levels, a threshold is applied which separates the documents into a set of relevant items and a set of irrelevant items. The example in Table 1 illustrates how levels of relevance aect the calculation of the measure AP The example shows a sorted list of items (A ::: H). The relevance of each item is denoted on a scale from 0 to 4 (5 relevance levels). For calculating the precision, a threshold t must be applied, to separate relevant from irrelevant items. The threshold t = 0 implies that all documents are relevant. We refer to this threshold as the irrelevant threshold. In contrast to t = 0, applying the threshold t = 5 leads to no relevant documents. Table 1 illustrates that the threshold t strongly aects the computed AP. To cope with this problem, we propose calculating the performance on each relevance level, and then computing the mean. This ensures that higher relevance levels are considered more frequently than lower relevance levels. The example visualized in Table 1 shows that item H having a relevance score of 4 is considered relevant more often than all other items.
1 APq = Pt2L dt t2L
X
APqt dt (4) where APqt denotes the average precision using the threshold t, and L a set of all relevance levels (meaning all thresholds) used in the reference ranking. dt denotes the distance between the relevance level ti and ti 1 if i > 1 (and t if i = 0). The following example demonstrates the approach: Given a set dataset based on three relevance levels (0:0, 0:3, 1:0), the threshold t = 0:3 leads to the AP t = 0:3 0:0 = 0:3. The threshold t = 1:0 leads to AP t = 1:0 0:3 = 0:7. 3.2
els making it impossible to compare NDCG values between dierent datasets. Table 2 illustrates this problem.In the rst example the NDCG is calculated as usual. In the second example, the number of relevance levels is doubled, but the number of assigned scores as well as the number of used levels of relevance is equal to the rst example. This doubling leads to a smaller NDCG compared to the rst example, even though no rated element became more or less relevant to another element. In the third example, the gain of example one is normalized and the NDCG is calculated. It can be seen that the normalization solves the inconsistency. A normalization of the gain overcomes the problem of incomparable performance values for data with relevance assignments within a dierent number of relevance levels. We dene the Normalized Discounted Cumulative
n NDCNG@n(q) = Nnq X 2ngainq(i) log(i + 1)
1 i=1 ; ngainq(i) = 8 gainq(i) > <
mq >:0 ; mq > 0 ; mq 0 (5) where mq is the highest reachable gain for the query q (normalization term).
rated with 0. All rating are 0; relevant items have relevance scores > 0. If these assumptions do not apply, the relevance scores must be shifted so that the irrelevant level is mapped to the relevance score 0.
Evaluation based on the Articial Dataset We evaluated the proposed performance measures on the articial dataset introduced in Section 2.1. Fig. 4 shows the mean of 100 evaluation runs with uniformly distributed relevance scores. From left to right the number of false pair-wise item preferences increases, and hence the measured performance decreases.
1 1 1 0,9 0,9 0,9 PµAM0000,,,,7685 aenCGNDm0000,,,,7685 aenCGNNDm0000,,,,7685 0,4 0,4 0,4 0,30 10 20 30nro4f0rand50oms6w0 itch7e0s 80 90 100 0,30 10 20 30 nr o40fran5d0oms6w0itch70es 80 90 100 0,3 0 10 20 30 nro40fran5d0om s6w0itch70es 80 90 100 2 levels of relevance 10 levels of relevance 20 levels of relevance 50 levels of relevance
(introduced in Sec. 2.2) uses three dierent relevance levels. Fig. 6 visualizes the measured performance of selected retrieval strategies using MAP, the mean
levels, the MAP is the mean of the MAP computed applying the thresholds t = 1 and t = 2.
assessments for the evaluation presented in Fig. 7. Strategy 1 assigns ordinal scores to 9 dierent levels of relevance. On this data, MAP is the mean of 8 dierent MAP values.
strategy 1 (as expected) with a performance value of 1:0, so does the mean NDCG and the mean NDCNG. All the considered evaluation measures agree that the retrieval strategy 9 is most similar to strategy 1, which makes sense, since strategy 9 is computed based on the TF-IDF of title and strategy 1 is computed based on TF of title. The main dierence between both retrieval strategies is the number of used relevance levels: Strategy 1 assigns ordinal relevance scores (using 9 dierent relevance levels); strategy 9 assigns real values (resulting in 158 relevance levels). The distance between these relevance levels varies a lot.
into account the distance between the relevance levels (Equ. 4) can be seen. Several very high relevance scores are used only once; lower relevance scores are used much more frequently. Fig. 8 shows the advantages of the NDCN G compared to standard NDCG. The comparison of the mean NDCG in Fig. 7 with the mean NDCG in Fig. 8 reveals that the NDCG is aected by the number of relevance levels. Since the strategies 1 and 9 show a very similar performances in both gures, the other strategies are evaluated with disproportionate lower performance values in Fig. 8 although both reference rating strategies assign similar relevance ratings. The MAP and the proposed mean NDCNG values do not dier much in both evaluations due to the fact the these measures are almost independent from the number of relevance levels. 5
handle more than two levels of relevance. The main advantages of the approach is that it extends the commonly used performance measures precision and Mean Average Precision. AP is fully compatible with the traditional measures, since it delivers the same performance values if only two reference relevance levels exist in the dataset. The properties of the proposed measures have been analyzed on dierent datasets. The experimental results show that the proposed measures satisfy the dened requirements and enable the comparison of semantic ltering strategies based on datasets with multi-graded relevance levels. Since AP is based on well-accepted measures, only a minor adaptation of theses measures is required. 1 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0 1 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0 1 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0 1 0,9 0,8 0,7 0,6 PA0,5 M 0,4 0,3 0,2 0,1 0 1 0,9 0,8 0,7 0,6 PA0,5 M 0,4 0,3 0,2 0,1 0 1 0,9 0,8 0,7 0,6 PA0,5 M 0,4 0,3 0,2 0,1 0 t_0 t_1 t_2 t_3 µMAP meanNDCG
meanNDCNG 1 5 9 11 15 19 21 22 1 5 9 11 15 19 21 22
Additionally, we showed in this paper that the NDCG measure is sensitive to the number of relevance levels in a dataset making it impossible to compare the performance values computed for datasets with a dierent number of relevance levels. To overcome this problem, we suggest an additional normalization ensuring that the number of relevance levels in the dataset does not inuence the computed performance values. Our evaluation shows that NDCNG assigns similar performance values to recommender strategies that are almost similar except that dierent numbers of relevance levels are used. In the analysis, we demonstrated that high gain values (caused by a high number of relevance levels) lead to incommensurately low NDCG values. Since typically the number of relevance levels diers between the data sets the NDCG values cannot be compared among dierent data sets. Thus, the gain values per level of relevance must be limited. An additional normalization solves this problem.
graded relevance assessments. We will focus on movie datasets such as EACH
ratings from the Internet Movie Database (IMDB) 1 (having user ratings on a scale from one to ten).