Recommendation Algorithms for Optimizing Hit Rate, User Satisfaction and Website Revenue

1 Introduction

Recommender systems have been widely applied to online shopping websites for better user experience. Traditional recommendation algorithms try to leverage item aspects and historical user behaviors to exploit the potential user preferences. Broadly, a customer's behavior can be divided into two types: explicit feedback and implicit feedback. The former, such as rating scores, reveals the preference degree of buyers, and the latter, such as browsing and clicking information, records valuable customer actions. Based on them, most well-known methods utilize the collaborative filtering (CF) technique, which learns the correlations of users and items beneath the feedback, in order to recognize potential useritem associations [Koren et al., 2009]. To measure recommendation performance, researches have also considered designing good metrics. For rating prediction, we usually evaluate the difference between predicted rating values and actual rating values by computing root mean square error (RMSE), mean square error (MSE) or mean absolute error (MAE). For item recommendation, we consider whether the most relevant items are recommended with the highest priority by measuring a ranked item list for each user in terms of precision, recall, normalized discounted cumulative gain (NDCG), area under the curve (AUC), expected reciprocal rank (ERR), etc. [Weimer et al., 2007; Rendle et al., 2009; Shi et al., 2013; Pan and Chen, 2013].

∗Corresponding author

Despite those algorithms and metrics, it is still challenging to comprehensively measure the performance of a particular recommendation algorithm. The rating prediction metrics (e.g., RMSE, MAE, MSE) or some item recommendation metrics on the whole item lists (e.g., NDCG, AUC, ERR) may not directly reflect system performance in applications, where only top-K items are provided. On the other hand, the hit rate based metrics (e.g. precision and recall) cannot convey preference degree information. Hence, in this paper, we consider two other important factors for designing and evaluating recommendation algorithms.

User Satisfaction We define user satisfaction as how much a user satisfies with an item (s)he has already bought. The models with higher hit rate performance may recommend more items that users tend to buy, but they do not guarantee that the proposed items suit the customers. An extreme example is that many users are not pleased with the bought items that recommended by the system. In this case, although the models achieve high hit rate, it is even worse than not recommending the items to these users, because they are disappointed with the items and even distrust the recommender systems in the future.

Website Revenue Another destination of recommender systems is to help website retailers earn more revenue (which is narrowly defined as retailer satisfaction for convenience). Unfortunately, it is ignored by almost all the related algorithms. Improving hit rate can indeed help improve sales, but it is limited and indirect. Suppose a user intends to buy one of two selected items, recommending any one of them will gain the same hit rate, but it is better to choose the item with higher profit for it can help the website earn more money without reducing users' satisfaction.

To illustrate the impact of these factors, we show a simple example in Table 1. It contains three similar items that the customer u is interested in. The satisfaction denotes the rating value that u will give to each item if s(he) buys it, and the revenue is related to item price. The following three lines show the performance of three recommendation algorithms (denoted as alg1, alg2 and alg3), and the hit means that u will buy the item if it is recommended. From the table, we immediately know that both alg1, alg2 and alg3 achieve similar performance in terms of hit rate (i.e., the same prediction, recall and F1 score), because they both hit one item. However, those methods have different performance when we consider the other two factors. If u buys the item recommended by alg1, he will give 3 stars to the item, and the retailer will get 5 dollars. If u buys the item recommended by alg2 instead, the user satisfaction value will drop 1 score, but the retailer can get double revenue. To the item recommended by alg3, the user gives the highest score, and the website retailer can get approximate optimal revenue. Therefore, we think that alg3 is the best algorithm because it satisfies both users and the retailer, and alg2 may be better than arg1 because it helps to double the revenue with the cost of only losing 1 level of user satisfaction.

To conclude, a good recommendation algorithm should not only improve hit rate, but also consider optimizing user satisfaction and website revenue, or at least achieve a balance among them. As a response, in this paper, we propose two novel algorithms to optimize them simultaneously. To test the performance of our methods in terms of user and retailer satisfaction, we design two simple but convincing metrics. The experimental results on 10 real-world datasets show that our models provide better overall performance than existing methods.

2 Background

In this section, we review several related studies and perform some analysis on real-world datasets.

The most popular techniques for collaborative filtering are matrix factorization(MF) models [Koren et al., 2009], which are effective in fitting the rating matrix with low-rank approximations. MF uses the latent factor U ∈ RD×N to represent N users and V ∈ RD×M to represent M items, and it employs the D-rank matrix U T V ∈ RN×M for rating prediction. The latent factors can be trained by adopting Singular Value Decomposition(SVD) [Koren, 2008]. For example, Salakhutdinov et al. [2008b; 2008a] propose a probabilistic matrix factorization (PMF) model, in which the factors and ratings are assumed to be sampled from Gaussian distribution, and the latent factors are learned by maximum likelihood estimation, which equals to minimizing ∑u,i∈To (U T u Vi - sui)2 + λ1 ∑u ||Uu||2 + λ2 ∑i ||Vi||2 , where sui is the rating score that u gives to i; To denotes the set of observed (user, item) pairs; ||U||2 and ||V ||2 are regularization terms for avoiding over-fitting.

Many MF models are originally proposed for rating prediction, hence they are weak for ranking tasks. To improve hit rate performance for implicit feedback, one-class collaborative filtering (OCCF) [Pan et al., 2008] and implicit matrix factorization (iMF) [Hu et al., 2008; Lin et al., 2014] are proposed based on the assumption of pointwise preferences on items. Both of them treat users' feedback as an indication of positive and negative preferences with different levels (cui) and try to minimize ∑u,i∈To cui(1 - U T u Vi)2 + ∑u,j∈Tuo cuj (0 - U T u Vj)2 for each (user,item) pair. In addition to these absolute preference assumptions, many pairwise algorithms such as BPR and some of its extensions are proposed [Rendle et al., 2009; 2010; Krohn-Grimberghe et al., 2012; Pan and Chen, 2013]. They directly optimize the observed and unobserved (user,item) pairs with relative preference assumptions. Although those algorithms are for implicit feedback, they can also be applied to ranking items with explicit information; the drawback is that the user satisfaction information (i.e., rating values) cannot be efficiently leveraged.

Nowadays, more and more methods try to utilize explicit information for item recommendation. For example, Weimer et al. [2007] propose a maximum margin matrix factorization (MMMF) method CofiRank to optimize ranking in terms of NDCG score. Similr to CofiRank, xCLiMF proposed by [Shi et al., 2013] builds a recommendation model by generalizing collaborative less-is-more filtering assumption and optimizes expected reciprocal rank (ERR). ListRank [Shi et al., 2010] combines a list-wise learning-to-rank algorithm with MF. It optimizes a loss function that represents the cross-entropy of the output rating lists and training lists. These algorithms perform well when the data is dense, but they may be unsuitable for sparse datasets, because few explicit ratings can be used to compare and learn users' preferences.

Beyond product ratings, directly optimizing website revenue is another interesting topic. Although a few researches have considered on how to make price with the help of recommender systems [Bergemann and Ozmen, 2006] or how to recommend discount items to users [Kamishima and Akaho, 2011], they do not consider optimizing the website revenue directly. A good recommender system should not only provide potential items to users that they like, but let the website earn as much money as possible. We study many real-world datasets and find it is feasible to both optimize user satisfaction and website revenue in applications. We briefly discuss it here by making a qualitative analysis of the relationship between user satisfaction and website revenue. Figure 1(a) shows our statistics on 13 Amazon datasets. The horizontal axis is user's satisfaction and the vertical axis represents the proportion of items which are above average price. Figure 1(b) records the rating values and related normalized item price of an example dataset. It is obvious that user satisfaction and website sales have some positive correlation and can be optimized simultaneously. Overall, we can draw the following conclusions: (1)For the products in the same category, item price has some impact on user satisfaction. The items with higher price may have good quality and hence tend to receive higher rating values. (2)Involving price information can not only benefit the website retailer, but also help to predict user satisfaction, because we can learn the acceptable price range of each user and avoid recommending the items that users do not accept.

3 Our Models andMetrics

In this section, we propose two different solutions to optimize Hit rate, user Satisfaction and website Revenue (HSR) simultaneously. We denote the probability (or the tendency) of a user u buying an item i by P(bui). We use sui to indicate the rating score that u gives to i and use P(sui) to represent how much u prefers i after (s)he has already bought it. Specifically, we assume the greater rating score that u gives to i in the dataset, the more likely u likes i. For the online retailer, we denote rui as the revenue it gets when u buys i. Therefore, P(rui) can be regarded as retailer satisfaction. In this paper, the revenue information is considered as the only factor to influence retailer satisfaction and is determined by hit rate and item price. The more sales the retailer achieves, the higher value of P(rui) will be. With the above assumptions, our goal is to maximize both P(bui), P(sui) and P(rui).

3.1 Algorithm1: HSR-1

Since bui has two states, i.e., bui ∈ {buy, not buy}, we use Bernoulli distribution to model it for HSR-1. The probability of bui is defined as follows:

where δui is an indicator parameter. δui = 1 if u buys i in the training set, otherwise δui = 0. Here σ(u, i) is the sigmoid funciton with fb(u, i) denoting the user-item association,

where c is a constant.

Our next task is to model user satisfaction and retailer satisfaction given bui. We note that some items, (1)items that users like but do not pretend to buy, and (2)items with high price but irrelevant to users, should not be over optimized due to the risk of reducing the hit rate. Hence, sui and rui are considered only when δui = 1. In other words, we optimize sui and rui when (user, item) pair is observed. Since the correlation of sui with rui is obviously positive based on our analysis in the previous section, we assume they are sampled from bivariate normal distribution, that is,

where K1 = 1/(2πσsσr√1-ρ2 ), K2 = 1/(2(1 - ρ2 )), ∆s = (sui -fs(u, i)) and ∆r = (rui -fr(u, i)). Here σ denotes standard deviation of each factor and ρ is the correlation between sui and rui. fs(u, i) and fr(u, i) can be depicted as satisfaction function for u and i.

Because sui and rui have different ranges, in applications, we standardize both of them to [0, L]. For example,

where rMax and rMin are supremum and infimum of item price set. We then formulate the maximum posterior to derive our optimization criterion:

where some model parameters are ignored for the sake of brevity. We assume bui, sui and rui are influenced by Uu and Vi, and a straightforward assumption is that fb(u, i) = fs(u, i) = fr(u, i) = U T u Vi.

We add regularization terms ||U||2 and ||V ||2 for avoiding over-fitting, and conduct stochastic gradient descent (SGD) algorithm to update U and V . Different from PMF, we update the latent factors with both observed and unobserved (user, item) pairs. Specifically, in each iteration, we sample two pairs from each class and update the latent factors in turn. In order to make a prediction, we compute the expected value U T u Vi for each (u, i) pair after finishing the update process. For u, the itemwith higher U T u Vi will rank higher and will be recommended with higher probability.

3.2 Algorithm2: HSR-2

Because the Gaussian assumption in HSR-1 may not be an optimal solution to modeling discrete values (i.e., sui), we use binomial distribution to model user satisfaction inspired by [Wu, 2009; Kim and Choi, 2014]. We further integrate bui into sui for consistency. Then the probability of sui can be written as:

where B denotes binomial distribution, and L is the maximal rating score in the dataset.

Intuitively, binomial distribution is always unimodal, which is more reasonable than Gaussian models. HSR-2 has another advantage than HSR-1: U T u Vi will not be limited by sui and rui when optimizing σ(u, i).

We also use binomial distribution to model rui. Note that rui needs not to be an integer because the first term in Eq.(6) will be eliminated in the optimization process. Similar to HSR-1, we also assume user satisfaction and retailer satisfaction are correlated but conditional independent given Uu and Vi. Combining distributions of sui and rui, and formulating the maximum posterior, we obtain the following optimization

We also conduct SGD algorithm to update U and V for HSR-2 and the learning process is similar to HSR-1. In each iteration, the time complexity of our methods is O(D), therefore the execution time is comparable to the existing pairwise item recommendation methods.

3.3 Discussion and Explanation

Both HSR-1 and HSR-2 rank items based on U T u Vi. This is because if U T u Vi is greater, P(bui), P(sui) and P(rui) will also be greater, and hence u will be more likely to choose and prefer i, while the website retailer will get relatively higher revenue. It can be explained in Figure 2, where the horizontal axis denotes user satisfaction, vertical axis represents website revenue and the contour expresses P(sui)P(rui) that HSR try to optimize. The black points represent the items that u wants to buy and the gray points are irrelevant items.

We now compare HSR with other related models and give an interpretation of their assumptions. For implicit feedback, the algorithms such as iMF and BPR aim to find the most relevant items but ignore horizontal and vertical directions. Therefore, they do not consider whether u likes the recommended items or not. The recommendation methods based on explicit feedback, e.g, CofiRank, ListRank and xCLiMF, try to search the potential items from direction A, in which the items that u most likes are supposed to be first recommended. However, because they do not try to avoid the irrelevant items when training the models, some points with high U T u Vi may be irrelevant to u in the test set.

For HSR, we search the items from direction B, which guarantees both user satisfaction and retailer satisfaction. We also try to avoid the irrelevant items in a training set by aforementioned Bernoulli or binomial assumptions, so the cheap and relevant items can also be recommended with many opportunities. From Eq.(5) and Eq.(7) we find that by involving item price information, HSR-1 and HSR-2 can not only globally optimize the website revenue, but also try to learn the acceptable price range of each customer, which is beneficial to learning user satisfaction. Because of those reasons, HSR are more comprehensive than existing approaches.

We note that for some datasets, the item price and user satisfaction may not be correlated obviously. In this case, we still try to balance all the factors for it can improve overall performance. In practice, we can also adjust the weight of hit rate part, user satisfaction part and revenue part of Eq.(5) and Eq.(7) for different purposes.

3.4 The Metrics

To measure user satisfaction and website revenue, we design two modified hit rate based metrics - satisfaction recall (S-R)

and price recall (P-R) as follows:

where R(b) is the recall metric on the test set. It can be represented as:

where N is the number of users, Ltr u denotes the recommended item set for u, and Lte u is the observed itemset. M(s) and M(r) are the mean rating score and mean price of hit items in the test set. For example,

From Eq.(8), we observe that if an algorithm achieves a high S-R score, it must guarantee both recall and mean rating score of hit items. This idea also applies to P-R, which balances both recall and mean price of hit items. Hence, our metrics describe overall system performance.

4 Experiments

4.1 Datasets

To fairly evaluate the performance of our models, we study 10 Amazon datasets provided by [McAuley and Leskovec, 2013]. Each dataset contains plenty of review information such as rating scores, item price, user comments and review time. We only consider user ratings and item price. Some related statistic information is summarized in Table 3. We preprocess the data by dropping the items without rating or price information, and subdivide them into training, validation and test sets, where 80% is used for training and the left 20% is evenly split between validation and test sets.

4.2 Baselines and Parameter Settings

We compare our models with 4 state-of-the-art methods for ranking: (1)CofiRank, (2)ListRank, (3)iMF and (4)BPR.

CofiRank [Weimer et al., 2007] and ListRank [Shi et al., 2010] are listwise methods for item ranking with explicit feedback (e.g, ratings). Both of them directly optimize a list of items based on rating values. iMF [Hu et al., 2008; Lin et al., 2014] is a pointwise method that updates observed and unobserved pairs individually. BPR [Rendle et al., 2009] adopts a pairwise ranking method with the assumption that the observed (user,item) pairs are more positive than the unobserved (user,item) pairs, and optimizes the comparison in each iteration. For iMF and BPR, we take a pre-processing step by keeping the ratings as observed positvie feedback and other (user, item) pairs as unobserved feedback. We conduct comparisons with iMF and BPR because they perform better in very sparse datasets than the other baseline methods.

We set the learning rate to 0.001 for iMF, ListRank and HSR-2 and to 0.01 for CofiRank, BPR and HSR-1. We fix latent dimension D = 10 and choose regularization coefficient from λ ∈ {0.001, 0.01, 0.1, 1}. The correlation ρ is set to 0.1 and L = 5. We adopt precision, recall and our proposed metrics S-R and P-R to test the performance. The length of recommendation lists is fixed at K = 5 for all metrics.

4.3 Analysis of Hit Rate

We show the hit rate performance comparison of our mothods with other baseline models. The precision and recall results are shown in Table 2, where the best performance is in bold font. For comprehensive comparison, we also list the improvement of F1 score in the last row. From the table, we have the following observations:

1. Because our test sets are very sparse, the precision results are small comparing with recall when K = 10. We also observe that the models considering unobserved items (i.e., iMF, BPR, HSR-1 and HSR-2) perform much better than the models which only use rating information (i.e., CofiRank and ListRank). Extremely, when each user only has one observed item in the training set, CofiRank and ListRank will be next-to-no benefit for exploiting the relevant items, and that is the reason for their poor performance in our experiments.
2. On average, BPR is better than iMF due to the pairwise assumption. Although iMF considers the unobserved pairs, it is based on an absolute assumption that the su,i will be 1 when u buys i, and 0 otherwise. On the contrary, BPR, HSR-1 and HSR-2 try to take feedback as relative preferences rather than absolute ones.
3. Both HSR-1 and HSR-2 are better than the other baseline methods in terms of both precision and recall results. They improve the precision by an average of more than 18% and improve the recall by an average of more than 20% comparing with the best baseline models. It is mainly because that HSR-1 and HSR-2 not only consider all possible (user, item) pairs, but also adopt explicit feedback information.

4.4 Analysis of User Satisfaction

We then analyse the performance of the compared models on S-R metric and list the improvement of our models on mean ratings of hit items (M(s)). The experimental results are shown in Table 4, from which we can have the following observations and conclusions:

1. Some models with lower precision or recall values can achieve higher S-R scores. For example, on the video games dataset, HSR-1 has lower recall performance than HSR-2 but achieves better S-R due to higher M(s).
2. Both HSR-1 and HSR-2 are better than the other baseline models on S-R, which demonstrates the benefit of

combining bui and sui. We also find that M(s) is not improved in some datasets. This is mainly because HSR try to balance hit rate and user satisfaction instead of simply optimizing the latter one. Because HSR have much better performance than the other models on recall values, the influence of M(s) is not obvious here.

4.5 Analysis of Revenue

We compare our models with other baselines on P-R metric, and list the improvement of HSR on mean price of hit items (M(r)). The results are summarized in the lower portion of Table 4, and we find that

1. There is plenty of room to optimize the website revenue. Some algorithms with poor recall performance may achieve better P-R metric and M(r). For example, on the toys&games dataset, iMF has nearly 19% lower recall score than BPR, but it performs better than BPR when we consider P-R metric, because it increases the average revenue a lot at the cost of decreasing a certain degree of the recall value.
2. Our models achieve much better performance than any other models on both P-R metric and M(r). For many datasets, the improvement is over 50%, and for some datasets, such as industrial&scientific and video games,

the performance can even double the best baseline models, which shows the efficiency of HSR by integrating the price factor into the recommendation models. Because total revenue and profit are almost always correlated, our methods have high degree of confidence to help earn much more money for the online aggregators.

4.6 Analysis of Stability

Finally, to study the recommendation stability, we vary the recommendation size K to be values of {1, 3, 5, 7, 9}, and some results are shown in Figure 3. As can be seen, when K increases, the precision scores have general downward trend, and other metrics pretend to increase. HSR-1 and HSR-2 are consistently better than other models. In particular, when K increases, the advantages of our models on P-R become more and more obvious.

5 Conclusion and FutureWork

In this paper, we consider three important factors, (1)hit rate, (2)user satisfaction, and (3)website revenue, to measure the performance of recommender systems. We then propose two algorithms, called HSR-1 and HSR-2, to optimize them. Finally, two simple but convincing metrics are designed to measure the comparison models. The experimental results show that our models can achieve better hit rate and user satisfaction results and also significantly improve website revenue.

In the future, we intend to exploit more kinds of user behaviors and design some mechanisms for recommendation diversification. To better measure the overall recommendation performance, we will try to design more effective metrics.

Acknowledgments

This research is supported by the National Natural Science Foundation of China (NSFC) No. 61272303 and Natural Science Foundation of Guangdong Province No. 2014A030310268. We also thank Dr. Weike Pan for helpful discussions.