Text-Based Information Retrieval Using Exponentiated Gradient Descent

Ron Papka, James P. Callan, Andrew G. BartoNeurIPS 1996 · OpenReview

TL;DR

This paper demonstrates that the Exponentiated Gradient Descent (EG) algorithm significantly outperforms traditional methods like Rocchio and Least Mean Squared (LMS) for weighting terms in expanded search queries. Its multiplicative update rule makes it exceptionally robust to the "noise" of irrelevant terms, a common hurdle in large-scale information retrieval.

The Challenge of Query Expansion

In Information Retrieval (IR), users often provide short, ambiguous natural-language queries. To improve results, systems use query expansion, adding related terms to the search to cast a wider net. However, this creates a "needle in a haystack" problem: how do you assign the correct weight (importance) to these newly added terms?

If a system gives too much weight to an irrelevant term, search results quickly become noisy. Traditional methods, like the Rocchio algorithm, use fixed formulas that don't always adapt well to specific document collections. The authors sought to determine if single-neuron learning algorithms could "learn" better weights from a small set of labeled training data (documents marked as relevant or non-relevant).

Methods: Additive vs. Multiplicative Learning

The researchers compared two primary learning algorithms against standard baselines:

  1. Least Mean Squared (LMS): An additive update rule. It adjusts weights by adding or subtracting a value based on the error, minimizing the squared Euclidean distance between the current weights and the ideal weights.
  2. Exponentiated Gradient Descent (EG): A multiplicative update rule. Instead of adding, it multiplies weights by an exponential factor. This approach minimizes relative entropy (Kullback-Leibler divergence).

The Secret Sauce: The authors used a "pocketing" technique. Instead of just taking the final result of the gradient descent, they tested the weights every 1,000 iterations and "pocketed" (saved) the best-performing set based on precision and recall.

Datasets

The study utilized a massive benchmark for its time:

  • Queries: 100 natural-language queries from the TREC (Text REtrieval Conference) topics 51-150.
  • Corpus: The Tipster collection, totaling 3.4 gigabytes of text (over 1 million documents) from sources like the Associated Press, Wall Street Journal, and Federal Register.
  • Setup: Volumes 1 and 2 were used for training (averaging 280 relevant and 1,236 non-relevant documents per query), while Volume 3 was reserved for testing.

Key Insights

  • Multiplicative vs. Additive: The core finding is that EG is fundamentally better suited for IR because it can "zero out" irrelevant terms much faster than LMS. In a query expanded by 1,000 terms, most terms are useless noise. EG’s exponential nature allows it to suppress these irrelevant attributes rapidly.
  • Robustness to Irrelevant Features: The paper confirms the Kivinen-Warmuth hypothesis: EG suffers significantly less from irrelevant attributes than LMS. While LMS gets "distracted" by the sheer volume of terms, EG stays focused on the high-signal keywords.
  • Statistical Filtering vs. Learning: The results suggest that while learning is powerful, it’s still better to use a statistical filter to pick the top 50 terms first rather than throwing 1,000 terms at the algorithm and expecting it to do all the selection itself.

Key Results

The researchers evaluated performance using R-Precision (RP) for ranking and Lower Bound Accuracy (LBA) for classification.

50-Term Expansion

When expanding queries by 50 terms, EG achieved an RP of 40.3, significantly beating the Rocchio baseline (33.4) and LMS (32.5). This represents a roughly 20% improvement in ranking over the industry standard.

Performance with 50-term expansion

1000-Term Expansion (The Stress Test)

To test robustness, the query was flooded with 1,000 terms. Under this stress test, the performance of Rocchio and LMS plummeted to ~20 RP. However, EG remained remarkably stable, maintaining an RP of 35.0.

Performance with 1000-term expansion

Across both scenarios, EG consistently provided the highest classification accuracy (LBA), correctly identifying thousands more relevant documents than the other approaches.

Limitations and Future Work

  • Sampling Bias: The authors noted that LMS and EG require different training strategies. LMS performed better with uniform random sampling, while EG required "balanced" sampling (alternating between relevant and non-relevant examples) to avoid being overwhelmed by the vast number of non-relevant documents.
  • Thresholding: While EG is excellent at ranking documents, finding the perfect "cutoff" point (threshold) to decide if a document is strictly relevant or not remains difficult. There was a notable gap between the "Potential LBA" and the "Actual LBA" achieved in practice.
  • New Contenders: The paper briefly mentions that newer optimization algorithms, like DFO (Derivative-Free Optimization), might be competitive with EG under certain parameter settings, suggesting a need for further head-to-head comparisons.

Summary updated

Abstract

The following investigates the use of single-neuron learning algo(cid:173) rithms to improve the performance of text-retrieval systems that accept natural-language queries. A retrieval process is explained that transforms the natural-language query into the query syntax of a real retrieval system: the initial query is expanded using statis(cid:173) tical and learning techniques and is then used for document ranking and binary classification. The results of experiments suggest that Kivinen and Warmuth's Exponentiated Gradient Descent learning algorithm works significantly better than previous approaches.
BibTeX
@inproceedings{papka1996text,
  author = {Ron Papka and James P. Callan and Andrew G. Barto},
  title = {{Text-Based Information Retrieval Using Exponentiated Gradient Descent}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1996},
  url = {https://openreview.net/forum?id=HyNPrDbdZS},
}
Figure