Query Understanding through Knowledge-Based Conceptualization

Zhongyuan Wang, Kejun Zhao, Haixun Wang, Xiaofeng Meng, Ji-Rong Wen

Abstract

Search queries are often short and ambiguous, posing significant challenges for traditional Natural Language Processing (NLP) techniques that rely on grammatical structure. This paper presents a holistic framework for query understanding through knowledge-based conceptualization. By utilizing a massive probabilistic knowledge base (Probase) and a novel Graph-Based Iterative Algorithm (GBIA), the proposed method maps query terms to their intended concepts. A key innovation is the inclusion of "non-instance" words—such as verbs and adjectives—as critical contextual signals. Experimental results demonstrate that this approach significantly outperforms traditional tiered NLP pipelines in both accuracy and efficiency, processing queries in under 10 milliseconds.

1. Introduction

Short texts, particularly search queries, lack the statistical signals and syntactic depth found in longer documents. A primary challenge in query understanding is conceptualization: the process of mapping a specific instance (e.g., "Apple") to its intended concept (e.g., Company vs. Fruit).

Traditional NLP approaches typically employ a multi-tiered pipeline—performing POS tagging, then chunking, and finally entity resolution. However, these steps are often interdependent. For instance, in the query "watch harry potter," identifying "watch" as a verb depends on recognizing "harry potter" as a movie, while identifying "harry potter" as a movie is reinforced by the presence of the verb "watch." This "chicken-and-egg" dependency leads to error propagation in linear pipelines.

2. Methodology

The authors propose the Graph-Based Iterative Algorithm (GBIA) to perform joint optimization across traditional NLP tiers.

2.1 Knowledge Mining and Network Construction

The framework leverages Probase, a large-scale probabilistic taxonomy, to mine relationships between instances, concepts, and "non-instance" terms (verbs, adjectives, and attributes). Lexical strengths are derived from billions of web documents to determine how strongly a modifier like "yummy" relates to a concept like fruit.

Figure 2: A semantic network illustrating the interplay between terms (instances and non-instances) and concepts.

The resulting semantic network consists of nodes representing terms and concepts, connected by edges representing isA relationships, typicality (e.g., verb-to-concept relevance), and concept-to-concept relatedness.

2.2 Iterative Random Walk

To resolve ambiguity, the system performs an iterative random walk with restarts. Unlike standard random walks with static weights, GBIA updates edge weights between iterations based on the model's evolving "belief" about a term's role. If the model becomes more confident that "watch" is a verb, it increases the weight of the edge connecting "watch" to the concept movie.

Figure 5: Probabilistic graph showing weighted relationships used for disambiguating terms like 'new york' and 'watch' through iterative updates.

3. Experimental Evaluation

The model was evaluated using Probase and a web corpus of billions of documents. A manually labeled set of 1,200 search queries served as the ground truth.

  • Superior Type Detection: The GBIA method demonstrated superior performance in type detection. For highly ambiguous terms like "orange," the model achieved 78.1% precision, significantly higher than the 45.6% achieved by the Stanford Parser.
  • Higher Conceptualization Accuracy: The model outperformed state-of-the-art baselines, including LDA-based and earlier conceptualization models, in mapping terms to correct concepts.
  • Computational Efficiency: Efficiency is critical for real-time search applications. The majority of queries converged in fewer than 10 iterations, with processing times typically under 10 milliseconds.

4. Discussion and Key Insights

The research highlights that "non-instances"—the modifiers often ignored in entity-centric research—are the primary drivers of disambiguation in sparse text. By treating POS tagging and conceptualization as a joint graph problem, the model avoids the pitfalls of sequential processing.

However, limitations remain. The current framework does not incorporate prepositions, which could offer additional linguistic context. Furthermore, the system's performance is inherently tied to the coverage of the underlying knowledge base; if a concept is missing from Probase, the model cannot conceptualize it.

5. Conclusion

By breaking down the boundaries between traditional NLP tiers, the GBIA framework provides a robust solution for understanding short, ambiguous text. Future work may explore scaling this holistic approach to longer documents and expanding the knowledge base to improve coverage of emerging concepts.

Summary updated

Abstract

The goal of query conceptualization is to map instances in a query to concepts defined in a certain ontology or knowledge base. Queries usually do not observe the syntax of a written language, nor do they contain enough signals for statistical inference. However, the available context, i.e., the verbs related to the instances, the adjectives and attributes of the instances, do provide valuable clues to understand instances. In this paper, we first mine a variety of relations among terms from a large web corpus and map them to related concepts using a probabilistic knowledge base. Then, for a given query, we conceptualize terms in the query using a random walk based iterative algorithm. Finally, we examine our method on real data and compare it to representative previous methods. The experimental results show that our method achieves higher accuracy and efficiency in query conceptualization.
BibTeX
@inproceedings{wang2015query,
  author = {Zhongyuan Wang and Kejun Zhao and Haixun Wang and Xiaofeng Meng and Ji-Rong Wen},
  title = {{Query Understanding through Knowledge-Based Conceptualization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure