Sequential Click Prediction for Sponsored Search with Recurrent Neural Networks

Yuyu Zhang; Hanjun Dai; Chang Xu; Jun Feng; Taifeng Wang; Jiang Bian; Bin Wang; Tie-Yan Liu

Source-linked AI summary

Sequential Click Prediction for Sponsored Search with Recurrent Neural Networks

Yuyu Zhang, Hanjun Dai, Chang Xu, Jun Feng, Taifeng Wang, Jiang Bian, Bin Wang, Tie-Yan Liu

arXiv:1404.5772v3Apr 23, 2014cs.IRcs.LGcs.NE

TL;DR

Sponsored-search click prediction often ignores temporal dependencies in users’ ad-browsing behavior. This paper uses recurrent neural networks to model those dependencies and reports 17.3% relative RIG improvement over logistic regression and 10% over neural networks.

Problem
Sponsored-search click prediction often treats each ad impression independently despite temporal dependencies in users’ prior ad behaviors.
Method
The framework uses recurrent neural networks to incorporate users’ sequential ad-browsing behavior into click-probability prediction.
Results
17.3% relative RIG improvement over LR and about 10% over NN demonstrate significantly more accurate click prediction.
Takeaways & Limitations
Modeling sequential dependency improves sponsored-search click prediction accuracy across the evaluated settings.
Takeaways & Limitations
The comparison uses the same impression-level feature setting for all click-prediction models.

Abstract

from arXiv · show

Click prediction is one of the fundamental problems in sponsored search. Most of existing studies took advantage of machine learning approaches to predict ad click for each event of ad view independently. However, as observed in the real-world sponsored search system, user's behaviors on ads yield high dependency on how the user behaved along with the past time, especially in terms of what queries she submitted, what ads she clicked or ignored, and how long she spent on the landing pages of clicked ads, etc. Inspired by these observations, we introduce a novel framework based on Recurrent Neural Networks (RNN). Compared to traditional methods, this framework directly models the dependency on user's sequential behaviors into the click prediction process through the recurrent structure in RNN. Large scale evaluations on the click-through logs from a commercial search engine demonstrate that our approach can significantly improve the click prediction accuracy, compared to sequence-independent approaches.

Introduction

Sponsored search click prediction often treats each ad impression independently, overlooking complex dependencies among a user’s sequential behaviors. This paper analyzes those dependencies and uses recurrent neural networks to incorporate them into click prediction, validating the approach through large-scale experiments.

Motivation: Sponsored search generates over 20 billion dollars annually in the US market, with revenue still rising.It is a major business model for commercial Web search engines and accounts for most income at Google, Yahoo, and Bing.
Related work: Most prior click-prediction methods use machine learning to estimate click probability from historical CTR and other extracted features.Examples include query, ad, user, and combined CTR features.
Problem: Previous studies typically treat a single ad impression as the input, without modeling dependencies between different impressions.Some recent work models spatial relationships between ad slots within the same query session.
Method: The proposed RNN models each user’s ad browsing history as a sequence and embeds impression dependencies through recurrent hidden states.Each impression’s features are combined with the previously accumulated hidden state during training.
Data analysis: The paper investigates sequential dependencies among users’ ad impressions and identifies several important dependency relationships.Search logs record ad impressions, clicks, queries, ad text, dwell time, and timestamps, motivating sequential analysis.
Experiments: Large-scale experiments validate the RNN model’s effectiveness for modeling sequential data in sponsored search.The experiments assess whether incorporating sequential dependency enhances click-prediction accuracy.

Data Analysis on Sequential Dependency

The analysis examines sequential dependency in sponsored-search click behavior using logs from a commercial search system. It finds that prior dwell-time and query-topic behavior affects subsequent click-through behavior, motivating models that learn these dependencies automatically.

Data Analysis on Sequential Dependency: The study analyzes sequential effects in sponsored-search behavior using logs from a commercial sponsored search system.User ad impressions and queries are treated as time-ordered sequences.
Dwell-Time Dependency: A “quick back” click, defined as dwell time under 20 seconds, leads to a lower click-through rate on the next impression.The pattern suggests users tend to avoid clicking an ad after an unsatisfying experience.
Dwell-Time Dependency: The effect of a “quick back” click is examined in relation to whether it occurred long ago, such as half a month earlier.The analysis explicitly asks whether a distant prior quick-back experience still affects subsequent behavior.
Query Dependency: Users become more likely to click ads under a query topic after previously submitting a query belonging to that topic.Queries are categorized into topics using a proprietary query taxonomy, and click-through rates are compared across first and future submissions.
Implications: The findings show that previous sponsored-search behaviors have strong but dynamic effects on subsequent behavior, so models should learn these dependencies automatically.The paper proposes designing features around identifiable dependencies while avoiding manual enumeration of all such relationships.

The Proposed Framework

The proposed framework uses an RNN to predict ad clicks from current impression features together with a recurrent representation of the user’s sequential history. It trains on temporally ordered user behaviors with BPTT and performs inference by carrying forward the previous hidden state.

RNN architecture: The RNN combines current behavior features i(t) with recurrent hidden state h(t−1) to produce a sequential representation for click prediction.The recurrent connections propagate sequential signals, while the hidden layer stores dynamic historical context.
Input features: Ad impressions are the training and testing instances, with features covering ad attributes, user information, and other impression-centric signals.All models use the same large, complex feature space to enable fair comparison of click-prediction capability.
Sequential data organization: User histories are reordered chronologically, with ads within each search session ranked by their natural display order across mainline and sidebar placements.This organization supplies the ordered sequences required to model temporal dependencies.
Training: BPTT unfolds the RNN across T shared recurrent layers so errors propagate through longer contexts while emphasizing recent inputs.The model is optimized with stochastic gradient descent and uses averaged cross entropy for click-probability prediction.
Inference: During testing, the model feeds current features together with the previous sample’s hidden state, predicts the click probability, and stores the resulting hidden state for the next sample.Only the hidden state from the last test sample is retained, regardless of the number of BPTT unfolding steps.

Experiments

The Experiments section describes the experimental settings and then reports the experimental results.

The section first describes the experimental settings, followed by the experimental results.

Data Setting

The experiments use fully anonymized click-through logs from a commercial search engine, comprising over 7 million ad impressions collected during November 9–22, 2013. Models are trained on the first week’s data and tested on the second week’s data.

The experimental dataset consists of click-through logs from a commercial search engine.
Over 7 million ad impressions were collected from randomly sampled, fully anonymized search engine users between November 9 and November 22, 2013.
Click prediction models were trained on the first week’s data and tested on the second week’s data.

Evaluation Metrics

The evaluation uses logged user actions as true labels and measures model performance with Area Under ROC Curve (AUC) and Relative Information Gain (RIG).

Evaluation Metrics: Logged user actions, namely clicks or non-clicks, serve as the true labels for evaluating ad-impression click-probability models.The models predict click probability on impressions in the testing dataset.
Evaluation Metrics: Overall model performance is evaluated using Area Under ROC Curve (AUC) and Relative Information Gain (RIG).These metrics follow common practice in prior sponsored-search click-prediction research.

Compared Methods

The study compares its RNN click prediction model with Logistic Regression and Neural Networks using an identical feature set, treating LR and NN as baseline models because prior studies established them as state-of-the-art.

Compared Methods: The RNN model is compared with Logistic Regression (LR) and Neural Networks (NN) using an identical feature set.These models serve as classical click prediction comparators.
Compared Methods: LR and NN are designated baseline models because prior studies demonstrated that they were state-of-the-art click prediction models.The cited prior studies include Richardson, Dominowska, and Ragno (2007), McMahan et al. (2013), and Wang et al. (2013).

Experimental Results

Experiments show that the proposed RNN improves click-prediction accuracy over sequence-independent LR and NN baselines, with gains across ad positions and longer histories. Ablations further show that sequential inference and three unfolding steps are important for performance.

Overall performance: 17.3% relative RIG improvement over LR and 10% over NN demonstrate that RNN outperforms both baselines overall.RNN also achieves a 1.7% relative AUC gain over LR and a 0.5% relative AUC gain over NN.
Position analysis: RNN outperforms NN and LR by AUC at every evaluated ad position, with a 3.12% RIG gain over NN on mainline positions.The evaluated positions are top first, mainline, and sidebar; most revenue comes from mainline ad clicks according to the authors’ daily traffic statistics.
Sequential inference: Removing the recurrent component during testing reduces performance to AUC 88.25% and RIG 18.95%, confirming the importance of sequential inference.The modified model feeds testing samples forward as a normal NN after training, ignoring sequential dependencies.
History length: RNN performs best across all history-length settings, and its relative gains over baselines increase as the accumulation period becomes longer.The experiment feeds an initial history of length T before evaluating the remaining sequence samples.
Unfolding steps: Three unfolding steps yield the best AUC and RIG; performance declines afterward because the backpropagated error vanishes after three steps.Increasing unfolding steps initially causes prediction accuracy to surge.
Sequential modeling: The framework captures short-span dependencies through explicit unfolding and long-span dependencies through the recurrent component’s accumulated weights.These mechanisms correspond to recent events and longer-run user history in sponsored search behavior.

Conclusion and Future Work

The paper proposes an RNN-based click-prediction framework that models temporal dependencies in users’ behavior sequences. Experiments show it outperforms state-of-the-art click-prediction models across various settings, motivating continued work in this direction.

Conclusion: The proposed framework uses Recurrent Neural Networks to incorporate temporal dependencies in users’ behavior sequences for click prediction.This differs from traditional click-prediction models by leveraging recurrent structure.
Conclusion: Experiments show that the method outperforms state-of-the-art click-prediction models in various settings.The passage reports broad comparative improvement without specifying individual metrics or values.
Future Work: Future work will continue developing this direction, while the current sequence construction is built at the user level.The passage introduces several future-work aspects but is truncated before describing them fully.