Modeling Difficulty in Recommender Systems

Abstract

Recommender systems have frequently been evaluated with respect to their average performance for all users. However, optimizing such recommender systems regarding those evaluation measures might provide worse results for a subset of users. De ning a di culty measure allows us to evaluate and optimize recommender systems in a personalized fashion. We introduce an experimental setup to evaluate the eligibility of such a di culty score. We formulate the hypothesis that provided a di culty score recommender systems can be optimized regarding costs and performance simultaneously.

Keywords

• di culty
• recommender systems
• user modeling
• evaluation

1. INTRODUCTION

Evaluating a recommender system's performance represents a non-trivial task. The choice of evaluation measure and methodology depends on various factors. Modeling the recommendation task as rating prediction problem favors measures such as root mean squared error (RMSE) and mean absolute error (MAE) [ 7 ]. In contrast, mean average precision (MAP) and normalized discounted cumulative gain (NDCG) qualify as evaluation measures for an item ranking scenario [ 12 ]. In either case, two recommendation algorithms are compared with respect to their average performance on the full set of users. This entails that all users are treated equally. However, we argue that the di culty of recommending items to users varies. Suppose we consider a recommender system with two users, Alice and Bob. Alice has rated a large number of items. Bob has recently started using the system and rated a few items. The system recommends a number of items to both of them. Alice and Bob rate the recommended items. Suppose we attempt to evaluate two recommender algorithms based on those ratings, denoted as R1 and R2. Assume that R1 predicts Alice's ratings with an error of 0.8 and Bob's ratings with an error of 0.9. On the other hand, we observe R2 to deviate 1.0 for Alice and 0.8 for Bob, respectively. Averaging the errors, we obtain 0.85 for R1 and 0.9 for R2. Still, R2 predicts Bob's ratings better even though his preferences exhibit higher sparsity compared to Alice's. Besides the number of ratings, there are further factors discriminating how well an recommendation algorithm perform for a given user. We introduce the notion of di culty in the context of recommender systems. Each user is assigned a di culty value re ecting her expected evaluation outcome. Users with high errors or disordered item rankings receive a high di culty value. Contrarily, we assign low di culty values to users exhibiting low errors and well ordered item rankings. Recommender systems bene t from those di culty value twofold. First, optimization can target di cult users who require such e orts. On the other hand, the recommender system can provide users with low di culty values with recommendations generated by more trivial methods. Recommending most popular items represents such an approach. Second, di culty values enable the system to estimate how likely a speci c user will perceive the recommendations as adequate. Thereby, the system can control interactions with users, e.g. by asking for additional ratings to provide better recommendations for particularly di cult users. 2.

RELATED WORK

Adomavicius and Tuzhilin reveal possible extensions to recommender systems [ 1 ]. They mention an enhanced understanding of the user as one such extension. Our work attempts to contribute to this by de ning a user's di culty. Hereby, the system estimates a user's likely perception of the recommendations. The methods performing best on the well-known Net ix Prize Challenge had applied ensemble techniques to further improve their rating prediction accuracy [ 3, 11 ]. Both do not state an explicit modeling of recommendation di culty on the user-level. However, ensemble techniques involve an implicit presence of such a concept. Combining the outcome of several recommendation algorithms does make sense in case a single recommendation algorithm fails for a subset of users. Such an e ect is consequently compensated by including other recommendation algorithms' outcomes. Bellogin presents an approach to predict a recommender systems performance [ 4 ]. However, the evaluation is reported on the system level averaging evaluation measures over the full set of users. Our approach focuses on predicting the user-level di culty. Koren and Sill introduced a recommendation algorithms that outputs con dence values [ 8 ]. Those con dence values could be regarded as di culty. However, the con dence values are algorithm speci c. We require the di culty score's validity to generally hold. The concept of evaluation considering di culty has been introduced in other domains. Aslam and Pavlu investigated estimation of a query's di culty in the context of information retrieval [ 2 ]. Their approach bases on the diversity of retrieved lists of documents by several IR systems. Strong agreement with respect to the document ranking indicates a low level of di culty. In contrast, highly diverse rankings suggest a high level of di culty. He et al. describe another approach to estimate a query's difculty [ 6 ]. Their method compares the content of retrieved documents and computes a coherence score. They assume that in case highly coherent documents are retrieved the query is clear and thus less di cult than a query resulting in minor coherency. Genetic Algorithms represent another domain where di culty has received the research community's attention. However, the di culty is determined by the tness landscape of the respective problem [ 5, 6 ]. Kuncheva and Whitaker investigated diversity in the context of a classi cation scenario [ 9 ]. Concerning a query's di culty, diversity has been found an appropriate measure [ 2 ]. We will adapt two diversity measures applied in the classi cation scenario for determining the di culty to recommend a user items. 3.

METHOD

We strive to determine the di culty of the recommendation task for a given user. Formally, we are looking for a map (u) : U 7! [0; 1] that assigns each user u 2 U a real number between 0 and 1 corresponding to the level of di culty. For one recommendation algorithm the di culty for a given user could be simply determined by a (normalized) evaluation measure, e.g. RMSE. However, such a di culty would not be valid for other recommendation algorithms. In addition, recommender systems optimized with respect to the item ranking would likely end up with di erent difculty values. We adapt the idea of measuring di culty in terms of diversity to overcome those issues. We assume the recommender systems comprises several recommendations methods, denoted A = fA1; A2; : : : ; Ang. Each such An generates rating predictions along with item rankings for a given user u. We choose RMSE to evaluate the rating predictions and NDCG to assess the item ranking, respectively. We measure a user's di culty by means of the diversity of those rating predictions and item rankings. For that purpose, we adjusted two diversity metrics introduced by Kuncheva and Whitaker for classi cation ensembles [ 9 ]. We alter the pair-wise Q statistics to t the item ranking scenario. Regarding the rating prediction we adapt the difculty measure .

Applied to the classi cation ensemble setting, the Q statistics base on a confusion matrix. The confusion matrix confronts two classi ers in a binary manner - correctly classi ed versus incorrectly classi ed. We need to adjust this setting to t the item ranking scenario. Table 1 illustrates the adjusted confusion matrix. We count all correctly ranked items as well as all incorrectly ranked items for both recommendations algorithms. Subsequently, the confusion matrix displays the overlap of those items sets. Equation 1 represents the Q statistic derived from the confusion matrix. Note that the Q statistic measures diversity in between two recommender algorithms. Hence, we need to average the Q statistic values obtained for all comparisons in between the available algorithms. Equation 2 computes the nal diversity measure.

Qij(u) = N 11N 00 + N 10N 01

N 11N 00

N 01N 10 QA(u) = jAj 2 ! 1

X Ai;Aj2A

Qij 3.2

Difficutly measure

Kuncheva and Whitaker introduce the di culty measure as a non-pairwise measure [ 9 ]. allows us to consider several recommendation algorithms simultaneously. We iterate over the set of withhold items for the given user. At each step we compute the RMSE for all recommendation algorithms at hand. Thereby, we observe the variance in between all recommender algorithms' RMSE values. The average variance displays how diverse the user is perceived by the set of recommendation algorithms. Equation 3 calculates . I denotes the set of items in the target user's test set. The (i) function computes the variances in between the recommendation algorithms' RMSE values for the given item.

(u) = 1 X (i) jIj i2I 3.3

Difficulty measure

We attempt to formulate a robust di culty measure for recommender systems. Therefore, we propose a combination of the Q statistic and . As a result, both RMSE and NDCG are considered. The more recommendation algorithms we include the more robust the nal di culty value will be. Equation 4 displays a linear combination of both measures. The parameter 2 [0; 1] controls the weighting. = 1 allows to focus on the ranking task. The absence of rating values might require such a setting. (1) (2) (3) (ujA) =

QA(u) + (1 ) (u) (4)

EXPERIMENTAL SETTING

We will evaluate the proposed di culty measure and subsequently outline the intended experimental protocol. Several data sets, such as Movielens 10M, Net ix and Last.fm provide the required data. We will implement item-based Aj: rank(k) rank(l) Aj: rank(k) > rank(l) Where rank(k) rank(l) is true. and user-based neighborhood recommenders, matrix factorization recommenders along with slope-one recommenders. All those recommendation methods do not require data except user preferences. As a rst step, we split each data sets in three partitions. The rst partition will be used for training and the second partition to assign each user a di culty score according to Equation 4. Finally, the third partition will be used as evaluation data set. The subset of users with comparably low di culty score will receive recommendations based on a non-optimized recommendation method such as the most popular recommender. The subset of users with medium di culty score will receive recommendations generated by slightly optimized recommender algorithms. Finally, the particularly hard users will receive recommendations generated by highly optimized recommenders. We will compare both required e orts and recommendation quality against approaches dealing with all users in the same ways. Such approaches will include optimizing recommenders to perform well averaged over the full set of users and recommending all users with trivial recommenders, for instance most popular recommendations. Our hypothesis is that the di culty score will allow us to achieve lower costs along with a comparably high recommendation quality by selecting an appropriate recommendation algorithm for a given user. In addition, we will observe what user characteristics determine her di culty.

CONCLUSION AND FUTURE WORK

We introduced the notion of di culty in the context of recommending items to users. Measuring that task's difculty on user-level allows a more personalized optimization of recommender systems. Users with comparably low di culty scores receive adequate recommendations without much e orts. On the other hand, users with a comparably high di culty score may be asked to provide additional data to improve the system's individual perception. A combination of the Q statistic and the di culty measure both adjusted to t the recommendation scenario - allows us to measure the di culty for a given user. The calculation requires a su ciently large data set containing user preferences on items along with a set of implemented recommendation algorithms. We introduced an experimental setting that we will use to evaluate the presented methodology in section 4. In addition, we intend to apply pattern recognition techniques to nd correlations between the di culty score and user characteristics. For instance, the number of ratings is known to correlate with the di culty for new users ("cold-start problem") and users with a large number of items ("power-users") [ 10 ].

ACKNOWLEDGEMENTS

This work is funded by the DFG (Deutsche Forschungsgemeinschaft) in the scope of the LSR project. 7.

References

[1] G. Adomavicius and A. Tuzhilin . Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions . IEEE Transaction on Knowledge and Data Engineering , 17 ( 6 ): 734 { 749 , 2005 .

[2] J. A. Aslam and V. Pavlu . Query hardness estimation using jensen-shannon divergence among multiple scoring functions . In Proceedings of the 29th European conference on IR research, ECIR'07 , pages 198 { 209 , 2007 .

[3] R. M. Bell and Y. Koren . Lessons from the net ix prize challenge . SIGKDD Explor . Newsl., 9 ( 2 ): 75 { 79 , 2007 .

[4] A. Bellogin. Predicting performance in recommender systems . In Proceedings of the fth ACM conference on Recommender systems , pages 371 { 374 . ACM, 2011 .

[5] M. Hauschild and M. Pelikan . Advanced neighborhoods and problem di culty measures . In Proceedings of the 13th annual conference on Genetic and evolutionary computation , GECCO '11 , pages 625 { 632 , 2011 .

[6] J. He , M. Larson , and M. De Rijke . Using coherence-based measures to predict query di culty . In Proceedings of the IR research, 30th European conference on Advances in information retrieval , ECIR'08 , pages 689 { 694 , 2008 .

[7] J. Herlocker , J. Konstan , L. Terveen , and J. Riedl . Evaluating collaborative ltering recommender systems . ACM Transactions on Information Systems , 22 ( 1 ):5{ 53 , 2004 .

[8] Y. Koren and J. Sill . Ordrec: an ordinal model for predicting personalized item rating distributions . In Proceedings of the fth ACM conference on Recommender systems, RecSys '11 , pages 117 { 124 , New York, NY, USA, 2011 . ACM.

[9] L. Kuncheva and C. Whitaker . Measures of diversity in classi er ensembles and their relationship with the ensemble accuracy . Machine Learning , 51 : 181 { 207 , 2003 .

[10] A. Said , B. Jain , and S. Albayrak . Analyzing weighting schemes in collaborative ltering: Cold start, post cold start and power users . In 27th ACM Symposium On Applied Computing (SAC '12) , New York, NY, USA, 2012 . ACM.

[11] G. Takacs , I. Pilaszy , B. Nemeth , and D. Tikk . Major components of the gravity recommendation system . SIGKDD Explorations , 9 ( 2 ), 2007 .

[12] S. Vargas and P. Castells . Rank and relevance in novelty and diversity metrics for recommender systems . In Proceedings of the fth ACM conference on Recommender systems, RecSys '11 , pages 109 { 116 , New York, NY, USA, 2011 . ACM.