PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Matrix Factorization for Online Recommendation with Implicit Feedback

Xiangnan He, Hanwang Zhang, Min-Yen Kan, Tat-Seng Chua

arXiv:1708.05024v1cs.IR

TL;DR

Implicit-feedback MF must represent missing data despite scarce negative feedback, while recommendation models also need to adapt to continuously arriving interactions. This paper uses item-popularity weighting with efficient element-wise ALS and incremental updates, and reports consistent gains over state-of-the-art implicit MF methods in offline and online evaluations.

  • Problem

    Implicit feedback lacks negative signals, while uniform weighting of missing data and offline-oriented methods inadequately address realistic weighting and continuously arriving interactions.

  • Method

    The paper weights missing data by item popularity, optimizes the resulting MF model with eALS, and incrementally updates parameters when new interactions arrive.

  • Results

    eALS consistently outperforms state-of-the-art implicit MF methods in experiments using offline and online protocols.

  • Takeaways & Limitations

    eALS makes implicit-feedback MF more practical by combining flexible missing-data weighting with efficient, parallelizable optimization and online updating.

  • Takeaways & Limitations

    The paper leaves optimal weighting for online data and extensions incorporating side information as future work.

Abstract

from arXiv · show

This paper contributes improvements on both the effectiveness and efficiency of Matrix Factorization (MF) methods for implicit feedback. We highlight two critical issues of existing works. First, due to the large space of unobserved feedback, most existing works resort to assign a uniform weight to the missing data to reduce computational complexity. However, such a uniform assumption is invalid in real-world settings. Second, most methods are also designed in an offline setting and fail to keep up with the dynamic nature of online data. We address the above two issues in learning MF models from implicit feedback. We first propose to weight the missing data based on item popularity, which is more effective and flexible than the uniform-weight assumption. However, such a non-uniform weighting poses efficiency challenge in learning the model. To address this, we specifically design a new learning algorithm based on the element-wise Alternating Least Squares (eALS) technique, for efficiently optimizing a MF model with variably-weighted missing data. We exploit this efficiency to then seamlessly devise an incremental update strategy that instantly refreshes a MF model given new feedback. Through comprehensive experiments on two public datasets in both offline and online protocols, we show that our eALS method consistently outperforms state-of-the-art implicit MF methods. Our implementation is available at https://github.com/hexiangnan/sigir16-eals.

1. INTRODUCTION

Implicit-feedback recommendation must handle scarce negative signals and continuously arriving interactions. The paper addresses these challenges with popularity-aware missing-data weights, efficient eALS optimization, and incremental updates for online learning.

  • Motivation: Implicit feedback is easier to collect than ratings but lacks negative signals, making observed interactions biased representations of user preferences.Users may consume items they expect to like while avoiding disliked genres, leaving negative preferences underrepresented.
  • Motivation: Modeling all missing entries as negative feedback improves coverage but reduces efficiency, complicating real-time deployment as users, items, and interactions stream in.Existing dynamic MF also uses uniform missing-data weights, which the paper identifies as unrealistic and limiting.
  • Contributions: The paper assigns missing-data weights according to item popularity instead of imposing a uniform weight across missing entries.This weighting scheme is intended to tailor the MF model more effectively to implicit feedback.
  • Contributions: The eALS algorithm efficiently learns the resulting model, and an incremental update strategy refreshes parameters when new feedback arrives.The method is designed to satisfy online-learning requirements while optimizing non-uniformly weighted implicit MF.
  • Evaluation: Experiments on two real-world datasets under offline and online protocols show that eALS consistently outperforms state-of-the-art implicit MF methods.The contribution list reports evaluation under both protocols rather than a single offline setting.

2. RELATED WORK

Prior implicit-feedback MF methods trade off coverage, predictive quality, flexibility, and efficiency, while online methods address dynamic data with several non-ALS learners. The paper positions eALS as an efficient ALS-based alternative supporting non-uniform weighting and online updates.

  • Implicit-feedback learning: Sample-based methods improve efficiency by sampling missing negative instances, whereas whole-data methods cover all missing entries but may be inefficient.The related-work discussion presents both strategies as having distinct advantages and disadvantages.
  • Implicit-feedback learning: Uniform weighting of missing entries favors efficiency but limits flexibility and extensibility; non-uniform alternatives have cubic complexity in the number of factors.The latter complexity is described as unsuitable for large-scale data requiring many latent factors.
  • MF optimization: SGD is unsuitable for whole-data MF because it processes the full interaction matrix, while ALS is widely used but remains inefficient.Approximate ALS and randomized coordinate-descent approaches were developed to reduce these costs.
  • Paper positioning: The paper proposes an efficient element-wise ALS solution for whole-data MF with non-uniform missing-data weights, a combination not previously studied.It also aims to exploit ALS for online learning.
  • Online learning: Dynamic recommender systems require timely updates, motivating incremental strategies for neighbor-based, graph-based, probabilistic, and MF methods.MF online learners include SGD, randomized coordinate descent, and dual averaging.

3. PRELIMINARIES

The paper formulates implicit-feedback MF as weighted regression with regularization and reviews ALS optimization. It then motivates element-wise updates as a way to avoid matrix inversion and reduce computational complexity.

  • MF formulation: MF maps users and items into a shared K-dimensional latent space, where interactions are modeled through inner products and item scores rank recommendations.User and item latent vectors provide the basic scoring representation.
  • MF formulation: The weighted regression model assigns confidence weights to predictions, including non-zero weights for missing entries that are treated as zero feedback.Regularization controls model complexity, typically through an L2 norm.
  • ALS optimization: ALS alternates optimization of one parameter while fixing the others, using analytically solvable subproblems such as ridge regression.The standard user-vector update requires matrix inversion.
  • ALS efficiency: Standard ALS requires O((M + N)K3 + MNK2) time per iteration, making it impractical for large datasets with millions of users and items.The cost arises from O(K3) matrix inversion for each latent-vector update.
  • ALS efficiency: Uniform missing-entry weights enable memoization and reduce ALS complexity to O((M + N)K3 + |R|K2), but the assumption can degrade model quality in real applications.The remaining cubic term and quadratic interaction term can still be costly at large K.
  • Element-wise ALS: Element-wise updates avoid matrix inversion; with precomputed predictions, eALS reaches O(MNK) time per iteration.The raw element-wise implementation takes O(MNK2) before prediction precomputation reduces the complexity.

4. OUR IMPLICIT MF METHOD

The method combines popularity-aware weighting of missing implicit feedback with an efficient element-wise ALS algorithm and localized incremental updates for online learning.

  • Item-Oriented Weighting on Missing Data: Popularity-aware weights distinguish likely negative missing feedback from unknown feedback using item popularity instead of a uniform assumption.The item-specific confidence can also encode practitioner domain knowledge; α controls how strongly popularity changes weights, with α = 0.5 usually effective.
  • Fast eALS Learning Algorithm: The eALS learner accelerates variably weighted missing-data optimization by reformulating repeated computations and caching terms independent of the updated user.An individual user-factor update takes O(K + |Ru|) time after memoization.
  • Fast eALS Learning Algorithm: One eALS iteration takes O((M + N)K^2 + |R|K) time, while element-wise ALS is K times faster than vector-wise ALS.The method has the same time complexity as RCD and is faster than ii-SVD, while avoiding RCD’s learning-rate line search through exact parameter optimization.
  • Fast eALS Learning Algorithm: The cached objective can be calculated in O(|R| + MK^2) time, and eALS iterations can be parallelized across disjoint user or item updates.The parallel updates retain an exact solution because shared cached quantities remain unchanged or are independent across workers.
  • Online Learning: Incremental updating optimizes only the latent factors for a new interaction, assuming the global model changes little while local user and item features adapt.A new interaction update costs O(K^2 + (|Ru| + |Ri|)K), independent of total users, items, and interactions.

5. EXPERIMENTS

The experiments use extensive evaluation under both traditional offline and more realistic online protocols.

  • Experimental Protocols: The evaluation begins with experimental settings, then compares the method under offline and online protocols.The online protocol is described as more realistic than the traditional offline protocol.

5.1 Experimental Settings

The experiments use filtered Yelp and Amazon Movies implicit-feedback datasets, evaluating recommendation accuracy under offline and online protocols against whole-data and sample-based MF baselines.

  • Datasets: The evaluation uses two publicly accessible datasets, Yelp and Amazon Movies, transformed into binary implicit-feedback data.Entries indicate whether a user reviewed an item; users and items with fewer than 10 interactions are filtered out.
  • Evaluation protocols: Offline evaluation holds out each user’s latest interaction and trains models on the remaining interactions.The authors note that this leave-one-out split is artificial and does not match the real recommendation scenario.
  • Evaluation protocols: Online evaluation sorts interactions chronologically, trains on the first 90%, and evaluates recommendations on the final 10% while updating with test interactions.This protocol simulates a dynamic data stream rather than a static train-test split.
  • Evaluation protocols: Hit Ratio and NDCG@100 measure whether the ground-truth item appears and how highly it is ranked.Scores are averaged over all test interactions.
  • Baselines: ALS, RCD, and BPR provide comparisons spanning conventional whole-data, online-suitable whole-data, and sample-based ranking methods.ALS is evaluated only offline because its time complexity makes real-time dynamic updating infeasible.

5.2 Offline Protocol

Offline experiments examine missing-data weighting, convergence, accuracy across factor counts, efficiency, and comparison with BPR. eALS benefits from popularity-aware weighting and achieves strong accuracy with substantially lower training cost than ALS.

  • 5.2.1 Weight of Missing Data: eALS performance peaks at c0 around 512 on Yelp and 64 on Amazon under uniform missing-data weighting.These values correspond to zero-entry weights of 0.02 on Yelp and 0.0001 on Amazon; both too-small and too-large weights degrade performance.
  • 5.2.1 Weight of Missing Data: Performance improves as α increases and reaches its best result around 0.4, with statistically significant gains on both metrics and datasets.Performance drops significantly when α exceeds 0.5, indicating that over-weighting popular items is harmful.
  • 5.2.2 Compare Whole-data based MF Methods: eALS achieves the best converged prediction performance, with all improvements statistically significant at p < 0.01, and converges faster than RCD.The authors attribute the accuracy advantage mainly to popularity-aware weighting and the convergence advantage to coordinate-wise objective minimization.
  • 5.2.2 Compare Whole-data based MF Methods: eALS consistently outperforms ALS and RCD across factor counts K, while all methods improve significantly as K increases.The authors note that larger K can increase representation ability, although it may risk overfitting.
  • 5.2.2 Compare Whole-data based MF Methods: When K is 512, ALS requires 11.6 hours per Amazon iteration, whereas eALS takes 12 minutes.Analytically, eALS and RCD are K times faster than ALS, although implementation details prevent eALS from realizing the full theoretical speed-up empirically.
  • 5.2.3 eALS vs. BPR (sample-based): BPR’s convergence depends on learning rate: higher rates converge faster, but final accuracy may suffer.On Yelp, eALS significantly outperforms BPR on both measures; on Amazon, eALS has higher hit ratio but lower NDCG.

5.3 Online Protocol

The online evaluation examines update iterations, new-interaction weighting, and performance under a simulated data stream. eALS benefits from rapid incremental updating, balances short- and long-term interests through wnew, and consistently outperforms the compared dynamic MF methods.

  • Evaluation setup: The online protocol holds out the latest 10% of interactions for testing and compares eALS with RCD and BPR after offline parameter selection.The evaluation studies online iterations, new-interaction weighting, and dynamic-method comparisons.
  • Number of Online Iterations: Most performance gain for eALS comes from the first online iteration, while additional iterations do not further improve its performance.One eALS step can find the optimal solution for a latent factor when other factors remain fixed, making one iteration sufficient for incremental learning.
  • Number of Online Iterations: BPR usually needs 5-10 iterations to reach peak performance, whereas more iterations can hurt through local over-training.RCD follows the same first-iteration trend as eALS.
  • Weight of New Interactions: Increasing wnew modestly improves both eALS and RCD, with peak performance around 4; larger values hurt by underusing historical data.The NDCG results indicate that recommendation quality depends on balancing users’ short-term and long-term interests.
  • Performance Comparison: eALS consistently outperforms RCD and BPR on both measures in the simulated stream, with all improvements statistically significant at p < 0.001.BPR outperforms RCD on Yelp but underperforms it on Amazon; dynamic-learning performance initially decreases, then increases and stabilizes.
  • Performance Comparison: Cold-start users perform no better than random, but performance improves significantly after the first interaction and rises further with additional feedback.The breakdown highlights the value of instantaneous feedback for cold-start and sparse users.

6. CONCLUSION AND FUTURE WORK

The conclusion presents eALS as an efficient MF approach for implicit data that replaces uniform missing-data weighting with popularity-aware weighting and supports real-time adaptation. Future work targets online weighting, side information, and binary coding, while the method’s parallelism supports large-scale deployment.

  • Conclusion: The paper studies MF for implicit feedback and replaces uniform missing-data weights with item-popularity-based weighting.The weighting paradigm can incorporate prior domain knowledge.
  • Conclusion: eALS uses coordinate descent with memoization to learn efficiently under non-uniform missing-data weights and provides incremental real-time updates.The method is described as embarrassingly parallel and attractive for large-scale industrial deployment.
  • Conclusion: The experiments use offline and online protocols and demonstrate promising results for the proposed approach.
  • Future Work: Future work includes optimizing online-data weighting and extending eALS with social contexts, reviews, collective factorization, and factorization machines.The authors also plan to study binary coding for MF on implicit data.
  • Future Work: The paper connects MF’s handling of sparse matrices to potential applications in natural language processing, where missing entries may be ignored or equally weighted.This connection motivates considering eALS beyond recommendation.
Loading 1708.05024v1…