Neural Network Matrix Factorization

Introduction

We are interested in modeling arrays of data, which arise in the analysis of networks, graphs, and, more generally, relational data. For example, in collaborative filtering and recommender system applications (Goldberg et al., 1992; Koren et al., 2009), we may have $N$ users and $M$ movies, and for some collection $J\subseteq[N]\times[M]$ of user–movie pairs $(n,m)$, we have recorded the rating $X_{n,m}$ that user $n$ gave movie $m$. The inferential goal we focus on in this work is to predict the ratings for those pairs not in $J$. The data can be modeled as a partial observation of an $N\times M$ array $\bm{X}=(X_{n,m})$. While the methods we discuss are applicable far beyond the setting of movie rating data or even two-dimensional arrays, we will rely on the user–movie metaphor throughout.

Probabilistic matrix factorization (Salakhutdinov and Mnih, 2008), or simply PMF, is based on matrix factorization, and further assumes the entries of $\bm{X}$ are independent Gaussians with common variance and means given by the corresponding entries of $\bm{U}^{T}\bm{V}$. Maximum likelihood inference of the features $\bm{U}$ and $\bm{V}$ leads one to minimize the Frobenius norm of $\bm{X}-\bm{U}^{t}\bm{V}$, or equivalently, the root mean squared error (RMSE) between the inner product of the features and the observed relations. In practice, regularization of the features vectors often improves the performance of the resulting predictions, provided the regularization parameter is chosen carefully, e.g., by cross validation.

PMF is extremely effective in practice, but is also easy to improve upon when dealing with large but sparsely observed array data, as is typical in collaborative filtering. One way to improve upon PMF is to introduce row and column effects that model systematic biases associated with users and with movies, leading to a model known in collaborative filtering community as BiasedMF (Koren et al., 2009). In this approach, the mean of $X_{n,m}$ is taken to be $U_{n}^{T}V_{m}+\mu_{n}+\tau_{m}+\beta$, where $\mu=(\mu_{1},\dotsc,\mu_{S})$, $\tau=(\tau_{1},\dotsc,\tau_{M})$, and $\beta$ are additional latent variables representing the user, movie, and global biases, respectively. Note that the row and column effects in BiasedMF can be seen as a special case of PMF where we fix an entry of $\bm{U}$ and a distinct entry of $\bm{V}$ to take the value 1. In other words, BiasedMF implements a strong inductive bias. Again, regularization improves prediction performance in practice.

Model

Let $f_{\theta}$ be a feed-forward neural network with weights $\theta$. Viewing $\theta$ and the latent features $(U,V)$ as unknown parameters, we assume the entries $X_{n,m}$ are independent random variables with means

In other words, the neural network $f_{\theta}$ has $2D+{D^{\prime}}$ real-valued input units and one real-valued output unit. The first $D$ are user-specific features; the next $D$ are movie-specific features; and the last ${D^{\prime}}$ inputs are the result of inner products between $K$-dimensional vectors.In our experiments, we took $K=1$ and ${D^{\prime}}$ large. Taking ${D^{\prime}}=1$ results in a model where the input to the neural network is the prediction of a rank-$K$ matrix factorization and $2D$ additional features. This simple modification of matrix factorization lead to improvements, but not as dramatic as those we report in Section 5.

Learning

To learn the network weights $\theta$ and latent features $(U,V)$, we minimize the objective

During training, we alternated between optimizing the neural network weights, while fixing the latent features, and optimizing the latent features, while fixing the network weights. Optimization was carried out by gradient descent on the entire dataset (i.e., we did not use batches). We used RMSProp to adjust the learning rate. (See Section 5 for details.) We did not evaluate other optimization algorithms.

Related Work

NNMF is related to some methods applied to Knowledge Bases and Knowledge Graphs. (See (Nickel et al., 2015) for a review of relational machine learning and Knowledge Graphs.) Knowledge bases (KBs) are relational data composed of entity–relation–entity triples. For example, a geopolitical knowledge base might contain facts such as (Rome, capitol-of, Italy) and (Lithuania, member-of, EU). Knowledge graphs (KGs) are representations of KBs as graphs whose vertices represent entities and whose (labelled) edges represent relations between entities. Given this connection, one can see that KBs can be thought of as a collection of (extremely sparsely observed) arrays, one for each relation, or as a single three-dimensional array. The key challenge in modeling KBs and KGs is to simultaneously learn many relations using shared representations in order to augment the limited data one has on each relation. This is one of the key differences with the collaborative filtering setting.

A method for KGs similar to NNMF is the Neural Tensor Network (NTN), which combines a tensor product with a single-layer neural network (Socher et al., 2013). (Methods similar to NTN have been applied to problems in speech recognition. See, e.g., (Yu et al., 2013).) Other approaches to KGs use neural networks to produce representations, rather than map representations to predictions, like NTN and NNMF. (See, e.g., (Huang et al., 2015) and (Bian et al., 2014).)

NTNs model each element of a two-dimensional array by

Ignoring the particularly nonlinearity used, the first layer of the NNMF model can be expressed in the form Eq. 3 if we take $W=0$ and allow ourselves to fix some entries of the latent features. (NTN employs no additional layers.) For example, taking $K=1$ as in our experiments, define for $n\in[N]$, $m\in[M]$, $i,j\in[2D+{D^{\prime}}]$, and $h\in[H]$,

There have been many scalable techniques proposed to model very large KGs. Nickel et al. (2015) split existing models into two categories: latent feature models and graph feature models. Latent variable methods learn unobserved representations of entities and use them to predict relations, while graph feature methods learn to predict relations directly from extracted features of local graph structure. Toutanova and Chen (2015) argue through empirical comparisons that these two categories of models exhibit complimentary strengths.

A number of state-of-the-art proposals for collaborative filtering are perhaps best thought of as incorporating aspects of graph feature models. An example of a method relaxing the low-rank assumption using graph features is the Local Low Rank Matrix Approximation (Lee et al., 2013), which assumes that every entry in the matrix is given by a combination of low rank matrices, where the combination is specific to the entry. LLORMA achieves impressive state-of-the-art performance.

Other approaches also use neural-network architectures but work by trying to predict the ground truth ratings directly from the observed ratings matrix $X$. For example, in I-AutoRec (Sedhain et al., 2015), an autoencoder is learned that takes as input the observed movie ratings vector $X_{n}$ for user $n$ and produces as output the ground truth $X^{\textrm{truth}}_{n}$. (Missing entries are typically replaced by value 3.) AutoRec achieves state-of-the-art performance, slightly besting LLORMA on some benchmarks, but a careful comparison would likely require a fresh data set and strict controls on how the numerous parameters for both models are chosen (Blum and Hardt, 2015; Dwork et al., 2015). Another model in this category is the I-RBM (Salakhutdinov et al., 2007), but its performance is now far from the state of the art.

Both LLORMA and I-AutoRec can be seen as models combining aspects of both graph feature and latent feature models. LLORMA identifies similar rows and columns (entities) using graph features, but model each local low-rank approximation using latent features. I-AutoRec takes as input all observed ratings (relations) for a user (entity), allowing the network to model the graph features, which in this case are similarities and distances among movies.

In Section 5, we compare the performance of NNMF and other approaches on benchmarks including link prediction in graphs, as well as collaborative filtering in movie rating datasets. In our experiments, NNMF dominated other latent feature methods, as well as the I-RBM model. However, NNMF was dominated by both LLORMA and I-AutoRec. One possibility is that a different approach to learning the underlying neural network would deliver results on par with these methods. Another possibility is that the difference reflects some fundamental limitation of latent feature models, which assume that the ratings are conditionally independent given the latent feature representations. Local graph structure may contain information that would aid in predicting ratings. In particular, NNMF does not learn from the pattern of missing ratings,which can reveal information about a user or movie: e.g., a user might tend only to give ratings when those ratings are extreme, and movies with low ratings are less likely to be viewed in the first place. In contrast to NNMF, both LLORMA and AutoRec could, in principle, be taking advantage of the information latent in the pattern of missing ratings, although the strength of this effect has not been studied. In LLORMA, the sparsity pattern affects the notion of locality. In AutoRec, the entire pattern of ratings is fed as input, although the sparsity is obscured somewhat by missing entries being replaced by 3’s.

Some recent work by Hernández-Lobato et al. (2014) demonstrates that explicitly modeling the non-random pattern of missing ratings can lead to a slight improvement in performance for latent feature models, although the gains they demonstrated were not dramatic enough that they would have closed the gap between NNMF and LLORMA/AutoRec. Indeed, we implemented a neural architecture similar in spirit to theirs, but were only able to improve the RMSE score by approximately $0.003$. A more careful analysis would be necessary to make more definitive conclusions.

Experiments

We evaluated NNMF on two graph datasets (NIPS and Protein) and two collaborative filtering datasets (MovieLens 100K and 1M). See Table 1 for more information about the datasets.

NNMF, NTN, PMF model performance was evaluated on 5 randomly subsampled test sets, each comprising $10\%$ of the data points, and then averaged. The remaining $90\%$ of the data was split into training and validation sets: For the graph datasets, we used a $10\%$ of the training data for validation. Due to the larger size of collaborative filtering datasets, we used $2\%$ and $0.5\%$ of the training data for validation on the MovieLens 100K and 1M datasets, respectively. These numbers were chosen to make the Monte Carlo error of the validation set estimate sufficiently small. (It is likely that results could be improved by better use of the training and validation data.)

The regularization parameter, $\lambda$, and optimal stopping time were chosen by optimizing the error on the validation set. For every fixed setting of $\lambda$, the network and features were learned by optimizing Eq. 2 as described in Section 3.

For simplicity, and to avoid the pitfalls of choosing parameters that produce good test set performance, the number and dimensionality of the features, as well as the network architecture, were fixed across experiments. It is conceivable that cross validating these parameters would have yielded better results. On the other hand, it would be wise to employ safeguards (Dwork et al., 2015) before embarking on an adaptive search for better architectures, learning rates, activation functions, etc.

To train the PMF model, we chose 60 dimensions after evaluating the performance of PMF with various choices for the dimensionality and finding that this worked best. On each run, the regularization parameter was chosen from a large range by optimizing the validation error. (We tried many other settings for PMF, and have reported the best numbers we obtained here to make the comparison conservative.)

The results appear in Table 2. As mentioned above, NNMF dominates PMF, RFM, and to a lesser extent NTN. In (Lloyd et al., 2012), the performance of RFM is compared with PMF when both models use the same number of latent dimensions. The performance of PMF, however, tends to improve with the higher dimension, assuming proper regularization, and so RFM (3) is seen here to perform worse than PMF (60). It is possible that recent advances in Gaussian process regression could in turn improve the performance of RFM.

NNMF outperforms BaisedMF, although the margin narrows as we move to the sparsely-observed MovieLens datasets. We note that adding bias correction terms to NNMF also improves the performance of NNMF, although the improvement is on the order of $0.003$, and so may not be robust. It is also possible that using more of the training data might widen the gap.

NNMF beats the (low-rank) global version of LLORMA, but not the local version that relaxes the low-rank constraint. NNMF is also bested by AutoRec. It is also not clear if we could have reliably found much better network weights and features had we made different choices around the architecture, composition, and training of the neural network. Given that NNMF dominates PMF so handily on the graph datasets, it might stand to reason that there is a lot of room for improvement on MovieLens through better engineering of NNMF. It is worth noting that a ‘local’ versions of NNMF could be developed along the same lines as were for LLORMA. Given that NNMF dominates PMF, it might then also stand to reason that a local version of NNMF would dominate LLORMA, because LLORMA can be understood as a local version of PMF.

To see whether deeper networks performed better on the collaborative filtering datasets, we also evaluated NNMF on the MovieLens data sets using a 4 hidden layer network. We observed that fewer units per layer yielded better results. (We compared 50 units per layer when $(D,{D^{\prime}})=(10,60)$ to 20 units per layer when $(D,{D^{\prime}})=(10,80)$.) However, to draw any conclusions, more experiments would be needed, with care to avoid overfitting. We reported scores for 4 hidden layer networks, with 20 units per hidden layer, and $(D,{D^{\prime}})=(10,80)$ latent feature dimensions. We believe that adding additional layers would likely improve the results, though we suspect the performance would saturate quickly (and then drop if we did not very carefully initialize and regularize the network).

Discussion

NNMF achieves state-of-the-art results among latent feature models, but is dominated by approaches that take into account local graph structure. However, it is possible that our experiments have not identified the limits of the NNMF model. It is difficult to exhaustively explore the range of network architectures, activation functions, regularization techniques, and cross-validation strategies. Even if we could explore them all, we would be in danger of overfitting and losing any hope of insight into the usefulness of NNMF. Indeed, we erred towards not trying to optimize over the model’s many possible configuration. It would be interesting to apply recent advances in adaptive estimation to control the possibility of overfitting during this phase of designing and evaluating a new model (Dwork et al., 2015).

Acknowledgments

The authors would like to thank Zoubin Ghahramani for feedback and helpful discussions.

References