Query to Knowledge

Ke Zhai, Zornitsa Kozareva, Yuening Hu, Qi Li, Weiwei Guo2016 · DOI

TL;DR

This paper introduces an unsupervised method for extracting brand and product entities from noisy online shopping queries using adaptor grammars. By standardizing query patterns and employing flexible grammar rules, their approach builds accurate knowledge bases that significantly improve downstream tasks like query tagging and chunking.

What Problem Does This Paper Address?

Extracting structured information, like brand and product names, from the vast amount of data in web search queries is a crucial step towards building comprehensive knowledge bases. However, online shopping queries present unique challenges: they are often short, noisy (misspellings, arbitrary word order), lack explicit linguistic features (like capitalization for proper nouns), and don't fit neatly into traditional Named Entity Recognition (NER) frameworks designed for full sentences. Existing NER methods often rely on human annotations or external resources, which are expensive and time-consuming to acquire, especially for less common entity types like brands and products. This paper aims to bridge this gap by developing an unsupervised, domain-independent method to extract these entities directly from raw query logs.

Methods

The core of the proposed method lies in adaptor grammars, a nonparametric extension of Probabilistic Context-Free Grammars (PCFGs). Unlike PCFGs, adaptor grammars can dynamically learn new grammar rules from data, making them more flexible and robust to the noise and variability found in web queries. The process involves three main steps:

  1. Preprocessing: This step cleans up queries by filtering out "out-of-domain" queries (informational, navigational) and removing domain-specific "stopwords" common in shopping contexts (e.g., "sale," "online," "cheap").
  2. Query Standardization: To combat the sparsity of word orderings for similar queries (e.g., "florajen probiotics" vs. "probiotics florajen"), this step groups queries with the same set of words and standardizes them to their most frequent word order. This significantly reduces noise and improves data efficiency.
  3. Grammar Rules and Inference: The authors propose three sets of grammar rules, starting with a basic "chunk grammar" and progressively adding complexity with "chunk+prep" (for prepositional phrases) and "chunk+prep+mod" (for modifiers like model names). Adaptor grammars are used to infer these rules and parse queries. The inference process leverages Markov Chain Monte Carlo (MCMC) methods, specifically a Metropolis-Hastings sampler, to learn the latent variables and grammar structures from the observed query data.

Datasets

The authors used a large collection of online shopping queries sampled over a 9-month interval. These queries were classified into five domains: Apparel, Electronics, Health & Beauty, Home & Garden, and Sporting Goods. The paper does not mention the creation of new benchmark datasets but rather uses this large-scale, real-world query log for evaluation.

Key Insights and Ideas

  • Adaptor Grammars for Noisy Data: The paper highlights the power of adaptor grammars in handling the inherent noise and variability of web search queries, outperforming traditional PCFGs which assume fixed grammar rules.
  • Query Standardization is Crucial: The insight that most query families have a dominant word ordering is key. Standardizing queries to their most frequent form dramatically reduces sparsity and improves model performance.
  • Grammar Hierarchy Matters: The progressive addition of grammar rules (chunk, chunk+prep, chunk+prep+mod) shows a clear benefit, with the most complex grammar ("chunk+prep+mod") yielding the best results, indicating the importance of capturing prepositional phrases and modifiers.
  • Unsupervised Extraction is Feasible and Effective: The success of a completely unsupervised approach, without human annotation or external resources, demonstrates a significant step towards scalable knowledge base construction.

Key Results

  • Intrinsic Evaluation: The proposed adaptor grammar approach consistently achieved better precision than PCFG-based methods and a semi-supervised baseline (CIKM07) across all five domains and for both brand and product entities. The "chunk+prep+mod" grammar generally performed best.
  • Extrinsic Evaluation: When the discovered knowledge bases were used as features for downstream tasks (query tagging with CRF and query chunking with MaxEnt), the proposed method significantly improved performance. The recall and F1 scores consistently improved as more entities from the discovered knowledge base were revealed to the models, indicating good coverage and quality.
  • Qualitative Findings: The method successfully identified complex brand entities (e.g., "tiffany and co," "bath and body works") and product entities (e.g., "engagement ring," "remote control") of arbitrary length. It also discovered useful joint phrases like "samsung galaxy" and common modifiers/prepositional phrases relevant to specific domains.

Limitations and Future Work

  • Product Families and Model Numbers: The current "chunk+prep+mod" grammar subsumes product families and model numbers under the "MODIFIER" nonterminal. The authors suggest explicitly modeling these as a future direction, as they are critical for detailed query understanding.
  • Scalability of Inference: While MCMC is used for inference, the authors mention that variational Bayesian inference could offer a more scalable and parallelizable alternative for future work.
  • Domain Specificity of Standardization: While query standardization is effective, the paper notes that phenomena like "paris hilton" (person vs. city) suggest that some standardization rules might be domain-specific and require careful handling across different domains.

Summary updated

Abstract

Web search queries provide a surprisingly large amount of information, which can be potentially organized and converted into a knowledgebase. In this paper, we focus on the problem of automatically identifying brand and product entities from a large collection of web queries in online shopping domain. We propose an unsupervised approach based on adaptor grammars that does not require any human annotation efforts nor rely on any external resources. To reduce the noise and normalize the query patterns, we introduce a query standardization step, which groups multiple search patterns and word orderings together into their most frequent ones. We present three different sets of grammar rules used to infer query structures and extract brand and product entities. To give an objective assessment of the performance of our approach, we conduct experiments on a large collection of online shopping queries and intrinsically evaluate the knowledgebase generated by our method qualitatively and quantitatively. In addition, we also evaluate our framework on extrinsic tasks on query tagging and chunking. Our empirical studies show that the knowledgebase discovered by our approach is highly accurate, has good coverage and significantly improves the performance on the external tasks.
BibTeX
@misc{zhai2016query,
  author = {Ke Zhai and Zornitsa Kozareva and Yuening Hu and Qi Li and Weiwei Guo},
  title = {{Query to Knowledge}},
  year = {2016},
  doi = {10.1145/2911451.2911495},
}
Figure