research-article

Conversational recommendation: : Theoretical model and complexity analysis

Authors:

Tommaso Di Noia,

Francesco Maria Donini,

Dietmar Jannach,

Fedelucio Narducci,

Claudio PomoAuthors Info & Claims

Volume 614, Issue C

Pages 325 - 347

https://doi.org/10.1016/j.ins.2022.07.169

Published: 01 October 2022 Publication History

Highlights

•

Conversational recommenders help users find relevant items in an interactive way.

•

We theoretically analyze the efficiency of different recommendation dialogs.

•

We find that determining an efficient dialog strategy is an NP-hard problem, solvable in PSPACE in general, and in POLYLOGSPACE for particular classes of catalogs.

•

In practice, the choice of the strategy should depend on item catalog characteristics.

•

Experimental evaluations are aligned with our theoretical findings.

Abstract

Recommender systems help users find items of interest in situations of information overload in a personalized way, using needs and preferences of individual users. In conversational recommendation approaches, the system acquires needs and preferences in an interactive, multi-turn dialog. This is usually driven by incrementally asking users about their preferences about item features or individual items. A central research goal in this context is efficiency, evaluated concerning the number of required interactions until a satisfying item is found. Today, research on dialog efficiency is almost entirely empirical, aiming to demonstrate, for example, that one strategy for selecting questions to ask the user is better than another one in a given application. This work complements empirical research with a theoretical, domain-independent model of conversational recommendation. This model, designed to cover a range of application scenarios, allows us to investigate the efficiency of conversational approaches in a formal way, particularly concerning the computational complexity of devising optimal interaction strategies. An experimental evaluation empirically confirms our findings.

References

[1]

D. Jannach, A. Manzoor, W. Cai, L. Chen, A survey on conversational recommender systems, ACM Comput. Surv. 54 (2021) 1–26.

[2]

F. Cena, L. Console, F. Vernero, Logical foundations of knowledge-based recommender systems: A unifying spectrum of alternatives, Information Sciences 546 (2021) 60–73,.

[3]

R. Reichman, Getting computers to talk like you and me, MIT Press, Cambridge, Massachusetts, 1985.

[4]

T. Shao, F. Cai, W. Chen, H. Chen, Self-supervised clarification question generation for ambiguous multi-turn conversation, Information Sciences 587 (2022) 626–641,.

Digital Library

[5]

D. Jannach, Advisor Suite – A knowledge-based sales advisory system, in: ECAI ’04, 2004, pp. 720–724.

[6]

D. Jannach, G. Kreutler, et al., Rapid Development of Knowledge-based Conversational Recommender Applications with Advisor Suite, J. Web Eng. 6 (2) (2007) 165–192.

[7]

L. Chen, P. Pu, Critiquing-based recommenders: survey and emerging trends, User Modeling and User-Adapted Interaction 22 (1–2) (2012) 125–150.

Digital Library

[8]

V. Bellini, G.M. Biancofiore, T.D. Noia, E.D. Sciascio, F. Narducci, C. Pomo, Guapp: A conversational agent for job recommendation for the italian public administration, in: EAIS, IEEE, 2020, pp. 1–7.

[9]

F. Narducci, P. Basile, M. de Gemmis, P. Lops, G. Semeraro, An investigation on the user interaction modes of conversational recommender systems for the music domain, User Model. User Adapt. Interact. 30 (2) (2020) 251–284.

[10]

L. Chen, P. Pu, Preference-based organization interfaces: aiding user critiques in recommender systems, in: International Conference on User Modeling, Springer, 2007, pp. 77–86.

[11]

P. Viappiani, P. Pu, B. Faltings, Conversational recommenders with adaptive suggestions, in: RecSys ’07, 2007, pp. 89–96.

[12]

J. Reilly, K. McCarthy, L. McGinty, B. Smyth, Dynamic critiquing, in: ECCBR 04, 2004, pp. 763–777.

[13]

H. Shimazu, ExpertClerk: A conversational case-based reasoning tool for developing salesclerk agents in E-Commerce webshops, Artificial Intelligence Review 18 (3–4) (2002) 223–244.

[14]

Z. Yin, K.-h. Chang, R. Zhang, DeepProbe: Information directed sequence understanding and chatbot design via recurrent neural networks, in: KDD ’17, 2017, pp. 2131–2139.

[15]

Y. Sun, Y. Zhang, Conversational recommender system, in: SIGIR ’18, 2018, pp. 235–244.

[16]

T. Mahmood, F. Ricci, Improving recommender systems with adaptive conversational strategies, in: Proceedings of the 20th ACM conference on Hypertext and hypermedia, 2009, pp. 73–82.

[17]

K. Christakopoulou, A. Beutel, R. Li, S. Jain, E.H. Chi, Q&R: A two-stage approach toward interactive recommendation, in: KDD ’18, 2018, pp. 139–148.

[18]

B. Loepp, T. Hussein, J. Ziegler, Choice-based preference elicitation for collaborative filtering recommender systems, in: CHI ’14, 2014, pp. 3085–3094.

[19]

F. Narducci, M. de Gemmis, P. Lops, G. Semeraro, Improving the user experience with a conversational recommender system, in: International Conference of the Italian Association for Artificial Intelligence, Springer, 2018, pp. 528–538.

[20]

G. Carenini, J. Smith, D. Poole, Towards more conversational and collaborative recommender systems, in: IUI ’03, 2003, pp. 12–18.

[21]

A. Iovine, P. Lops, F. Narducci, M. de Gemmis, G. Semeraro, An empirical evaluation of active learning strategies for profile elicitation in a conversational recommender system, Journal of Intelligent Information Systems (2021) 1–26.

[22]

K. Christakopoulou, F. Radlinski, K. Hofmann, Towards conversational recommender systems, in: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pp. 815–824.

[23]

G. Adomavicius, Y. Kwon, New Recommendation Techniques for Multicriteria Rating Systems, IEEE Intelligent Systems 22 (3) (2007) 48–55,.

Digital Library

[24]

P. Viappiani, C. Boutilier, Regret-based optimal recommendation sets in conversational recommender systems, in: RecSys ’11, 2009, pp. 101–108.

[25]

P. Grasch, A. Felfernig, F. Reinfrank, Recomment: Towards critiquing-based recommendation with speech interaction, in: Proceedings of the 7th ACM Conference on Recommender Systems, RecSys ’13, ACM, New York, NY, USA, 2013, pp. 157–164.

[26]

W. Wang, I. Benbasat, Research Note–A contingency approach to investigating the effects of user-system interaction modes of online decision aids, Information Systems Research 24 (3) (2013) 861–876.

[27]

F. Pecune, S. Murali, V. Tsai, Y. Matsuyama, J. Cassell, A model of social explanations for a conversational movie recommendation system, in: HAI ’19, 2019, p. 135–143.

[28]

L. Chen, P. Pu, Evaluating critiquing-based recommender agents, in: AAAI ’06, 2006, pp. 157–162.

[29]

F. Ricci, Q.N. Nguyen, O. Averjanova, Exploiting a map-based interface in conversational recommender systems for mobile travelers, in: Tourism Informatics: Visual Travel Recommender Systems, Social Communities, and User Interface Design, IGI Global, 2010, pp. 73–79.

[30]

K. McCarthy, M. Salamó, L. Coyle, L. McGinty, B. Smyth, P. Nixon, Group recommender systems: A critiquing based approach, in: IUI ’06, 2006, pp. 267–269.

[31]

Y. Jin, W. Cai, L. Chen, N.N. Htun, K. Verbert, MusicBot: Evaluating critiquing-based music recommenders with conversational interaction, in: CIKM ’19, 2019, pp. 951–960.

[32]

P. Wärnestål, User evaluation of a conversational recommender system, in: Proceedings of the 4th IJCAI Workshop on Knowledge and Reasoning in Practical Dialogue Systems, 2005, pp. 32–39.

[33]

Y. Ikemoto, V. Asawavetvutt, K. Kuwabara, H.-H. Huang, Tuning a conversation strategy for interactive recommendations in a chatbot setting, Journal of Information and Telecommunication 3 (2) (2019) 180–195.

[34]

A. Iovine, F. Narducci, G. Semeraro, Conversational recommender systems and natural language: A study through the converse framework, Decision Support Systems 131 (2020).

Digital Library

[35]

W. Cai, L. Chen, Predicting user intents and satisfaction with dialogue-based conversational recommendations, in: UMAP ’20, 2020, p. 33–42.

[36]

D. Jannach, Finding preferred query relaxations in content-based recommenders, in: Intelligent techniques and tools for novel system architectures, Springer, 2008, pp. 81–97.

[37]

A. Felfernig, G. Friedrich, D. Jannach, M. Zanker, Constraint-based recommender systems, in: Recommender systems handbook, Springer, 2015, pp. 161–190.

[38]

D. Jannach, Preference-based treatment of empty result sets in product finders and knowledge-based recommenders, in: 18th PUK Workshop - New Results in Planning, Scheduling, and Design (PUK 2004), 2004, pp. 55–69.

[39]

S. Colucci, T. Di Noia, E. Di Sciascio, F.M. Donini, M. Mongiello, Concept abduction and contraction for semantic-based discovery of matches and negotiation spaces in an e-marketplace, Electron. Commer. Res. Appl. 4 (4) (2005) 345–361.

[40]

P. Gärdenfors, Belief revision and knowledge representation, in: Proceedings of the Sixth Conference on Theoretical Aspects of Rationality and Knowledge, 1996, p. 117.

[41]

B.M.E. Moret, Decision trees and diagrams, ACM Comput. Surv. 14 (4) (1982) 593–623.

[42]

L. Hyafil, R.L. Rivest, Constructing optimal binary decision trees is np-complete, Inf. Process. Lett. 5 (1) (1976) 15–17.

[43]

I. Chikalov, S. Hussain, M. Moshkov, Totally optimal decision trees for boolean functions, Discrete Applied Mathematics 215 (2016) 1–13.

[44]

D. Guijarro, V. Lavín, V. Raghavan, Exact learning when irrelevant variables abound, Inf. Process. Lett. 70 (5) (1999) 233–239.

[45]

C.H. Papadimitriou, M. Yannakakis, A note on succinct representations of graphs, Inf. Control. 71 (3) (1986) 181–185.

[46]

W.J. Savitch, Relationships between nondeterministic and deterministic tape complexities, J. Comput. Syst. Sci. 4 (2) (1970) 177–192.

Digital Library

[47]

D. Bertsimas, J. Dunn, Optimal classification trees, Mach. Learn. 106 (7) (2017) 1039–1082.

Digital Library

[48]

G. Aglin, S. Nijssen, P. Schaus, Learning optimal decision trees using caching branch-and-bound search, in: IAAI 2020, 2020, pp. 3146–3153.

[49]

N. Narodytska, A. Ignatiev, F. Pereira, J. Marques-Silva, Learning optimal decision trees with SAT, in: Proceedings IJCAI 2018, 2018, pp. 1362–1368.

[50]

V.W. Anelli, T. Di Noia, E. Di Sciascio, A. Ragone, J. Trotta, How to make latent factors interpretable by feeding factorization machines with knowledge graphs, in: Proceedings ISWC 2019, 2019, pp. 38–56.

Cited By

Anelli VChen LMelo GMcAuley JNarducci FRagone A(2024)Preface to the special issue on conversational recommender systems: theory, models, evaluations, and trendsUser Modeling and User-Adapted Interaction10.1007/s11257-024-09420-234:5(1529-1533)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1007/s11257-024-09420-2
Xie BJia XSong XZhang HChen BJiang BWang YPan Y(2023)ReCoMIFInformation Fusion10.1016/j.inffus.2023.03.01696:C(192-201)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.inffus.2023.03.016

Index Terms

Conversational recommendation: Theoretical model and complexity analysis

Index terms have been assigned to the content through auto-classification.

Recommendations

Unifying Recommender Systems and Conversational User Interfaces
CUI '22: Proceedings of the 4th Conference on Conversational User Interfaces

This paper considers unifying research on conversational user interfaces and recommender systems. Studies on conversational user interfaces (CUIs) typically examine how conversations can be facilitated (i.e., optimizing the means). Recommender systems ...
Recognizing users feedback from non-verbal communicative acts in conversational recommender systems

A multimodal framework for monitoring users attitude and profile.A dynamic model for monitoring user liking attitude.We integrated the module in a content-based recommender system. Conversational recommender systems produce personalized recommendations ...
Learning to Ask Appropriate Questions in Conversational Recommendation
SIGIR '21: Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval

Conversational recommender systems (CRSs) have revolutionized the conventional recommendation paradigm by embracing dialogue agents to dynamically capture the fine-grained user preference. In a typical conversational recommendation scenario, a CRS ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Sciences: an International Journal

Information Sciences: an International Journal Volume 614, Issue C

Oct 2022

580 pages

ISSN:0020-0255

Issue’s Table of Contents

Elsevier Inc.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 October 2022

Author Tags

Author Tag

CRS

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Anelli VChen LMelo GMcAuley JNarducci FRagone A(2024)Preface to the special issue on conversational recommender systems: theory, models, evaluations, and trendsUser Modeling and User-Adapted Interaction10.1007/s11257-024-09420-234:5(1529-1533)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1007/s11257-024-09420-2
Xie BJia XSong XZhang HChen BJiang BWang YPan Y(2023)ReCoMIFInformation Fusion10.1016/j.inffus.2023.03.01696:C(192-201)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.inffus.2023.03.016

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents