Source-linked AI summary
Task-Oriented Query Reformulation with Reinforcement Learning
Rodrigo Nogueira, Kyunghyun Cho
TL;DR
Search engines can miss relevant documents when query wording does not match document wording. This paper learns neural query reformulation with reinforcement learning, selecting terms to improve retrieval, and reports stronger performance than baselines while estimating substantial remaining headroom.
Problem
Search engines may miss relevant documents when the words in a query do not match the words in those documents.
Method
A neural reinforcement-learning agent selects terms from the initial query and retrieved documents to form reformulated queries for task-specific retrieval.
Results
The RL-based models outperform strong supervised and unsupervised baselines across the evaluated tasks, while RL-RNN-SEQ produces queries averaging 15 versus 47 words for RL-RNN.
Takeaways & Limitations
The framework can train an agent to use a black-box search engine for tasks including question answering, citation recommendation, and passage or snippet retrieval.
Takeaways & Limitations
The oracle upper bound is conservative, and the gap between the oracle and best method indicates substantial room for improvement.
Abstract
from arXiv · showhide
Search engines play an important role in our everyday lives by assisting us in finding the information we need. When we input a complex query, however, results are often far from satisfactory. In this work, we introduce a query reformulation system based on a neural network that rewrites a query to maximize the number of relevant documents returned. We train this neural network with reinforcement learning. The actions correspond to selecting terms to build a reformulated query, and the reward is the document recall. We evaluate our approach on three datasets against strong baselines and show a relative improvement of 5-20% in terms of recall. Furthermore, we present a simple method to estimate a conservative upper-bound performance of a model in a particular environment and verify that there is still large room for improvements.
1 Introduction
The paper frames automatic query reformulation as a reinforcement-learning problem: an agent selects terms from an initial query and its retrieved documents to improve retrieval. It evaluates this framework across tasks and introduces an upper-bound estimation method and a large academic dataset.
- 28-52% of web queries are modifications of previous queries, underscoring the prevalence of iterative reformulation when search results are inadequate.
- Term mismatch between queries and relevant documents can cause search engines to miss relevant documents.
- The proposed agent selects terms from the initial query and retrieved documents, treating the search engine as an environment that returns new document states.
- The black-box formulation supports training task-specific agents for question answering, citation recommendation, and passage or snippet retrieval.
- The study uses TREC-CAR and Jeopardy plus MS Academic, a new dataset with hundreds of thousands of query/relevant-document pairs.
- The paper contributes a reinforcement-learning framework and a simple method for estimating an RL model’s upper-bound performance in a given environment.
2 A Reinforcement Learning Approach
The method represents candidate terms with neural encoders and learns to select them using reinforcement learning, either independently or sequentially. Sequential generation addresses duplicate and overly long reformulated queries, while practical training uses retrieved-document terms and stabilization techniques.
- 2.1 Model Description: Candidate terms come from the original query and documents retrieved for it, and the model encodes query and term context with CNNs or RNNs.
- 2.1 Model Description: At test time, terms whose selection probabilities exceed ϵ are concatenated into a reformulated query used to retrieve new documents.
- 2.2 Sequence Generation: Independent term selection can duplicate terms and produce long queries, motivating a sequential generator that selects one term at a time and stops explicitly.
- 2.2 Sequence Generation: The sequential model uses an LSTM hidden state to condition each selection on the previously selected term and produce more concise queries.
- 2.3 Training: Restricting candidates to retrieved-document terms makes inference faster and reinforcement-learning training practical, while leaving whole-vocabulary selection for future work.
- 2.3 Training: REINFORCE training uses the retrieval reward and a value-network baseline, with a small loss weight conjectured to stabilize learning by limiting extreme-reward fitting.
- 2.3 Training: Entropy regularization is added because peaked selection probabilities reduced exploration of terms that might yield better reformulated queries.
3 Related Work
Prior query-reformulation methods include global and local expansion, relevance models, supervised term selection, iterative graph navigation, and latent representations. The paper instead learns term-selection strategies with reinforcement learning for open-domain queries.
- Local reformulation adjusts queries using initially retrieved documents, whereas global methods ignore that feedback; this work focuses on local methods.
- Relevance models use pseudo-relevance feedback and language-model word co-occurrence without requiring query/relevant-document training pairs.
- Supervised approaches label candidate terms by their individual retrieval contribution and train classifiers to select expansion terms.
- Iterative graph-based reformulation can be slow because the search engine is queried after each newly added term, unlike this method’s batched term additions.
- Alternative latent-representation methods use click-through or anchor-text data, whereas this approach learns term selection through reinforcement learning.
- Compared with a related iterative RL method using domain-specific templates, this work assumes open-domain queries.
4 Experiments
The experiments compare raw, unsupervised, supervised, and reinforcement-learning query reformulation methods across three datasets using retrieval metrics and oracle bounds. RL models are evaluated with R@40 as their training reward, while the oracle analyses estimate remaining potential.
- Baselines and proposed models: The evaluation compares raw retrieval with PRF, embedding-similarity, supervised, and multiple RL-based reformulation methods.The RL variants include feed-forward, CNN, RNN, and sequential-generator models.
- Datasets: The experiments use TREC-CAR, Jeopardy, and Microsoft Academic datasets with query-document relevance judgments.TREC-CAR uses Wikipedia section queries, Jeopardy uses questions and answer-article documents, and Microsoft Academic uses paper titles with cited papers as answers.
- Metrics and reward: Recall@K measures relevant documents among the top-K results, while precision and mean average precision provide complementary retrieval measures.Recall is the main metric because reformulation aims to increase the proportion of relevant returned documents; mean average precision also values document rank.
- Metrics and reward: R@40 is used as the reward for training the RL-based models because it has been effective for improving other evaluation metrics.The reported test-set results use R@40 as the RL training reward.
- Oracle bounds: The SL-Oracle assumes independent term contributions, whereas the RL-Oracle estimates a conservative upper bound without that independence assumption.The RL-Oracle averages rewards from models trained on small subsets until overfitting, but may remain below undiscovered reformulation strategies.
- Implementation details: The reported results use two search-and-reformulation rounds because additional reformulation produced no significant improvement.Although the framework supports multiple rounds, the experiments did not find a significant gain from reformulating more than once.
5 Results and Discussion
The results show that reinforcement-learning reformulation models outperform supervised and unsupervised baselines, while shorter sequential queries trade a small performance decrease for faster retrieval. Qualitative analyses indicate task-specific term selection, and oracle gaps reveal substantial improvement potential.
- RL-based models outperform supervised and unsupervised reformulation baselines, with supervised methods generally between the two groups.
- RL-RNN-SEQ produces queries averaging 15 words versus 47 for RL-RNN, while performing slightly worse and potentially enabling faster retrieval.The authors identify RL-RNN-SEQ as a possible production candidate because of its shorter queries.
- The oracle-to-best-model gap indicates substantial room for improvement, possibly because term-selection learning is difficult under partial observability.
- Only a small subset of candidate terms is useful, suggesting that the method learned efficient selection despite relevant terms being infrequent.
- Scalability: Number of Terms vs Recall: RL models benefit from additional candidate terms, whereas classical PRF quickly saturates.The best RL model used the maximum candidate-term set that fit on a single GPU, and further gains were expected with more computational resources.
- Qualitative Analysis: RL-CNN assigns higher probabilities to query-related terms but also selects common neutral words because the reward does not penalize them.
- Qualitative Analysis: RL-CNN reformulation examples retrieve more relevant documents than the original queries, addressing failures caused by relying on surface text overlap.
- Qualitative Analysis: Task-specific training produces different reformulations: TREC-CAR favors semantically similar terms, while Jeopardy favors proper nouns.
6 Conclusion
The paper introduces task-oriented automatic query reformulation through reinforcement learning and reports that it outperforms strong baselines across three tasks. Oracle analysis indicates meaningful room for further development, including iterative reformulation, multimodal information, and improved reinforcement learning for partially observable environments.
- The framework trains an agent to perform task-oriented automatic query reformulation using a search engine.
- The empirical evaluation shows that the approach outperforms strong baselines in three separate tasks.
- Oracle analysis reveals meaningful room for further development in iterative reformulation, additional modalities, and reinforcement learning for partially observable environments.