A Generic Coordinate Descent Framework for Learning from Implicit Feedback

Introduction

In recent years, the focus of recommender system research has shifted from explicit feedback problems such as rating prediction to implicit feedback problems. Most of the signal that a user provides about her preferences is implicit. Examples for implicit feedback are: a user watches a video, clicks on a link, etc. Implicit feedback data is much cheaper to obtain than explicit feedback, because it comes with no extra cost for the user and thus is available on a much larger scale. However, learning a recommender system from implicit feedback is computationally expensive because the observed actions of a user need to be contrasted against all the non-observed actions .

Stochastic gradient descent (SGD) and coordinate descent (CD) are two widely used algorithms for large scale machine learning. Both algorithms are considered state-of-the-art for learning matrix factorization models from implicit feedback and have been studied extensively. SGD and CD have shown different strengths and weaknesses on various data sets . While SGD is available as a general framework to optimize a broad class of models , CD is only available for a few simple models . In fact, it is even unknown if CD can be used to efficiently optimize complex recommender models. Our work closes this gap and identifies a model property called $k$-separability, that is a sufficient condition to allow efficient learning from implicit feedback. Based on $k$-separability, we provide a general framework to derive efficient implicit CD solvers.

Our paper is organized as follows: First, we introduce the problem of learning from implicit feedback and show that the number of implicit training examples makes the application of standard algorithms challenging. Next, we provide our general framework for efficient implicit learning with CD. We identify $k$-separability of a model as a sufficient property to make efficient learning feasible and introduce iCD, a generic learning algorithm for $k$-separable models. In Section 5, we show how to apply iCD to a diverse set of models, including, matrix factorization (MF), factorization machines (FM) and tensor factorization. This section serves both as solutions to popular models as well as a guide for applying the framework to other complex recommender models.

We identify a basic property of recommender models that allows efficient CD learning from implicit data.

We provide iCD, a framework to derive efficient implicit CD algorithms.

We apply the framework and derive algorithms for MF, MF with side information, FM, PARAFAC and Tucker Decomposition.

Related Work

Since several years, matrix factorization (MF) is regarded as the most effective, basic recommender system model. Two optimization strategies dominate the research on MF from implicit feedback data. The first one is Bayesian Personalized Ranking (BPR) , a stochastic gradient descent (SGD) framework, that contrasts pairs of consumed to non-consumed items. The second one is coordinate descent (CD) also known as alternating least squares on an elementwise loss over both the consumed and non-consumed items . In terms of the loss formulation, BPR’s pairwise classification loss is better suited for ranking whereas CD loss is better suited for numerical data. With regard to the optimization task, both techniques face the same challenge of learning over a very large number of training examples. BPR tackles this issue by sampling negative items, but it has been shown that BPR has convergence problems when the number of items is large . It requires more complex, non-uniform, sampling strategies for dealing with this problem . On the other hand, for CD-MF, Hu et al. have derived an efficient algorithm that allows to optimize over the large number of non-consumed items without any cost. This computational trick is exact and does not involve sampling. Many authors have compared both CD-MF and BPR-MF on a variety of datasets and some work reports better quality for BPR-MF whereas for other problems CD-MF works better . This large body of results indicates that the advantages of CD and BPR are orthogonal and both approaches have their merits.

Our discussion so far was focused on learning matrix factorization models from implicit data. Shifting from simple matrix factorization to more complex factorization models has shown large success in many implicit recommendation problems . However, work on complex factorization models relies almost exclusively on SGD optimization using the generic BPR framework. Our work, provides the theory as well as a practical framework for deriving CD learners for such complex models. Like CD for MF, our generic algorithm is able to optimize on all non-consumed items without explicitly iterating over them. To summarize, our paper enables researchers and practitioners to apply CD in their work and gives them a choice between the advantages of BPR and CD.

Problem Statement

Let $I$ be a set of items and $C$ a set of contexts. Let $S$ be a set of observed feedback where a tuple $(c,i,y,\alpha)\in S$ indicates that in context $c$, a score $y$ has been assigned to item $i$ with confidence $\alpha$. See Figure 1 for an illustration. We use a general notation of context which can include for instance user, time, location, attributes, history, etc. Section 5 and Section 6 show more examples for context.

The learning task is to find the values of the model parameters that minimize a loss over the data $S$, e.g., a squared loss

where $\lambda_{\theta}$ is an regularization constant for parameter $\theta$.

2 Coordinate Descent Algorithm

Objective (1) can be minimized by coordinate descent (CD). CD iterates through the model parameters and updates one parameter at a time. For a selected parameter $\theta\in\Theta$, CD computes the first $L^{\prime}$ and second derivative $L^{\prime\prime}$ of $L$ with respect to the selected coordinate $\theta$:

where $\eta\in(0,1]$ is the step size. For multilinear models, a full step, i.e., $\eta=1$, can be chosen without risking divergence . All models in Section 5 fall into this category.

Such CD algorithms have been well studied and the runtime complexity is typically linear in the complexity of the training examples and embedding dimension. For MF, shows a complexity of $\mathcal{O}(|S|\,k)$ and for FM, derives a complexity of $\mathcal{O}(N_{Z}(X)\,k)$ where $N_{Z}(X)$ is the number of non-zero entries in the design matrix $X$. The linear runtime complexity in the number of training examples makes these algorithms well suited for explicit recommendation settings, however, they become infeasible for implicit problems.

3 Learning from Implicit Feedback

In an implicit recommendation problem, the non-consumed items are meaningful and cannot be ignored. For instance, in Figure 1 (right), the data depicts how often each item was consumed in a context in the past. The non-consumed items, i.e., the ones with a count of zero, are useful to learn user preferences. To formalize, the training data $S_{\text{impl}}$ of an implicit problem consists of a set $S^{+}$ of observed feedback and all the non-consumed tuples $S^{0}$

$S^{+}$ contains the observed feedback and is of much smaller scale than $S_{\text{impl}}$, usually $|S^{+}|\ll|C|\,|I|$.

The implicit learning problem can be stated as minimizing the objective in eq. (1) over the implicit data $S_{\text{impl}}$. While possible in theory, in practice, it is infeasible to apply the learning algorithms of Section 3.2 to this problem due to their linear computational runtime in the size of the training data which is $|S_{\text{impl}}|=|C||I|$ for implicit problems. Our paper shows how to derive efficient CD algorithms for optimizing eq. (1) over implicit data.

Generic Coordinate Descent Algorithm for Implicit Feedback

As discussed in Section 3.3, the reason why training on implicit data is challenging is the large number of implicit examples $S^{0}$ which is typically $|S^{0}|\in\mathcal{O}(|C||I|)$. Note that $S^{0}$ includes all context-item pairs that are not in $S^{+}$. We show now that we can rephrase the optimization criterion to sum over all context-item pairs. This reformulation is a prerequisite to later allow the decomposition of the loss in Section 4.2. Moreover it allows to study implicit optimization without having to consider $S^{+}$.

Implicit learning can be rephrased as a combination of learning on a small positive set and minimizing the scoring function on any context-item pair.

Per definition of the loss (eq. 1) and the implicit training set $S_{\text{impl}}$ (eq. 5)

We further can collapse each pair of examples into a single one. We show this for the pair $(c,i,y,\alpha)\in S$ and its counterpart $(c,i,0,-\alpha_{0})$.

The additional constant does not change the optimum for $\Theta$, so rescaling of examples as in eq. (8) preserves the optimum.

The lemma allows an interesting interpretation of implicit learning tasks. Implicit problems can be seen as explicit or one-class problems with an additional implicit regularizer or bias $R(\Theta)$ for predicting zeros. Compared to a common regularizer such as L2, the implicit regularizer is aware of the model $\hat{y}$. L2 penalizes non-zero model parameters $\Theta$ whereas the implicit regularizer penalizes non-zero predictions $\hat{y}$. Consequently, the implicit regularizer is less restrictive than L2 because small predictions can be achieved even with large model parameters.

2 iCD Algorithm for k𝑘k-separable Models

As shown in eq. (7), implicit learning can be formulated as explicit learning on a small set $S$ with an expensive implicit regularizer $R$. Learning models over an explicit loss is already well studied , so we focus now on the implicit regularizer

The general computational complexity is $\mathcal{O}(|C||I|)$.

In this section, we introduce the concept of a $k$-separable model. We will provide an efficient implicit CD solver for any $k$-separable model. In Section 5, we show that many common models are $k$-separable, including matrix factorization, feature-based approaches such as factorization machines, but also higher-order tensor factorization such as PARAFAC or Tucker decomposition. The iCD framework that we derive in this section is not limited to the models described above but can serve as a blueprint for other $k$-separable models as well.

A model $\hat{y}(c,i)$ is called $k$-separable iff the model can be rewritten as

where $\boldsymbol{\phi}$ is parameterized by $\Theta^{C}$ and $\boldsymbol{\psi}$ is parameterized by $\Theta^{I}$ with $\Theta^{C}\cap\Theta^{I}=\emptyset$.

The implicit regularizer of any $k$-separable model can be decomposed to:

The lemma follows from inserting the $k$-separable model (eq. 10) into the implicit regularizer (eq. 9) and rearranging the summations.

This lemma is key to efficient learning algorithms from implicit data. It shows that the context and item sides can be computed independently, which drops the computational complexity from $\mathcal{O}(|C|\,|I|)$ to $\mathcal{O}((|C|+|I|)\,k^{2})$. Next, we show how this can be used for gradient computation which is required for the update step in CD (see eq. 4).

The implicit regularizer gradients of any $k$-separable model with respect to any model parameter $\theta\in\Theta^{C}$ (or analogously $\theta\in\Theta^{I}$), can be simplified to

The lemma follows from deriving eq. (12).

This lemma shows that computing $R^{\prime}$ and $R^{\prime\prime}$ of any context parameter is independent of $|I|$.

From the analysis follows the recipe to derive an efficient iCD learning algorithm for a model $\hat{y}$. First, rewrite the model as a dot product of $\boldsymbol{\phi}$ and $\boldsymbol{\psi}$. Second, construct the first and second derivative of $\boldsymbol{\phi}$ and $\boldsymbol{\psi}$ with respect to any model parameter $\theta\in\Theta$. These results allow to compute $R^{\prime}(\theta)$ and $R^{\prime\prime}(\theta)$ for any model parameter $\theta\in\Theta$ efficiently. With these gradients for the expensive implicit regularizer, a Newton step can be applied. Algorithm 1 shows a generic iCD algorithm using the ideas of this section.

Most models allow some further optimizations: (i) When the gradients of $\boldsymbol{\phi}$ or $\boldsymbol{\psi}$ are sparse, some of the summands of eqs. (13, 14) drop. (ii) The model parameters usually have some structure which can be used for traversing the model parameters more systematically. We will show both of these steps in the next section for a variety of models.

Applications

In this section, we apply iCD to two classes of complex factorization models, namely feature-based factorization models and tensor factorization models. We have chosen these two classes because they are very powerful and frequently used. Moreover each of them has some interesting properties with respect to deriving iCD algorithms. The provided algorithms can be directly applied to many common recommender system tasks. This section also serves as a guide for deriving iCD algorithms in general.

We start by applying our framework to matrix factorization (see Figure 2). For MF, the scoring function is

A MF model is trivially $k$-separable with

and all second derivatives are 0. Thus, the regularizer derivatives simplify to

The derivation is symmetric for the item side.

As MF associates each model parameter with an embedding dimension $f$, we can traverse the parameters one dimension at a time. A full step $\eta=1$ can be taken because MF is bilinear. Algorithm 2 shows the full procedure.

The computation of $J_{I}(f^{*},\cdot)$ is trivially in $\mathcal{O}(|I|\,k)$. Gradient computation of the implicit regularizer is $\mathcal{O}(k)$ per parameter and for the explicit part $\mathcal{O}(|S|)$ for all parameters. Overall, the algorithm has a complexity of $\mathcal{O}((|I|+|C|)\,k^{2}+|S|\,k)$ per iteration.

2 Feature-Based Factorization Models

One of the most powerful extension of MF is feature based modeling for the context and item. Feature-based factorization models are strictly more powerful than MF and have shown large improvements in many applications (e.g. ). For instance, the cold-start problem is commonly solved by replacing or complementing user and item ids with user and item attributes . Another example is context-aware recommendation, where the context is represented by several variables, e.g. location or time in addition to the user id. Also sequential models can be represented by feature based modeling .

Learning general feature-based models on implicit feedback was restricted to BPR so far. This is the first work that provides an implicit CD algorithm for this important model class.

We start with a feature based extension of matrix factorization similar to :

with $\Theta=\{W,H\}$. MFSI is $k$-separable using

Due to sparse gradients of $\boldsymbol{\phi}$ and $\boldsymbol{\psi}$, the first and second regularizer derivatives simplify to:

Note that the sums over the context variable depend only on context where $x_{c,l^{*}}\neq 0$, so with a sparse iterator, the computation is $\mathcal{O}(k\,N_{Z}(X))$ for optimizing all of the context variables in a given embedding layer $f^{*}$.

This computation assumes that $\Phi$ and $\Psi$ are given. Obviously, while optimizing $W$, $\Psi$ does not change and while optimizing $H$, $\Phi$ does not change. However, while optimizing $W$, $\Phi$ changes but can be kept in sync with changes in $W$ by updating:

The item side can be derived analogously. The total runtime of Algorithm 3 for one epoch over all variables is $\mathcal{O}(k^{2}\,(N_{Z}(X)+N_{Z}(Z)))$ for the implicit regularizer.

2.2 Factorization Machines

Similar to MFSI, due to the sparsity in gradients, one of the nested loops drops for the first regularizer derivative $R^{\prime}$ and both nested sums drop for the second regularizer derivative $R^{\prime\prime}$. Consequently, the flow and runtime analysis for FM is the same as for MFSI.

3 Tensor Factorization

Tensor factorization generalizes matrix factorization and deals with problems that involve more than two categorical variables. For instance, in personalized recommendation of tags for bookmarks , the context consists of two variables, the user $C_{1}$ and the bookmark $C_{2}$, and the item $I$ corresponds to the tag. For personalized web search , the context consists of the user $C_{1}$ and the query $C_{2}$ and the item $I$ to the web page. The data can be seen as a three mode tensor over $C_{1}$, $C_{2}$ and $I$. Figure 4 shows an example of how observations over context $C\subseteq C_{1}\times C_{2}$ and items $I$ translate to a tensor. A tensor factorization model tries to approximate the tensor with a low rank decomposition (see Figure 5). Although tensor factorization models are multilinear, we show that they fit well into our framework.

Additionally, we want to highlight, that existing tensor factorization learning algorithms require that the tensor data is dense, i.e., the empty parts in the tensor in Figure 4 are filled with zeros. This would imply that context combinations that never have been observed, are used for training as well, i.e., $C=C_{1}\times C_{2}$. In some applications, this might not make sense, for instance if $C_{1}$ encodes a device type and $C_{2}$ encodes an operating system version. Our iCD framework works for both sparse and dense context. We will point out the differences when necessary.

We first discuss the Parallel Factor Analysis (PARAFAC) model which is a 3-mode extension of matrix factorization.

The item side is equivalent to matrix factorization.

If the context is dense and includes all possible combinations of context variables, i.e., if $C=C_{1}\times C_{2}$, then the computation of $J_{C}(f,f^{\prime})$, can be decomposed to:

This means, the computation is in $\mathcal{O}(|C_{1}|+|C_{2}|)$ instead of $\mathcal{O}(|C_{1}|\,|C_{2}|)$. On the other hand if $C$ is sparse and contains only the subset of the observed context combinations, i.e., $C\subset C_{1}\times C_{2}$, then there is no need for decomposing this sum. The same applies to the loss derivatives of eqs. (37,38): Again, if all possible context is modeled, then $\{c_{2}:(c^{*}_{1},c_{2})\in C\}=C_{2}$ and thus $J_{C_{2}}(f,f^{\prime})$ can replace the sum over $C_{2}$.

The overall runtime for PARAFAC’s implicit regularizer is $\mathcal{O}((|C|+|I|)\,k^{2})$ for sparse context and $\mathcal{O}((|C_{1}|+|C_{2}|+|I|)\,k^{2})$ for dense context. The traversal over model parameters can be arranged as in the MF algorithm.

3.2 Tucker Decomposition

Tucker Decomposition (TD) is a generalization of PARAFAC which computes all interactions between the factor matrices. The strength of each interaction is given by a core tensor $B$. For our running example with two context variables $c_{1},c_{2}$ and one item variable $i$, TD is defined as

Even though Tucker decomposition contains nested sums, it is $k_{3}$-separable with

Unlike all the other models we have presented so far, the gradients for $\boldsymbol{\phi}$ are non-zero for any factor index $f\in\{1,\ldots,k\}$. Consequently, the nested loops over factors of the loss gradient (eq. 13) cannot be improved further. However, for $\boldsymbol{\psi}$, which is sparse, the same optimization as in the other models can be applied.

Like for PARAFAC, if $C$ is dense, i.e., $C=C_{1}\times C_{2}$, we can precompute intermediate matrices for $C_{1}$ and $C_{2}$ and the computation of $J_{C}(f,f^{\prime})$ simplifies to

If $C$ is sparse, there is no need for this optimization and we can use a straightforward computation of $J_{C}$. The overall runtime complexities are $\mathcal{O}(k_{1}^{2}\,k_{2}^{2}\,k_{3}^{2}\,(|C_{1}|+|C_{2}|+|I|))$ for dense context and $\mathcal{O}(k_{1}^{2}\,k_{2}^{2}\,k_{3}^{2}\,(|C|+|I|))$ for sparse context.

Experiments

The main objective of the experiments is to illustrate the generality of the iCD framework. We show how iCD can be applied to a variety of recommender problems that cannot be solved with MF alone. For MF models, efficient coordinate descent algorithms (CD) have been previously proposed and its performance compared against gradient descent algorithms such as BPR . Both approaches are considered state-of-the-art and while CD outperforms BPR on certain datasets , BPR has been shown to work better on others . The purpose of our experiments is not to compare BPR and CD on yet another dataset, but rather to demonstrate the versatility of the iCD framework and illustrate how it can serve as a building block for future research on complex recommender models. As with MF, it is likely that both iCD and BPR will show strengths in different applications.

We evaluate on a dataset of $200,000$ users interacting with YouTube. Our subset contains $|I|=68,000$ videos. The dataset also contains side information about age, country, gender and device info. We apply iCD to three popular recommendation problems – Cold-Start, Offline Recommendation, and Instant Recommendation (see Section 6.2). We compare the following algorithms:

Popularity: a static recommender that returns the most popular videos.

Coview: returns based on the previously watched video, the most commonly chosen next video.

iCD-MF: user-item matrix factorization using iCD for optimization, similar to .

iCD-FM: a factorization machine with varying features for the context (Section 5.2). We report results for different feature choices.

We measure the recall and NDCG for the top 100 returned videos. Note that we report relative improvements over the Popularity recommender. All hyperparameters are tuned on a separate tuning holdout set.

2 Results

In the Cold-Start recommendation scenario, we assume that a user interacts with the recommender system for the first time. To simulate this scenario, we select a random subset of users and hold out all their events for evaluation purposes; we train on the remaining users.

The common approach for dealing with cold-start is to represent a user by side information . Here, we use the feature-based FM model (iCD-FM) with the user’s age, gender, country and device info as context features. Figure 7 shows that attribute-aware FM achieves a 2x improvement over the baselines. As expected, neither MF nor Coview can do any better than most-popular recommendation.

2.2 Offline Recommendation

In the Offline Recommendation scenario, we hold out the last feedback of each user and use all the previous feedback for training. This is the most commonly used protocol to evaluate the performance of a recommender algorithm. We experiment with multiple FM models: (1) iCD-FM A: an FM with user attributes, (2) iCD-FM P: a sequential FM that only uses the previously watched video (similar to FPMC or Coview) and (3) iCD-FM A+P+U: an FM that uses all signals: attributes, previously watched video and user id (similar to FPMC with user attributes). As shown in Figure 6(a), the complex FM model with all features achieves the best quality, illustrating the flexibility of feature engineering with iCD.

2.3 Instant Recommendation

In large-scale industrial applications, online training is often not feasible due to complex serving stacks. Commonly, models are periodically trained offline (e.g., every day or week) and applied on a stream of user interactions. When the model is queried to generate recommendations for a user, all feedback until the current time is taken into account for prediction. We simulate this setting by choosing a global cutoff time where all the events before the cutoff are used for training and all the remaining ones for evaluation.

In such settings, models relying on user ids, such as MF, cannot capture recent feedback. Instead, describing a user by the sequence of previously watched videos allows for instant personalization. Such a model can be configured using a feature-based FM model (Section 5.2) and we experiment with four configurations (1) iCD-FM A: FM using user attributes, (2) iCD-FM P: a sequential FM based on the previously watched video, (3) iCD-FM H: a FM based on all previously watched videos, (4) iCD-FM A+P+H: an FM combining all signals. As expected, the complex FM model with all features achieves the best quality. Again, we would like to note the generality of the iCD framework, which enables flexible feature engineering.

3 Computational Costs

As stated in Section 3.3, any conventional CD solver, e.g. , could solve the implicit feedback problem. Now, we substantiate that this is infeasible because of the large number of implicit examples. Figure 8 compares the computational cost for learning an FM with a conventional CD to the costs of iCD on our dataset with 70k items. We use three different context features from Figure 6. The plot shows relative costs to iCD-FM P. For all three context choices, conventional CD shows four orders of magnitude higher compuational costs than iCD. The empirical measured runtime for iCD was in the order of minutes; consequently, CD’s four order of magnitude increase in runtime translates to weeks of training for each iteration. Clearly, using a conventional CD solver to optimize the implicit loss directly is infeasible.

Conclusion

In this work, we have presented a general, efficient framework for learning recommender system models from implicit feedback. First, we have shown that learning from implicit feedback can be reformulated as optimizing a cheap explicit loss and an expensive implicit regularizer. Then we have introduced the concept of $k$-separable models. We have shown that the implicit regularizer of any $k$-separable model can be computed efficiently without iterating over all context-item pairs. Finally, we have shown that many popular recommender models are $k$-separable, including matrix factorization, factorization machines and tensor factorization. Moreover, we have provided efficient learning algorithms for these models based on our framework. Our framework is not limited to the models discussed in the paper but designed to serve as a general blueprint for deriving learning algorithms for recommender systems.

References