Online recommender systems often deal with continuous, potentially fast and unbounded ows of data. Ensemble methods for recommender systems have been used in the past in batch algorithms, however they have never been studied with incremental algorithms, that are capable of processing those data streams on the y. We propose online bagging, using an incremental matrix factorization algorithm for positiveonly data streams. Using prequential evaluation, we show that bagging is able to improve accuracy more than 20% over the baseline with small computational overhead.
In many real world recommender systems, user feedback is continuously
generated at unpredictable rates and order, and is potentially unbounded. In large
scale systems, the rate at which user feedback is generated can be very fast.
Building predictive models from these continuous ows of data is a problem
actively studied in the eld of data stream mining. Ideally, algorithms that learn
from data streams should be able to process data at least as fast as it arrives, in
a single pass, while maintaining an always-available model [
Ensemble methods in machine learning are convenient techniques to improve
the accuracy of algorithms. Typically, this is achieved by combining results from
a number of weaker sub-models. Bagging [
In this paper we propose online bagging for incremental recommendation algorithms designed to deal with streams of positive user feedback. To our best knowledge this is the rst ensemble method proposed for incremental recommender systems in the literature. 2
Bagging [
To obtain a bootstrap sample of a dataset with size N , we perform N trials, sampling a random example with replacement from the dataset. Each example has probability of 1=N to be sampled at each trial. The resulting dataset will have the same size of the original dataset, however some examples will not be present whereas some others will occur multiple times. To obtain M samples, we simply repeat the process M times.
In its original proposal [
P (K = k) =
N k
In an incremental setting, one could just initialize M sub-models { or bootstrap nodes { and then use (1) to train new examples K times, redrawing K for each node. The problem is that this would still require knowing N beforehand. However, if we assume that N ! 1, then the distribution of K tends to a P oisson(1) distribution, and therefore
P (K = k) = e 1 k! (1) (2) eliminating the need of any prior knowledge about the data. 2.1
We use incremental bagging with ISGD [12], an online matrix factorization algorithm for positive-only data. ISGD (Algorithm 1) uses Stochastic Gradient Descent in one pass through the data, which is convenient for data stream processing. It is designed for positive-only streams of user-item pairs (u; i). Each pair indicates a positive interaction between user u and item i.
Algorithm 1: ISGD - Incremental SGD for positive-only ratings [12] Data: a nite set or a data stream D = f(u; i)1; (u; i)2; : : :g input : no. of latent features k, no. of iterations iter, regularization factor , learn rate output: user and item factor matrices A and B for (u; i) 2 D do if u 62 Rows(A) then
Au Vector(size : k)
Au N (0; 0:1) if i 62 Rows(B) then
Bi Vector(size : k)
Bi N (0; 0:1) for n 1 to iter do errui 1 Au Bi Au Au + (erruiBi Bi Bi + (erruiAu
Au)
Bi)
By applying the online bagging approach described in Section 2, we obtain Algorithm 2 { BaggedISGD.
BaggedISGD learns a model based on M bootstrap nodes. To perform the actual list of recommendations for a user u, items i are sorted by a function f = j1 R^uij as with ISGD. The scores R^ui are the average score of all nodes: R^ui = PmM=1 Aum Bim (3)
M
At training time, this algorithm requires at least m times the computational resources needed for ISGD, with m bootstrap nodes. Recommendation also has the overhead of aggregating m predictions from the submodels. 3
To simulate a streaming environment we need datasets that maintain the natural order of the data points, as they were generated. Additionally, we need positiveonly data, since the tested algorithm is not designed to deal with ratings. We use Algorithm 2: BaggedISGD - Bagging version of ISGD (training algorithm) Data: a nite set or a data stream of user-item pairs D = f(u; i)1; (u; i)2; : : :g input : no. of latent features k, no. of iterations iter, regularization factor , learn rate , no. of bootstrap nodes M output: M user and item factor matrices Am and Bm 4 datasets that conciliate these two requirements { positive-only and naturally ordered {, described in Table 1. ML1M is based on the Movielens-1M movie rating dataset4. To obtain the YHM-6KU, we sample 6000 users randomly from the Yahoo! Music dataset5. LFM-50U is a subset consisting of a random sample of of 50 users taken from the Last.fm6 dataset7. PLC-STR consists of the music streaming history taken from Palco Principal8, a portuguese social network for non-mainstream artists and fans. All of the 4 datasets consist of a chronologically ordered sequence of positive user-item interactions. However, ML1M and YHM50U are obtained from ratings datasets. To use them as positive-only data, we retain the user-item pairs for which the rating is in the top 20% of the rating scale. This means retaining only the rating 5 in ML1M and rating of 80 or more in the YHM-6KU dataset. Naturally, only single accurrences of user-item pairs are available in these datasets, since users do not rate the same item more than once. PLC-STR and LFM-50 have multiple occurrences of the same user-item pairs.
We run a set of experiments using the prequential approach [5] as described in [12]. Each observation in the dataset consists of a simple user-item pair (u; i)
5 https://webscope.sandbox.yahoo.com/catalog.php?datatype=r [Jan 2013] 6 http://last.fm/ 7 http://ocelma.net/MusicRecommendationDataset [Jan 2013] 8 http://www.palcoprincipal.com/ that indicates a positive interaction between user u and item i. The following steps are performed in the prequential evaluation process: 1. If u is a known user, use the current model to recommend a list of items to u, otherwise go to step 3; 2. Score the recommended list given the observed item i; 3. Update the model with (u; i) (optionally); 4. Proceed to { or wait for { the next observation
This process is entirely applicable to algorithms that learn either incrementally or in batch mode. This is the reason why step 3. is annotated as optional. For example, instead of performing this step, the system can store the data to perform batch retraining periodically.
To kickstart the evaluation process we use 10% the available data to train a base model in batch, and use the remaining 90% to perform incremental training and evaluation. We do this initial batch training to avoid cold-start problems, which are not the subject of our research.
In our setting, the items that users have already co-occurred with { i.e. items that users know { are not recommended. This has one important implication in the prequential evaluation process, speci cally on datasets that have multiple occurrences of the same user-item pair. Evaluation at these points is necessarily penalized, since the observed item will be not be within the recommendations. In such cases, we bypass the scoring step, but still use the observation to update the model.
We measure two dimensions on the evaluation process: accuracy and time. In the prequential process described above, we need to make a prediction and evaluate it at every new user-item pair (u; i) that arrives in the data stream. To do this, we use the current model to recommend a list of items to user u. We then score this recommendation list, by matching it to the actually observed item i. We use a recommendation list with at most 20 items, and then score this list as 1 if i is within the recommended items, and 0 otherwise, using Recall@C with cuto s C 2 f1; 5; 10; 20g. Because only one item is tested against the list, Recall@C can only take the values f0; 1g. We can calculate the overall Recall@C by averaging the scores at every step. Additionally, we can also depict it using a moving average. Time is measured in milliseconds at every step and we depict it using the same techniques we use with accuracy.
All experiments were run in Intel Haswell 4-core machines, with CentOS Linux 7 64 bit. The algorithms and prequential evaluation code is implemented on top of MyMediaLite [6]. The recommendation step is implemented with multicore code { predictions from nodes are computed in parallel. 3.1
To evaluate bagging, we experiment with four levels of bootstrapping M 2 f8; 16; 32; 64g. Table 2 summarizes the results of our experiments. Values in Table 2 are obtained by averaging Recall and time obtained at all prequential evaluation steps. With all datasets except YHM-6KU, bagging improves the Recall, especially with M 32. One interesting observation is that bagging has a bigger in uence on higher Recall cuto s, which suggests that improvements of the predictive ability are typically not obtained in the top 5 recommended items.
The model update times increase approximately in proportion to the number of bootstrap nodes M , which is not surprising, since the algorithm performs the update operations one time (in average) in each one of the M bootstrap nodes. However, since the baseline update time is small, this overhead is also small. The last column of Table 2 contains the recommendation time, speci cally the average time required to produce a recommendation list. This is important, because the bagging algorithm needs to aggregate predictions coming from all M nodes, which is obviously an overhead. Results show that both the update times and recommendation times increase proportionally to M . However, the recommendation step is a far more costly operation, even when computed in parallel. For example, using M = 64 with LFM-50U and YHM-6KU, recommendations are computed in nearly two seconds in average, in 4-core machines.
A useful feature of prequential evaluation is that it allows us also to depict the
evolution of Recall@209 in Figure 1. This visualization reveals how the predictive
ability of the algorithm performs over time, as the incremental learning process
occurs.
Results in Table 2 and Figure 1 show that bagging clearly improves the accuracy
of ISGD, with accuracy improvements of 20% over the baseline (see Table 2
LFM50U and ML1M). This improvement is mainly observable with cuto s C 5 of
Recall. Given that bagging reduces variance [
It is also clear that the time overheads grow linearly with the number of bootstrap models. However, the overhead in model update times is not very relevant in practice, given that the baseline update times are very low in ISGD { with M = 64 the highest update time falls below 400ms. The overhead at recommendation time is more evident, when aggregating results from the M bootstrap nodes. Fortunately, as with most ensemble techniques, parallel processing can be trivially used to alleviate this overhead. Additionally, there may be room for code optimization or approximate methods that require less and/or more e cient computations. 4
Bagging is a an ensemble technique successfully used with many machine learning algorithms, however it has not been thoroughly studied in recommendation problems, and particularly with incremental algorithms. In this paper, we experiment online bagging with an incremental matrix factorization algorithm that learns from unbounded streams of positive-only data. Our results suggest that with manageable overheads, accuracy clearly improves { more than 20% in some cases {, especially as the number of recommended items increases. In the near future, we intend to experiment this and other online ensemble methods in a larger number of stream-based recommendation algorithms. 5
Project \TEC4Growth { Pervasive Intelligence, Enhancers and Proofs of Concept with Industrial Impact/NORTE-01-0145-FEDER-000020" is nanced by the North Portugal Regional Operational Programme (NORTE 2020), under the PORTUGAL 2020 Partnership Agreement, and through the European Regional Development Fund (ERDF). This work is partially funded by the European Commission through project MAESTRA (Grant no. ICT-2013-612944). We thank Ubbin Labs, Lda. for kindly providing data from Palco Principal. 5. Gama, J., Sebastia~o, R., Rodrigues, P.P.: On evaluating stream learning algorithms. Machine Learning 90(3), 317{346 (2013), http://dx.doi.org/10.1007/s10994-012-5320-9 6. Gantner, Z., Rendle, S., Freudenthaler, C., Schmidt-Thieme, L.: Mymedialite: a free recommender system library. In: Proc. of the 2011 ACM Conference on Recommender Systems, RecSys 2011. pp. 305{308. ACM (2011) 7. Jahrer, M., Toscher, A., Legenstein, R.A.: Combining predictions for accurate recommender systems. In: Proc. of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2010. pp. 693{702. ACM (2010), http://doi.acm.org/10.1145/1835804.1835893 8. Oza, N.C., Russell, S.J.: Experimental comparisons of online and batch versions of bagging and boosting. In: Proc. of the 7th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD 2001. pp. 359{364. ACM (2001), http://portal.acm.org/citation.cfm?id=502512.502565 9. Schclar, A., Tsikinovsky, A., Rokach, L., Meisels, A., Antwarg, L.: Ensemble methods for improving the performance of neighborhood-based collaborative ltering. In: Proc. of the 2009 ACM Conference on Recommender Systems, RecSys 2009. pp. 261{264. ACM (2009), http://doi.acm.org/10.1145/1639714.1639763 10. Segrera, S., Moreno, M.N.: An experimental comparative study of web mining methods for recommender systems. In: Proc. of the 6th WSEAS Intl. Conf. on Distance Learning and Web Engineering. pp. 56{61. WSEAS (2006) 11. Sill, J., Takacs, G., Mackey, L.W., Lin, D.: Feature-weighted linear stacking. CoRR abs/0911.0460 (2009), http://arxiv.org/abs/0911.0460 12. Vinagre, J., Jorge, A.M., Gama, J.: Fast incremental matrix factorization for recommendation with positive-only feedback. In: Proc. of the 22nd Intl. Conference on User Modeling, Adaptation, and Personalization, UMAP 2014. LNCS, vol. 8538, pp. 459{470. Springer (2014), http://dx.doi.org/10.1007/978-3-319-08786-3 41 13. Wolpert, D.H.: Stacked generalization. Neural Networks 5(2), 241{259 (1992), http://dx.doi.org/10.1016/S0893-6080(05)80023-1