In this paper, we make two proposals to speed up listwise collaborative filtering and improve its accuracy. The first is to speed up computation by only using a subset of the rating information (the high ratings). The second is to improve accuracy using temporary ratings that estimate the rating scores that neighboring users are not rating. Experiments using MovieLens datasets (1M and 10M) demonstrate that these proposals effectively reduce computation time about 1/50 and improve accuracy 2.22% compared with ListCF, a well-known listwise collaborative filtering algorithm.
recommender systems have become increasingly important
in various situations; many researchers are now focusing on
recommendation technologies and systems [
recommends items based on this. We will focus on this method due to its performance. Ranking-oriented CF can be further divided into two types: pairwise ranking-oriented © 2018. Copyright for the individual papers remains with the authors. Copying permitted for private and academic purposes.
WII'18, March 11, Tokyo, Japan.
[7,10] and listwise ranking-oriented [
In this section, we give an overview of ListCF [
calculated based on a probability distribution of item permutations for each user, calculated using the Plackett–
model [8], which is a representative permutation probability model. The flow of similarity calculation is shown on the left of Fig. 2 and Fig. 3. Let the set = { 1, 2, ⋯ , } of items = ( 1, 2, ⋯ , ) (∈ ) be an ordered list where ∈ and ≠ if ≠ , and let Ω (⊂ ) be the set of all possible permutations of . Given the item ratings ( , 1
2 , ⋯ , ) (e.g., on a real interval
in the case of MovieLens [
( 1, 2, ⋯ , ) = { | ∈ Ω , = , = 1, ⋯ , , = 1, ⋯ , ! ( − )! } and the probability of the top-k permutation is calculated as ( ( 1, 2, ⋯ )) = ∏
Let (⊂ Ω ) be the set of top-k permutations of , and let
the probabilities of these permutations form the probability
distribution. Then, define , (⊂ ) as the set of items rated
(⊂ Ω ),
( )
∑
=1 = ( )
(2)
(3)
proposed method (right).
by users and , and and (∈ [
(4) ( ∥ ) =
∑ ( ) If the set , only includes a few items, the similarity will be high, so this is relaxed by multiplying by the similarity function by min{ , ⁄ , 1}, where is a threshold. Each user’s neighboring
users can then be found from the similarities calculated using Eqs. (3)–(5).
Let U be the set of users, (⊂ ) be the set of the user ’s
neighbors and (⊂ ∖ ) be the set of items whose ranks
are to be predicted. Let ̂ (∈ [
, ∑ ′∈ , ′ where { , |∀ ∈
} are unknown variables assigned to the top-k permutations. In ListCF, the cross entropy is used as a loss function for prediction. Consider a target user , for whom you want to rank a set of items , and a neighboring user ∈ . Let the set of items rated by be , with , = ∩ , and top-k permutations of , . The cross entropy is calculated , (⊂ Ω , ) be the set of using probability distributions ̂′ and ′ over , as ( ̂′ , ′ ) = − ′ ( )log2 ̂′ ( ).
(7) ∑
, only on high ratings. The flow of similarity calculation is shown on the right of Fig. 2 and Fig.5. Let (⊂ ) be the set of items that were rated highly by the target user , and , (⊂ , ) be the set of items that both and rated highly. Given the user and rating matrix, we define the similarity between and as follows: where ( , ) = ( , ) is | , | | | complexity is , it is never worse than that of conventional
by introducing temporary ratings. In ListCF, the cross entropy in Eq. (7) is calculated from the probability distribution of , , the set of permutations of , .
However, optimizing the objective function may fail if , has too few elements, e.g., if it only includes one element and that item received a low rating from the neighboring user . In this case, despite the item’s low rating, optimization generates a high item rank, which is unhelpful for user . Fig. 6 shows how the probability distribution for target user ’s unrated items before optimization (upper) and neighboring user ’s distribution (middle) give a graph like the one on the lower. Item 1 was given a low rating by but, since no other items were rated, it is guaranteed to top the rankings. As a result, ’s probability distribution is updated to place item 1 at a higher position. The proposed method therefore makes ranking predictions after giving temporary estimated ratings to items that were not rated by the neighboring user . The flow of ranking prediction is shown on the right of Fig 4 and Fig.7. Let , be the rating given by user to item , and let unrated items have a score of zero. ∑
,
. , ← , − (11)
occur when users have only one low-rated item in common.
The horizontal axis represents the item number. For a given neighborhood user ∈ and set = ′, (if , is zero) , ( = 1, ⋯ , ), (13) used. where ′ , is the set of ’s neighbors ′ ∈ who have rated item . If none of ’s neighbors have rated , the temporary rating will still be zero. In that case, we can obtain a nonzero temporary rating by calculating the temporary ratings ( ′, ) for each neighbor ′ of . By calculating the cross entropy of Eq. (7) using these temporary ratings (Eq. (13)) and replacing ( , ) in Eq. (8) with ( , ) (Eq. (12)), ranking predictions can then be made in the same way as for ListCF by using
allows the neighbors’ probability distributions in situations such as Fig. 6 to be more reasonable. As a result, since the parameters are less frequently updated in an undesirable way, this should improve the ranking accuracy. =1 2 − 1 log2(1 + ) (14) where is a normalization term that ensures the NDCG value of the correct ranking is 1 and is the rating of the pth-ranked item for user . For a set of users , the overall 1 | | | | ∑ =1
time. We compared the time taken to calculate the user similarities using both the proposed and ListCF methods, and then compared the ranking accuracy of
predictions made using the calculated similarities. The criterion used to determine high ratings was changed from 1 to 5 in increments of 1, and similarities were obtained for each criterion. A criterion of 1 means all ratings are used, while a criterion of 5 means that only items rated as 5 are
1,000,209 71,567 10,681 10,000,054 60 50 s 40 e itun 30 m20 10 0
and 9(b)-(d) show the corresponding ranking accuracy results. The horizontal axes show the high rating criterion in all graphs, while the vertical axes show calculation time in Figs. 8(a) and 9(a), NDCG@1 in Figs. 8(b) and 9(b), NDCG@3 in Figs. 8(c) and 9(c) and NDCG@5 in Figs.
and 9(a), similarity computation is considerably more rapid for the proposed method than for conventional ListCF. In addition, Figs. 8(b)-(d) and 9(b)-(d) show that when scores of 4 and 5 are considered to be high ratings, the rankings are as accurate as those of the conventional method.
Next, we conducted experiments to examine the effect of using temporary ratings on ranking prediction accuracy. We compared the accuracy of ranking predictions made using both the proposed and ListCF methods using the similarities calculated in the previous subsection. We used an initial , value of 10 for both datasets with learning rates of 0.025 and 0.01 for MovieLens 1M and 10M, respectively.
ListCF prediction proposed prediction
ListCF prediction proposed prediction ListCF 1 2 3 4 5
ListCF 1 2 3 4 5 ListCF 1 3 4 5
ListCF 1 3 4 5
ListCF 1 3 4 5 Fig. 10 shows that the computation times for the proposed ranking prediction method were shorter in all cases. In addition, Figs. 11 and 12 show that its NDCG@1,
calculate user similarity scores using only high ratings, instead of all ratings, to speed up computation. The second is to introduce temporary estimated ratings for items that have not been rated by neighboring users to improve ranking accuracy.
In experiments using the MovieLens 1M and 10M datasets, we have compared the computation time and accuracy of both proposals with those of conventional ListCF. The results demonstrated that the first proposal provided a considerable reduction in computation time, compared with conventional ListCF, while maintaining equal or greater ranking accuracy. In addition, the second proposal shortened the prediction time in most cases while always improving the ranking accuracy.
http://dx.doi.org/10.1145/1273496.1273513