TL;DR
Sponsored search relies on matching user queries to limited advertiser keywords. This paper introduces an active learning approach to improve query rewriting, which bridges this gap. By intelligently selecting the most informative query-rewrite pairs for human labeling, they significantly boost the accuracy of the relevance model, leading to better ad matching and potentially more efficient ad spending.
What Problem Does This Paper Address?
Sponsored search, a major revenue driver for search engines, faces a fundamental challenge: the vast and unpredictable nature of user queries versus the curated and limited set of keywords advertisers can choose. To bridge this gap, query rewriting systems transform user queries into forms that are more likely to match available advertisement keywords. The effectiveness of this rewriting hinges on accurately predicting the relevance between a user's original query and its rewritten form. Traditionally, this relevance model is trained using human-labeled data, which is expensive and time-consuming to acquire. The core problem this paper tackles is how to build a highly accurate query rewriting relevance model with minimal human labeling effort.
Methods
The authors leverage an active learning strategy called Transductive Experimental Design (TED) to address the labeling bottleneck. Instead of randomly selecting query-rewrite pairs for human review, TED aims to pick the most informative ones.
Here's a breakdown of their approach:
- Feature Generation: For each (original query, rewritten query) pair, they extract a rich set of features. These include:
- Syntactic features: Edit distance, token overlap, and character prefix overlap.
- Statistical rewrite frequency features: How often a rewrite occurs for a given query, derived from query logs.
- Web occurrence features: How often the query and rewrite appear on the same web pages.
- Web search features: How often they share common search result URLs.
- Advertiser bid features: Whether the same advertisers bid on both.
- Location features: If there's a change in location between the query and rewrite.
- Relevance Model: They employ a linear regression model to predict the relevance score of a query-rewrite pair. The model is trained to minimize the sum of squared errors between predicted and actual relevance scores.
- Active Learning (TED): The core innovation is how they select samples for labeling. TED aims to minimize the average expected square prediction error of the model across all potential data points. This is achieved by selecting query-rewrite pairs whose feature vectors, when used to train the model, lead to the smallest expected error in future predictions. Essentially, it prioritizes samples that are most likely to improve the model's understanding of the underlying relevance function.
Datasets
The paper describes experiments conducted on a dataset of 5000 query-rewrite pairs. From this pool, 1500 examples were used for training and 1500 held-out examples were used for testing. The training set was further divided: 1500 samples were selected for labeling and training using either random sampling or their active learning approach.
Key Insights and Ideas
- Active learning is a game-changer for expensive labeling tasks: The fundamental insight is that not all data points are created equal when training a model. By strategically selecting the most informative samples, we can achieve better performance with significantly less human effort.
- TED's advantage in minimizing prediction error: The TED approach is mathematically grounded in minimizing the expected prediction error, which directly translates to a more robust and accurate relevance model.
- No need for labels to select samples: A key practical advantage highlighted is that the TED algorithm can select informative samples without requiring any initial labels for those samples. This is crucial for real-world scenarios where labeling and modeling might be separate processes.
Key Results
The experimental results demonstrate the effectiveness of their active learning approach:
- Consistent outperformance: The active learning approach consistently outperformed random sampling in terms of precision-recall curves for the top k best query rewrites.
- Significant improvement for top rewrites: The most notable gains were observed when considering only the single best rewrite (k=1). In this scenario, their approach achieved a 1.7% improvement in average precision, which translates to an 18% reduction in error.
Limitations and Future Work
- Focus on linear models: The current work focuses on a linear regression model for relevance prediction. While effective, more complex non-linear models might capture more nuanced relationships, and it would be interesting to see if active learning can similarly benefit them.
- Generalizability of TED: While TED is shown to be effective here, its performance might vary across different types of active learning problems and feature spaces.
- Future work could explore: Extending this active learning framework to other aspects of sponsored search, such as optimizing bidding strategies or improving ad ranking. The authors also suggest that their approach can reduce the labor-intensive nature of labeling, leading to improved production efficiency in real-world sponsored search systems.
Summary updated