Personalized Advertisement Recommendation: A Ranking Approach to Address the Ubiquitous Click Sparsity Problem

Sougata Chaudhuri, Georgios Theocharous, Mohammad GhavamzadeharXiv 2016 · OpenReview

TL;DR

This paper tackles the challenge of personalized ad recommendations when users rarely click on ads (extreme click sparsity). They propose a novel ranking-based approach that outperforms traditional classifier-based methods by directly optimizing for ranking quality, proving effective even with very sparse data.

What Problem Does This Paper Address?

Personalized Advertisement Recommendation (PAR) systems aim to show the most relevant ad to a user based on their profile (context). These systems are often framed as "contextual bandits," where the system learns by observing user feedback (clicks or no clicks). A major hurdle in PAR is "click sparsity" – users click on ads very infrequently. This makes it incredibly difficult for traditional methods, which rely on classifiers to predict the probability of a click, to learn effective recommendation policies. When clicks are rare, classifiers tend to predict "no click" for almost everyone, failing to identify the few users who would click, thus leading to poor overall performance.

Methods

The authors propose a ranker-based policy as an alternative to classifier-based policies. Instead of trying to predict the exact probability of a click, their approach learns a function that ranks ads based on their likelihood of being clicked. Specifically, they train a separate ranker for each ad by optimizing the Area Under the Curve (AUC) ranking loss. AUC is a metric that measures how well a model can distinguish between positive and negative instances, making it robust to class imbalance.

The core idea is to learn a ranking function $f_w(x) = w \cdot x$ for each ad, where $w$ is a weight vector and $x$ is the user context. This ranker is trained by minimizing a surrogate loss function for AUC, which is computationally tractable. To convert these rankers into a recommendation policy, they introduce a threshold score ($s_a$) for each ad. The final policy then selects the ad with the maximum "normalized score," calculated as $f_{w_a}(x) - s_a$. This normalization helps to account for potential scoring biases inherent in individual rankers.

Datasets

The paper utilizes a combination of datasets:

  • Public Classification Datasets: Several standard multi-class classification datasets from the UCI repository (OptDigits, Isolet, Letter, PenDigits, Movementlibras) were converted into bandit datasets using a standard technique. This allowed for evaluation of deterministic policies.
  • Industry Proprietary Datasets: Three datasets from real-world campaigns (one hotel chain, two banks) were used for evaluating stochastic policies. These datasets are characterized by varying degrees of click sparsity, with the bank campaigns exhibiting extreme sparsity.

Key Insights and Ideas

  • AUC is Robust to Sparsity: The fundamental insight is that optimizing for ranking quality (AUC) is inherently more resilient to click sparsity than optimizing for click probability. AUC focuses on the relative ordering of ads, not the absolute probability, which is precisely what's needed when positive signals (clicks) are rare.
  • Rankers Outperform Classifiers on Sparse Data: The paper provides strong empirical evidence that ranker-based policies significantly outperform classifier-based policies, especially in scenarios with extreme click sparsity. This is a crucial finding for practical PAR systems.
  • Normalization is Key: The introduction of threshold scores ($s_a$) to normalize the output of individual rankers is a clever way to combine them into a coherent policy, preventing one ranker's inherent bias from dominating the decision-making.
  • Offline Evaluation is Crucial: The paper highlights the importance of robust offline evaluation techniques for bandit settings, especially when dealing with proprietary data where direct online A/B testing might be costly or infeasible.

Key Results

  • Improved CTR: The ranker-based policy consistently achieved higher Click-Through Rates (CTR) compared to both linear and ensemble (RandomForest) classifier-based policies.
  • Significant Gains on Sparse Data: On datasets with extreme click sparsity (like the bank campaigns), the ranker-based approach showed substantial improvements, gaining 15-25% in importance-weighted CTR over RF-based approaches.
  • Robustness: The ranker-based policy's performance was less affected by under-sampling techniques compared to classifier-based policies, further demonstrating its robustness to class imbalance.

Limitations and Future Work

  • Computational Cost of AUC: While the paper uses SGD to make AUC optimization tractable, the direct optimization of AUCL can still be computationally intensive due to pairwise comparisons. The authors mention that this issue is overcome by SGD.
  • Feature Selection: The authors note that they performed feature selection on the proprietary datasets, indicating that not all features were equally useful and that careful selection can improve learning. This suggests that feature engineering and selection could be an area for further exploration.
  • Online Learning: The current work focuses on offline batch learning. Future work could explore online versions of the ranker-based approach to adapt to changing user preferences and ad inventories in real-time.
  • Non-linear Rankers: The paper mentions the possibility of learning non-linear kernel ranking functions, which could potentially capture more complex user-ad interactions, though at the cost of memory efficiency.

Summary updated

Abstract

We study the problem of personalized advertisement recommendation (PAR), which consist of a user visiting a system (website) and the system displaying one of $K$ ads to the user. The system uses an internal ad recommendation policy to map the user's profile (context) to one of the ads. The user either clicks or ignores the ad and correspondingly, the system updates its recommendation policy. PAR problem is usually tackled by scalable \emph{contextual bandit} algorithms, where the policies are generally based on classifiers. A practical problem in PAR is extreme click sparsity, due to very few users actually clicking on ads. We systematically study the drawback of using contextual bandit algorithms based on classifier-based policies, in face of extreme click sparsity. We then suggest an alternate policy, based on rankers, learnt by optimizing the Area Under the Curve (AUC) ranking loss, which can significantly alleviate the problem of click sparsity. We conduct extensive experiments on public datasets, as well as three industry proprietary datasets, to illustrate the improvement in click-through-rate (CTR) obtained by using the ranker-based policy over classifier-based policies.
BibTeX
@misc{chaudhuri2016personalized,
  author = {Sougata Chaudhuri and Georgios Theocharous and Mohammad Ghavamzadeh},
  title = {{Personalized Advertisement Recommendation: A Ranking Approach to Address the Ubiquitous Click Sparsity Problem}},
  year = {2016},
  eprint = {1603.01870},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1603.01870},
}
Figure