Conversational Recommendation: Theoretical Model and Complexity Analysis

• URL: http://arxiv.org/abs/2111.05578v2
• Date: Fri, 12 Nov 2021 16:39:27 GMT
• Title: Conversational Recommendation: Theoretical Model and Complexity Analysis
• Authors: Tommaso Di Noia, Francesco Donini, Dietmar Jannach, Fedelucio Narducci, Claudio Pomo
• Abstract summary: We present a theoretical, domain-independent model of conversational recommendation. We show that finding an efficient conversational strategy is NP-hard. We also show that catalog characteristics can strongly influence the efficiency of individual conversational strategies.
• Score: 6.084774669743511
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recommender systems are software applications that help users find items of interest in situations of information overload in a personalized way, using knowledge about the needs and preferences of individual users. In conversational recommendation approaches, these needs and preferences are acquired by the system in an interactive, multi-turn dialog. A common approach in the literature to drive such dialogs is to incrementally ask users about their preferences regarding desired and undesired item features or regarding individual items. A central research goal in this context is efficiency, evaluated with respect to the number of required interactions until a satisfying item is found. This is usually accomplished by making inferences about the best next question to ask to the user. Today, research on dialog efficiency is almost entirely empirical, aiming to demonstrate, for example, that one strategy for selecting questions is better than another one in a given application. With this work, we complement empirical research with a theoretical, domain-independent model of conversational recommendation. This model, which is designed to cover a range of application scenarios, allows us to investigate the efficiency of conversational approaches in a formal way, in particular with respect to the computational complexity of devising optimal interaction strategies. Through such a theoretical analysis we show that finding an efficient conversational strategy is NP-hard, and in PSPACE in general, but for particular kinds of catalogs the upper bound lowers to POLYLOGSPACE. From a practical point of view, this result implies that catalog characteristics can strongly influence the efficiency of individual conversational strategies and should therefore be considered when designing new strategies. A preliminary empirical analysis on datasets derived from a real-world one aligns with our findings.

Related papers

• ProCIS: A Benchmark for Proactive Retrieval in Conversations [21.23826888841565]
  We introduce a large-scale dataset for proactive document retrieval that consists of over 2.8 million conversations. We conduct crowdsourcing experiments to obtain high-quality and relatively complete relevance judgments. We also collect annotations related to the parts of the conversation that are related to each document, enabling us to evaluate proactive retrieval systems.
  arXiv  Detail & Related papers  (2024-05-10T13:11:07Z)
• Dialogue Agents 101: A Beginner's Guide to Critical Ingredients for Designing Effective Conversational Systems [29.394466123216258]
  This study provides a comprehensive overview of the primary characteristics of a dialogue agent, their corresponding open-domain datasets, and the methods used to benchmark these datasets. We propose UNIT, a UNified dIalogue dataseT constructed from conversations of existing datasets for different dialogue tasks capturing the nuances for each of them.
  arXiv  Detail & Related papers  (2023-07-14T10:05:47Z)
• FCC: Fusing Conversation History and Candidate Provenance for Contextual Response Ranking in Dialogue Systems [53.89014188309486]
  We present a flexible neural framework that can integrate contextual information from multiple channels. We evaluate our model on the MSDialog dataset widely used for evaluating conversational response ranking tasks.
  arXiv  Detail & Related papers  (2023-03-31T23:58:28Z)
• GODEL: Large-Scale Pre-Training for Goal-Directed Dialog [119.1397031992088]
  We introduce GODEL, a large pre-trained language model for dialog. We show that GODEL outperforms state-of-the-art pre-trained dialog models in few-shot fine-tuning setups. A novel feature of our evaluation methodology is the introduction of a notion of utility that assesses the usefulness of responses.
  arXiv  Detail & Related papers  (2022-06-22T18:19:32Z)
• Suggesting Relevant Questions for a Query Using Statistical Natural Language Processing Technique [0.0]
  Suggesting similar questions for a user query has many applications ranging from reducing search time of users on e-commerce websites, training of employees in companies to holistic learning for students. The use of Natural Language Processing techniques for suggesting similar questions is prevalent over the existing architecture.
  arXiv  Detail & Related papers  (2022-04-26T04:30:16Z)
• What Does The User Want? Information Gain for Hierarchical Dialogue Policy Optimisation [3.1433893853959605]
  optimisation via reinforcement learning (RL) is susceptible to sample inefficiency and instability. We propose the usage of an intrinsic reward based on information gain to address this issue. Our algorithm, which we call FeudalGain, achieves state-of-the-art results in most environments of the PyDial framework.
  arXiv  Detail & Related papers  (2021-09-15T07:21:26Z)
• Analysing Mixed Initiatives and Search Strategies during Conversational Search [31.63357369175702]
  We present a model for conversational search -- from which we instantiate different observed conversational search strategies, where the agent elicits: (i) Feedback-First, or (ii) Feedback-After. Our analysis reveals that there is no superior or dominant combination, instead it shows that query clarifications are better when asked first, while query suggestions are better when asked after presenting results.
  arXiv  Detail & Related papers  (2021-09-13T13:30:10Z)
• Dialogue History Matters! Personalized Response Selectionin Multi-turn Retrieval-based Chatbots [62.295373408415365]
  We propose a personalized hybrid matching network (PHMN) for context-response matching. Our contributions are two-fold: 1) our model extracts personalized wording behaviors from user-specific dialogue history as extra matching information. We evaluate our model on two large datasets with user identification, i.e., personalized dialogue Corpus Ubuntu (P- Ubuntu) and personalized Weibo dataset (P-Weibo)
  arXiv  Detail & Related papers  (2021-03-17T09:42:11Z)
• Learning an Effective Context-Response Matching Model with Self-Supervised Tasks for Retrieval-based Dialogues [88.73739515457116]
  We introduce four self-supervised tasks including next session prediction, utterance restoration, incoherence detection and consistency discrimination. We jointly train the PLM-based response selection model with these auxiliary tasks in a multi-task manner. Experiment results indicate that the proposed auxiliary self-supervised tasks bring significant improvement for multi-turn response selection.
  arXiv  Detail & Related papers  (2020-09-14T08:44:46Z)
• Seamlessly Unifying Attributes and Items: Conversational Recommendation for Cold-Start Users [111.28351584726092]
  We consider the conversational recommendation for cold-start users, where a system can both ask the attributes from and recommend items to a user interactively. Our Conversational Thompson Sampling (ConTS) model holistically solves all questions in conversational recommendation by choosing the arm with the maximal reward to play.
  arXiv  Detail & Related papers  (2020-05-23T08:56:37Z)
• A Bayesian Approach to Conversational Recommendation Systems [60.12942570608859]
  We present a conversational recommendation system based on a Bayesian approach. A case study based on the application of this approach to emphstagend.com, an online platform for booking entertainers, is discussed.
  arXiv  Detail & Related papers  (2020-02-12T15:59:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.