TL;DR
This paper tackles the challenge of distinguishing between informational and truly ambiguous queries in web search. They propose a novel metric, "User Entropy," derived from clickstream data, which proves more effective than existing methods in identifying ambiguous queries, especially for less frequent search terms.
What Problem Does This Paper Address?
Understanding a user's intent behind a search query is fundamental to providing effective search results. A key challenge is differentiating between queries that are purely informational (e.g., "lyrics") and those that are ambiguous, meaning they can have multiple distinct meanings or intents (e.g., "al pacino" could refer to the actor, a movie, etc.). Existing methods for classifying query ambiguity often struggle to make this distinction, conflating informational queries with ambiguous ones. This paper aims to improve this classification by leveraging user click behavior.
Methods
The authors propose a new metric called User Entropy to quantify query ambiguity. Unlike "Overall Entropy," which considers the distribution of clicks across all users and all results for a query, User Entropy focuses on the average entropy of click distributions for individual searchers. The intuition is that for an ambiguous query, a single user is likely to focus on one specific interpretation at a time, leading to a more concentrated set of clicked URLs. Conversely, for an informational query, a user might explore a broader range of related results.
They also introduce Domain Entropy as a more robust measure when click data for individual URLs is sparse. This metric assumes that URLs within the same domain likely relate to the same topic. These novel metrics, along with established features like query length and click frequency, are then used as input for standard machine learning classifiers (Naive Bayes, Logistic Regression, SVM).
Datasets
The study utilizes an MSN Search query log from 2006, containing 15 million queries from US users over one month. Queries with fewer than 10 clicks were discarded, resulting in 84,703 unique queries. These queries were further categorized into low (10-100 clicks), medium (100-1000 clicks), and high (over 1000 clicks) frequency groups. A random sample of 50 queries from each group (totaling 150) was manually labeled by three annotators to create a ground truth for classification.
Key Insights and Ideas
- User Entropy is Key: The core insight is that focusing on individual user click patterns (User Entropy) is more discriminative for ambiguity than looking at the aggregate click distribution (Overall Entropy). Ambiguous queries, despite potentially having a wide range of clicked URLs across all users, often exhibit low User Entropy because individual users tend to stick to one interpretation.
- Ambiguity vs. Informational: The paper highlights that informational queries can have a broad range of results, leading to high Overall Entropy, but they are not necessarily ambiguous. User Entropy helps tease apart these two distinct types of query intent.
- Low-Frequency Queries Matter: The proposed User Entropy metric shows its greatest benefit for low-frequency queries, which are the most common in search logs and often contain a higher proportion of informational queries that are harder to classify.
Key Results
The experiments demonstrate that incorporating User Entropy features significantly improves classification performance. For instance, when using all features, SVM achieved an accuracy of 0.78 for distinguishing between informational and ambiguous queries. When User Entropy features were excluded, the accuracy dropped to 0.76.
The paper also shows that User Entropy is particularly beneficial for low-frequency queries. While the impact on high and medium frequency queries was less pronounced, this is attributed to the fact that these query groups are already largely "clear" (unambiguous and navigational), and User Entropy is most useful for identifying unclear queries.
Limitations and Future Work
The authors acknowledge that User Entropy's effect is less pronounced on high and medium frequency queries. They suggest that this is because these query groups are already predominantly clear, and the benefit of User Entropy lies in identifying ambiguity in less common or more complex queries.
Future work could explore how these metrics can be integrated into real-world search engines to improve query understanding and result presentation. The paper also implicitly suggests further investigation into the relationship between query frequency and the effectiveness of different ambiguity detection metrics.
Summary updated