Abstract
Co-occurrence analysis has been used to determine related words or terms in many NLP-related applications such as query expansion in Information Retrieval (IR). However, related words are usually determined with respect to a single word, without relevant information for its application context. For example, the word "programming" may be considered to be strongly related to "Java", and applied inappropriately to expand a query on "Java travel". To solve this problem, we propose to add another context word in the relation to specify the appropriate context of the relation, leading to term relations of the form "(Java, travel) → Indonesia". The extracted relations are used for query expansion in IR. Our experiments on several TREC collections show that this new type of context-dependent relations performs much better than the traditional co-occurrence relations.
Introduction
Traditional query expansion (QE) often fails because it ignores context—expanding "Java travel" with "programming" just because "Java" and "programming" are frequently related in general corpora. In Information Retrieval (IR), users often provide short, ambiguous queries. QE attempts to mitigate this by adding related terms to the search. Traditionally, this is done using "unigram" relations: if a user searches for term A, the system adds term B based on their frequent co-occurrence.
The fatal flaw in this approach is semantic ambiguity. The term "Java" is strongly related to "programming" in a computer science context, but it relates to "hotel" or "volcano" in a travel context. If a user searches for "Java travel," a traditional system might still inject "programming" into the query, polluting results with irrelevant technical documents. This research introduces context-dependent term relations (e.g., (Java, travel) → Indonesia) to ensure expansion terms align with the user's specific intent.
Methodology
The authors implement their approach within a Language Modeling (LM) framework for IR, comparing two primary models:
- CIQE (Context-Independent Query Expansion): A baseline QE approach where expansion terms are chosen based on their relationship to individual query terms in isolation.
- CDQE (Context-Dependent Query Expansion): The proposed approach where expansion terms are selected based on biterm relations. Instead of calculating $P(expansion | query\_term)$, it evaluates $P(expansion | query\_term_1, query\_term_2)$.
Technical Implementation
- Relation Extraction: "Triterms" (groups of three words appearing within a 10-word window) are extracted from large text corpora. The model calculates the probability of the third word given the first two.
- Filtering: To manage data volume and noise, relations are retained only if the word pair appears at least 10 times, the conditional probability exceeds a threshold, and the Pointwise Mutual Information (PMI) between context words is positive.
- Weighting: For multi-word queries, PMI determines which word pairs are most "meaningful" to drive expansion.
Experimental Setup
The models were evaluated on three standard TREC (Text REtrieval Conference) collections:
- AP: Associated Press (1988-89)
- SJM: San Jose Mercury News (1991)
- WSJ: Wall Street Journal (1990-92)
These collections serve as industry benchmarks, containing hundreds of thousands of documents and standardized query sets.
Key Results and Discussion
The proposed CDQE model consistently and significantly outperformed both the basic unigram model (UM) and the standard context-independent expansion (CIQE).
As shown in the table above, CDQE achieved substantial improvements in Mean Average Precision (MAP) across all tested collections. Specifically, it achieved a 22% improvement over the baseline on the AP collection and a 21% improvement on the SJM collection. Qualitatively, for a query like "insider trading," CDQE suggested highly specific terms like "Boesky" and "Drexel," whereas CIQE suggested generic terms like "year" and "report."
The Precision-Recall curves further illustrate that CDQE maintains superior precision across the entire recall spectrum compared to UM and CIQE. Unlike traditional QE, which often improves recall at the expense of precision, CDQE improves both.
Insights
- Context as a Constraint: Treating the second word in a query as a filter for the first word's meaning allows (Java, travel) to act as a single unit pointing to a specific semantic space.
- Transferability: Relations extracted from one dataset (e.g., AP) performed well on others (e.g., WSJ), suggesting these relations capture general semantic knowledge rather than dataset-specific noise.
Conclusion
While CDQE shows significant promise, challenges remain regarding computational complexity. Moving from unigram to biterm relations increases the data scale exponentially. Future work may explore "triterm" conditions for even greater precision or incorporate syntactic dependency parsing to move beyond simple co-occurrence windows.
Summary updated