TL;DR
This paper introduces "subtopic retrieval," a new information retrieval problem where the goal is to find documents covering diverse subtopics of a query, moving beyond traditional independent relevance assumptions. They propose novel evaluation metrics (S-recall, S-precision, WS-precision) and demonstrate that combining relevance with novelty measures, particularly using a mixture model for novelty, can improve retrieval performance, though relevance remains a dominant factor.
What Problem Does This Paper Address?
Traditional information retrieval (IR) systems typically assume that the relevance of a document is independent of other documents in the search results. This means each document is evaluated and ranked based on its own merit relative to the query. However, in many real-world scenarios, users are interested in a broader understanding of a topic, which often comprises multiple subtopics. For instance, a student researching "machine learning" might want documents covering various algorithms, applications, and theoretical underpinnings, not just a list of documents that are all highly relevant to a narrow interpretation of "machine learning."
This is the core of the "subtopic retrieval" problem: finding documents that collectively cover a diverse set of subtopics related to a user's query. This problem inherently violates the independent relevance assumption because the utility of a document can depend on what other documents have already been presented. For example, a document that covers a subtopic already well-represented in the top results might be less valuable than one covering a new, underexplored subtopic. Existing IR methods and evaluation metrics are ill-suited for this task, necessitating new approaches.
Methods
The authors propose a novel evaluation framework to address the challenges of subtopic retrieval.
- Evaluation Metrics:
- S-recall (Subtopic Recall): Measures the percentage of subtopics covered by the top K documents in a ranking.
- S-precision (Subtopic Precision): Compares the rank at which a specific subtopic recall level is achieved by a system to the rank achieved by an optimal system. This accounts for the "intrinsic difficulty" of a topic.
- WS-precision (Weighted Subtopic Precision): Extends S-precision by incorporating a cost for document redundancy, penalizing rankings that repeat subtopics. This is achieved by defining a cost function for a ranking that includes costs for presenting documents and processing subtopics.
- Retrieval Methods:
- Novelty Measures: To address the "dependent relevance" aspect, they explore ways to measure the novelty of a document relative to previously seen documents. They propose six novelty measures based on language models, including KL-divergence and mixture models. The MixAvg (mixture model, averaging novelty scores) emerged as the most effective.
- Cost-Based Combination: They combine relevance (using query likelihood, equivalent to KL-divergence) and novelty (using MixAvg) into a scoring function. This function balances retrieving relevant documents with avoiding redundant ones. The scoring function is parameterized by a ratio that reflects the trade-off between relevance and novelty.
- Greedy Ranking: A generic greedy algorithm is used to rank documents by iteratively selecting the document that best satisfies the scoring function at each step.
Datasets
The experiments were conducted using data from the TREC (Text RElevance Conference) interactive track. Specifically, they utilized document collections and relevance judgments from TREC-6, TREC-7, and TREC-8. The document collection was the Financial Times of London 1991-1994 collection (part of the TREC-7 ad hoc collection), approximately 500MB in size with 210,158 documents. For each topic, assessors identified subtopics and judged which documents covered them, creating binary relevance judgments for each document-subtopic pair. This dataset is a valuable resource for subtopic retrieval research as it provides explicit subtopic relevance judgments.
Key Insights and Ideas
- Dependent Relevance is Crucial: The paper strongly argues that traditional IR's assumption of independent relevance is a significant limitation for tasks like subtopic retrieval, where the value of a document is context-dependent.
- Novelty is More Than Just "Not Seen Before": Simply retrieving documents that haven't been seen is insufficient. The type of novelty matters, and a mixture model approach (MixAvg) proved more effective at capturing useful novelty than KL-divergence-based measures.
- Balancing Act: Relevance vs. Novelty: The core challenge is finding the right balance. While novelty is important for diversity, relevance remains paramount. The proposed cost-based combination method attempts to formalize this trade-off.
- Redundancy is a Cost: The WS-precision metric explicitly acknowledges that redundant documents incur a cost for the user, making it a more nuanced evaluation than simple S-precision.
- Relevance Dominates in Mixed Collections: When faced with a mix of relevant and non-relevant documents, the benefit of novelty is somewhat diminished, suggesting that robust relevance ranking is still the primary driver of performance.
Key Results
- Novelty Measures: Among the six novelty measures explored, the MixAvg (mixture model) consistently outperformed others, especially at higher subtopic recall levels.
- Cost-Based Combination: The cost-based method combining relevance and novelty showed consistent improvement over a baseline relevance ranking for the task of re-ranking relevant documents, particularly at higher recall levels.
- Mixed Document Ranking: For the more challenging task of ranking a mixed pool of relevant and non-relevant documents, the cost-based combination offered only slight improvements over the baseline. Pseudo-feedback also showed marginal gains.
- "Upper Bound" Performance: Even an advanced method using subtopic queries and a greedy set-covering algorithm (intended as an informal upper bound) only modestly improved S-precision (by ~20%) and WS-precision (by ~9%) over the best realistic methods. This highlights the difficulty of the subtopic retrieval task.
Limitations and Future Work
- Relevance Dominance: The authors acknowledge that in their experiments with mixed document collections, the gains from novelty were offset by the difficulty of maintaining high relevance ranking. This suggests that relevance is a dominating factor.
- Independent Treatment of Relevance and Novelty: A major deficiency noted is the independent treatment of relevance and novelty in their MMR-style approaches. They suggest future work should focus on directly measuring the relevance of the novel part of a document, rather than treating relevance and novelty as separate entities.
- Synthetic Data for Control: To better understand the interaction of relevance and redundancy, they propose using synthetic data to control factors like redundancy levels and the number of subtopics.
- User Study: While not explicitly stated as future work, the paper's focus on user utility implies that direct user studies would be valuable to validate the proposed metrics and methods.
Summary updated