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:
- 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").
- 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.
- 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