Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm

Introduction

Trace-norm regularization is a popular approach for matrix completion and collaborative filtering, motivated both as a convex surrogate to the rank Fazel et al. (2001); Candes & Tao (2009) and in terms of a regularized infinite factor model with connections to large-margin norm-regularized learning Srebro et al. (2005b); Bach (2008); Abernethy et al. (2009); Salakhutdinov & Mnih (2008).

Current theoretical guarantees on using the trace-norm for matrix completion all assume a uniform sampling distribution over entries of the matrix Srebro & Shraibman (2005); Candes & Tao (2009); Candes & Recht (2009); Candes & Tao (2009); Recht (2009). In a collaborative filtering setting, where rows of the matrix represent e.g. users and columns represent e.g. movies, this corresponds to assuming all users are equally likely to rate movies and all movies are equally likely to be rated. This of course cannot be further from the truth, as in any actual collaborative filtering application, some users are much more active then others and some movies are rated by many people while others are much less likely to be rated.

In Section 4 we suggest a correction to the trace-norm regularizer, which we call the weighted trace-norm, that takes into account the sampling distribution. This correction is motivated by our analytic analysis and we discuss how it corrects the problems that the unweighted trace-norm has with non-uniform sampling. We then show how the weighted trace-norm indeed yields a significant improvement on the (highly non-uniformly sampled) Netflix dataset.

Complexity Control in terms of Matrix Factorizations

where $Y_{S}$, and similarly $X_{S}$, denotes the matrix “masked” by $S$:

For now we ignore possible repeated entries in $S$. We will also assume that $n\leq m$ without loss of generality.

The two formulations (1) and (2) are equivalent up to some (unknown) correspondence between $\lambda$ and $C$, and we will be referring to them interchangeably at our convenience.

Directly constraining the rank of $X$ forms one of the most popular approaches to collaborative filtering. Training such a model amounts to finding the best rank-$k$ approximation to the observed target matrix $Y$ under the given loss function. However, the rank is non-convex and hard to minimize. It is also not clear if a strict dimensionality constraint is most appropriate for measuring the complexity.

2 Trace-norm Regularization

Lately, methods regularizing the norm of the factorization $U^{\top}V$, rather then its dimensionality, have been advocated and were shown to enjoy considerable empirical success Rennie & Srebro (2005); Salakhutdinov & Mnih (2008). This is captured by measuring complexity in terms of the trace-norm of $X$, which can be defined equivalently either as the sum of the singular values of $X$, or as Fazel et al. (2001):

Note that the dimensionality of $U$ and $V$ in (4) is not constrained. Beyond the modeling appeal of norm-based, rather then dimension-based, regularization, the trace-norm is a convex function of $X$ and so can be minimized by either local search or more sophisticated convex optimization techniques.

3 Scaling of the Trace-norm

It will be useful for us to consider the scaling of the trace-norm with the size of the matrix $X$. This will allow us, for example, to understand the magnitude of the bound $C$ we can expect to put on the trace-norm in the formulation (2).

The rank, as a measure of complexity, does not scale with the size of the matrix. That is, even very large matrices can have low rank. Viewing the rank as a complexity measure corresponding to the number of underlying factors, if data is explained by e.g. two factors, then no matter how many rows (“users”) and columns (“movies”) we consider, the data will still have rank two.

where in the second inequality we used the fact that the number of non-zero singular values is equal to the rank. The Frobenius norm certainly increases with the size of the matrix, since the magnitude of each element does not decrease when we have more elements, and so the trace-norm will also increase. The above suggests measuring the trace-norm relative to the Frobenius norm. Without loss of generality, consider each target entry to be of roughly unit magnitudeAny other constant magnitude will only result in some constant scaling, e.g. $\pm 1$, and so in order to fit $Y$ each entry of $X$ must also be of roughly unit magnitude. This suggests scaling the trace-norm by $\sqrt{nm}$. More specifically, we study the trace-norm through the complexity measure:

which puts the trace-norm on a comparable scale to the rank. In particular, when each entry of $X$ is, on-average, of unit magnitude (i.e. has unit variance), in which case $\left\lVert{X}\right\rVert_{\text{F}}=\sqrt{nm}$, we have:

Another place where we can see that $\textit{tc}(X)$ plays a similar role to $\textit{rank}(X)$ is in the generalization and sample complexity guarantees that can be obtained for low-rank and low-trace-norm learning. Such learning guarantees were mostly discussed in the context of Lipschitz continuous loss functions (i.e. functions with a bounded first derivative), rather then the squared loss. The squared loss has a bounded second derivative rather then bounded first derivative and so requires somewhat different technical tools. Nevertheless, the main thrust of the results is still valid.

Without getting into the technical tools required to rigorously establish the above sample complexity guarantees, it is useful to understand them at a more abstract level. In order to understand the guarantees for low-rank learning, it is enough to consider the number of parameters in the rank-$k$ factorization $X=U^{\top}V$. It is easy to see that the number of parameters in the factorization is roughly $k(m+n)$ (perhaps a bit less due to rotational invariants). And so we would expect to be able to learn $X$ when we have roughly this many samples, as is indeed confirmed by the rigorous sample complexity bounds.

For low-trace-norm learning, consider a sample $S$ of size $|S|\leq Cn$, for some constant $C$. Taking entries of $Y$ to be of unit magnitude, we have $\left\lVert{Y_{S}}\right\rVert_{\text{F}}=\sqrt{|S|}=\sqrt{Cn}$ (Recall that $Y_{S}$ is defined to be zero outside $S$). From (5) we therefore have: $\left\lVert{Y_{S}}\right\rVert_{\text{tr}}\leq\sqrt{Cn}\cdot\sqrt{n}=\sqrt{C}n$ and so $\textit{tc}(Y_{S})\leq C$. That is, we can “shatter” any sample of size $|S|\leq Cn$ with $\textit{tc}(X)=C$: no matter what the underlying matrix $Y$ is, we can always perfectly fit the training data with a low trace-norm matrix $X$ s.t. $\textit{tc}(X)\leq C$, without generalizing at all outside $S$. On the other hand, we must allow matrices with $\textit{tc}(X)=\textit{tc}(X^{*})$, otherwise we can’t hope to find ${\cal{X}}^{*}$, and so we can only constrain $\textit{tc}(X)\leq C=\textit{tc}(X^{*})$. We therefore cannot expect to learn with less then $n\textit{tc}(X^{*})$ samples. It turns out that this is essentially the largest random sample that can be shattered with $tc(X)\leq C=\textit{tc}(X^{*})$, and that if we have more then this many samples we can start learning. For our purposes here, we will mostly just make use of non-learnability arguments of this form: if we can shatter a random sample of size $|S|$ with a matrix $X$ have the same complexity (e.g. trace-norm) as our target matrix $X^{*}$, we cannot hope to learn without a larger sample.

Trace-Norm Under a Non-Uniform Distribution

In this section, we will analyze trace-norm regularized learning when the sampling distribution is not uniform. That is, when there is some, known or unknown, non-uniform distribution ${\cal{D}}$ over entries of the matrix $Y$ (i.e. over index pairs $(i,j)$) and our sample $S$ is sampled i.i.d. from ${\cal{D}}$. Of course, if ${\cal{D}}$ concentrates on only a small subset of the matrix, we have no hope of recovering rows and columns of $Y$ on which we have zero probability of seeing an observation. Instead, our objective here, as is typically the case in learning under an arbitrary distribution, is to get low average error with respect to the same distribution ${\cal{D}}$. That is, we measure generalization performance in terms of the weighted sum-squared-error:

However, the same does not hold when learning using the trace-norm. To see this, consider an orthogonal rank-$k$ square $n\times n$ matrix, and a sampling distribution which is uniform over an $n_{A}\times n_{A}$ sub-matrix $A$, with $n_{A}=n^{a}$ (see Fig. 1). That is, the row (e.g. “user”) is selected uniformly among the first $n_{A}$ rows, and the column (e.g. “movie”) is selected uniformly among the first $n_{A}$ columns. We will use $A$ to denote the subset of entries in the submatrix, i.e. $A=\{(i,j)|1\leq i,j\leq n_{A}\}$, rather then the matrix itself, and so we can say that ${\cal{D}}$ is uniform on $A$. For any sample $S$, we have:

where we again take the entries in $Y$ to be of unit magnitude. In the second inequality above we use the fact that $Y_{S}$ is zero outside of $A$, and so we can bound the rank of $Y_{S}$ by the dimensionality $n_{A}=n^{a}$ of $A$.

To do so, consider another submatrix $B$ of size $n_{B}\times n_{B}$ with $n_{B}=n/2$, such that the rows and columns of $A$ and of $B$ do not overlap (Fig. 1). Now, consider a sampling distribution ${\cal{D}}$ which is uniform over $A$ with probability half, and uniform over $B$ with probability half. Consider fitting a noisy matrix $Y=X^{*}+\text{noise}$ where $X^{*}$ is “orthogonal” rank-$k$. In order to fit on $B$, we need to allow a trace-norm of at least $\left\lVert{X^{*}_{B}}\right\rVert_{\text{tr}}=\frac{n}{2}\sqrt{k}$, i.e. allow $\textit{tc}(X)=k/4$. But as discussed above, with such a generous constraint on the trace-norm, we will be able to shatter $S\subset A$ whenever $|S\cap A|=|S|/2\leq k/4n^{2-a}$. Since there is no overlap in rows and columns, and so values in the sub-matrices $A$ and $B$ are independent, shattering $S\cap A$ means we cannot hope to learn in $A$. Setting $a=2/3$ as before, it seems that with $o(n^{4/3})$ samples, we cannot learn in both $A$ and $B$: either we constrain to a trace-norm which is too low to fit $X^{*}_{B}$ (we under-fit on $B$), or we allow a trace-norm which is high enough to overfit $Y_{S\cap A}$. Either way, we will make errors on at least half the mass of ${\cal{D}}$.To make the above argument more precise, we should note that if we do allow high enough trace-norm to fit $B$, and $|S|=o(n^{4/3})$, then the “cost” of overfitting $Y_{S\cap A}$ is negligible compared to the cost of fitting $X^{*}_{B}$. For large enough $n$, we would be tempted to very slightly deteriorate the fit of $X^{*}_{B}$ in order to “free up” enough trace-norm and completely overfit $Y_{S\cap A}$.

Figure 2, left panel, precisely illustrates this phenomenon on a simulation experiment. For this synthetic example, we used $n_{A}=300$ and $n_{B}=4700$, with an orthogonal rank-2 matrix $X^{*}$ and $Y=X^{*}+{\cal{N}}(0,1)$ (in case of repeated entries, the noise is independent for each appearance in the sample). The training sample size was also set to $|S|$=140,000.

The three curves of Fig. 2 measure the excess (test) error $\left\lVert{X-X^{*}}\right\rVert_{{\cal{D}}}^{2}=\left\lVert{X-Y}\right\rVert_{{\cal{D}}}^{2}-\left\lVert{Y-X^{*}}\right\rVert_{{\cal{D}}}^{2}$ of the learned model, as well as the error contribution from $A$ and from $B$, as a function of the constraint on $\textit{tc}(X)$, for the sampling distribution discussed above and a specific sample size. As can be seen, although it is possible to constrain $\textit{tc}(X)$ so as to achieve squared-error of less then $0.8$ on $B$, this constraint is too lax for $A$ and allows for over-fitting. Constraining $\textit{tc}(X)$ so as to avoid overfitting $A$ (achieving almost zero excess test error), leads to a suboptimal fit on $B$.

Until now we discussed learning by constraining the trace-norm, i.e. using the formulation (2). It is also insightful to consider the penalty view (1), i.e. learning by minimizing

First observe that the characterization (4) allows us to decompose $\left\lVert{X}\right\rVert_{\text{tr}}=\left\lVert{X_{A}}\right\rVert_{\text{tr}}+\left\lVert{X_{B}}\right\rVert_{\text{tr}}$, where w.l.o.g. we take all columns of $U$ and $V$ outside $A$ and $B$ to be zero. Since we also have $\left\lVert{Y_{S}-X_{S}}\right\rVert_{\text{F}}^{2}=\left\lVert{Y_{A\cap S}-X_{A\cap S}}\right\rVert_{\text{F}}^{2}+\left\lVert{Y_{B\cap S}-X_{B\cap S}}\right\rVert_{\text{F}}^{2}$, we can decompose the training objective (10) as:

Returning to our simulation experiment, the solid curves of Fig. 3 show the excess test error for the minimizer of the training objective (11), as a function of the regularization tradeoff parameter $\lambda$. Note that these are essentially the same curves as displayed in Fig. 2, except the path of regularized solutions is now parameterized by $\lambda$ rather then by the bound on $\textit{tc}(X)$. Not surprisingly we see the same phenomena: different values of $\lambda$ are required for optimal learning on $A$ and on $B$. Forcing the same $\lambda$ on both parts of the training objective (11) yields a deterioration in the generalization performance.

Weighted Trace Norm

The decomposition (11) and the discussion in the previous section suggests weighting the trace-norm by the frequency of rows and columns. For a sampling distribution ${\cal{D}}$, denote by $p(i)$ the row marginal, i.e. the probability of observing row $i$, and similarly denote by $q(j)$ the column marginal. We propose using the weighted version of the trace-norm as a regularizer:

where $\textrm{diag}(\sqrt{p})$ is a diagonal matrix with $\sqrt{p(i)}$ on its diagonal (similarly $\textrm{diag}(\sqrt{q})$). The corresponding normalized complexity measure is given by $\textit{tc}_{p,q}(X)=\left\lVert{X}\right\rVert_{\text{tr}\left(p,q\right)}^{2}$. Note that for a uniform distribution we have that $\textit{tc}_{p,q}(X)=\textit{tc}(X)$. Furthermore, it is easy to verify that for an “orthogonal” rank-$k$ matrix $X$ we have $\textit{tc}_{p,q}(X)=k$ for any sampling distribution.

Returning to the penalization view (2) we can again decompose the training objective:

avoiding the scaling by the block sizes which we encountered in (11).

Returning to the synthetic experiments of Fig. 3, and comparing (11) with (14), we see that introducing the weighting corresponds to a relative change of $n_{A}/n_{B}$ in the correspondence of the regularization tradeoff parameters used for $A$ and for $B$. This corresponds to a shift of $\log\frac{n_{A}}{n_{B}}$ in the log-domain used in the figure. Shifting the solid red (bottom) curve by this amount yields the dashed red (bottom) curve. The solid blue (top) curve and the dashed red (bottom) curve thus represent the excess error on $B$ and on $A$ when the weighted trace norm is used, i.e. the training objective (14) is minimized (except for an overall scaling in $\lambda$). The dashed black (middle) curve is the overall excess error when using this training objective. As can be seen, the weighting aligns the excess errors on $A$ and on $B$ much better, and yields a lower overall error. The weighted trace-norm achieves the lowest MSE of 0.4301 with corresponding $\lambda=0.11$. This is compared to the lowest MSE of 0.4981 with $\lambda=0.80$, achieved by the unweighted trace-norm. It is also interesting to observe that the weighted trace-norm outperforms its unweighted counterpart for a wide range of regularization parameters $\lambda\in[0.01;0.6]$. This may also suggest that in practice, particularly when working with large and imbalanced datasets, it may be easier to search for regularization parameters using weighted trace-norm. Fig. 2, right panel, further shows the test error as a function on the constraint $\textit{tc}_{p,q}(X)$.

Finally, Fig. 3 also suggests that the optimal shift is actually smaller then $n_{A}/n_{B}$. We consider a smaller shift by using the partially-weighted trace-norm:

And he corresponding normalized complexity measure $\textit{tc}_{p,q,\alpha}(X)=\left\lVert{X}\right\rVert_{\text{tr}\left(\frac{p^{\alpha}}{n^{1-\alpha}},\frac{q^{\alpha}}{m^{1-\alpha}}\right)}^{2}$.

Practical Implementation

When dealing with large datasets, such as the Netflix data, the most practical way to fit trace-norm regularized models is through stochastic gradient descent Salakhutdinov & Mnih (2008); Koren (2008).

Let $n_{i}=\sum_{j}S_{ij}$ and $m_{j}=\sum_{i}S_{ij}$ denote the number of observed ratings for user $i$ and movie $j$ respectively. The training objective (over the index pairs $(i,j)$) using partially-weighted trace-norm (Eq. 4) can be written as:

Note that even though the objective (16) as a function of $U$ and $V$ is non-convex, there are no non-global local minima if we set $k$ to be large enough, i.e. $k>\min(n,m)$ Burer & Monteiro (2005). However, fitting orthogonal models in practice with very large values of $k$ becomes computationally expensive. Instead, we consider truncated trace-norm minimization by restricting $k$ to smaller values. In the next section we demonstrate that even when using truncated trace-norm, its weighted version significantly improves model’s prediction performance.

In all of our experiments, we also replace unknown row $p(i)$ and column $q(j)$ marginals in $\eqref{eq:sgd}$ by their empirical estimates $\hat{p}(i)=\nicefrac{{n_{i}}}{{|S|}}$ and $\hat{q}(j)=\nicefrac{{m_{j}}}{{|S|}}$. This results in the following objective:

Setting $\alpha=1$, corresponding to the weighted trace-norm (4), results in stochastic gradient updates that do not involve the row and column counts at all and are in some sense the simplest. Strangely, and likely originating as a “bug” in calculating the stochastic gradients by one of the participants, these are the actual SGD steps used by many practitioners on the Netflix dataset Koren (2008); Takács et al. (2009); Salakhutdinov & Mnih (2008).

Experimental results

We evaluated various models on the Netflix dataset, which is the largest publicly available collaborative filtering dataset. The training set contains 100,480,507 ratings from 480,189 randomly-chosen, anonymous users on 17,770 movie titles. As part of the training data, Netflix also provides qualification set, containing 1,408,395 ratings. The pairs were selected from the most recent ratings for a subset of the users in the training dataset. Due to the special selection scheme, ratings from users with few ratings are overrepresented in the qualification set, relative to the training set. To avoid the issue of dealing with different training and test distributions, we also created our own validation and test sets, each containing 100,000 ratings that were randomly selected from the training set. As a baseline, Netflix provided the test score of its own system trained on the same data, which is 0.9514.

This dataset is interesting for several reasons. First, it is very large, and very sparse (98.8% sparse). Second, the dataset is very imbalanced with highly non-uniform samples. It includes users with over 10,000 ratings as well as users who rated fewer than 5 movies.

In our first experiment, for various values of $\alpha$, we fit parameters $U$ and $V$ using stochastic gradient descent as in (17) with $k=30$. Both $U$ and $V$ were randomly initialized for all models and regularization parameters $\lambda$ were chosen by cross-validation.

Performance results of the weighted trace-norm regularization for various values of $\alpha$ are shown in table 1. Observe that that the weighted trace-norm ($\alpha=1$) achieved a RMSE of 0.9105 on the Netflix qualification set, significantly outperforming its unweighted counterpart with $\alpha=0$, that achieved a RMSE of 0.9235. This large performance gap is striking. It clearly suggests that the weighting is quite important. Table 1 further reveals that the weighted trace-norm ($\alpha=1$) is not optimal. Surprisingly, partially weighted trace-norm with $\alpha=0.9$ achieved a RMSE of 0.9091, slightly outperforming the weighted matrix factorization. Performance results on the artificially created test set are similar to the results on the qualification set. Note also that the large gap in generalization performance between the test and the qualification sets is due to the Netflix’s special qualification selection scheme.

In our second experiment, we fitted much larger models with $k=100$. As expected, the weighted trace-norm regularization ($\alpha=1$) attained a RMSE 0.9071, significantly improving upon the unweighted model’s RMSE of 0.9203. Again, this large performance gap strongly suggests that the weighting can yield significant performance boost, particularly when dealing with very imbalanced data, such as the Netflix dataset.

In all of our experiments, we also empirically observed that for a wide range of regularization parameters $\lambda$, optimizing the weighted trace-norm almost always yielded better predictions on both the test and the Netflix qualification sets than optimizing the unweighted trace-norm. This confirms our previous results on the synthetic experiment and strongly suggests that it may be far easier to search for regularization parameters using the weighted trace-norm.

Discussion

In this paper we showed both analytically and empirically that under non-uniform sampling, trace-norm regularization can lead to significant performance deterioration and an increase in sample complexity. Motivated by our analytic analysis, we further suggested a corrected version of the trace-norm, called weighted trace-norm, that does take into account the non-uniform sampling distribution. Our results on both synthetic and highly imbalanced Netflix datasets further demonstrate that the weighted trace-norm yields significant improvements in prediction quality. It is interesting to note that setting $\alpha=1$ in the weighted trace-norm objective (4) implies that the frequent users (movies) get regularized much stronger than the rare users (movies). From Bayesian perspective, such regularization is quite unusual, since it effectively states that the effect of the prior becomes stronger as we observe more data. Yet, our analysis and empirical results strongly suggest that in non-uniform setting, such “unorthodox” regularization is crucial for achieving good generalization performance.

Although theoretical guarantees are not the focus of this work, we hope that the weighted trace-norm, and the discussions in Sections 3 and 4, will be helpful in deriving theoretical learning guarantees for non-uniform sampling distributions, both in the form of generalization error bounds as in Srebro & Shraibman (2005), and generalizing the compressed-sensing inspired work on recovery of noisy low-rank matrices as in Candes & Plan (2009); Recht (2009).

R.S. acknowledges the financial support from NSERC, Shell, and NTT Communication Sciences Laboratory.

References