TL;DR
This paper introduces a novel methodology for classifying rare web queries by leveraging the content of search results. By treating search results as a source of external knowledge, they achieve significantly higher accuracy than previous methods, which is crucial for improving ad matching and user experience, especially for the vast majority of less frequent queries.
What Problem Does This Paper Address?
The internet is awash with information, and search engines are our primary tools for navigating it. However, users often submit very short, ambiguous queries that carry little explicit meaning. This brevity makes it challenging for search engines to accurately understand user intent, which is particularly problematic for "rare" queries that don't appear frequently enough for traditional machine learning models to learn from. This lack of understanding directly impacts the effectiveness of online advertising, where relevant ads are crucial for both advertisers and users. The paper aims to bridge this gap by developing a robust query classification system that can handle thousands of query classes with high accuracy, even for these difficult, infrequent queries.
Methods
The core of the methodology involves a two-phase approach:
- Document Classifier: First, they build a classifier to categorize web pages into a large, hierarchical taxonomy (around 6000 nodes). This is achieved using a centroid-based classifier, which is efficient for handling a large number of classes. Human editors provided labeled queries to train this classifier.
- Query Classification using Search Results: Given a query, they retrieve top search results from a general web search engine. The key innovation here is the use of a "blind relevance feedback" technique. They assume the top search results are relevant and then crawl these pages to extract their content. This content is then classified using the document classifier built in phase 1. Finally, a voting scheme is employed to aggregate the classifications of individual search results to determine the most likely class for the original query. This approach effectively uses the "wisdom of the crowd" from search results to infer query intent.
Datasets
- Taxonomy: A commercial taxonomy of approximately 6000 nodes, arranged hierarchically, was used. This is significantly larger than taxonomies used in prior work.
- Training Data: Human editors provided labeled queries for populating the taxonomy nodes.
- Evaluation Datasets: Two sets of 1000 queries each were used. These sets were specifically curated to contain "rare" queries, meaning they were not directly matched to advertisements and had low frequencies in search logs. Set 1 queries could be matched to ads via broad match, while Set 2 queries were even rarer and harder to interpret.
Key Insights and Ideas
- Leveraging Search Results is Powerful: The most significant insight is that the content of search results, even for rare queries, provides a rich source of external knowledge that dramatically improves query classification accuracy.
- Full-Page Crawling Outperforms Summaries (with caveats): While using search result summaries is computationally cheaper, crawling the full pages of search results generally leads to better classification accuracy, especially when combined with a voting approach. This suggests that the detailed content of the pages offers more discriminative power.
- Voting is Robust for Rare Queries: For rare and difficult queries, a voting scheme that aggregates individual classifications of search results is more effective than bundling results into a single meta-document. This is because individual summaries can be noisy, but when aggregated, they provide a more stable signal.
- Taxonomy Size Matters: Using a much larger and more granular taxonomy (6000 nodes) poses a greater challenge but also allows for more specific and useful classifications, which is critical for applications like ad matching.
Key Results
- Significant Accuracy Improvement: The proposed methodology achieved substantial improvements in classification accuracy compared to a baseline classifier that did not use external knowledge. Statistical significance tests confirmed these improvements (p < 0.0005).
- Effectiveness of External Knowledge: Using external knowledge (search results) improved precision and F1 scores considerably. For example, a baseline achieved F1 scores around 0.536, while methods using external knowledge reached scores around 0.827 to 0.893.
- Full-Page vs. Summary Performance: While search engine A performed better with full-page text, search engine B showed better results with summaries, suggesting differences in how search engines present information.
- Optimal Number of Results: Classification accuracy generally increased with the number of search results used, peaking around 40 results, after which performance slightly dropped due to increased noise.
Limitations and Future Work
- Failure Cases: The methodology struggled with queries that were random strings (e.g., phone numbers), yielded no search results, or corresponded to very recent events not yet well-covered by search engines.
- Computational Cost: While the voting mechanism is efficient at runtime if pages are pre-classified, crawling and classifying full pages can be computationally intensive.
- Future Directions: The authors suggest exploring the use of search result classifications as features for a second-level classifier, investigating other page features beyond quality scores for weighting search results, and incorporating session information to leverage knowledge from previous queries. They also acknowledge the difficulty of direct comparison with prior work due to the lack of standardized benchmarks.
Summary updated