TL;DR
This paper introduces a novel, computationally efficient method for calculating the semantic similarity between search queries using a large web corpus. Their approach, which leverages distributional semantics and a geometric mean for combining word vectors, significantly outperforms existing web-kernel methods and shows that chunking queries into meaningful n-grams further boosts performance.
What Problem Does This Paper Address?
In the realm of information retrieval and search engines, understanding the semantic similarity between queries is crucial for various applications like query expansion, suggestion, and targeted advertising. Traditional methods often rely on expensive, real-time interactions with search engines or require pre-computing massive phrase vectors, making them computationally prohibitive for large-scale analysis. This paper aims to bridge this gap by proposing a data-driven, unsupervised approach that is both effective and computationally scalable, allowing for the calculation of query similarities without direct reliance on search engine APIs or the overhead of full phrase vector computation.
Methods
The core of the proposed method lies in adapting distributional similarity techniques, traditionally used for word similarity, to query similarity. Instead of relying on search engine results, they build context vectors for each word in a query by analyzing its co-occurrence with other words within a fixed window (chosen as 3 words) in a large web corpus.
Key steps include:
- Contextual Word Vectors: For each word in a query, a vector is constructed representing the frequency of words appearing nearby in the corpus.
- Geometric Mean for Query Representation: To represent a multi-word query, the paper uses the geometric mean of the frequency vectors of its constituent words. This is a novel way to combine word-level information into a query-level representation, aiming to capture the essence of the phrase.
- Cosine Similarity: Once queries are represented as vectors, their similarity is calculated using the standard cosine similarity metric.
- N-gram Chunking (Advanced Version): An extension to the method involves identifying and chunking meaningful n-grams (phrases) within queries. This allows treating phrases like "new york" as a single unit, leading to more robust context vectors.
Datasets
The authors utilized a large web corpus of hundreds of millions of documents, crawled in August 2008, to build their contextual word vectors. For evaluation, they used a dataset of one and a half million anonymized English queries from the Google search engine. A gold-standard set of query similarities was manually created by having two human raters evaluate suggestions for 65 randomly sampled queries.
Key Insights and Ideas
- Distributional Semantics for Queries: The paper demonstrates that distributional semantics, a well-established technique for word similarity, can be effectively adapted to measure the similarity between entire search queries, even those that are syntactically informal.
- Geometric Mean as a Smart Aggregator: The use of the geometric mean to combine word vectors into a query vector is a clever way to approximate an "AND" operation while still retaining magnitude information. This helps in disambiguating words and focusing on shared contextual features.
- N-gram Chunking Enhances Performance: Identifying and treating meaningful phrases (n-grams) as single units within queries significantly improves similarity scores, suggesting that syntactic structure, even in informal queries, plays a role.
- Computational Efficiency: The proposed corpus-based approach bypasses the need for expensive online search engine interactions, making it highly scalable for large-scale similarity computations.
Key Results
The proposed distributional similarity method, particularly when combined with n-gram chunking, significantly outperforms the "Web Kernel" method, a state-of-the-art unsupervised query-to-query similarity technique. Table 3 shows that the "N-grams" approach achieved higher Precision@1, Precision@3, Precision@5, mAP, and AUC scores compared to both the "Unigrams" (basic word-based approach) and the "Web Kernel" baseline. For instance, the N-grams method achieved an AUC of 0.54, compared to 0.22 for the Web Kernel.
Limitations and Future Work
The authors acknowledge that their approach, while effective, does not automatically benefit from search engine features like spelling correction or relevance scores, which their baseline method does. They also note that the manual evaluation showed some disagreements between raters, particularly for queries that were only slightly related, suggesting that the 5-point Likert scale might be too granular. Future work could explore incorporating these search engine features or refining the evaluation methodology. The authors also mention their intention to make their dataset available to the research community.
Summary updated