On the Equilibrium of Query Reformulation and Document Retrieval

Shihao Zou, Guanyu Tao, Jun Wang, Weinan Zhang, Dell Zhang

TL;DR

This paper frames information retrieval (IR) as a strategic game between a query formulator and a retrieval model. By analyzing their interactions through game theory, they propose new algorithms that jointly optimize both components, leading to improved performance in text retrieval and item recommendation. This approach offers a more holistic way to understand and enhance IR systems.

What Problem Does This Paper Address?

Traditional information retrieval systems often tackle query reformulation (how to best express a user's need) and document relevance estimation (how to score documents for a given query) as separate problems. However, these two aspects are deeply intertwined. A better query can lead to more accurate relevance scores, and improved relevance feedback can inform a better query. This paper addresses the challenge of effectively modeling and optimizing this interplay, recognizing that treating them independently might miss opportunities for synergistic improvement. They aim to bridge this gap by viewing the entire IR process as a strategic interaction between two "players."

Methods

The core of this paper is the application of game theory, specifically normal-form games, to model the relationship between query reformulation and document retrieval.

  • Two-Player Game: The system is modeled as a two-player game:
  • Query Formulator (Q): Aims to create the optimal query to maximize its utility, which is based on the relevance scores provided by the retrieval model.
  • Retrieval Modeler (M): Aims to produce document relevance scores that maximize its own utility, typically based on training data and the formulated query.
  • Equilibrium: The system reaches an equilibrium when neither player can improve its outcome by unilaterally changing its strategy, meaning they are best responses to each other.
  • Utility Functions: The paper distinguishes between two scenarios based on utility functions:
  • Partnership Game (Standard Relevance Feedback): When both players share the same objective function (e.g., maximizing the separation of relevant and non-relevant documents), they form a partnership.
  • General-Sum Game (Pseudo Relevance Feedback): When players have different objectives (e.g., the query formulator relies on the retrieval model's output, which might not perfectly align with the retrieval model's own objective), it becomes a general-sum game. This is particularly relevant for pseudo relevance feedback where user feedback is simulated.
  • Algorithms: Based on this framework, they propose iterative learning algorithms (Conv-Q, Conv-M, Equil-Q&M) that update either the query, the retrieval model, or both simultaneously until an equilibrium is reached.

Datasets

  • Text Retrieval: TREC disks 4 & 5. This dataset consists of documents, topics (queries), and judged relevance judgments.
  • Item Recommendation: Movielens (100k) dataset. This is a standard dataset for evaluating recommender systems.

Key Insights and Ideas

  • IR as a Strategic Game: The most significant insight is framing IR as a strategic game. This perspective naturally captures the interdependence of query formulation and relevance estimation, moving beyond treating them as isolated tasks.
  • Different Game Types: The distinction between partnership and general-sum games based on the utility functions is crucial. It explains why different feedback mechanisms (standard vs. pseudo relevance feedback) lead to different interaction dynamics and potential outcomes.
  • Pseudo Relevance Feedback and Query Drift: The paper highlights how pseudo relevance feedback, due to potentially misaligned objectives, can lead to "query drift" (queries moving away from the true information need). However, their game-theoretic approach, by jointly optimizing both players, can mitigate this issue.
  • Synergistic Improvement: The core idea is that by coordinating the query formulation and retrieval model, the system can achieve better overall performance than optimizing each component in isolation.

Key Results

  • Text Retrieval:
    • The proposed Equil-Q&M algorithm (joint optimization) consistently outperformed baseline methods (Naive, Rocchio) and individual optimization approaches (Conv-Q, Conv-M) across various metrics (NDCG, MAP, MRR, Precision).
  • For standard relevance feedback, Equil-Q&M achieved significant improvements, demonstrating the benefit of coordinated learning.
  • For pseudo relevance feedback, Equil-Q&M also showed superior performance, effectively preventing query drifts that could plague simpler approaches.
  • Item Recommendation:
    • Similar to text retrieval, the Equil-Q&M approach for user-based item recommendation outperformed Conv-Q and Conv-M, showing slight but consistent improvements.
  • The paper notes that while Conv-M (retrieval model iteration) might not perform as well in later stages, Equil-Q&M can correct this and achieve better results.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that the retrieval models used in the experiments are relatively simple (e.g., linear models). More complex models could be explored.
  • For item recommendation, the study was limited to the Movielens (100k) dataset, and scalability to larger datasets is a future direction.
  • The paper assumes a fixed information need throughout a session.
  • Future Work:
    • Deeper exploration of utility function design to further optimize equilibrium performance.
  • Investigating more real-world application scenarios like online advertising and social network recommendation.
  • Exploring more efficient Nash equilibrium learning techniques, potentially using reinforcement learning.
  • Extending the normal-form game to an extensive-form game to handle the dynamic nature of information retrieval sessions.

Summary updated

Abstract

In this paper, we study jointly query reformulation and document relevance estimation, the two essential aspects of information retrieval (IR). Their interactions are modelled as a two-player strategic game: one player, a query formulator, taking actions to produce the optimal query, is expected to maximize its own utility with respect to the relevance estimation of documents produced by the other player, a retrieval modeler; simultaneously, the retrieval modeler, taking actions to produce the document relevance scores, needs to optimize its likelihood from the training data with respect to the refined query produced by the query formulator. Their equilibrium or equilibria will be reached when both are the best responses to each other. We derive our equilibrium theory of IR using normal-form representations: when a standard relevance feedback algorithm is coupled with a retrieval model, they would share the same objective function and thus form a partnership game; by contrast, pseudo relevance feedback pursues a rather different objective than that of retrieval models, therefore the interaction between them would lead to a general-sum game (though implicitly collaborative). Our game-theoretical analyses not only yield useful insights into the two major aspects of IR, but also offer new practical algorithms for achieving the equilibrium state of retrieval which have been shown to bring consistent performance improvements in both text retrieval and item recommendation.
BibTeX
@inproceedings{zou2018equilibrium,
  author = {Shihao Zou and Guanyu Tao and Jun Wang and Weinan Zhang and Dell Zhang},
  title = {{On the Equilibrium of Query Reformulation and Document Retrieval}},
  booktitle = {ICTIR},
  year = {2018},
  doi = {10.1145/3234944.3234962},
}
Figure