We focus on the measure of recommendation stability, which reflects the consistency of recommender system predictions. Stability is a desired property of recommendation algorithms and has important implications on users' trust and acceptance of recommendations. Prior research has reported that some popular recommendation algorithms can suffer from a high degree of instability. In this study we propose a scalable, general-purpose iterative smoothing approach that can be used in conjunction with different traditional recommendation algorithms to improve their stability. Our experimental results on real-world rating data demonstrate that the proposed approach can achieve substantially higher stability as compared to the original recommendation algorithms. Importantly, the proposed approach not only does not sacrifice the predictive accuracy in order to improve recommendation stability, but is actually able to provide additional accuracy improvements at the same time.
In the recommender systems literature, evaluating performance of
recommendation algorithms has always been a key issue, and
recommendation accuracy has been the major focus in developing
evaluation metrics [
Based on how unknown ratings are predicted, recommendation
techniques can be classified into three general categories:
contentbased, collaborative filtering, and hybrid [
Recommendation stability measures the inherent consistency
among the different predictions made by the system. Consider an
example where the system makes predictions for two movies, i1
and i2, for user u. Let’s denote the two rating predictions as
R*(u,i1) and R*(u,i2). Let’s assume that prediction R*(u,i1) is
precisely accurate and, after user u consumes item i1, it gets added
to the system as part of the known ratings, i.e., R(u,i1) = R*(u,i1).
The recommendation algorithm re-computes all other predictions
in light of the new data. Would this change the value of the other
prediction, R*(u,i2), and to what extent, even though the newly
incoming rating data was exactly as predicted by the system? In
other words, two predictions R*(u,i1) and R*(u,i2) of the same
recommender system can be viewed as “inconsistent” with each
other, if adding one of them to the training data for the system
changes the other prediction. As discussed in [
Specifically, the stability of a recommender system is defined as
the extent to which the system’s predictions for the same items
stay the same/similar (i.e., are stable), when any and all new
incoming ratings submitted to the system are in complete
agreement with system’s prior predictions. Based on this idea, a
two-phase approach (illustrated in Figure 1) for computing
stability of a recommendation algorithm has been introduced in
prior literature [
RMSS
, ∈ ∩
,
,
|
∩
|
where P1 and P2 are the predictions made in Phase 1 and 2,
respectively, i.e., RMSS captures the shift in predictions made by
the same recommendation algorithm with new ratings that are in
complete agreement with algorithm’s own prior estimations.
Providing consistent predictions has important implications on
users’ trust and acceptance of recommendations. In the consumer
psychology literature, it has been shown that online advice-giving
agents with greater fluctuations in past opinions are considered
less informative than those with a more uniform pattern of
opinions [
High instability results from predictions that are inconsistent with each other. We propose an iterative smoothing approach, which involves multiple iterations for repeatedly and collectively adjusting the rating predictions of a recommendation algorithm based on its other predictions and, thus, is explicitly aimed at improving consistency of predicted ratings. The key idea of iterative smoothing is that the rating predictions computed during current iteration will be fed back into the data to predict other ratings in subsequent iterations.
Figure 2 provides an overview of the proposed iterative smoothing algorithm, and Figure 3 gives a high-level illustration of the overall process. Given rating space S and training set D where ratings are known, predictions on unknown ratings S\D are first estimated using some standard recommendation algorithm T. These predictions are denoted as P0. The procedure of iterative smoothing then starts to iteratively adjust estimations for each rating in S\D based on all other ratings in the rating space S (i.e., both known as well as predicted) in order to proactively improve consistency between different predicted ratings.
More specifically, during the k-th iteration (for any k = 1, 2, …), for each unknown user-item pair (u,i)S\D, a model fk,u,i is built based on training dataset Dk,u,i. This dataset is constructed to contain all known ratings combined with all predictions on useritem pairs in S\D computed in the previous (k-1) iteration, except for the prediction on (u,i) as indicated in Figure 2. As the result of the k-th iteration, each model fk,u,i produces a new prediction for (u,i) that is stored as Pk(u,i), i.e.: , , , , , ∈ ∈ \ ,, Here R(u,i) represents the known rating that user u gave item i, and fk,u,i is the prediction model built based on Dk,u,i. Figure 4 illustrates the process within each iteration of the iterative smoothing approach. The set of predictions made in the current iteration is compared with predictions made in the previous iteration to compute the deviation between the two sets (measured in root mean squared difference). The iterative smoothing process stops either after a fixed, pre-determined number of iterations or when predictions on unknown ratings do not change.
By definition, in each iteration, a separate model is built for every user-item pair with unknown rating. Thus, in total, |S\D|K models need to be constructed over the course of K iterations, each using |S|–1 ratings as a training dataset. If t(x) is the time needed to build a predictive model on data sample of size x using recommendation algorithm T, then the time complexity of the iterative smoothing approach is O(|S\D|Kt(|S|)).
Inputs: known ratings data D, # of iterations K, algorithm T
1. Build model f0 on known ratings D using some standard recommendation algorithm T, i.e., f0T(D) 2. Apply model f0 to compute predictions P0 for unknown ratings S\D, i.e., P0(u,i) = f0(u,i) for (u,i)S\D 3. For each iteration k {1, …, K}
For each unknown rating pair (u, i)S\D a. Construct dataset Dk,u,i by including all known ratings D and all predicted ratings Pk-1 from the previous iteration, except for rating Pk-1(u,i), i.e.,
Dk,u,i = D ∪ Pk-1\ {Pk-1(u,i)} b. Build model fk,u,i on dataset Dk,u,i using T, i.e.,
fk,u,i T (Dk,u,i) c. Make prediction on (u, i) and store in P k, i.e.,
Pk(u, i) = fk,u,i(u, i) 4. Output predictions made in the final iteration PK
In other words, the complexity of iterative smoothing algorithm is
proportional to the size of unknown ratings in the rating space.
This computational requirement is likely to be prohibitively
expensive for many real-world scenarios, i.e., anytime the
useritem rating space is large and rating data is sparse. For example,
the Movielens 100K dataset is a publicly available movie rating
dataset [
We propose a variation of iterative smoothing approach that substantially simplifies the original approach and significantly reduces its computational requirements.
Figure 5 provides an overview of the proposed scalable iterative smoothing algorithm. Similarly to the original iterative smoothing approach, the proposed scalable version also involves multiple iterations for repeatedly adjusting estimations for each unknown rating. However, in each iteration, instead of building one model for each unknown rating, only one single model is built upon all known ratings and predicted ratings in previous iteration. Specifically, during k-th iteration (for any k = 1, 2, …), model fk is built based on training dataset Dk which contains all known ratings D combined with all predictions Pk-1 on user-item pairs in S\D computed in the previous iteration. Pk(u,i) denotes the predicted rating for (u,i) in the k iteration by the collective inference approach, defined as follows: , ∈ , ∈ \ ,
, , Here R(u,i) represents the known rating that user u gave item i. As the result of the k-th iteration, for each (u,i)S\D, the model fk produces a new prediction for (u,i) that is stored as Pk(u,i). Similarly to the original approach, new predictions are compared with predictions made in the previous iteration and the procedure ends either after a fixed number of iterations or when predictions on unknown ratings converge (i.e., do not change).
The key difference between this simplified variation and the original iterative smoothing algorithm is the number of predictive models built within each iteration k. The original algorithm builds a separate model for every unknown rating in the rating space, in order to properly adjust the predicted rating Pk(u,i) using all other ratings from previous iteration, i.e., all ratings from D as well all ratings Pk-1(u',i') where (u',i') (u,i).
Inputs: known ratings data D, # of iterations K, algorithm T Process: 1. Build model f0 on known ratings D using some standard recommendation algorithm T, i.e., f0T(D) 2. Apply model f0 to compute predictions P0 for unknown ratings S\D, i.e., P0(u,i) = f0(u,i) for (u,i)S\D 3. For each iteration k {1, …, K} a. Construct dataset Dk by including all known ratings D and all predicted ratings Pk-1 from the previous iteration, i.e.,
Dk = D ∪ Pk-1 b. Build model fk on dataset Dk using T, i.e.,
fk T(Dk) c. For each unknown rating pair (u, i)S\D , make prediction on (u, i) and store in Pk, i.e.,
Pk(u, i) = fk(u, i) 4. Output predictions made in the final iteration PK
Figure 5. Overview of scalable iterative smoothing approach. In contrast, the simplified algorithm builds only one predictive model in each iteration, based on the entire rating matrix. In other words, predicted rating Pk(u,i) is adjusted using all ratings from previous iteration, i.e., all ratings from D as well as from Pk-1, including Pk-1(u,i). Thus, in the simplified algorithm, for any given rating prediction P1(u,i) in the first iteration, the predictive model is built on a rating data (i.e., D1) that only differs from the rating data used in the original algorithm by one additional rating (i.e., D1\{P0(u,i)}). Because the influence of one additional rating is often subtle, especially when entire rating space is large (i.e., in settings with large numbers of users and items), the single overall model build in the simplified algorithm should produce outcomes similar to the ones produced by individual models built in the original algorithm, especially in the first iteration. While the difference between the original and simplified versions of the iterative smoothing may slowly increase as the number of iterations grows, the simplified approach still provides significant performance improvements (both in stability and accuracy), as demonstrated by the experimental results later in the paper. Moreover, the runtime complexity of the simplified algorithm is much lower, making it much more practical from the scalability perspective. In particular, as only one overall model is built on all available ratings (i.e., dataset of size |S|) within each iteration, in total K models are constructed over the course of K iterations. Thus, the time complexity of the simplified variation is O(Kt(|S|)). Comparing this to the complexity of the original algorithm, O(|S\D|Kt(|S|)), the scalable heuristic offers huge computational improvements (i.e., by roughly |S\D| times). In this paper, we use scalable iterative smoothing in our experiments.
Our experiments test the stability improvements achieved by the proposed meta-algorithmic approach in conjunction with several popular collaborative filtering techniques.
The experiments follow the two-phase stability computation from
prior literature [
Step 0: Create training and test datasets, i.e., DT, DV, ET, EV. Step 1: Find the best model parameters: i. Use a portion (e.g., 75%) of training set DT to build rating prediction models using iterative smoothing. ii. Compute model accuracy on other portion (25%) of DT. iii. Compute model stability on predictions made on ET. iv. Repeat steps i-iii with various parameter settings for iterative smoothing (i.e., number of iterations). v. Find the best parameters for iterative smoothing, i.e., the specifications that result in best stability and accuracy. Step 2: Evaluate accuracy and stability of the final predictions i. Use the best parameter settings for iterative smoothing. ii. Train the system on the entire training set DT using iterative smoothing. iii. Evaluate predictive accuracy on the reserved validation rating set DV. iv. Evaluate recommendation stability on the reserved unknown rating space EV.
Step 3: Report parameter setting(s) as well as the accuracy and stability of the final predictions.
Figure 6. Overall experimental process.
Additionally, the process of iterative smoothing involves multiple iterations to adjust the predictions of unknown ratings. One of the goals in this study is to find whether predictions converge during the process of iterative smoothing and, if so, when. In addition, there is possibility that iterative smoothing models can “overadjust” rating predictions after a number of iterations, in their attempt to maximize the performance on training data. Overfitting is a well-known phenomenon which occurs when a predictive model is fine-tuned to fit the training data (including the random errors, outliers, and noise in the data) too well, which typically leads to diminished predictive performance on test data. Therefore, for a given algorithm, it is necessary to find the best number of iterations to use on a given dataset in the final iterative smoothing procedure. In order to find the optimal parameter settings, we further used the standard train-test data splitting approach internally within the training data to identify the best parameter values for the proposed approach, i.e., that result in best accuracy and stability. The overall experiment process is summarized in Figure 6.
In our experiments, we test the proposed approach in conjunction
with four popular recommendation algorithms: the simple
baseline method, classic user- and item-based variations of
neighborhood-based CF approaches, and the matrix factorization
technique. A brief overview of each technique is provided below.
Baseline. In real-world settings, some users may systematically
tend to give higher ratings than others, and some universally liked
items might receive higher ratings than others. Without
normalization, such user and item effects could bias system’s
predictions. Hence, recommender systems often involve a
preprocessing step to remove these “global effects”. One common
practice is to estimate and remove three effects: the overall mean,
the main effect of an item, and the main effect of a user [
bui = µ + bu + bi ,
where µ is the overall average rating, bu is the average observed
deviation from µ on ratings provided by user u, and bi is the
average observed deviation from µ on ratings given to item i.
Note that, in all of our experiments (i.e., with all other
recommendation algorithms), the ratings data were normalized by
removing these global effects. Moreover, this estimate is often
used as a baseline recommendation technique for comparison with
other recommendation algorithms, i.e., R*(u,i) = bui, and we
investigate its performance in our experiments as well.
User-Based Collaborative Filtering (CF_User). The user-based
nearest-neighbor collaborative filtering approach is a heuristic that
makes predictions of unknown ratings for a user based on the
ratings previously rated by this user’s “nearest neighbors”, i.e.,
other users who have similar rating patterns [
∗ , ∑∈ , | | where N(u,i) is a set of “neighbors” with similar rating patterns to user u and that have provided ratings for item i, simuv is the similarity between users u and v, and bui is the baseline estimate for user u on item i. In our implementation, two users must have rated at least 3 items in common to allow computation of similarity between them. The similarity between two users is calculated as Pearson correlation between rating vectors (based on the commonly rated items) of the two users. Prediction of each unknown rating is formulated by combining the preferences of 20 most similar users who have rated the same item.
Item-Based Collaborative Filtering (CF_Item). The user-based
collaborative filtering technique also has an analogous item-based
version, where the ratings of the nearest-neighbor items are used
to predict unknown ratings for a given item. Several studies have
presented empirical evidence that item-based algorithms often
provide better predictive accuracy than user-based methods (e.g.,
[
The objective of the experiment is to compare the performance of
the proposed iterative smoothing approach with standard
singlemodel recommendation techniques on several real world datasets.
The first dataset we used is the Movielens 100K dataset [
Experimental results are consistent across different datasets. On all three datasets, our proposed meta-algorithmic iterative smoothing approach outperformed the original recommendation techniques in both stability and accuracy in the vast majority of cases. In particular, on average (i.e., across all datasets), iterative smoothing provided a dramatic 55% improvement over the original recommendation algorithms in stability (as measured by RMSS) for CF_User and CF_Item algorithms. Even for the fairly stable SVD and baseline techniques, on average, iterative smoothing was able to further improve RMSS by 14%. In terms of predictive accuracy, on average, iterative smoothing provided 1.4% improvements in RMSE across different algorithms. CF_Item Baseline SVD CF_User CF_Item Baseline SVD CF_User CF_Item Baseline
This paper introduces a general-purpose, practical metaalgorithmic approach – based on iterative smoothing – for improving stability of a variety of traditional recommendation algorithms. The iterative smoothing approach uses multiple iterations to repeatedly and explicitly adjust predictions of a recommendation algorithm based on its other predictions in order to make them more consistent with each other. We examined the performance of iterative smoothing approach on several real world datasets. Our experiments show that the proposed approach demonstrates effectiveness in their ability to improve stability for several widely used recommendation algorithms. Perhaps as importantly, the proposed approach not only does not sacrifice the predictive accuracy to obtain these stability improvements, but actually is able to provide some additional accuracy improvements at the same time.
This work provides several interesting directions for future research. This study shows that iterative smoothing can improve stability for different recommendation algorithms, providing larger improvements for some algorithms and smaller improvements for some others. Providing some additional theoretical understanding of what algorithmic and data characteristics can lead to larger vs. smaller improvements in recommendation stability for the proposed approach is an important direction for future work. Another interesting direction would be to perform user behavior studies to investigate the value of stable (i.e., as opposed to unstable) recommendations on users’ usage patterns and acceptance of recommender systems.
This research was supported in part by the National Science Foundation grant IIS-0546443.