TL;DR
This paper introduces the General Click Model (GCM), a novel Bayesian network-based approach for predicting user clicks on online advertisements. GCM overcomes limitations of prior models by incorporating multiple user and ad-specific attributes beyond just position, enabling better prediction for less frequent "tail" queries and providing a unified framework that encompasses existing click models.
What Problem Does This Paper Address?
Online advertising relies heavily on predicting user click-through rates (CTR) to optimize ad placement and auctions. Existing click models often struggle with "tail queries" (low-frequency queries) due to insufficient training data. Furthermore, many models only consider query, URL, and position, neglecting other crucial factors like local time or user agent, which demonstrably influence CTR. The paper aims to develop a more robust and generalizable click model that addresses these limitations.
Methods
The core contribution is the General Click Model (GCM), a Bayesian network that models user browsing behavior. GCM's novelty lies in:
- Multi-Attribute Modeling: It incorporates a rich set of attributes (user-specific like local hour, user agent; and URL-specific like position, relevance) to predict transition probabilities between user actions (examining, clicking).
- Across-Query Learning: By modeling attributes shared across queries, GCM can generalize to predict clicks for tail queries, even with limited specific training data.
- Nested Bayesian Network: GCM uses an outer Bayesian network for user browsing and an inner model that defines transition probabilities based on attribute values.
- Expectation Propagation: The model uses Expectation Propagation for approximate Bayesian inference to learn model parameters.
- Unified Framework: The paper demonstrates that GCM can subsume prior models (Examination Hypothesis, Cascade, Click Chain, Dynamic Bayesian Network) as special cases by appropriately defining attributes and parameters.
Datasets
The paper uses two primary datasets:
- Advertisement Dataset: A large-scale commercial advertisement dataset collected over three days, comprising 4,530,044 query sessions and 16,268,349 URL impressions. Queries are categorized by frequency.
- Search Dataset: A web search dataset sampled over three days, with 959,148 query sessions and 8,813,048 URL impressions. Queries are also categorized by frequency.
Key Insights and Ideas
- Beyond Position: The paper strongly emphasizes that user behavior and click prediction are significantly influenced by attributes beyond just the position of an ad or search result. Local time and user agent are shown to be important factors.
- Generalization for Tail Queries: By learning from shared attributes across queries, GCM offers a significant advantage in predicting clicks for infrequent queries, a major challenge for models trained on a per-query basis.
- A Unifying Framework: The ability of GCM to encompass and generalize from previous click models highlights a common underlying structure and provides a path for future research to build upon.
- Attribute Importance: The research identifies position, match type (related to relevance), and user agent as the most influential attributes for click prediction in their advertisement dataset.
Key Results
- Log-Likelihood: GCM consistently outperformed baseline models (Cascade, CCM, DBN) on the advertisement dataset, achieving a 1.2% improvement over CCM and DBN, and 1.5% over Cascade. This improvement is significant given the low CTR of ads.
- Perplexity: GCM showed superior performance in perplexity, indicating better accuracy across individual positions. It achieved a 17.4% improvement over Cascade, 12.9% over CCM, and 12.1% over DBN.
- R2 Score: GCM achieved the highest R2 score (0.993), indicating the best linear relationship between predicted and actual CTR, outperforming Cascade (0.956), CCM (0.939), and DBN (0.958).
- Bias Explanation: GCM was most effective at explaining positional bias, particularly for lower-ranked positions, and successfully modeled the local hour bias, which other models struggled with.
- Search Data Performance: While GCM performed comparably to state-of-the-art models on search data, its superiority was more pronounced on advertisement data. This is attributed to the richer set of attributes used for ads and the inherent complexity of advertising click prediction.
Limitations and Future Work
- Computational Cost: While GCM shows strong performance, its running time is higher than some prior models. The authors suggest investigating approximate Bayesian inference techniques and parallel GCM instances for real-time, large-scale applications.
- Continuous Attributes: The current model primarily treats attributes as discrete. The paper suggests future work to incorporate continuous attributes (e.g., BM25 score) by modifying the model to handle multiplication terms.
- Page Structure: The authors propose making better use of page structure, such as differentiating between main line and sidebar ad placements, to further improve accuracy.
- CTR@1 Prediction: The paper notes that GCM can predict CTR at position 1, which could be further explored for applications like improving NDCG or ad auctions.
- Attribute Significance: The paper suggests using the variance of attribute parameters to measure attribute significance, potentially replacing separate confidence calculations.
Summary updated