Practical Linear Models for Large-Scale One-Class Collaborative Filtering

1 Introduction

Personalized recommendation systems are a core component in many modern e-commerce services [Leavitt, 2006]. Collaborative filtering (CF) is the de-facto standard approach for making recommendations based on information in a database of item preferences from a population of users [Goldberg et al., 1992; Sarwar et al., 2001]. Most of the work on CF has considered the explicit feedback setting, where users express both positive and negative preferences for items in terms of ratings or likes/dislikes [Koren et al., 2009]. In contrast, in the one-class collaborative filtering setting (OC-CF) [Pan et al., 2008], we do not have explicit negative preference information. For example, consider recommending items to users of an e-commerce website based on their purchase history. One can assume that a purchase indicates a positive preference for an item. However, the lack of a purchase does not necessarily indicate a negative preference; it may just be that the user is unaware of the item.

In designing a real world recommender system there are various factors to be considered [Adomavicius and Tuzhilin, 2005; Ricci et al., 2011]. First and foremost, a recommender system should produce good recommendations which can be quantified in terms of relevance. The relevance of a recommender system is measured using evaluation metrics such as precision@k, recall@k etc. Second, a recommender system should be highly scalable. In modern day applications, it is very common to have millions of users and items and billions of recorded interactions. A model should be able to handle the data in a computationally efficient manner as the number of users and items grow to this scale. Third, recommending similar items is very prevalent in real-world recommender systems. For instance, Amazon.com shows product suggestions to customers based on the items they are browsing [Linden et al., 2003a]. Hence, a recommendation algorithm should ideally produce item similarities. Also, interpretability of the recommendation is very critical in persuading users. By explaining the recommendations, the system becomes more transparent, builds users' trust in the system and convinces them to consume the recommended items. For example, the "why this was recommended" feature on Netflix.com explains to users their recommendations by showing them the similar movies that they liked in the past. A lack of interpretability weakens the ability to persuade the users in their decision making [Vig et al., 2009].

While there is a rich literature on OC-CF (discussed subsequently), to our knowledge, all existing methods lack one or more desiderata. Neighborhood-based methods [Sarwar et al., 2001; Linden et al., 2003b] are scalable, incorporate a similarity metric in the model and give explainable recommendations. However, the relevance of their recommendation is weaker as compared to other methods. Matrix factorization models [Hu et al., 2008] optimize a non-convex objective whose solution is sensitive to initialization and hyperparameters. Matrix factorization models are not competitive in terms of top-k ranking performance [Ning and Karypis, 2011; Sedhain et al., 2016]. Also, the recommendations are not explainable and there is no notion of similarity in the model. On the other hand, Linear recommenders [Ning and Karypis, 2011; Sedhain et al., 2016] are the state-of-the-art in terms of relevance. Furthermore, the model explicitly learns a similarity metric. Also, like neighborhood models, recommendations from linear model are easily explainable. However, current linear methods are computationally expensive which limits their applicability to large scale real world problems.

In this paper we address the computational bottleneck of linear models, enabling them to scale up to large OC-CF problems without compromising performance. Our method, Linear-FLow (Fast Low Rank Linear Model), formulates OCCF as a regularized linear regression problem with a randomized SVD for fast dimensionality reduction. Although regularized regression and randomized SVD are not new ideas, their combined use in the context of OC-CF is, to the best of our knowledge, novel. Through extensive experiments on known benchmarks and real-world datasets, we demonstrate that Linear-FLow achieves state-of-the-art performance as compared to other methods, with a significant reduction in computational cost. Due to its scalability and performance, Linear-FLow has all the desirable properties of a practical recommender system. Table 1 summarizes the comparison of the existing OC-CF methods with respect to Linear-FLow.

2 Background

Let U denote a set of users, and I a set of items, with m = ♣U♣ and n = ♣I♣. In OC-CF, we have a purchase 1 matrix R 2 ¶0↪ 1♦m⇥n . We use Rui to refer to the purchase status for the user u and item i. We use R:i to denote the indicator vector of each users' purchase of an item, and similarly Ru: to denote the vector of a user's preference for each item i. We denote by R(u) the set of the items purchased by user u. The goal in OC-CF is to learn a recommender, which for our purposes is simply a matrix ˆR 2 Rm⇥n . We call ˆR the recommendation matrix. The notations are summarized in table 2.

In the rest of this section we review some existing approaches to OC-CF.

2.1 Neighbourhood methods

In (item-based) neighbourhood methods, we produce a recommendation matrix of the form

where S 2 Rn⇥n is some item-similarity matrix. Typically, one uses a predefined matrix S that relies on R. A popular example is cosine similarity [Sarwar et al., 2001; Linden et al., 2003b],

1 We use the word "purchase" simply for the purposes of exposition.

It is typical to sparsify S so that its columns only keep the top-k similar items. Neighbourhood methods are attractive for several reasons. They are simple to implement, efficient and interpretable. However, they are unable to adapt to the characteristics of the data as they rely on a fixed S that is not learned from the new data [Koren, 2008]. Furthermore, recommendation performance can be quite sensitive to the choice of S.

2.2 Matrix Factorization

Matrix Factorization methods are the de facto approach to collaborative filtering with explicit feedback. The basic idea is to embed users and items into some shared latent space, with the aim of inferring complex preference profiles for both users and items. Weighted matrix factorization (WRMF) for one class collaborative filtering [Hu et al., 2008; Pan and Scholz, 2009] optimizes

where, A 2 Rk⇥m, B 2 Rk⇥n , and J 2 Rm⇥n + is some pre-defined weighting matrix and

Jui = JRui = 0K + ↵JRui > 0K (3) where ↵ assigns an importance weight to the observed interaction. WRMF uses Alternating Least Squares (ALS) method for optimization. The solution for A and B in each step of ALS is given by (4)

where, Ju 2 Rn⇥n and Ji 2 Rm⇥m are diagonal matrices such that Juij = Jui and Jiuu = Jui. In each iteration of ALS, due to the weighting, we need to compute the inverse for each user and item as shown in (4). This makes WRMF computationally expensive compared to unweighted matrix factorization.

2.3 Linear Recommenders

Linear methods [Ning and Karypis, 2011; Sedhain et al., 2016] learn the similarity metric from the data. SLIM [Ning and Karypis, 2011] views the recommendation as learning item-item similarity and learns an item-similarity matrix W 2 Rn⇥n via

where λ↪ θ > 0 are appropriate constants, and

Here, ♣♣ · ♣♣1 denotes the elementwise `1 norm of W so as to encourage sparsity, and the constraint diag(W) = 0 prevents a trivial solution of W= In⇥n. SLIM is equivalent to an item-based neighbourhood approach where the similarity matrix S = W is learned from the data. In a related linear model for OC-CF [Sedhain et al., 2016], the authors report very good performance, but the proposed method is computationally expensive, which restricts its applicability in real world problems.

Linear methods are attractive for several reasons. They have superior performance, and unlike neighborhood methods, they adapt with the data as the parameters are learned from data itself. Furthermore, the recommendations are easily interpretable. However, linear methods can be computationally expensive as they require solving a large number of regression subproblems with a big design matrix R. This can scale quadratically with the order of R, or worse.

2.4 Randomized SVD

SVD is the archetypal matrix factorization algorithm and has been widely used in machine learning for dimensionality reduction. However, SVD is computationally expensive and not scalable to large scale datasets. It has been recently shown that SVD can be significantly scaled up, at a negligible cost in performance, by randomization [Halko et al., 2011]. We will describe the randomized SVD algorithm in the next section, in the context of the OC-CF problem.

Randomized SVD has been applied to matrix factorization [Tang and Harrington, 2013] (but not in the OC-CF setting that we are considering). The authors compute the rank-k randomized SVD of the matrix R (Algorithm 1),

where, Pk 2 Rm⇥k , Qk 2 Rn⇥k and ⌃k 2 Rk⇥k . Given the truncated SVD solution, they initialize the item latent factor with the SVD solution and solve

Similarly, if the matrix A is fixed instead of the matrix B, the objective becomes

We refer to (9) and (8) as U-MF-RSVD and I-MF-RSVD respectively. As we will see in the results, the performance of these two models can vary significantly.

3 Large Scale Linear Methods for One-Class Collaborative Filtering

Despite their superior performance, the applicability of Linear methods on real world large scale dataset are constrained by their computational cost. Linear methods involve solving a large number of regression subproblems on a huge design matrix R making it extremely challenging on real world applications where the number of users and items is in millions.

Here we propose a model and an algorithm for scaling up linear methods to large OC-CF problems. In particular, we are seeking an approximation R ⇡ RW that attempts to capture most of the row space of the matrix R through a matrix W that is low-rank and has small Frobenius norm. The motivation for such a double regularization is to better control the generalization error of the model, an insight that was proven correct by our experiments. Moreover, it turns out that there is a natural and efficient way to compute such an approximate decomposition of the matrix R by randomization [Halko et al., 2011], which allows scaling to large problems.

Our model amounts to solving the following optimization problem

where, typically, k ⌧ n. For λ = 0, the optimal solution is given by the Eckart-Young theorem (see, e.g., [Halko et al., 2011])

where Qk is an orthogonal matrix computed by a truncated SVD as in Equation 7. Similarly, if we drop the low-rank constraint in (10), the optimal matrixW is given by the solution of a standard regression problem

which involves the inverse of the original matrix R and therefore does not scale to large problems.

However, under both a low-rank constraint and λ > 0 in (10), finding the optimal W involves solving a hard nonconvex problem with no analytical solution in general. Nonetheless, an analytical solution is possible for a certain parametrization of W as we explain next. We first compute an approximate orthogonal basis Qk of the row space of R, i.e.,

using randomized SVD. In Algorithm 1, we outline the randomized SVD algorithm (We refer to [Halko et al., 2011] for more details.) Then we re-parametrize the matrix W as

for some matrix Y. Note that through this parametrization the rank of W is automatically controlled, no optimality is lost when λ = 0, and the optimization problem (10) reads

Since Qk is orthogonal, we have kQkYkF = kYkF , and (15) becomes

The latter can be solved analytically to give

Note that this inversion involves a k ⇥ k matrix, and hence it is tractable.

The choice of W = QkY is motivated by the following observation. When λ = 0, the solution to our problem is W = QkQTk . This is also the solution to the new formulation of our problem for Y = QTk . When λ is close to zero, we believe that sufficiently good solutions lie close to the span of Qk. Therefore, we choose W = QkY. We demonstrate that this choice performs well empirically in the experimental section. Furthermore, Linear-FLow can be seen as an autoencoder collaborative filteringmodel [Sedhain et al., 2015] with linear activation and Qk as input-hidden weights.

We refer to (15) as I-Linear-FLow as it corresponds to item-item model. Similarly, we can define a user-user model, U-Linear-FLow

As we discussed earlier, recommending similar items is very prevalent in real-world recommender systems. In I-LinearFLow model, the item-item similarity is explicitly given by the matrix W = QkY.

Algorithm 1 Given R 2 Rm⇥n , compute approximate rank-k SVD; R ⇡ Pk⌃kQk

• 1: procedure RSVD(R, k)
• 2: Draw n⇥k Gaussian randommatrix ⌦
• 4: Construct m⇥k orthonormal matrix Z, such that A= ZX
• 3: Construct n⇥k sample matrix A=R⌦
• 5: Constuct k ⇥n matrix B= ZT R
• 6: Compute the SVD of B, B = ˆ Pk⌃kQk
• 7: Compute Pk = Z ˆ Pk
• 8: return (Pk↪ ⌃k↪ Qk)
• 9: end procedure

4 Experiments and Evaluation

We now present an extensive set of experiments where we compare the recommendation performance of the proposed method and all the baselines described under Section 2 on several real-world datasets.

4.1 Datasets

For quantitative evaluation, we used two publicly available datasets and two proprietary datasets. In all of our datasets, we remove users with fewer that 3 corresponding items and vice-versa. Table 3 summarizes statistics of the 4 datasets and they are described in details next.

ML10M The MovieLens 10M dataset 2 is a standard benchmark for collaborative filtering tasks. Following the

2 http://grouplens.org/datasets/movielens/

"Who Rated What" KDD Cup 2007 challenge [Bennett et al., 2007], we created a binarized version of the dataset suitable for evaluating implicit feedback methods. From the original rating matrix ˜R 2 ¶0↪ 1↪ ▷ ▷ ▷ ↪ 5♦m⇥n , we created a binarized

preference matrix R with Rui = J ˜Rui ≥ 4K. LASTFM The LastFM dataset 3 [Celma, 2008] contains the play counts of ⇠1000 users on ⇠170,000 artists. As per ML10M we binarized the raw play counts.

PROPRIETARY-1 & PROPRIETARY-2 are two real but anonymized purchase datasets. PROPRIETARY-1 dataset consists of ⇠27,000 users, ⇠14,000 items and ⇠120,000 item purchases. Similarly, PROPRIETARY-2 dataset consists of ⇠264,000 users, ⇠57,000 items and ⇠1 million item purchases.

4.2 Evaluation Protocol

We split the datasets into random 90%-10% train-test set and hold out 10% of the training set for hyperparamater tuning. We report the mean test split performance, along with standard errors corresponding to 95% confidence intervals. To evaluate the performance of the various recommenders, we report precision@k and recall@k for k 2 ¶3↪ 5↪ 10↪ 20♦ (averaged over test users), and mean average precision (mAP@20).

4.3 Methods compared

We compared the proposed method to a number of baselines:

• User- and item-based nearest neighbour (U-KNN and IKNN). For each dataset, we use Jaccard and Cosine similarity metric and picked the best performing one.
• PureSVD of [Cremonesi et al., 2010]. Instead of exact SVD, we use randomized SVD for efficiency.
• Weighted matrix Factorization (WRMF) as defined in Eq. (2).
• MF-RSVD of [Tang and Harrington, 2013]. We ran this method with user and item based initialization, U-MFRSVD and I-MF-RSVD, as discussed in Eq. (9) and (8) respectively.
• SLIM, as per Eq. (5). For computational convenience, we used the SGDReg variant [Levy and Jack, 2013], which is identical to SLIM except that the nonnegativity constraint is removed. We did not evaluate SLIM with nonnegativity directly as [Levy and Jack, 2013] reports superior performance to SLIM, and is considerably faster to train.

We do not compare against LRec [Sedhain et al., 2016] due to its memory complexity on a large dataset. For instance on the PROPRIETARY-2 dataset, LRec requires ⇠260GB of memory.

3 http://ocelma.net/MusicRecommendationDataset

4.4 Performance Evaluation

Tables 4 - 7 summarize the results of our methods and the various baselines. The results demonstrate that in terms of the quality of recommendation, the linear methods (LinearFLow and SLIM) always outperform other methods in all four datasets. Linear-FLow and SLIM perform equally well and there is little separation between them in terms of the quality of the recommendation. However, as we will show in section 4.5, Linear-FLow is much more efficient than SLIM. Also, unlike other methods, the performance of Linear-FLow is not sensitive to the choice of user vs. item based formulation. From these tables, we make the following additional observations:

• Among the matrix factorization methods, those that use Randomized SVD [Tang and Harrington, 2013] consistently performed the best. This is possibly due to the fact that SVD provides a good initialization whereas matrix factorization optimizes a highly nonconvex bilinear objective and is sensitive to the initialization and hyperparameters. In Table 4 - 6, we observe that the performance of MF-RSVD varies significantly based on whether we initialize user or item latent factors. Also, the factorization methods do not directly provide itemto-item or user-to-user similarity measures. Hence they are not applicable when a recommendation of similar items or users is needed.
• We observe that the neighborhood models yield inferior results compared to the Linear models. Also, the performance varies with the user and item based models. While they perform competitively in the PROPRIETARY2 and PROPRIETARY-1 datasets, they perform poorly in LASTFM and ML10M dataset. Hence, we conclude that neighborhood methods are not consistent with their performance.

4.5 Runtime Evaluation

To compare the training times of the various algorithms, we choose PROPRIETARY-2 and ML10M , the two largest datasets for analysis. We benchmarked the training time of the algorithms by training the model on a workstation with 128 GB of main memory and Intel(R) Xeon(R) CPU E5-2650 v2 @ 2.60GHz with 32 cores. All of the methods exploit multi-core enabled via numpy linear algebra library, whereas SLIM and WRMF attains parallelism via multiprocessing. For a fair comparison, we ran SLIM and WRMF in parallel to use all available cores. In Table 8 we compare the runtime of the proposed method with the baseline methods.

The results demonstrate that while Linear-FLow offers the same quality of recommendation as SLIM, its training time is an order of magnitude faster than SLIM. SLIM is computationally expensive and is the slowest among the baselines. Neighborhood methods are computationally cheap as they only involve sparse linear algebra, however as demonstrated previously, their recommendation quality is not consistent and lagging behind the other methods. For factorization approaches, those that use randomized SVD similar computational footprints as Linear-FLow while WRMF is much more computationally expensive.

4.6 Qualitative Analysis of Learned Similarities

In this section, we provide a qualitative evaluation of the itemitem similarities learned by our I-Linear-FLow model. We use PROPRIETARY-3 , a dataset from a major stock image market site 4 . The data provides whether a given user has clicked on a particular image category, and from these our model can infer the similarity measure between the image categories. Note that the similarity is inferred solely based on the click patterns, without doing any analysis of the textual content of the category names. We choose this dataset for the qualitative evaluation mainly because the category names and are much easier to interpret compared to the other datasets.

In Table 9, we show some examples 5 of top-5 similar items learned by I-Linear-FLow model. We observe that the model discovers meaningful and explainable similarities, hence making it applicable in similar item recommendations.

5 Conclusion

We proposed Linear-FLow, a fast low-dimensional regularized linear model for One-Class Collaborative Filtering, which addresses the computational bottleneck of other linear models for this problem, enabling scaling up to large problem instances while retaining the same performance. In our experiments, we illustrated that the proposed method is computationally superior to the state of the art (an order of magnitude faster than SLIM) and yields competitive performance. In future work, we will explore the possibility of incorporating additional user and item side-information to the model, and further improving the computational and memory footprints by exploring more efficient dimensionality reduction techniques. The main computational bottleneck for Linear-FLow is currently in the computation of randomized SVD, which heavily depends on the linear algebra library, and hence we expect significant speedups by using a GPU back-end linear algebra library [Voronin and Martinsson, 2015].

4 The dataset sharing agreement with the provider restricts us from reporting the statistics and quantitative results. Hence, we do not report summary statistics and quantitative results on this dataset

5 Visit http://ssedhain.com/demos/Item-Item.html for interactive visualization

I-Linear-FLow 0▷0520 ◦ 0▷0012 0▷0398 ◦ 0▷0004 0▷0262 ◦ 0▷0003 0▷0162 ◦ 0▷0002 0▷1062 ◦ 0▷0032 0▷1362 ◦ 0▷0026 0▷1758 ◦ 0▷0026 0▷2145 ◦ 0▷0033 0▷0971 ◦ 0▷0028

I-Linear-FLow 0▷0885 ◦ 0▷0003

0▷0656 ◦ 0▷0002

0▷0429 ◦ 8▷6598 ⇥ 10-5

0▷0256 ◦ 4▷0894 ⇥ 10-5

0▷1783 ◦ 0▷0012

0▷2202 ◦ 0▷0012

0▷2719 ◦ 0▷0010

0▷3259 ◦ 0▷0010

0▷1598 ◦ 0▷0006

I-Linear-FLow 0▷6229 ◦ 0▷0103

0▷5913 ◦ 0▷0046

0▷5337 ◦ 0▷0021 0▷4653 ◦ 0▷0023 0▷0203 ◦ 0▷0011

0▷0310 ◦ 0▷0010

0▷0529 ◦ 0▷0006

0▷0874 ◦ 0▷0015 0▷3615 ◦ 0▷0014

I-Linear-FLow 0▷2242 ◦ 0▷0009

0▷1909 ◦ 0▷0010

0▷1468 ◦ 0▷0005

0▷1077 ◦ 0▷0004

0▷1276 ◦ 0▷0007

0▷1765 ◦ 0▷0010

0▷2609 ◦ 0▷0008

0▷3676 ◦ 0▷0017

0▷1592 ◦ 0▷0007