Online Ranking Prediction in Non-stationary Environments

Erzsébet Frigó, Róbert Pálovics, Domokos Kelen, Levente Kocsis, András A. BenczúrRecTemp@RecSys 2017 · OpenReview

Abstract

In real-world recommendation systems, user preferences and item popularity shift rapidly, creating a "non-stationary" environment. Traditional batch-trained models often fail to capture these dynamics, becoming stale between updates. This paper investigates top-k recommendation in streaming settings and introduces an efficient "sampling from the past" technique for Matrix Factorization (MF). This method allows online models to achieve the performance of periodic batch retraining without the associated computational overhead. Our evaluation across diverse datasets shows that in non-stationary environments, simple, reactive models and incrementally updated latent factor models consistently outperform static batch models.

Introduction

Most recommender system research historically focuses on batch rating prediction using static datasets. However, production environments are inherently online and non-stationary. User interests evolve due to external trends, news, or seasonal changes, and new entities enter the system continuously. Traditional batch models, updated on daily or weekly cycles, cannot react to immediate context or viral events. This study addresses the challenge of top-k ranking in a streaming setting, where models must be evaluated and updated sequentially as each new interaction occurs.

Methods and the "Sampling from the Past" Approach

The authors evaluate several algorithmic classes, including popularity-based baselines, time-sensitive nearest neighbor (t-NN) models, and Matrix Factorization. While standard online Stochastic Gradient Descent (SGD) for MF can incorporate new data quickly, it often "forgets" older patterns or fails to converge in a single pass.

To bridge the gap between online efficiency and batch quality, the authors propose a sampling from the past technique. For every new interaction $(u, i)$ at time $t$, the model performs a gradient step on that interaction plus a small number of random "positive samples" drawn from the user's history. This hybrid approach allows the model to incrementally re-learn past patterns while staying reactive to the present.

The proposed sampling mechanism draws positive samples from the past to augment online learning.

Evaluation is performed using Online DCG@K and Online MRR@K, metrics calculated sequentially: for every event, the model predicts a top-k list based only on prior data before updating itself with the current event.

Key Insights: The Stationarity Gap

A critical finding of this research is the "stationarity gap." In stationary environments (simulated by shuffling the temporal order of datasets), complex Matrix Factorization models are dominant. However, in real-world non-stationary data, simpler models like t-NN or even global popularity often perform better because they are more reactive to recent changes.

The distribution of time intervals across datasets highlights the strong recency bias in user behavior.

As shown in the distribution of time intervals, many interactions occur within very short windows, emphasizing the importance of recency. A simple model that incorporates data from minutes ago is often more effective than a complex model that only knows what happened a week ago. In highly "bursty" datasets like Twitter, global trends move so quickly that popularity-based models become extremely difficult to beat.

Results and Performance

  • Online vs. Batch: In non-stationary environments, online MF consistently outperformed batch MF. On the MovieLens dataset, the online version achieved significantly higher DCG than the batch version.
  • Sampling Efficiency: The proposed sampling method, using just three extra positive samples per interaction, reached the performance levels of computationally expensive "Batch & Online" hybrids while remaining fully incremental.
  • Impact of Temporal Order: When datasets were shuffled to remove temporal signals, the performance of transition-based models plummeted, while batch MF regained its status as the top performer. This confirms that temporal signals are a distinct feature requiring specific algorithmic handling.

Conclusion

This work demonstrates that the temporal dynamics of recommendation data are as important as the underlying collaborative signals. By utilizing incremental updates and intelligent sampling from the past, latent factor models can maintain high performance in fast-moving environments. Future work may explore non-uniform sampling strategies to further optimize how models balance long-term preferences with short-term trends.

Summary updated

BibTeX
@inproceedings{frigo2017online,
  author = {Erzsébet Frigó and Róbert Pálovics and Domokos Kelen and Levente Kocsis and András A. Benczúr},
  title = {{Online Ranking Prediction in Non-stationary Environments}},
  booktitle = {RecTemp@RecSys},
  year = {2017},
  url = {https://openreview.net/forum?id=BuONnzLfUg5},
}
Figure