Query Expansion in Information Retrieval Systems using a Bayesian Network-Based Thesaurus

Luis M. de Campos, Juan M. Fernández-Luna, Juan F. HueteUAI 1998

TL;DR

This paper introduces a novel query expansion method for Information Retrieval (IR) systems that leverages a Bayesian network as a dynamic, collection-specific thesaurus. By learning the relationships between terms in a document collection, the system can intelligently suggest new terms to broaden or refine user queries, leading to improved retrieval effectiveness.

What Problem Does This Paper Address?

Information Retrieval (IR) systems aim to identify relevant documents for a user's information need, typically expressed as a query. A major challenge is that user queries are often vague, and standard IR systems may struggle to retrieve all relevant documents or may return too many irrelevant ones. Query expansion is a technique to address this by automatically adding new terms to the original query. However, traditional thesauri are often static and general. This paper tackles the problem of creating a more adaptive and context-aware query expansion mechanism by building a thesaurus tailored to the specific document collection being searched.

Methods

The core of this work is the construction of a Bayesian network that acts as a thesaurus. The authors propose a learning algorithm to build this network from a document collection. Specifically, they learn a "polytree" (a directed acyclic graph where there's at most one undirected path between any two nodes) where nodes represent terms and edges represent probabilistic dependencies.

The learning process involves:

  1. Dependency Measurement: Calculating the dependency between pairs of terms using Kullback-Leibler cross-entropy (mutual information).
  2. Skeleton Construction: Building a maximum weight spanning tree (MWST) based on these dependency measures. Prim's algorithm is used for this. An independency test is incorporated to refine edge weights and avoid linking terms that are more independent than dependent.
  3. Edge Orientation: Orienting the edges of the tree to form a polytree, ensuring that the network accurately reflects the probabilistic relationships between terms.

Once the Bayesian network thesaurus is built, query expansion proceeds by:

  1. Evidence Propagation: Setting the terms in the user's query as "relevant" evidence in the network.
  2. Inference: Propagating this evidence through the polytree to calculate the posterior probability of relevance for all other terms.
  3. Term Selection: Selecting terms with a posterior probability above a certain threshold to be added to the original query. The weights of these added terms are their posterior probabilities.

Datasets

The authors evaluated their method on three standard Information Retrieval test collections:

  • Adi: 82 documents, 828 terms, 35 queries.
  • Cranfield: 1398 documents, 3857 terms, 225 queries.
  • Medlars: 1033 documents, 7170 terms, 30 queries.

These collections were chosen for their differing characteristics, particularly in the number of terms. The experiments used the "Smart" IR system, a well-known implementation of the vector space model, as the baseline retrieval system.

Key Insights and Ideas

  • Collection-Specific Thesaurus: The most significant idea is using a Bayesian network learned from the document collection itself to create a dynamic thesaurus. This allows the thesaurus to capture nuanced relationships specific to the domain of the documents, unlike static, general-purpose thesauri.
  • Bayesian Networks for Term Relationships: Bayesian networks are a powerful tool for modeling probabilistic dependencies. Applying them to represent term co-occurrence and infer relationships offers a principled way to understand how terms relate to each other within a corpus.
  • Polytrees for Efficiency: The choice of learning a polytree (a singly connected network) is a pragmatic decision. It balances the expressiveness of Bayesian networks with the computational tractability of inference algorithms, which is crucial given the large number of terms in typical document collections.
  • Threshold Sensitivity: The experiments revealed that the threshold used to select terms for expansion can significantly impact retrieval performance, suggesting that this parameter is crucial and might benefit from adaptive selection strategies.

Key Results

The query expansion method demonstrated a moderate improvement in retrieval effectiveness across the tested collections.

  • For the Adi collection, average precision increased by 16.53% with query expansion.
  • For the Medlars collection, average precision increased by 13.87%.
  • For the Cranfield collection, the improvement was 4.62%, but the paper notes that this collection showed more sensitivity to the expansion threshold.

The authors observed that the confidence level used for independency tests in the Bayesian network learning had less impact than the threshold for selecting expansion terms. They also noted that for Adi and Medlars, the method consistently outperformed the baseline across various experimental settings.

Limitations and Future Work

Limitations: * The authors acknowledge that the improvement in retrieval effectiveness is "moderate" and "collection-dependent." * The choice of a polytree, while efficient, is a simplification that might limit the expressiveness of the learned model compared to more complex Bayesian networks. * The paper does not delve deeply into why the method performed better on Adi and Medlars than Cranfield, suggesting this requires further study of collection characteristics.

Future Work: * More Complex Structures: Develop more sophisticated Bayesian network learning algorithms to create structures beyond polytrees, aiming for greater accuracy and closer representation of real-world term dependencies. This includes incorporating conditional dependencies. * Document Networks: Extend the model to incorporate document representations and learn relationships between documents themselves. * Inference Optimization: Improve the efficiency of the propagation (inference) process, potentially through pre-processing or more advanced techniques. * Adaptive Thresholding: Develop heuristics for automatically selecting the expansion threshold based on collection characteristics (e.g., inverse document frequencies). * Full Bayesian Network IR System: The long-term goal is to develop an entire IR system based on Bayesian networks.

Summary updated

BibTeX
@inproceedings{campos1998query,
  author = {Luis M. de Campos and Juan M. Fernández-Luna and Juan F. Huete},
  title = {{Query Expansion in Information Retrieval Systems using a Bayesian Network-Based Thesaurus}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1998},
}
Figure