会话推荐:理论模型和复杂性分析(CS)

推荐系统是帮助用户在信息过载的情况下以个性化的方式找到感兴趣的项目的软件应用程序，利用关于个人用户的需求和偏好的知识。在会话推荐方法中，这些需求和偏好是由系统在一个交互式的、多回合的对话中获得的。在文献中，驱动这种对话框的一种常见方法是逐步询问用户关于所需和不需要的项特性或单个项的偏好。在此背景下的一个中心研究目标是效率，即在找到令人满意的物品之前，根据所需的交互次数进行评估。这通常是通过推断最好的下一个问题来问用户。如今，关于对话效率的研究几乎完全是实证的，目的是证明，例如，在给定的应用程序中，一种选择问题的策略比另一种更好。通过这项工作，我们用一个理论的、领域独立的会话推荐模型来补充实证研究。该模型旨在涵盖一系列应用场景，允许我们以正式的方式研究会话方法的效率，特别是设计最佳交互策略的计算复杂性。通过这样的理论分析，我们表明找到一个有效的会话策略是NP-hard，而且在一般的PSPACE中，但对于特定种类的目录，上界降低到POLYLOGSPACE。从实践的角度来看，这一结果表明目录特征可以强烈地影响个体会话策略的效率，因此在设计新策略时应考虑到。对来自真实世界的数据集的初步实证分析与我们的发现一致。

原文题目：Conversational Recommendation:Theoretical Model and Complexity Analysis

原文：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.