Tools that interact vocally with users are becoming increasingly popular in the market, boosting industry and academia interest in them. In such environments, conversational recommender systems succeed in guiding users in situations of information overload. Through multiple interactions with users, such systems ask questions, filter the catalog in a personalized manner, and suggest items that are of potential interest to the consumer. In this context, conversational eficiency in terms of the number of required interactions often plays a fundamental role. This work introduces a theoretical and domain independent approach to support the eficiency analysis of a conversational recommendation engine. Observations from an empirical analysis align with our theoretical findings.
increase the eficiency of the dialog [8, 9, 10, 11, 12, 13, 14].
Today, research in the general area of recommender System-generated recommendations have become a systems, and specifically area of , is almost entirely common feature of modern online services such as e- empirical [15, 16, 17]. Such empirical studies are cercommerce sites, media streaming platforms, and social tainly important and insightful. However, little is known networks. In many cases, the suggestions made by the about the theoretical aspects of the underlying interactive underlying recommender systems are personalized ac- recommendation processes. Unfortunately, theoretical cording to the user’s tastes, needs, and preferences. In questions regarding, e.g., the computational complexity the most prominent applications of recommender sys- of determining a good or the best interaction strategy, tems, user preferences are estimated based on past user can not be answered without a formal characterization behaviors. However, there are several application do- of the overall problem. mains where no past interaction logs are available or With this work, we address this research gap and prowhere the user’s needs and preferences might difer each vide a theoretical model of conversational recommendatime the user interacts with the service (e.g., restaurant tion. The model is designed in a domain-independent recommendation for a party or a romantic dinner). In way and aims to cover a wide range of realistic applicasuch application settings, a multi-turn, interactive rec- tion scenarios. A conversational recommendation proommendation process is required, where the system’s cess is modeled as a sequence of states, where state trangoal is to learn about the user preferences to the extent sitions correspond to common user intents and conversathat appropriate recommendations can be made. Con- tional moves [18, 19, 20] that can be found in the literature. versational Recommender Systems () support such Since our model is agnostic about the application doprocesses and these systems received increased attention main and the algorithm that is used to select and rank in recent years [1, 2, 3, 4, 5, 6, 7]. the objects for recommendation (i.e., the recommenda
The preference elicitation process in such settings can tion algorithm) it serves as a basis to analyze important be implemented in diferent ways, ranging from prede- theoretical properties of . ifned fill-out forms to natural language interfaces—see The main contribution of this work1 is the study of the Jannach et al. [5] for an overview. In that context, a spe- computational complexity for finding an eficient convercific goal when designing a is to minimize the efort sational strategy in terms of number of dialog turns. In for users by asking as few questions as possible, i.e., to particular, we demonstrate that: (i) the problem of finding an eficient conversational strategy in terms of number of dialog turns is NP-hard, but in PSPACE; (ii) some specific factors of the item catalog influence the complexity of the problem; (iii) for a special class of catalogs, the upper bound lowers to POLYLOGSPACE. From a prac1An extended version of this work is available in Di Noia et al. [21]. tical perspective, our analysis leads to the observation that the eficiency of a conversation strategy is tied to the characteristics of the catalog. Observations from an empirical analysis on datasets based on MovieLens-1M support these theoretical considerations.
In our theoretical framework we assume a retrieval-based item filtering approach, which is commonly used in (b) the user can state that she dislikes every item critiquing-based and constraint-based approaches to rec- where a features is filled with a particular value ommendation [22, 23]. In critiquing approaches, users are (e.g., “I don’t like green cellphones”) presented with a recommendation soon in the dialogue and can then apply pre-defined critiques on the recom- The formalization of the interaction process described mendations, e.g., (“less $$”) [5]. In analogy to database- by Di Noia et al. [21] allow us to establish the results oriented approaches, we therefore use the term “query” mentioned above. when referring to positive user’s preferences. Negative preferences are modeled as constraints on disliked item 3. Empirical Analysis features. The retrieved items are then ranked according to any type of information, e.g., the popularity of cer- 3.1. Experimental Design tain items. In order to carry a general analysis, in our One main theoretical result is that the chosen conversaapproach we abstract from the details of this ranking. tion strategy (protocol) not only impacts the eficiency of
To model the conversational recommendation process, a CRS, but that the eficiency also depends on the characwe rely on the notion of state of a conversation, and teristics of the item catalog, e.g., in terms of the number what transformations this state can be subject to, de- of available item features and the number of distinct valpending on the interaction. For example, each preference ues. We devised an in-vitro (ofline) experiment using expressed by the user leads to a change of the state of the two protocols to empirically validate this result. conversation and may also imply a change in the set of Protocols. A CRS may support two diferent ways recommendable items. This formalization through con- (protocols) of how users can reject a recommendation versation states ultimately serves as a basis to study the made the system: eficiency of conversational strategies. The most eficient conversational strategies will minimize the number of states which must pass through to reach an end.
In our model, we mainly deal with the system-driven part of a conversation, where a conversation consists of a sequence of interactions.2 The system can perform one of the following actions:3
CRS does not ask the user to provide a specific reason, i.e., a reason that refers to a disliked feature value. Examples of such more unspecific feedback—if any feedback is given at all—could be, “I don’t want to go to the Green Smoke restaurant” or “I don’t want to see the movie American Beauty” (for some reason, but I cannot explain this to a system); 1. ask the user to fill in (provide) a value for a particular feature under-specified so far ( e.g., the item color);
feature value (e.g., to change the price limit);
to red for the color feature);
CRS asks for a specific item characteristic ( i.e., feature value) she does not like at all. For example, green color for cellphones, sea-view restaurants, a particular movie director, etc. We assume that a user will truthfully answer such questions. 2In constraint-based and critiquing-based systems the recommender Hypotheses. Based on our theoretical results, we system usually drives the conversation in an initial preference elici- formulate two hypotheses, where the diference lies in tation phase. In typical implementations of such systems, the user the characteristics of the item catalog. can however also take the initiative and, for example, request recommendations at any time or proactively revise their preferences. H1 We do not expect a strong diference in terms of 3(We.eg.n,oretetrtahcattainnythreeqarueiareomf KenntoawbloedugtecoRleoprrse)sceonutaldtiobne,csolontsuidnefillriendga eficiency between P1 and P2 when the items in special case of knowledge contraction [24], while slot change (e.g., the catalog have few features with a large number from green to red) is a form of revision [25]. of distinct values.
H2 We do expect a strong diference in terms of efi- existing preferences regarding item features and truthciency between P1 and P2 when the items in the fully responds to system questions about these prefercatalog have several features with few distinct ences. When provided with a recommendation, the user values. either rejects it, which means that the dialog continues, or accepts it, and the dialog ends. The in our sim
Experiment Specifics. In our experiment, we simu- ulation implements one of the described conversation late the above-mentioned protocols and vary the under- strategies, P1 or P2. lying item catalog as an independent variable. Note that in our experiment we simulate a user coldstart situation, i.e., we are not taking any long-term Eficiency Metric. As commonly done in the litera- user profile into account during the dialog. In order to ture [14, 17], we use the number of questions (NQ) the simulate the response of a user, we first select a set of asks before the user accepts a recommendation as positively-rated items (PRI) for each user. This set conan eficiency measure. Fewer questions indicate higher sists of those items in the dataset that the user has rated interaction eficiency. with a value that is greater or equal to their average rating in the MovieLens dataset. We use this set PRI for two Dataset and Catalog Description. We rely on the purposes. First, we simulate a dialog for each element widely used MovieLens-1M (ML-1M) dataset for our ex- of PRI as an “ideal” item (that the user will accept). periment, which we enrich with item features using DB- Second, we use the items in PRI to determine the prepedia [26]. The resulting dataset comprises 3,308 items existing preferences of a user and simulate their answers with 279 unique features. From this dataset, we create to the questions posed by the system. Therefore, if the two versions to test our hypotheses. user previously liked action and romantic movies, the set of pre-existing preferences contains only these values. • Itemset1 (IS1) has only a few features but with a When the simulated dialog with a defined ideal item larger number of distinct values. It is designed to ˆ starts, the system will ask a question on a feature e.g., support H1 (we do not expect a strong diference “What is your favorite genre?”. The simulated user will in terms of eficiency between P1 and P2 when then respond by choosing a value from the set of values the items in the catalog have few features with a for that feature occurring in PRI. In our simulation, the large number of distinct values). user cannot answer with a value that is not present in any recommendable object. After each user answer, the • Itemset2 (IS2), in contrast, has a larger number set of recommendable items is updated by the of features, but each of them only has a few dis- according to her answer. A recommendation is shown tinct values and is designed to support H2 (we when the system has no more questions to ask. This situexpect a strong diference in terms of eficiency ation may occur when: (i) preferences on all the features between P1 and P2 when the items in the catalog have been expressed, (ii) only one item on the catalog is have several features with few distinct values). consistent with the user preferences. The user rejects the (iIftfsaaSoenSoheimnpn.m1acegdeeoutor.tpc,ueuvnshsitlrruficaihgeaoefalcrrerynsutelehehlimerytnsaae.ehte,gorbhmsAeaetvopaorac.imuftecescrtmchstooachtu1imraiahne0mvdskyy0eit1gepn)pl,voryt5gwoteaia0lhotfleflily0huotsenc,herettowdotssaefthaeehoa2osastecni,ra,ut5nehsnIrc0agpeSh0ilelatl1lteaasxvedfcrpvaemeisaesrnaeuacdta.lrdtificutginuFesimeeeIoecrrSneteirtrfs2-asontvvtelnrtiahcyaac,dlaIalcsuwSoudnhve2mdeieesfe.hdfe,lrmeT4sayewfacoveancatrheakuhbtinetberoeodureetsntertdhe1eaoelny0essrf itfrrsbqonmnheeeeyumoraclceIeteteoytomnehrcshnmwmyyteceetceisoonmmansdcutnrdsyegaestefetemstheneantadtrhyaoidedlnsteoifdmaetuttgthauearudriremalrerosdstiijet.enstones,eareT.cgssacwamahticIgtniftgrhiesaoshocitaeeinbvheenanitnne,aersdwopdle,p.uirfboeaIrerbeiniesolectsmsoyigetomncgnosimamtagne,coohyslnstomtvqeeeh.hilecupnseeoaftdergneevfPfinesaddfetswPa1rtiaelouo1dmitnatr,mnuirhnooteetrshncrdiiatnventoehoiPagfirmsttesslh2thuyttrmhcaheeselreanejeetasleteainunaopcssmdsdldtntreoeeaeoelotrgsdetvom.ftii,cioaatIrotldtetnrneyehumiticddfesss-interactions are discared. In protocol P2, in contrast, the Simulation Procedure. We simulate the part of a con- user declares one of the feature values as disliked for the versation between a user and a where the sys- recommended items. tem drives the interaction by asking the user about pre- When the recommendation succeeds—i.e., when the ferred item features and making recommendations for ideal item is in the list of recommendations—the dialog items4. We assume that the simulated user has certain pre- is successfully ended and the simulation continues with 4Other parts of the conversations may include greetings or chit-chat. a new dialog for another user and/or target item. The For a catalog of common user intents in CRS, see [18]. simulation ends when a dialog was simulated for each
524 Itemset2 (b) 3.2. Results and Discussion
IS2, and we counted the Number of Questions (NQ) required to reach the test item in each configuration. Figure 1 summarizes the results. As expected from the theoretical analysis, with IS1 we observe minor diferences between the two protocols in terms of number of requird questions made by the system. More specifically, P1 needs 72.64 as the average number of questions with IS1, whereas P2 needs 67.45. The diference is however huge for IS2 where P1 needs more than 1,000 questions on average to reach the test item, while P2 requires around 166 questions (Fig. 1a). Hence, we can confirm that when the items in the catalog have many features with a smaller number of distinct values, the eficiency of P2 grows drastically compared to P1. Also the maximum number of questions confirms this diferent eficiency for IS1 and IS2 (Fig. 1b). We note that NQ in absolute terms is very large—even in the best combination (P2 with IS1), the number of questions is close to 70, which sounds too high for practical applications. Recall, however, that in this experiment we implemented a worst-case scenario and our experiment used an unrealistic setting on purpose. In our scenario the recommendation task is deliberately dificult: • for each dialog, there is only one test item (true positive); • the CRS works in cold-start condition without any user profile; • the CRS does not implement a cut-of on the number of questions to ask the user.
In conclusion, our experimental evaluation results align with our theoretical findings, thus providing support for our research hypotheses H1 and H2. In other words, our simulation confirmed what was foreseen by the theoretical analysis: the diference between protocol P1 and protocol P2 shows up clearly only in a dataset with many features with a small set of diferent values.
With this work, we contribute to a better understanding of theoretical properties of conversational recommendation problems and we specifically address questions related to the computational complexity of finding eficient dialog strategies. One main insight of our theoretical analysis—which was also confirmed by an in-vitro experiment—is that when designing an eficient conversation strategy, we must always consider the characteristics of the item catalog. More specifically, we demonstrated that when a few features characterize the items in the catalog with a large number of distinct values, the critiquing strategy based on asking the user about a disliked characteristic of the recommended item does not give any significant advantage in terms of user efort. Conversely, when the catalog is composed of items with several features with a few distinct values, a critique strategy based on item features can drastically reduce the user efort for reaching a liked recommendation. On a more general level, we hope that our work might help to stimulate more theory-oriented research in this area, leading us to a better understanding of the foundational properties of this essential class of interactive AI-based systems. In future research, we will investigate the explicit consideration of individual long-term user preferences in the interactive recommendation process.