Incremental Matrix Factorization: A Linear Feature Transformation Perspective

1 Introduction

Recent years, Matrix Factorization (MF) models have been successfully applied to various real-world recommender systems [Liu et al., 2011; Wu et al., 2012; Zhu et al., 2015; Lin et al., 2017; Wu et al., 2017], due to the advantages of high accuracy, low computational cost and easy implementation [Salakhutdinov and Mnih, 2008; Bach et al., 2008; Hazan, 2008; Zeng et al., 2015; Chen et al., 2016]. Indeed, most of MF models are batch-based, which usually have intensive computational cost when updating the latent feature vectors after the training phase [Rendle and Schmidt-Thieme, 2008; Luo et al., 2012]. Therefore, a critical demand is to incrementally refine the MF models with new ratings for real-world online scenarios.

In the literature, to facilitate the computational overhead of batch-based MF models, a number of incremental MF studies have been made. However, there are still some major challenges to be addressed. First, most of the algorithms for incremental MF are not general, which are limited by specific batch-based MF models [Wang et al., 2011; Luo et al., 2012; Vinagre et al., 2014], such as Non-negative Matrix Factorization (NMF) [Lee and Seung, 1999] or Probabilistic Matrix Factorization (PMF) [Salakhutdinov and Mnih, 2008], or some strict use restrictions, such as a pre-processed matrix without any missing elements [Brand, 2003; Sarwar et al., 2002], the small-scale incremental data batch [Rendle and Schmidt-Thieme, 2008; Wang et al., 2011; Luo et al., 2012; Devooght et al., 2015; Matuszyk et al., 2015] and the scenarios of the new user/item problem [Song et al., 2015]. Second, most existing incremental MF models have to store coming ratings nearly as much as that in batch-based MF models [Luo et al., 2012; Devooght et al., 2015], which is not truly incremental from a data storage perspective. Moreover, as most incremental MF models are non-convex and complex, the error bounds of them are hardly theoretical analyzed. To the best of our knowledge, there still lacks a holistic view for addressing all the above challenges at the same time.

∗Corresponding author.

To fill the above void, in this paper, we propose a general Linear Feature Transformation (LFT) framework for incremental MF. Specifically, the framework only needs to train a small-sized feature transformation matrix for capturing the changes of model parameters when new data stream comes. Furthermore, only a small constructed collection of samples needs to be saved to train the feature transformation matrix in our framework, and most coming ratings will be dropped in short periods of time. In particular, to demonstrate that the proposed framework is generally applicable for incrementally updating most of MF models, we select a representative batch-based MF model (i.e., a constrained MF model), and detail how to incrementally update it under the proposed LFT framework. We further theoretically explain the framework and analyze the training error bound from a low-rank approximation perspective. To be specific, the contributions of this paper can be summarized as follows:

• We propose a general LFT framework of incremental MF for efficient online recommendation, which is generally applicable for incrementally updating most of MF models. In particular, we develop a concrete LFT implementation for a constrained MF model.
• We theoretically explain our proposed framework from a low-rank approximation perspective. In the case of using the framework for MF models with no constraints and

no regularization terms, we prove the upper bound of the training error expectation in the incremental phase.

• We conduct extensive experiments on two real-world datasets. The results clearly validate the effectiveness, efficiency and storage performance of our concrete LFT implementation comparing with other state-of-the-art incremental MF models.

2 RelatedWork

In this section, we illustrate some existing incremental models, which are often designed for updating latent feature matrices in an online recommendation scenario. Up to now, incremental MF models can be mainly divided into the following three categories from a technical point of view.

SVD-based Model. This kind of incremental MF models is characterized by using SVD as its batch-based model (eg., [Brand, 2003; Sarwar et al., 2002]). Incremental updating operations through the basic algebraic properties of SVD such as one-rank operations [Brand, 2003] leads to a high efficiency. However, SVD requires a matrix that has no missing elements to be decomposed. Therefore the performance of these models on the sparse datasets is limited.

Vector-retraining Model. Unlike the SVD-based Model, there are different kinds of batch-based MF approaches which can be applied into vector-retraining models [Rendle and Schmidt-Thieme, 2008; Devooght et al., 2015]. Particularly, the key idea of this models is that, when a new rating arrives, the latent feature vectors used to estimate the rating need to be slightly updated [Vinagre et al., 2014] or retrained [Rendle and Schmidt-Thieme, 2008; Luo et al., 2012; Devooght et al., 2015; Matuszyk et al., 2015] in order to have a better performance in later time periods. Although some strategies to improve efficiency [Rendle and Schmidt-Thieme, 2008; Matuszyk et al., 2015] and accuracy [Luo et al., 2012] are introduced, this kind of models can only update coming ratings one by one. Besides, when the data comes incrementally, discarding some of the existing data will reduce the average number of elements corresponding to each user (item), which brings a quite negative impact on the effectiveness for such models. As a result, vector-retraining models have limited efficiency when large-scale incremental ratings arrive at the same time and relatively high storage consumption for saving ratings (in Section 4.2).

Space-retraining Model. In order to rule out the redundant calculation of the overhead which is caused by the "One by One" updating in the vector-retraining models, some space-retraining models are proposed. [Wang et al., 2011] assumes the smooth evolution of the latent feature matrix, and optimizes the increment of the latent feature matrix by minimizing the upper bound of the loss function with a bunch of incremental ratings. However, the assumption is only established when the F-norm of the incremental rating matrix is small. Another space-retraining model [Song et al., 2015] retrains the feature space via auxiliary feature learning and matrix sketching strategies [Liberty, 2013], while it is only designed for solving the new user/item problem.

Compared to vector-retraining models, the matrix we trained in this paper is to reflect the linear change of latent feature vectors over time, rather than latent feature vectors themselves. Therefore, algorithms based LFT framework have better time-space complexity when the incremental data scale reaches a certain size (in Section 4.2). Besides, the different assumption from [Wang et al., 2011] makes the feasibility of our approach unaffected by the large-scale incremental rating matrix and the new user/item problem. Moreover, we illustrate the reasonableness of our assumption from a low rank approximation perspective and guarantee the quality of the solution when batch-based MF problems are formulated with no constraints and no regularization terms (in Section 5).

3 The Proposed LFT Framework

In this section, we introduce the overview of our incremental MF framework LFT (Linear Feature Transformation). For better illustration, we first list some important notations and their descriptions in Table 1. Moreover, for a matrix A, we set Sy(A) = [ 0 A AT 0 ], where the 0 means the missing ratings rather than the exact values.

Indeed, most of incremental MF methods are made up of two steps. First, a batch-based MF method is used to train the initial latent feature matrices. Second, an incremental training process is developed for updating latent feature matrices when a bunch of new ratings come. As designing more sophisticated batch-based MF models is not the focus of our paper, here we pay close attention to the second step, and design an incremental MF framework with a linear transformation assumption to describe latent feature changes. Then we introduce the problem formulation, followed by the proposed LFT framework.

In a recommender system, there are n users and m items. In each time period t + 1, incremental ratings are recorded as ∆R|t+1 ∈ Rn×m. And ∆Y|t+1 = [∆P|t+1,∆Q|t+1] ∈ R(n+m)×K is the latent feature matrix decomposed by the matrix ∆X|t+1 = Sy(∆R|t+1) with the batch-based MF model G (e.g., PMF or NMF). We concatenate all the ratings till time t as R|t ∈ Rn×m estimated by P|tQT|t , where matrix Y|t = [P|t,Q|t ] has been learned before. Here, the time period is application-depended such as an hour, a day or a week. Given the above definition, the incremental MF problem turns into: how to efficiently learn and update the new feature matrix Y|t+1 from Y|t when a bunch of new ratings ∆R|t+1 come in time period t + 1. We have the assumption:

Assumption 3.1. The transformation of the latent feature matrix Y|t over the time period (t = 1, 2, ...) can be described as a linear function of its past value and the incremental latent feature matrix:

where there are

It should be noted that C|t+1 and D|t+1 are K-dimensional matrices which project different latent feature vectors (Yi,:|t+1 and ∆Yi,:|t+1) into a same linear space. In fact, the above linear transformation Eq.(1) presents a special form that resembles Vector Auto Regression (VAR) [Scott Hacker and Hatemi-J, 2008; Hatemi-J, 2004], which is an econometric model to capture the linear interdependencies among multiple time series. Besides, we will introduce this transformation with a low-rank approximation perspective in Section 5. In particular, we show the work flow of updating the latent feature matrix in Figure 1.

In order to get the updated feature matrix Y|t+1, we need to figure out the matrix L|t+1 when the matrix X|t+1 = Sy(R|t+1). Specifically, the incremental training problem could be generally formulated as Eq.(3), where f G(.) is the objective function. n1 and n2 are the numbers of equality constraints hG(.) and inequality constraints gG(.) respectively. As shown in Eq.(3), the proposed incremental framework LFT is applicable to any batch-based MF model G with explicit objective functions (and explicit constrains).

Before introducing the concrete algorithms to solve the objective function, we summarize the LFT framework in Algorithm 1. As can been seen from this algorithm, the key to LFT framework lies in Step 3. We leave the details for learning the matrix L|t+1 in the next section.

Algorithm 1 The Linear Feature Transformation Process.

Input: Incremental matrix∆R|t+1; Feature matrix Y|t; The selected batch-based MF model G;

Output: Updated latent feature matrix Y|t+1;

• 1: Decompose the incremental matrix ∆R|t+1 with the selected MF model G and get a feature matrix ∆Y|t+1;
• 2: Combine the matrix Y|t and ∆Y|t+1 to get O|t+1 by Eq.(2);
• 3: Calculate L|t+1 until the objective function Eq.(3) converges;
• 4: return Updated feature matrix Y|t+1 = O|t+1L|t+1;

4 Implementation of LFT

In this section, we introduce a concrete LFT implementation for a constrained MF model named FAVA [Zeng et al., 2015]. Compared to the choice of unconstrained batch-based MF models (e.g., PMF), choosing FAVA can be more representative to show that our framework is generally applicable to incrementally updating most of batch-based MF models by formalizing the corresponding incremental training problem as Eq.(3). After that, we compare the time-space complexity of our proposed model with some state-of-the-art methods.

4.1 The Incremental FAVAModel based on LFT

In this section, we develop a model named FAVA LFT which incrementally update a batch-based MF model named FAVA as an example of applying LFT framework to batch-based constrained MF models.

Batch MF Phase. As with FAVA, FAVA LFT uses the hyper-parameters written as {σj}Kj=1, which can ensure that the superiority of hyper-parameters will not lose when the scale of the rating matrix is increasing [Zeng et al., 2015]. The loss function is formulated in the following

where X = Sy(R) and Y denotes the combination of user and item feature matrix as shown in Section 3.

Through the FAVA algorithm, we can get the matrix ∆Y|t+1 from optimizing the problem [Zeng et al., 2015]:

LFT Phase. After getting the matrix ∆Y|t+1, we can establish O|t+1 with the Assumption 3.1 and the known latent feature matrix Y|t, then Y|t+1 can be updated by Eq.(1) after getting the matrix L|t+1 through optimizing the problem:

where X|t+1 = Sy (R|t+1 ), and R|t+1 consists of some original rating samples (a sub-matrix of R|t) and new coming ratings (∆R|t+1). The scale of the matrix X|t+1 could be manually adjusted for balancing the effectiveness and efficiency of FAVA LFT. Considering from the reasonableness,

Algorithm 2 FAVA LFT Algorithm.

Input: Threshold of the absolute difference of the objective function ε; Sample rating matrix R|t+1; Factorization Variances {σ2 i }Ki=1; Latent feature matrix Y|t; Incremental latent feature matrix ∆Y|t+1;

Output: Updated latent feature matrix Y|t+1;

• 1: Initialize L|t+1 and combined feature matrix O|t+1 by Eq.(2); 2: do
• 3: Calculate the gradient of L|t+1 by Eq.(8);
• 4: Use the steepest descent method to get the step size η;
• 5: Update column vectors of L|t+1 by Eq.(7);
• 6: Calculate the absolute difference εt of the objective function before and after the update of L|t+1;
• 7: while εt ≥ ε;
• 8: return Y|t+1 = O|t+1L|t+1

such process can also be regarded as a kind of approximation of original rating matrix by sparsification [Halko et al., 2011].

For the constrained nonconvex optimization problem Eq.(6), we use a non-standard projection gradient method to update the optimization variables while maintaining its feasibility as follows:

where the gradient of L|t+1 and the projection function Π(.) are respectively described as Eq.(8) and Eq.(9). Besides, the step size η can be calculated by the steepest descent method.

It should be noted that we project the different column vectors L:,i|t+1 of the intermediate solution to the hyperellipsoidal surface in direction of the connection between the L:,i|t+1 and the origin, which can help us to approximate a feasible point without solving linear equations established by proximal methods. In addition, the selection of the initial values for L|t+1 in the feasible set is also a critical step. A simple idea is that we set L|t+1 = [I, 0] as the initial optimization variable, because the solution Y|t in the previous time period necessarily satisfies the constraints.

To summarize the process that we iteratively update L|t+1 and η until Eq.(6) converges, the implementation of FAVA LFT has been detailed in Algorithm 2.

4.2 Complexity Analysis

In this section, we compare FAVA LFT with Batch MF and vector-retraining models (e.g., RMF R [Rendle and SchmidtThieme, 2008] and IRMF [Luo et al., 2012]) in terms of the time-space complexity. And the results are shown in Table 2, where D is the iteration number. To a certain extent, the result can show the high efficiency and low storage overhead of our framework. And the same complexity can be extended to LFT implementations based on some other batch-based MF models (e.g., PMF or NMF).

Time Complexity. According to Table 2, Batch MF is usually slower than RMF R and IRMF in the case of |ΩRt | ≫ |Ω∆Rt |. However, when |Ω∆Rt | ≥ min{n,m}, RMF R and IRMF would have lower efficiency than the Batch MF. As a result, most vector-retraining models (e.g., RMF R and IRMF) cannot address the incremental MF problem well when the number of coming ratings in each time period is large. On the other hand, the efficiency of our framework in incremental phase can be easily controlled by tuning ∣∣ΩRt ∣∣ which is usually a constant multiple of |Ω∆Rt |. Besides, according to Table 2, the scale of the incremental rating matrix has limited impact on the efficiency of LFT based models, and we believe that LFT framework will have high efficiency in large-scale online recommender systems.

Space Complexity. Vector-retraining models usually require a large number of user's historical ratings Ri,: when retraining the user's feature vector Pi,:, which leads a certain number of historical ratings to be stored for each user. And because of the sparseness of the rating matrix, most of coming ratings cannot be dropped in each time period. As a result, the overhead of saving ratings shown in Table 2 should not be ignored. On the other hand, the matrix trained in LFT framework is a linear change of latent feature vectors over time rather than specific feature vectors. Therefore, only a small-scale sample matrix ∣∣ΩRt ∣∣ is needed and the data storage overhead can be reduced.

5 Theoretical Analysis

In this section, we conduct theoretical analysis to further explain the LFT framework and discuss its properties. Specifically, we first introduce a kind of model based on LFT named extend LFT (eLFT), and then analyze eLFT from the lowrank approximation perspective. It is worth mentioning that we prove an upper bound on the training error expectation of the model. The bound can give the theoretical basis to guarantee that incremental MF models using the LFT framework is reasonable and practical.

Problem Formulation. Similar to Eq.(3), we formulate the eLFT problem with no constraints and no regularization terms as follows:

where ˜X|t+1 is defined as

It should be noted that since users cannot repeat rating, we assume ΩR|t ⋂ Ω∆R|t+1 = ∅ in all subsequent analysis. Through Eq.(11), the estimated rating matrix has an offset which is related to the latent feature matrix. Therefore, we need some other methods to predict the missing ratings (e.g., the average of the ratings which are predicted as exact values in previous time periods).

Equivalence and Approximation. In order to understand eLFT from the perspective of low rank approximation, we consider the following joint optimization problem of existing ratings and incremental ratings in time period t + 1

We replace the variable with O ∈ R(n+m)×2K , and O = [ P ∆P Q ∆Q ]. The optimization problem Eq.(12) can be equally expressed as

where P = [ In 0 ] O [ IK 0 ]. Besides, Q,∆P,∆Q can be obtained in a similar way.

We know that a local optimal solution O|t+1 of Eq.(13) can be easily found when O|t+1 = [ P|t ∆P|t+1 Q|t ∆Q|t+1 ]. And the distinction between the local optimal and the global optimal solutions only depends on the batch-based model which is used to decompose R|t and ∆R|t+1 into P|tQT|t and ∆P|t+1∆QT|t+1 . To solve the incremental problem Eq.(13) in different time periods, an intuitive idea is that when incremental data arrives, the columns of the matrix O are expanded with the incremental latent feature matrix to obtain the local optimal solution of the joint optimization problem Eq.(13). However, as time goes by, we cannot tolerate the continuous growing of the rank of the latent feature matrix. Therefore, we should find a K-rank approximation of O|t+1.

According to [Halko et al., 2011], the approximation can be set as O|t+1MM T , where the column vectors of matrix M ∈ R2K×K are orthonormal. The problem Eq.(13) can be relaxed as follows:

which is equivalent to Eq.(10) when columns of L|t+1 are orthonormal vectors.

In summary, the eLFT can be considered as to find a special K-rank approximation of a local optimal solution which can be got through optimizing a joint optimization problem of existing ratings and incremental ratings in time period t + 1. In particular, we have the following theorem.

Theorem 5.1. In any time period t + 1, we can obtain a solution of the optimization problem Eq.(10) to make the expectation of the training error e|t+1 satisfies Eq.(15) when K ≥ 2.

In Eq.(15), λj means the j-th largest singular value of matrix O|t+1, and ∆e|t means the residual sum of squares (RSS) of the matrix ∆R|t and ∆P|t∆QT|t .

Proof. According to the discussion above, we know that the optimization problem Eq.(14) is equal to the low-rank approximation of a local optimal solution of problem Eq.(12).

For any known M, we have

According to the Average Frobenius errors mentioned in [Eckart and Young, 1936], in Eq.(16), if we initialize the M with M which can be got by Randomized Range Finder algorithm [Halko et al., 2011], we have

when K ≥ 2. And we can get the following inequality for any M through the Cauchy-Schwarz inequality.

Through Eq.(17) and Eq.(18), we can easily get

Then we substitute Eq.(19) into Eq.(16).

As the problem Eq.(10) and Eq.(14) are equivalent when matrix of L|t+1 is orthonormal, we can apparently obtain a solution that meets Eq.(15) when L|t+1 is initialized with M. Besides, the error bounds will be maintained after the gradient descent process of optimizing Eq.(10). Therefore, the theorem has been proved.

According to the theorem and the proof, regardless of the number of incremental ratings, the total error will always be a function of the rank of latent feature matrices K and the singular values {λj}2K j=K+1 of matrix O|t+1. Thus, finding the optimal K-rank approximation of the joint optimization problem is a good way to solve the incremental problem.

6 Experiments

In this section, we mainly introduce four experiments, which evaluate our method and baselines from four aspects: effectiveness, efficiency, the storage and use rate of rating samples.

Dataset. The experiments were conducted on two realworld datasets MovieLens1M (ML1M) and MovieLens10M (ML10M), which are standard datasets in rating prediction. The data is collected by the GroupLens Research from the MovieLens web site 1 .

Measurements. The four metrics, which are designed to evaluate the effectiveness, efficiency, storage and use rate of rating samples are the RMSE of all predicted ratings [Luo et al., 2012], the cumulative runtime, the number and the use rate of rating samples in each time period, respectively.

Baselines. We chose two widely used incremental MF methods, namely RMF R [Rendle and Schmidt-Thieme, 2008] and IRMF [Luo et al., 2012], for comparison on a small dataset. Besides, we accelerated the above two models as new baselines, namely QRMF R and QIRMF, on both datasets. Otherwise, the efficiency of original vector-retraining models on ML10M is intolerable because of the high time complexity. For QRMF R and QIRMF, the main idea is that we update a latent feature vector only when the corresponding user (item) last appears in the incremental ratings. Therefore, we can effectively reduce the number of gradient calculation to improve the efficiency. Of course, it will make algorithms less effective because of incomplete updates, and specific performance gaps will be shown on the ML1M dataset.

Experimental Process. The specific steps of experimental process is as follows:

• First, the experimental data sorted by timestamp was divided into T disjoint continuous parts with a similar scale. We call the i-th incremental data part i-ID.
• Second, 1-ID was used as the batch training set of incremental recommenders.
• After that, we applied i-ID to simulate the real-world rating batch, and evaluated each model by calculating the four metrics mentioned above. Note that, we only predicted the ratings of whom the user and item have appeared in former ID.
• Then, vector-retraining models (RMF R, IRMF, QRMF R and QIRMF) need to deal with the coming ratings one by one, and FAVA LFT can update the whole feature matrix with batch production (e.g., Algorithm 1).
• We repeated steps 3 and 4 from i = 2 until i = T

Through such experimental setup demonstrated in Figure 2, we can observe that the incremental training process is shown as the arrow from testing 2-ID to training 2-ID.

1 http://movielens.org

Parameters Settings. The initial values of the feature matrices of RMF R, IRMF, QRMF R and QIRMF were randomly drawn from a normal distribution (N(0, 0.01)). The main parameters listed in Table 3 are: the regularization term coefficient λ, the step size η, the number of iteration in incremental training phase D, the rank of latent feature matrices K, the size of sampled matrix |Ω|, the threshold of the absolute difference of the objective function in FAVA LFT ε, and the ID number for each dataset T .

It should be noted that all the MF parameters (λ, η, D) are obtained by five folds cross tuning on original datasets with corresponding batch-based MF models.

Experimental Results. The experimental results on ML1M and ML10M are depicted in Figure 3 and Figure 4, and the accurate values at last time period are shown in Table 4.

Effectiveness and Efficiency. We can see that original vector-retraining models (RMF R and IRMF) are usually more effective, while the efficiency of them is much lower than the accelerated baselines (QRMF R and QIRMF) in Figure 3. Especially for IRMF, it is difficult to find a balance between effectiveness and efficiency, because the negative effect of speeding up the algorithm cannot be accepted. And we think the main reason is that the non-standard descent method in IRMF will expand the error in the case of incomplete updates. For RMF R, although speeding up the algorithm has only a limited effect on the precision, its performance in terms of effectiveness is also less satisfactory on ML1M dataset. As a contrast to IRMF, the FAVA LFT algorithm based LFT framework has increased the speed almost 174 times in the case of losing about 2% accuracy on ML1M. Meanwhile, compared to RMF R, FAVA LFT in terms of accuracy and efficiency can achieve more outstanding performance. And a similar result also appears on ML10M dataset, which is shown by Figure 4.

Storage Overhead and Sample Use Rate. In Figure 3 and Figure 4, RMF R, QRMF R, IRMF and QIRMF have to store much more rating samples than FAVA LFT, which is caused by the uncertainty of using historical data. While consuming a large amount of storage resources, the low sample use rate causes the bad impacts on the effectiveness of QRMF R and QIRMF. As for FAVA LFT, with the high sample use rate, we are able to calculate the feature transformation matrix (L|t+1) while saving a small amount of rating samples.

In summary, experimental results on two real-world datasets clearly validate the excellent effectiveness, efficiency and storage performance of the proposed framework.

7 Conclusions

In this paper, we designed a framework of incremental MF for enhancing the performance of online recommendation. Specifically, we demonstrated that the LFT framework is generally applicable for incrementally updating most of MF models. Besides, This framework shows a relatively high accuracy with a computation and space efficient training process in a online scenario. Furthermore, we explained the LFT framework in a low-rank approximation perspective, and proved an upper bound on the training error expectation of the model. Finally, extensive experimental results on two realworld datasets clearly validated the superiority of the proposed framework.

Acknowledgements

This research was partially supported by grants from the National Key Research and Development Program of China (Grant No. 2016YFB1000904), the National Science Foundation for Distinguished Young Scholars of China (Grant No. 61325010), the National Natural Science Foundation of China (Grants No. 61403358, No. 61602147 and U1605251), and the Anhui Provincial Natural Science Foundation(Grant No. 1708085QF155). Qi Liu gratefully acknowledges the support of the Youth Innovation Promotion Association of CAS (No. 2014299).