Using Random Walks for Question-focused Sentence Retrieval

Jahna Otterbacher, Günes Erkan, Dragomir R. RadevEMNLP 2005 · OpenReview

TL;DR

This paper introduces "topic-sensitive LexRank," a novel graph-based approach for retrieving sentences that answer specific questions within complex, multi-event news stories. It significantly outperforms a baseline method by better capturing sentence relevance to the question and inter-sentence relationships, crucial for dynamic news narratives.

What Problem Does This Paper Address?

Traditional question answering (QA) systems often focus on single, static questions. However, users interacting with complex, evolving news stories (like disaster reports or political events) have a more nuanced information need. They might want to understand a story's timeline, specific sub-events, or how facts change over time. This requires retrieving sentences that not only match a query but also provide context and answer time-sensitive questions within a collection of documents. Existing passage retrieval methods often struggle with this dynamic and multi-faceted information need, especially when answers can be spread across multiple documents and evolve.

Methods

The core of the paper is the topic-sensitive LexRank algorithm. It builds upon the LexRank method, originally developed for generic multi-document summarization. LexRank represents sentences as nodes in a graph, with edges connecting sentences that are lexically similar above a certain threshold. Sentence importance is then determined by their eigenvector centrality within this graph.

The "topic-sensitive" aspect introduces two key modifications for question-focused retrieval:

  1. Relevance to the Question: Each sentence's score is influenced by its direct relevance to the input question. This is calculated using an IDF-weighted word overlap, a standard technique in query-based retrieval.
  2. Mixture Model: A crucial innovation is the use of a mixture model that combines the sentence's direct relevance to the question with its similarity to other high-scoring sentences. This is formalized as a random walk on a Markov chain, where transitions are guided by a "question bias" parameter (d). A high d prioritizes direct question relevance, while a lower d allows the walk to explore sentences similar to already relevant ones, capturing contextual information and related facts.

The similarity between sentences is calculated using cosine similarity, weighted by word Inverse Document Frequency (IDF).

Datasets

The authors created a new benchmark corpus consisting of 20 multi-document clusters of complex news stories. These stories covered topics like terror threats, plane crashes, political controversies, and natural disasters. The data was collected from various news sources.

For annotation:

  • Annotators generated factual questions central to understanding each story.
  • Two judges then annotated sentence-question pairs, indicating if a sentence contained a complete answer.
  • The corpus was split into training (11 clusters), development/test (3 clusters), and test (6 clusters) sets.
  • A total of 341 annotated questions were used.

Key Insights and Ideas

  • Inter-sentence similarity matters: Simply finding sentences similar to a query isn't enough. A sentence that is lexically similar to another highly relevant sentence might also contain valuable information, even if its direct overlap with the query is weaker. Topic-sensitive LexRank captures this by allowing "walks" between related sentences.
  • Dynamic nature of news requires flexible retrieval: Answers to questions in news stories can change over time. The proposed method's ability to consider multiple relevant sentences and their relationships is crucial for handling this dynamism.
  • Question bias is key: The "question bias" parameter (d) is critical. A high bias is needed to ensure direct relevance to the question, but a small probability of transitioning to lexically similar sentences is also beneficial for capturing context.
  • TRDR is a better metric for this task: While Mean Reciprocal Rank (MRR) is common, Total Reciprocal Document Rank (TRDR) is more appropriate here because complex stories often have multiple correct answers, and TRDR accounts for finding all of them.

Key Results

  • The topic-sensitive LexRank system (specifically LR[0.20,0.95]) significantly outperformed the baseline system in terms of average TRDR scores on the test set (0.9906 vs. 0.8673).
  • The improvement in TRDR was statistically significant with a p-value of 0.0619.
  • On the development/test set, all tested LexRank configurations outperformed the baseline.
  • The optimal similarity threshold for graph construction was found to be between 0.14 and 0.20, and a high question bias (d around 0.95) was generally preferred.

Limitations and Future Work

  • Mixed strategies: While the authors experimented with mixed strategies (using LexRank or baseline based on question characteristics), they did not find significant improvements over the pure LexRank approach. This suggests further exploration into adaptive strategies might be beneficial.
  • Chronological ordering: The system preserves chronological ordering, which is important for news stories. However, the paper notes that in cases of ties, the earlier published sentence is ranked higher. This could be a point of further refinement.
  • Future work: The authors suggest continuing to improve performance, potentially by developing more sophisticated mixed strategies using different configurations of LexRank. They also envision the retrieved sentences being fed into an answer identification component for further processing.

Summary updated

BibTeX
@inproceedings{otterbacher2005using,
  author = {Jahna Otterbacher and Günes Erkan and Dragomir R. Radev},
  title = {{Using Random Walks for Question-focused Sentence Retrieval}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2005},
  url = {https://openreview.net/forum?id=SjCRFT5aI27},
}
Figure