Seeker: Real-Time Interactive Search

Ari Biswas, Thai T. Pham, Michael Vogelsong, Benjamin Snyder, Houssam Nassif

TL;DR

Seeker is a novel real-time interactive search system that allows users to dynamically refine search results using simple "like" and "dislike" feedback. This approach is particularly useful when users can't precisely articulate their needs in words, enabling a more intuitive and adaptive search experience akin to having a personal shopper.

What Problem Does This Paper Address?

Traditional search engines, whether keyword-based or representation-based (like visual search), often fall short when users struggle to articulate their desires. Users might have a clear mental image of what they're looking for but lack the precise vocabulary or a suitable example (like a photo) to initiate a search. Furthermore, existing systems are largely static; once a search is performed, the results are fixed, and adapting them requires a new query. Seeker tackles this by enabling users to iteratively refine search results in real-time through simple feedback, bridging the gap between a user's implicit understanding and the system's explicit output.

Methods

Seeker's core innovation lies in its real-time adaptation to user feedback. The system models user preferences by converting "likes" and "dislikes" into "preference pairs." These pairs are then used to estimate a probability distribution over the entire catalog, indicating the likelihood of each item being the user's desired "target."

Key components include:

  • Pair Formation: Generates preference pairs (liked item $a_i$, disliked item $b_j$) from user feedback.
  • Target Estimator: Uses these pairs to estimate the probability of a catalog item being the hidden target, leveraging a probabilistic model that accounts for the distance between item embeddings and the target.
  • Item Recommendation: Employs a Boltzmann Exploration strategy. This method balances exploiting current knowledge (recommending items with high estimated probability) with exploring potentially better options. It uses a Gumbel-Max trick for efficient sampling and incorporates an annealing schedule to adjust the exploration-exploitation trade-off over time.

The system is designed to be agnostic to the underlying embedding representation, working with visual, textual, or audio features.

Datasets

The paper does not mention specific pre-existing datasets for training. Instead, it introduces a novel human-in-the-loop evaluation framework. This framework simulates user interactions with a catalog of 2228 items, where volunteers provide likes and dislikes to find a target item within a limited number of timesteps (K=15). This approach allows for quantitative evaluation of different search strategies under realistic user behavior.

Key Insights and Ideas

  • Ordinal Feedback is Powerful: Users can easily provide "like" or "dislike" feedback on item similarity, which is often more intuitive than precise verbal descriptions. This ordinal feedback is sufficient to guide the search effectively.
  • Real-time Adaptation is Crucial: The ability to dynamically update search results based on immediate user feedback transforms the search experience from a static query-response to an interactive discovery process.
  • Boltzmann Exploration Balances Needs: The Boltzmann exploration method, with its annealing schedule, proves effective at quickly converging on the target item while still allowing for exploration, which is vital in large and complex catalogs.
  • Human-in-the-Loop is Necessary for Evaluation: For interactive systems like Seeker, traditional offline evaluation metrics are insufficient. A human-in-the-loop setup is essential to capture the dynamic nature of user interaction and measure true effectiveness.

Key Results

The experimental results, based on the human-in-the-loop study, demonstrate the effectiveness of Seeker's Boltzmann exploration strategy.

  • Improved Recall: Seeker's Boltzmann exploration achieved the highest recall at various normalized rank cutoffs, meaning it was more likely to rank the target item within a desired percentile compared to other strategies like greedy or random exploration. For instance, it achieved a recall of 0.4 at a normalized rank of 0.02.
  • Faster Convergence: The Boltzmann exploration strategy also showed faster convergence, requiring fewer interactions (timesteps) on average to rank the target item better than a given percentile. This translates to a more efficient user experience.
  • Comparison to Baselines: Seeker's Boltzmann exploration consistently outperformed random exploration and performed better than greedy and noiseless (pure exploitation) strategies, especially at lower rank cutoffs.

Limitations and Future Work

The authors acknowledge several limitations and propose future research directions:

  • Catalog Size and Similarity: The experimental setup used a catalog of 2228 items, and the presence of many similar items made it challenging to surface the target item quickly. This suggests that performance might be even better with less similar items or larger catalogs where exploration is more critical.
  • Bipartite Preference Model: The current model treats likes and dislikes equally. Future work could explore a bipartite preference model that assigns different weights to likes and dislikes, as likes are intuitively more informative.
  • Incorporating Additional Feedback: The system currently relies solely on likes and dislikes. Future work could incorporate other forms of feedback, such as text or speech, by mapping them into embedding vectors.
  • Personalized Recommendations: The system could be further enhanced by incorporating user-specific embeddings to provide truly personalized search experiences.
  • Covariance in Sampling: The current sampling strategy doesn't explicitly account for the covariance between item features, which could be addressed in future work to improve recommendation quality.

Summary updated

Abstract

This paper introduces Seeker, a system that allows users to adaptively refine search rankings in real time, through a series of feedbacks in the form of likes and dislikes. When searching online, users may not know how to accurately describe their product of choice in words. An alternative approach is to search an embedding space, allowing the user to query using a representation of the item (like a tune for a song, or a picture for an object). However, this approach requires the user to possess an example representation of their desired item. Additionally, most current search systems do not allow the user to dynamically adapt the results with further feedback. On the other hand, users often have a mental picture of the desired item and are able to answer ordinal questions of the form: "Is this item similar to what you have in mind?" With this assumption, our algorithm allows for users to provide sequential feedback on search results to adapt the search feed. We show that our proposed approach works well both qualitatively and quantitatively. Unlike most previous representation-based search systems, we can quantify the quality of our algorithm by evaluating humans-in-the-loop experiments.
BibTeX
@inproceedings{biswas2019seeker,
  author = {Ari Biswas and Thai T. Pham and Michael Vogelsong and Benjamin Snyder and Houssam Nassif},
  title = {{Seeker: Real-Time Interactive Search}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2019},
  url = {https://openreview.net/forum?id=ZV8iOcvHNwM},
}

Loading related content...

Figure