Collaborative Filtering on a Budget

Alexandros Karatzoglou, Alexander J. Smola, Markus WeimerAISTATS 2010 · OpenReview

Abstract

Matrix factorization is a successful technique for building collaborative filtering systems. While it works well on a large range of problems, it is also known for requiring significant amounts of storage for each user or item to be added to the database. This is a problem whenever the collaborative filtering task is larger than the medium-sized Netflix Prize data. In this paper, we propose a new model for representing and compressing matrix factors via hashing. This allows for essentially unbounded storage (at a graceful storage / performance trade-off) for users and items to be represented in a pre-defined memory footprint. It allows us to scale recommender systems to very large numbers of users or conversely, obtain very good performance even for tiny models (e.g. 400kB of data suffice for a representation of the EachMovie problem). We provide both experimental results and approximation bounds for our compressed representation and we show how this approach can be extended to multipartite problems.

Introduction

Collaborative filtering via matrix factorization is the "gold standard" for recommender systems, powering platforms like Netflix and Amazon. However, a major scalability flaw exists: memory requirements grow linearly with the number of users and items. For a system with 100 million users and 100-dimensional factor vectors, tens of gigabytes of RAM are required just to store the model.

Furthermore, most users and items have very few ratings. Allocating a full, dedicated vector to a user who has only rated one movie is highly inefficient. This paper introduces a method to perform matrix factorization within a fixed, pre-defined memory "budget" using feature hashing. By training directly on a compressed representation, recommender systems can scale to millions of users and items on modest hardware while maintaining high predictive accuracy.

Methodology

The core innovation is the application of feature hashing (the "hashing trick") to matrix factorization.

  1. Hashed Representation: Instead of storing large matrices $U$ and $M$, hash functions map user/item indices and their vector dimensions into a single, much smaller, fixed-size array $w$.
  2. Unbiased Reconstruction: To reconstruct a specific factor value, the authors use a sign-flipping trick (Rademacher functions $\sigma$) to ensure that the expected value of the reconstructed factors is correct, effectively turning hash collisions into zero-mean noise.
  3. Direct Optimization: Crucially, the model is trained directly on the hashed array $w$ using Stochastic Gradient Descent (SGD). This allows the model to learn to compensate for hash collisions during the training process.
  4. Robust Loss Functions: Beyond standard squared error, the paper introduces the use of $\epsilon$-insensitive loss and Huber loss to improve robustness against outliers and noise in user rating data.

Experimental Results

The authors evaluated their approach on two classic benchmarks: EachMovie (~61k users, 2.8M ratings) and MovieLens (~6k users, 1M ratings).

Hashing vs. Dimensionality Reduction

A key insight is that when memory is extremely tight, hashing performs better than simply reducing the dimensionality ($d$) of the factor vectors. A hashed model with higher dimensionality can outperform a standard model with lower dimensionality, even if they use the same total amount of memory. This is demonstrated in Figure 3, where the hashed representation consistently achieves lower RMSE as the number of columns increases compared to simple dimensionality reduction.

Comparison of Hashing and Reduced Dimensionality on MovieLens (a) and EachMovie (b) datasets.

Performance of Robust Loss Functions

The choice of loss function is critical for handling the noise inherent in user ratings. As shown in Figure 6, the $\epsilon$-insensitive loss significantly outperformed standard squared error on the EachMovie dataset, while results were comparable on MovieLens.

RMSE performance across different loss functions for MovieLens and EachMovie datasets.

Key Insights

  • Hashing as a Regularizer: Hashing forces different users/items to share parameters via collisions, pressuring the model to find more general patterns and acting as a form of regularization.
  • Graceful Degradation: The trade-off between memory and performance is smooth. Models can be compressed to a fraction of their original size while losing only a small percentage in accuracy. For example, a model using only 400kB of memory provided high-quality recommendations for the EachMovie dataset.
  • Handling the "Long Tail": This approach is particularly efficient for users/items with very few ratings, as they share the global memory budget rather than consuming dedicated storage.

Conclusion

The proposed hashing method allows for "unbounded" growth of users and items within a fixed storage limit. Once the size of the hash array is set, the memory footprint remains constant. While hash collisions introduce variance, the model's ability to learn through this noise makes it a robust solution for large-scale collaborative filtering on a budget. Future work will explore extending this approach to more complex multipartite relational data.

Summary updated

Abstract

Matrix factorization is a successful technique for building collaborative filtering systems. While it works well on a large range of problems, it is also known for requiring significant amounts of storage for each user or item to be added to the database. This is a problem whenever the collaborative filtering task is larger than the medium-sized Netflix Prize data. In this paper, we propose a new model for representing and compressing matrix factors via hashing. This allows for essentially unbounded storage (at a graceful storage / performance trade-off) for users and items to be represented in a pre-defined memory footprint. It allows us to scale recommender systems to very large numbers of users or conversely, obtain very good performance even for tiny models (e.g. 400kB of data suffice for a representation of the EachMovie problem). We provide both experimental results and approximation bounds for our compressed representation and we show how this approach can be extended to multipartite problems.
BibTeX
@inproceedings{karatzoglou2010collaborative,
  author = {Alexandros Karatzoglou and Alexander J. Smola and Markus Weimer},
  title = {{Collaborative Filtering on a Budget}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2010},
  url = {https://openreview.net/forum?id=8A_5587hXcF},
}
Figure