Dynamic Facet Selection by Maximizing Graded Relevance

Michael Glass, Md Faisal Mahbub Chowdhury, Yu Deng, Ruchi Mahindru, Nicolas Rodolfo Fauceglia, Alfio Gliozzo, Nandana MihindukulasooriyaACL 2021

TL;DR

This paper introduces "Optimistic Facet Selection," a novel unsupervised approach for dynamic facet generation in interactive search. By aiming to maximize the expected discounted cumulative gain (DCG), it significantly improves document ranking compared to existing methods, offering a more effective way for users to refine their search queries.

What Problem Does This Paper Address?

Traditional faceted search systems often rely on pre-defined taxonomies, which are costly to maintain and lack flexibility. Dynamic Faceted Search (DFS) aims to overcome this by generating facets at runtime based on the user's query and search results. However, a key challenge in DFS is selecting the best set of dynamic facets to present to the user from a potentially large pool of candidates. Simply generating many facets isn't helpful; the goal is to present those that will most effectively guide the user towards their information need and improve the ranking of relevant documents. This paper tackles the problem of how to intelligently select a subset of dynamically generated facets that maximizes the overall quality of the search results.

Methods

The core of the paper is the "Optimistic Facet Selection" algorithm. It operates under two key assumptions:

  1. Optimism: Users will choose the facet that leads to the best possible improvement in search result ranking.
  2. Relevance Probability: The likelihood of a document being relevant is approximated by its rank in the initial search results.

The algorithm first generates candidate facets by extracting terms from search results that appear frequently and have a high cosine similarity to the original query. Then, it employs a strategy to select a subset of these candidates. This selection process is guided by the goal of maximizing the expected Discounted Cumulative Gain (DCG), a standard metric for evaluating search result quality. The paper describes a two-phase approach:

  • Greedy Phase: Iteratively adds the facet that provides the largest expected improvement in DCG to the facet set.
  • Local Search Phase: Attempts to swap facets within the current set with better candidates to further optimize the DCG.

This process can be repeated until no further improvement is observed.

Datasets

The authors evaluated their approach on two datasets:

  1. TechQA Benchmark: An existing dataset for technical customer support questions, aligned with a corpus of IBM Technotes documents. This dataset was chosen because it's frequently used in recent faceted search research.
  2. Stackoverflow Benchmark: A newly created dataset developed by the authors. It consists of 883 queries extracted from Stack Overflow forum threads, where accepted answers contain links to documents in the Technotes corpus. This dataset was created to test the generality of their approach on noisier, real-world queries.

Key Insights and Ideas

  • Optimism as a Driving Force: The "optimistic" assumption that users will pick the best facet is a clever way to frame the problem of facet selection. It allows the algorithm to aim for the highest possible outcome, even if it's not guaranteed.
  • Rank as a Proxy for Relevance: Using the initial document rank as a proxy for relevance probability is a pragmatic approach when explicit relevance judgments are unavailable or too costly to obtain.
  • Maximizing DCG for Interactive Search: Directly optimizing for DCG, a measure that considers graded relevance and rank, is a strong objective for improving the user's search experience in an interactive setting.
  • Unsupervised Generation is Key: The approach is unsupervised, meaning it doesn't require pre-defined taxonomies or external knowledge bases, making it more adaptable and scalable.

Key Results

  • Quantitative Improvements: The proposed "Optimistic DFS" approach demonstrated significant improvements over a strong baseline DFS method (Mihindukulasooriya et al., 2020) across all evaluated metrics (DCG, MRR, Hits@K) on both the TechQA and Stackoverflow datasets. For instance, on the Stackoverflow dataset, Hits@1 improved from 75 to 205.
  • Outperforming Strong IR Baselines: The approach also significantly enhanced the performance of the underlying strong IR baselines themselves.
  • Qualitative Evaluation: A Subject Matter Expert (SME) evaluated the generated facets for a sample of queries. The SME found that a substantial portion (89%) of the dynamically generated facets were "unseen in Post" (meaning not explicitly in the user's query text but relevant), and of those, 25% were relevant. Among the facets seen in the post, 82% were relevant.

Limitations and Future Work

  • Limitations:
    • The current approach relies on a simulated user-based evaluation (ORACLE), which might not perfectly capture real-world user behavior.
  • The relevance probability is approximated by rank, which is a simplification.
  • Future Work:
    • Leveraging the algorithm to automatically group generated facets by type.
  • Exploring the use of language models as knowledge bases for dynamic facet generation.
  • Developing an active learning component to explicitly learn from user feedback and fine-tune NLP models.
  • The authors envision transforming interactive search into a learnable knowledge discovery process.

Summary updated

BibTeX
@inproceedings{glass2021dynamic,
  author = {Michael Glass and Md Faisal Mahbub Chowdhury and Yu Deng and Ruchi Mahindru and Nicolas Rodolfo Fauceglia and Alfio Gliozzo and Nandana Mihindukulasooriya},
  title = {{Dynamic Facet Selection by Maximizing Graded Relevance}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
}

Loading related content...

Figure