Context-Tree Recommendation vs Matrix-Factorization: Algorithm Selection and Live Users Evaluation

Stéphane Martin, Boi Faltings, Vincent SchickelAAAI 2019 · DOI

Introduction

In the competitive landscape of e-commerce, recommender systems are critical revenue drivers. However, transitioning algorithms from theoretical research to production environments requires navigating significant constraints, including memory overhead, prediction latency, and the volatility of user sessions. This paper evaluates the performance of industry-standard Matrix Factorization (MF) against a specialized sequential model, the Bayesian Variable-order Markov Model (BVMM), across both offline datasets and live A/B tests.

Methodology

The study compares three primary approaches, each preceded by an Ontology Filtering (OF) stage to narrow the product catalog to approximately 400 relevant candidates:

  1. Bayesian Variable-order Markov Model (BVMM): A context-tree-based algorithm that treats browsing history as a sequence. It utilizes a tree structure to estimate the probability of subsequent items, employing a "back-off" strategy to shorter suffixes when long-sequence data is unavailable.
  2. SSAGD (Sequential, Session-based, Asymmetric Gradient Descent): A session-oriented variant of Matrix Factorization. It dynamically constructs user preferences by aggregating the latent vectors of recently viewed items, weighted by recency.
  3. Ontology Filtering (Baseline): A content-based method utilizing a directed acyclic graph of product categories to identify catalog neighbors.

Experimental Setup

The evaluation utilized two distinct data sources:

  • Offline Tuning: 100,000 page-views were used to calibrate algorithm parameters.
  • Live A/B Testing: Conducted across two platforms: a high-traffic furniture/electronics retailer (19 million impressions) and a youth fashion webshop (440,000 impressions).

Results and Analysis

Accuracy and Sequentiality

Offline evaluations demonstrated that sequential modeling is paramount. Both BVMM and the sequential MF variant (SSAGD) outperformed traditional MF implementations. By explicitly modeling the order of user interactions rather than treating them as an unordered set, these models better captured intent.

Accuracy over training steps for various algorithms.

Live Performance Metrics

In large-scale live testing, BVMM emerged as the clear leader in user engagement and conversion.

  • Click-Through Rate (CTR): BVMM achieved a CTR of 0.246%, significantly higher than MF (0.171%) and the baseline (0.127%).
  • Sales Impact: BVMM generated a 409% increase in recommendation-mediated sales relative to the baseline, whereas MF provided a 152% increase.
CTR comparison in the first live experiment.

Computational Efficiency

The "memory greed" of Matrix Factorization proved a significant hurdle in production. MF required 7GB of RAM and was prone to crashes during training. In contrast, BVMM operated efficiently on 5GB of RAM. Training efficiency was also stark: BVMM processed 100,000 clicks in under one minute, while the most accurate MF variant (ALSWR) required nearly 10 hours. Furthermore, BVMM delivered recommendations in 1.95 ms, compared to 4.39 ms for SSAGD.

Conclusion

The findings suggest that for fast-paced e-commerce environments, simpler sequential models like BVMM can outperform complex Matrix Factorization variants in both accuracy and operational efficiency. While MF remains a powerful tool, its resource intensity and "cold start" struggles in session-based contexts make context-tree models a compelling alternative for real-time deployment.

Summary updated

BibTeX
@inproceedings{martin2019context,
  author = {Stéphane Martin and Boi Faltings and Vincent Schickel},
  title = {{Context-Tree Recommendation vs Matrix-Factorization: Algorithm Selection and Live Users Evaluation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33019534},
}
Figure