Learning click models via probit bayesian inference

Yuchen Zhang, Dong Wang, Gang Wang, Weizhu Chen, Zhihua Zhang, Botao Amber Hu, Li ZhangCIKM 2010 · DOI

TL;DR

This paper introduces Probit Bayesian Inference (PBI), a novel framework for learning click models that unifies existing models and allows for the integration of richer features beyond simple position bias. PBI significantly improves the accuracy of click prediction and search ranking compared to traditional methods, while also offering a scalable and flexible approach for handling large-scale clickstream data.

What Problem Does This Paper Address?

In web search, understanding user behavior through clickstream data is crucial for improving search result ranking. Click models aim to capture this behavior, but existing methods often struggle with:

  • Model Comparison Difficulty: Different click models use distinct inference methods, making it hard to fairly compare their underlying assumptions and performance.
  • Limited Feature Integration: Most models primarily focus on "position bias" (the tendency for higher-ranked results to be clicked more often), neglecting other important factors like document relevance (e.g., BM25 score) or authority (e.g., PageRank).
  • Scalability: Processing the ever-growing volume of clickstream data presents a significant computational challenge.

This paper addresses these issues by proposing a unified Bayesian inference framework that is flexible, extensible, and computationally efficient.

Methods

The core innovation is the Probit Bayesian Inference (PBI) framework. Here's how it works:

  • Unified Probabilistic Model: PBI treats the parameters of various click models (like UBM, DBN, CCM) as latent variables.
  • Probit Link Function: Crucially, PBI introduces auxiliary Gaussian variables for each click model parameter and links them using a probit function ($\theta_i = \Phi(x_i)$). This transformation allows for Bayesian inference while maintaining computational tractability, especially when dealing with polynomial likelihood functions common in click models.
  • Gaussian Density Filtering: An online learning scheme is employed to approximate the posterior distribution of the auxiliary variables with a Gaussian, enabling efficient updates as new data arrives.
  • Deep PBI: To incorporate richer features, the authors extend PBI to a "Deep PBI" framework. Here, the auxiliary variables are modeled as a combination of historical information and external measures (like BM25, PageRank), allowing for a more sophisticated understanding of user preferences.

Datasets

The experiments were conducted on a large-scale clickstream dataset collected from a commercial search engine. This dataset comprised:

  • Training Data: 6,104,278 sessions.
  • Testing Data: 6,095,267 sessions.

The dataset was divided based on query frequency, with specific considerations for ensuring that queries in the testing set were also present in the training set. No new benchmarks were introduced; rather, existing click models were evaluated on this large, real-world dataset.

Key Insights and Ideas

  • Bayesian Inference Unifies and Improves: PBI provides a common ground for comparing different click models by using a consistent inference mechanism. This unification reveals that the Bayesian approach often leads to better generalization and accuracy than original, model-specific inference methods.
  • Beyond Position Bias: The ability of PBI to seamlessly integrate features like BM25 and PageRank significantly enhances click prediction accuracy, demonstrating that user clicks are influenced by more than just rank.
  • Scalability is Key: The incremental nature of the PBI inference algorithm makes it well-suited for handling the massive and continuously growing datasets typical of web search logs.
  • Deep PBI for Richer Context: The Deep PBI extension shows that incorporating external signals can further boost performance, especially for certain types of queries or models.

Key Results

  • Improved Perplexity: PBI-inferred models (H-UBM, H-CCM, H-DBN) consistently outperformed their original counterparts in terms of click perplexity across various query frequencies. For example, H2-UBM showed significant improvements.
  • Enhanced Ranking (NDCG): When integrated with additional measures (Deep PBI), the models achieved substantial gains in NDCG scores, indicating better search ranking performance. For DBN, H2-DBN was 14.6% better on NDCG@1 and 7.63% better on NDCG@5 compared to the original DBN.
  • Efficiency: The PBI inference algorithm is computationally efficient, with the average number of iterations for computing intermediate values being very low (around 2.04 in the H-CCM training process).

Limitations and Future Work

  • Model Assumptions: While PBI offers a unified inference method, the underlying assumptions of the original click models (UBM, CCM, DBN) still play a role. The paper notes that CCM's assumptions might be less reasonable than UBM's or DBN's on their dataset.
  • Parameter Sensitivity: For DBN, the optimal parameter $\gamma$ was found to be frequency-dependent, suggesting that some models might still require careful tuning or more sophisticated methods to handle varying query characteristics.
  • Future Work: The authors suggest further exploring the potential applications of PBI in click models and investigating its use with other types of click models and data. They also hint at further research into the "deep hierarchical extension" for even more sophisticated feature integration.

Summary updated

BibTeX
@inproceedings{zhang2010learning,
  author = {Yuchen Zhang and Dong Wang and Gang Wang and Weizhu Chen and Zhihua Zhang and Botao Amber Hu and Li Zhang},
  title = {{Learning click models via probit bayesian inference}},
  booktitle = {ACM International Conference on Information and Knowledge Management},
  year = {2010},
  doi = {10.1145/1871437.1871496},
}
Figure