Recommender systems play an important role in supporting people getting items they like. One type of recommender systems is userbased collaborative ltering. The fundamental assumption of user-based collaborative ltering is that people who share similar preferences for common items behave similar in the future. The similarity of user preferences is computed globally on common rated items such that partial preference similarities might be missed. Consequently, valuable ratings of partially similar users are ignored. Furthermore, two users may even have similar preferences but the set of common rated items is too small to infer preference similarity. We propose rst, an approach that computes user preference similarities based on learned user preference models and second, we propose a method to compute partial user preference similarities based on partial user model similarities. For users with few common rated items, we show that user similarity based on preferences signi cantly outperforms user similarity based on common rated items.
Users are overwhelmed with the vast amount of items (e.g. books, movies, locations such as bars or restaurants) o ered by online stores or web guides. They have to invest a lot of e ort to discover relevant items. Keyword-based ltering approaches are not suitable to reduce the vast amount of items to a reasonable size. Additionally, keyword-based ltering does not consider the user's preferences or the item quality. Even the use of average item ratings over all users is not expressing a single user opinion adequately and for that reason only provides poor user support. For this reason, recommender systems play an important role in supporting people nding items they like. Recommender systems aim to lter relevant items according to personal user preferences. Relevant items are provided directly to the user instead of asking the user to search for relevant items. A good example of a recommender system is the Amazon online store which provides recommendations such as "People that bought product X, also bought product Y ".
The fundamental assumption of recommender systems that are based on user-based collaborative ltering is that people who share similar preferences for the same items behave similar in the future. Consequently, each user can bene t from the past item experiences of these users. Typical recommender systems compare user preferences based on the set of items that both users rated. We call these items the common rated items. However, we argue that the set of common rated items re ect the user preferences only partially. First, two users might share the same interest only in parts of the item domain. For example in the domain of restaurant recommendations, users might share similar ratings on Italian restaurants but not on Chinese restaurants. Traditionally, the similarity of the user preferences is computed globally over all common rated items and do not consider that the user preferences can overlap only in parts of the domain. Second, if two users live in di erent cities, the set of common rated items might be empty, if the users did not visit at least one time the same restaurant. In this case traditional recommender systems cannot compute the similarity of the preferences between these users.
In this paper we argue that the set of common rated items might be too small to infer the similarity of the user preferences and may re ect the user preferences only partially. In addition, partial similarities between users might be missed because the user preference similarity is computed globally. Thus, we suggest to compare the similarity among user preferences based on learned user preference models that are an accurate approximation of the users' real preferences. We propose a formal probabilistic framework that compares user preference models and enables the similarity computations of partial user preferences. 2
The fundamental assumption of recommender systems is that people who share
similar preferences for common items behave similar in the future. Thus,
computing the user preference similarity is a key challenge. Several user preference
metrics like Pearson correlation and cosine similarity have been proposed [
Computing partial user preferences has been discussed in [
In this section, we rst introduce the notation used in this paper and the basic framework of recommender systems. Section 3.2 discusses the formal representations of the user's true preferences. In Section 3.3, we introduce our approach of how to de ne the similarity of user preference models followed by its application to predict item ratings. We continue in Section 3.5 with our second approach and the de nition of the partial user preference similarity. We close with Section 3.6 that describes how to compute item ratings based on partial user preference similarities. 3.1
The basic elements in a collaborative recommender system are the set of users N , the set of items I, the set of ratings that are provided by the users for some items and the set of rating concepts C from which users can choose to describe adequately their opinion about an item. We denote R as the n m rating matrix with n = jN j as the number of users and m = jIj as the number of items such that the value of the ith row at position j corresponds to the rating of the ith user for the jth item. We refer to a certain user as Ui with i 2 f1; : : : ; ng, to a certain item as Ij with j 2 f1; : : : ; mg and denote rij 2 C [ f?g of the rating matrix R as the rating of user Ui for the item Ij . The value of rating rij is either a rating concept ck 2 C or ?, if no rating has been provided yet. z = jCj is the number of rating concepts the user can assign to every item in I. The item rating vector Ri for the user Ui contains the rating for every item in I. Further, we refer to the set of items that user Ui has actually rated (rij 6= ?) as the item subset Ii I. We denote the user for whom we compute the recommendations as the active user Ua with a 2 f1; : : : ; ng.
Depending on the recommendation algorithm, we can distinguish between several sets of rating concepts C. These can be classi ed into four groups: { Nominal rating : The task of item recommendation can be treated as a classi cation problem that associates an item with one ore more rating classes. Popular classes of rating concepts C are frelevant; irrelevantg or flikes; likes notg. { Ordinal rating : The rating concepts are interrelated and can be ordered. The typical example for ordinal rating concepts is the star-rating on a 1-5 integer scale: fF; : : : ; FFFFFg. With ordinal ratings only the assertion can be done that a 4-star rated item is better then a 2-star rated item. { Interval rating : Items can be rated with a numeric value from R. In general, such ratings can be normalized to a [ 1; 1] scale. { Ratio rating : Items can be rated with a numeric value from R. In general, such ratings can be normalized to a [0; 1] scale.
In general, a recommender system is a function f which returns for the active user Ua the computed item rating vector Ra. The function f takes all ratings in R, the user Ua, all users in N , all items in I and the rating concepts in C as input. We can conceptualize a recommender system as follows:
Rba = f (R; I; C; Ua), r 2 C [ ? 3.2
Most recommender systems represent the true user preferences as item true rating vector Rtrue which contains for every item Vj 2 I the true rating reij 2 C: i
Rtrue = hrit1rue; : : : ; ritmruei
i
If all true item ratings of a user are known, providing recommendation comes down to a trivial sorting problem (sorting the vector Rtrue). In general, a recomi mender system has only partial knowledge about the user Ui's true preferences Rtrue. We assume that the provided ratings in Ri are equal to the corresponding i true ratings in Rtrue. The user Ui provides only partial rating information for i three reasons: { Costs: Temporal or monetary costs restrict the amount of items that a user is able to consume and provide a rating for. { Usability : The rating e ort is too high because the item has to be found rst (search costs) and then being rated with too much e ort (usability). { Privacy : The user has an interest in not to publish all personal item ratings Since the true item rating vector Rtrue is only partially known, we adjust i the representation of the user's preferences to a more general way and more adaptable to machine learning. We assume that every user is able to assign the proper rating concept to an item. More formally, every user Ui 2 N is able to assign a rating concept ck 2 C to every item Ij 2 I using his mental rating function ui(I):
ui(Ij ) : Ij 7! ck = ritjrue; 8Ij 2 I
We can reason that the user Ui always associates the item Ij with the true rating concept ck. Therefore, the probability that the rating function ui(I) provides the true rating concept ck for all Ij 2 I is always 1.
P ui(Ij ) = ckjritjrue = ck = 1; 8Ij 2 I
Instead of guessing all the user Ui's ratings, we approximate the rating function ui(I) based on the known user Ui's ratings Ri over the subset Ii I. We assume, that the distribution of ratings of Ri represent the real rating distribution of Rtrue. The rating distribution is the frequency of appearance of every i rating concept in C in the vector Ri. Hence, a computer program can learn an approximation of ui(I) based on Ri and the set of items I.
The learner faces the problem to hypothesize the rating concepts ck 2 C for the items Ij 2 Ia. For this purpose, the learner has to nd the hypothesis h from the hypotheses space of all possible hypotheses H that estimates best the proper rating concept ck the active user Ua associates with item Ij . The performance measure P is used to determine the best hypothesis h. To summarize, the rating concept learning task is to nd the set of hypotheses that associates all items Ij 2 Ia with the proper rating concepts ck 2 C. The learner selects the hypotheses subset Ha H and builds a hypothesized rating function ha(I) that selects the best hypothesis h 2 Ha to hypothesize the active user Ua's rating for the item Ij . The hypothesized rating function is a classi er that is built by the learner. A perfect hypothesized rating function ha(I) for Ij 2 Ia with j = f1; : : : ; mg means:
ha(Ij ) = ua(Ij ); 8Ij 2 Ia
In general, ha(I) is an approximation of ua(I) such that the probability that ha(I) = ua(I) is usually below 1. That can be expressed as:
z m X X P ha(Ij ) = ckjua(Ij ) = ck k=1 j=1 1
The sum is normalized to 1 with the normalization factor . Hence, we can state that ha(I) approximates ua(I) by an error function "(Ij ):
ua(I) = ha(I) + "(I)
The performance of ha(I) depends on the hypotheses space H that is based on the human designer's choice and on the other side on the amount of experience E respectively amount of the user's item ratings. If an adequate hypotheses space H has been de ned by a human designer, we argue that the error function "(I) ! 0 because the performance of ha(I) increases with more experience E. Hence, we can state: ua(I) ha(I) (3.1) 3.3
We denote the similarity of preferences between user Ua and Ub as sim(Ua; Ub). If user Ua and Ub always rate the same item identically, user Ua and Ub share the identical preferences. If user Ua and Ub always rate the same item di erently, no preference similarity exists between the preferences of user Ua and Ub. We de ne the similarity sim(Ua; Ub) as the probability P that user Ua and user Ub both rate all items Ij 2 I with j = f1; : : : ; mg equally. We denote z = jCj as the number of rating concepts.
sim(Ua; Ub)
z m X X P (raj = ck ^ rbj = ck) k=1 j=1
The sum is normalized to 1 with the normalization factor . Hence, we de ne the similarity on the interval [0; 1] with 0, no similar preferences, and 1, identical preferences. Since not all ratings are known by the recommender system, the similarity sim(Ua; Ub) can be computed only based on common rated items Ij 2 Ia \ Ib. The smaller the size of the intersecting item set is, the smaller the con dence of the accuracy and the smaller the accuracy of the similarity sim(Ua; Ub) is.
Therefore, we have to generalize the idea of similarity. The user Ui's preferences can be explained with his personal rating function ui(I) as demonstrated in the previous Section 3.2. Hence, we can formulate the similarity sim(Ua; Ub) between user Ua and Ub as the similarity of both personal rating functions ua(I) and ub(I): sim(Ua; Ub) = sim (ua(I); ub(I)
z X P ua(I) = ck ^ ub(I) = ck k=1
z X P ua(I) = ckjub(I) = ck P ub(I) = ck k=1
Because either ua(I) or ub(I) are known, we approximate both with ha(I) and hb(I) respectively according to Eq. 3.1. Hence, we can write the similarity sim ua(I); ub(I) as: sim ua(I); ub(I) u sim ha(I); hb(I)
z X P ha(I) = ckjhb(I) = ck P hb(I) = ck k=1 (3.2)
Compared to the computation of the similarity sim(Ua; Ub) on common rated items Ia \ Ib, we now can compute the similarity sim(Ua; Ub) on the merged item set Ia [ Ib. The probabilities are computed by applying ha(I) and hb(I) to the merged item set and comparing the predicted rating concepts. 3.4
In user-based collaborative ltering, the similarity among users can be used to predict for the active user Ua the rating r^aj of the item Ij. The rating r^aj is the
Listing 1.1. Example of a conjunction of constraints of movie features
movie hasGenre Drama = y e s
movie hasGenre Romance = y e s
movie h a s R e l e a s e Y e a r = 1942
movie isOfCountry = m: Country USA
movie i s P r e s e n t e d I n Black and White = y e s
movie i s P r e s e n t e d I n Color = no : 5
weighted deviation from the active user Ua's average rating. More speci cally,
the rating r^aj is the sum of Ua's average rating ra and the normalized sum of
the weighted di erence of all the other user Ub's rating rbj and their average
ratings rb [
The factor is a normalization factor such that the similarities sum to unity. According to the previous section 3.3, it is feasible to approximate the similarity sim(Ua; Ub) of user Ua and Ub with the similarity sim ha(I); hb(I) . Therefore, we predict the rating r^aj as follows: r^aj = ra + (rbj
rb) n X sim ha(Ij ); hb(Ij ) b6=a 3.5
In the previous Section 3.3, we proposed a probabilistic approach to de ne the similarity of two user preference models. But as we have already argued, overall similarity of user preferences misses partial user preference similarity. In general, a user has various preferences. In the context of movies, a user may not only like action movies, but also romantic movies. The user's preferences consist of a set of single preferences. Each such preference is described by a conjunction of constraints of features as shown in Lst. 1.1. The constraints may be a speci c value, no acceptable value exists or any value is acceptable.
It is not feasible to compare single preferences of two users because a single preference may be similar to a set of preferences of the other user. Hence, it is necessary to describe the problem of computing partial user preference similarity of user Ua and Ub as the problem of computing the similarity of user Ua's preference to a composition of user Ub's preferences.
According to Eq. 3.1 in Section 3.2, it is feasible to approximate hypotheses to
preferences. A user Ui's preference model hi(I) consists of a subset of hypotheses
ha;q 2 Ha with q 2 f1; : : : ; jHajg of the hypotheses space H. Analogously to
preferences, a hypothesis h is described as a conjunction of constraints of the set
of features [
sim ha;q; hb(I)
To compare the hypotheses ha;q 2 Ha with q 2 f1; : : : ; jHajg of user Ua's preference model with the preference model hb(I) of user Ub, all hypotheses ha;q of user Ua's preference model have to be extracted. For each hypothesis ha;q, an item set Ia;q is built with the items that matches ha;q's conjunction of constraints of item features. Note, that the item set I is partitioned into item sets Ia;q with q 2 f1; : : : ; jHajg and are disjoint. That is because each item is associated with one rating concept by a well-de ned hypothesis. The hypothesis ha;q associates every item Ij 2 Ia;q with exactly one concept ck 2 C. We de ne the partial similarity of user Ua's hypothesis ha;q and user Ub's user preference model hb(I) as the probability P , that the user preference model hb(I) predicts rating concept ck under the condition that the hypothesis ha;q(I) associates all items I 2 Ia;q with ck: sim ha;q; hb(I)
P hb(I) = ck ^ ha;q(I) = ck
P hb(I) = ckjha;q(I) = ck P ha;q(I) = ck
The hypothesis ha;q associates all items with ck that matches ha;q's conjunction of constraints of item features. Hence, the probability of P (ha;q) = 1. Therewith, we can simplify the upper de nition: sim ha;q; hb(I)
P hb(I) = ckjha;q(I) = ck ; 8Ij 2 Ia;q (3.3) 3.6
Similar to Section 3.4, partial preference similarity can be used to predict for user Ua the rating r^aj of item Ij . To this goal, the proper hypothesis ha;q has to be identi ed that is chosen by the user Ua's preference model ha(Ij ) given the item Ij . The well-de ned hypothesis ha;q is identi ed by matching the conjunction of constraints of features with the item's feature vector. Thereafter, the similarity of ha;q and the user models hb(I) of other users Ub can be computed. Note, that all partial user preference similarities can be computed o ine to provide a rating predictions online. The similarity sim ha;q; hb(I) between two people is computed on the merged item set Iha;q that matches the hypothesis ha;q and have been rated by at least one of both people. The rating r^aj is the sum of Ua's average rating ra and the normalized sum of the weighted di erence of all the other user Ub's rating rbj and their average ratings rb:
n r^aj = ra + X sim ha;q; hb(I) (rbj rb)
b6=a The sum is normalized to 1 with the normalization factor . (3.4)
In this section, we provide an empirical evaluation of our two proposed methods to compute user preference similarities and partial user preference similarities. First, we describe the used dataset and second, we describe the experimental settings. We close discussing the comparison of our approach with others. 4.1
We created a movie dataset that consists of user ratings and movie descriptions.
We used the Net ix-Prize dataset [
Both datasets provide partially di erent movie informations like year releases or titles. Furthermore, movie titles tend to be used by several movies. Thus, we uni ed movie titles of both datasets. We de ned a movie of one dataset identical to a movie dataset of the other dataset if the uni ed titles are identical and the di erence between the year releases is minimal. We made the assumption that movies with the same title are not produced and published within several years. With this method, we automatically identi ed 10 128 Net ix movies in the IMDb with 83 029 805 ratings of 479 437 users. In a precedent data analysis, we measured the average number of ratings per user of 173.2 and the median of 80 ratings. The average rating is 3.56 and the median is 4. 4.2
To evaluate our approach we used two di erent settings: the rst setting consists of users with few common rated items and the second setting consists of users with many common rated items. We assume that users with few ratings have less common rated items then users with many ratings. Hence, we selected randomly 500 users with 50 ratings and 500 users with 200 ratings for the rst and second setting, respectively. We chose 50 ratings to have a reasonable amount of ratings to learn user preferences from and 50 are below the median and the average. We chose users with 200 ratings because it is more then the median or the average and thus a reasonable amount. We split both datasets in a training set and a test set with a ratio of 4:1.
For the partial user preference model approach pUMsim, we used the machine
learning algorithm Part [
We evaluate all approaches by measuring the root mean square error (RMSE)
and mean absolute error (MAE) as suggested in [
The evaluation results are presented in Table 1. We tested the signi cance with a non parametric test for dependent samples because the results are not normal distributed. We applied the Wilcoxon signed-ranks test and tested all methods pairwise. Therefore, we applied Bonferroni correction to control the family-wise error. We set = 0:01 as signi cance level.
In Table 1 and the setting with few common rated items (50 rat./user), both classi ers based on Part and SVM perform worst regarding RMSE and MAE. In case of RMSE and MAE, computing user preference similarity based on user preference model similarity (UMSim) and partial user model similarity (pUMSim) signi cantly outperform the user similarity based on Pearson correlation. That is because Pearson correlation is computed on common rated items that are rarely found in this setting. In contrast, the user model similarity is computed on all rated items of the users and thus, is based on more examples. However, UMSim signi cantly outpferoms pUMSim regarding MAE, but does not regarding RMSE. We assume that the hypotheses partition the set of items into too small sets such that partial user preference model similarity is less accurate compared to user preference model similarity. No signi cant di erence exists regarding precision, recall and the F1-measure in this setting.
In the setting with many common rated items (200 rat./user), both classi ers still perform signi cantly worst regarding RMSE and MAE. In contrast to the previous setting, UMSim based on SVM is not signi cantly better then Pearson correlation, but both are signi cantly better then UMSim based on Part regarding RMSE. However, they are not signi cantly better then UMSim based on Part regarding MAE. In this setting, UMSim and Pearson correlation are signi cantly better then pUMSim. Regarding precision, the classi er based on SVM performs signi cantly worse compared to others. The classi er based on Part performs signi cantly worse then other approaches only globally but not with the Bonferroni correction. In case of recall, Pearson correlation signi cantly outperforms all approaches. Our proposed approaches together with Pearson correlation signi cantly outperform the two classi ers only without Bonferroni correction.
In general, our proposed approaches perform similar to traditional collaborative ltering approaches. However, they signi cantly outperform traditional collaborative ltering in settings with few common rated items. 5
We proposed a probabilistic method to compute user preference similarities based on user preference models and partial user preference similarities based on hypothesized user preferences that are extracted from learned user preference models. We have empirically shown that user similarity based on preferences is signi cantly better then user similarity based on common rated items for users with few common rated items. However, the accuracy of partial user preference similarity is promising but needs further improvement. Note, the learned user models might not be total functions and the user model comparison incomplete. But we argue that these missing items are irrelevant because they do not match the user's preferences.
Due to user-user comparison, our proposed approach is suitable for small amount of users because it has order of O(n2) time complexity. Therefore, in future work, we investigate clustering and ltering to improve scalability. Further, we will improve the accuracy of the learned user preference models. For this purpose, we will increase the hypotheses space by applying more features and enrich them with background knowledge from domain ontologies. In a next step, we will consider regression-based machine learning algorithms to improve the rating predictions and re ne the currently suggested probabilistic similarity with a more semantical interpretation of what similar ratings are. In addition, we will consider global user preference similarity as background evidence for partial user preference similarity. In a last step, we will investigate how to prune hypotheses such that partial preference similarity relies on more examples. That leads to higher evidence of the accuracy of partial preference similarity. We will investigate how background knowledge in form of a domain ontology can be used to prune hypotheses since the features are related to instances in the movie ontology. 6
We would like to Thank Jorg-Uwe Kietz for his insightful comments on the ideas.