Maurizio Ferrari Dacrema
Nicolò Felicioni
ABSTRACT
It has been long known that quantum computing has the potential to revolutionize the way we find solutions of problems that are difficult to solve on classical computers. It was only recently that small but functional quantum computers have become available on the cloud, allowing to test their potential. In this paper we propose to leverage their capabilities to address an important task for recommender systems providers, the optimal selection of recommendation carousels. In many video-on-demand and music streaming services the user is provided with a homepage containing several recommendation lists, i.e., carousels, each built with a certain criteria (e.g., artist, mood, Action movies etc.). Choosing which set of carousels to display is a difficult problem because it needs to account for how the different recommendation lists interact, e.g., avoiding duplicate recommendations, and how they help the user explore the catalogue. We focus in particular on the adiabatic computing paradigm and use the D-Wave quantum annealer, which is able to solve NP-hard optimization problems, can be programmed by classical operations research tools and is freely available on the cloud. We propose a formulation of the carousel selection problem for black box recommenders, that can be solved effectively on a quantum annealer and has the advantage of being simple. We discuss its effectiveness, limitations and possible future directions of development.
Supplemental Material
- Tameem Albash and Daniel A Lidar. 2018. Adiabatic quantum computation. Reviews of Modern Physics 90, 1 (2018), 015002.Google Scholar
Cross Ref
- B Apolloni, N Cesa-Bianchi, and D De Falco. 1988. A numerical implementation of ”quantum annealing”. Technical Report BIBOS-324. Bielefeld TU. Bielefeld-Bochum-Stochastik, Bielefeld. https://cds.cern.ch/record/192546Google Scholar
- Walid Bendada, Guillaume Salha, and Théo Bontempelli. 2020. Carousel Personalization in Music Streaming Apps with Contextual Bandits. In RecSys 2020: Fourteenth ACM Conference on Recommender Systems, Virtual Event, Brazil, September 22-26, 2020, Rodrygo L. T. Santos, Leandro Balby Marinho, Elizabeth M. Daly, Li Chen, Kim Falk, Noam Koenigstein, and Edleno Silva de Moura (Eds.). ACM, 420–425. https://doi.org/10.1145/3383313.3412217Google ScholarDigital Library
- James Bennett, Stan Lanning, 2007. The netflix prize. In Proceedings of KDD cup and workshop, Vol. 2007. New York, 35.Google Scholar
- Kelly Boothby, Paul Bunyk, Jack Raymond, and Aidan Roy. 2020. Next-generation topology of d-wave quantum processors. arXiv preprint arXiv:2003.00133(2020).Google Scholar
- Laming Chen, Guoxin Zhang, and Eric Zhou. 2018. Fast greedy map inference for determinantal point process to improve recommendation diversity. In Advances in Neural Information Processing Systems. 5622–5633.Google Scholar
- Andrzej Cichocki and Anh Huy Phan. 2009. Fast Local Algorithms for Large Scale Nonnegative Matrix and Tensor Factorizations. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 92-A, 3(2009), 708–721. https://doi.org/10.1587/transfun.E92.A.708Google Scholar
- Colin Cooper, Sang-Hyuk Lee, Tomasz Radzik, and Yiannis Siantos. 2014. Random walks in recommender systems: exact computation and simulations. In 23rd International World Wide Web Conference, WWW ’14, Seoul, Republic of Korea, April 7-11, 2014, Companion Volume, Chin-Wan Chung, Andrei Z. Broder, Kyuseok Shim, and Torsten Suel (Eds.). ACM, 811–816. https://doi.org/10.1145/2567948.2579244Google ScholarDigital Library
- Paolo Cremonesi, Yehuda Koren, and Roberto Turrin. 2010. Performance of recommender algorithms on top-n recommendation tasks. In Proceedings of the 2010 ACM Conference on Recommender Systems, RecSys 2010, Barcelona, Spain, September 26-30, 2010, Xavier Amatriain, Marc Torrens, Paul Resnick, and Markus Zanker (Eds.). ACM, 39–46. https://doi.org/10.1145/1864708.1864721Google ScholarDigital Library
- Vasil S. Denchev, Sergio Boixo, Sergei V. Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, and Hartmut Neven. 2016. What is the Computational Value of Finite-Range Tunneling?Phys. Rev. X 6 (Aug 2016), 031015. Issue 3. https://doi.org/10.1103/PhysRevX.6.031015Google Scholar
- Weicong Ding, Dinesh Govindaraj, and S. V. N. Vishwanathan. 2019. Whole Page Optimization with Global Constraints. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, Ankur Teredesai, Vipin Kumar, Ying Li, Rómer Rosales, Evimaria Terzi, and George Karypis(Eds.). ACM, 3153–3161. https://doi.org/10.1145/3292500.3330675Google ScholarDigital Library
- Nicolò Felicioni, Maurizio Ferrari Dacrema, and Paolo Cremonesi. 2021. A Methodology for the Offline Evaluation of Recommender Systems in a User Interface with Multiple Carousels. In Adjunct Proceedings of the 29th ACM Conference on User Modeling, Adaptation and Personalization. 10–15.Google ScholarDigital Library
- Nicolò Felicioni, Maurizio Ferrari Dacrema, Fernando Benjamín Pérez Maurera, and Paolo Cremonesi. 2021. Measuring the Ranking Quality of Recommendations in a Two-Dimensional Carousel Setting. In Proceedings of IIR2021 - 11th Italian Information Retrieval Workshop.Google Scholar
- Maurizio Ferrari Dacrema, Simone Boglio, Paolo Cremonesi, and Dietmar Jannach. 2021. A Troubling Analysis of Reproducibility and Progress in Recommender Systems Research. ACM Trans. Inf. Syst. 39, 2, Article 20 (Jan. 2021), 49 pages. https://doi.org/10.1145/3434185Google ScholarDigital Library
- Fred W. Glover, Gary A. Kochenberger, and Yu Du. 2019. Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models. 4OR 17, 4 (2019), 335–371. https://doi.org/10.1007/s10288-019-00424-yGoogle Scholar
- Alois Gruson, Praveen Chandar, Christophe Charbuillet, James McInerney, Samantha Hansen, Damien Tardieu, and Ben Carterette. 2019. Offline Evaluation to Make Decisions About PlaylistRecommendation Algorithms. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, WSDM 2019, Melbourne, VIC, Australia, February 11-15, 2019, J. Shane Culpepper, Alistair Moffat, Paul N. Bennett, and Kristina Lerman (Eds.). ACM, 420–428. https://doi.org/10.1145/3289600.3291027Google ScholarDigital Library
- F. Maxwell Harper and Joseph A. Konstan. 2016. The MovieLens Datasets: History and Context. ACM Trans. Interact. Intell. Syst. 5, 4 (2016), 19:1–19:19. https://doi.org/10.1145/2827872Google ScholarDigital Library
- Yifan Hu, Yehuda Koren, and Chris Volinsky. 2008. Collaborative Filtering for Implicit Feedback Datasets. In Proceedings of the 8th IEEE International Conference on Data Mining (ICDM 2008), December 15-19, 2008, Pisa, Italy. IEEE Computer Society, 263–272. https://doi.org/10.1109/ICDM.2008.22Google ScholarDigital Library
- Andrew Lucas. 2014. Ising formulations of many NP problems. Frontiers in Physics 2(2014), 5. https://doi.org/10.3389/fphy.2014.00005Google ScholarCross Ref
- Bamshad Mobasher, Xin Jin, and Yanzan Zhou. 2003. Semantically Enhanced Collaborative Filtering on the Web. In Web Mining: From Web to Semantic Web, First European Web Mining Forum, EMWF 2003, Cavtat-Dubrovnik, Croatia, September 22, 2003, Revised Selected and Invited Papers(Lecture Notes in Computer Science), Bettina Berendt, Andreas Hotho, Dunja Mladenic, Maarten van Someren, Myra Spiliopoulou, and Gerd Stumme (Eds.), Vol. 3209. Springer, 57–76. https://doi.org/10.1007/978-3-540-30123-3_4Google Scholar
- Riccardo Nembrini, Maurizio Ferrari Dacrema, and Paolo Cremonesi. 2021. Feature Selection for Recommender Systems with Quantum Computing. Entropy 23, 8 (2021). https://doi.org/10.3390/e23080970Google Scholar
- Xia Ning and George Karypis. 2011. SLIM: Sparse linear methods for top-n recommender systems. In Proceedings of the 11th IEEE International Conference on Data Mining (ICDM ’11). 497–506.Google ScholarDigital Library
- Bibek Paudel, Fabian Christoffel, Chris Newell, and Abraham Bernstein. 2017. Updatable, Accurate, Diverse, and Scalable Recommendations for Interactive Applications. ACM Trans. Interact. Intell. Syst. 7, 1 (2017), 1:1–1:34. https://doi.org/10.1145/2955101Google ScholarDigital Library
- Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2009. BPR: Bayesian Personalized Ranking from Implicit Feedback. In UAI 2009, Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, Montreal, QC, Canada, June 18-21, 2009, Jeff A. Bilmes and Andrew Y. Ng (Eds.). AUAI Press, 452–461. https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=1630&proceeding_id=25Google ScholarDigital Library
- Badrul Munir Sarwar, George Karypis, Joseph A. Konstan, and John Riedl. 2001. Item-based collaborative filtering recommendation algorithms. In Proceedings of the Tenth International World Wide Web Conference, WWW 10, Hong Kong, China, May 1-5, 2001, Vincent Y. Shen, Nobuo Saito, Michael R. Lyu, and Mary Ellen Zurko (Eds.). ACM, 285–295. https://doi.org/10.1145/371920.372071Google ScholarDigital Library
- Harald Steck. 2019. Embarrassingly Shallow Autoencoders for Sparse Data. In The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, Ling Liu, Ryen W. White, Amin Mantrach, Fabrizio Silvestri, Julian J. McAuley, Ricardo Baeza-Yates, and Leila Zia (Eds.). ACM, 3251–3257. https://doi.org/10.1145/3308558.3313710Google ScholarDigital Library
- Chao-Yuan Wu, Christopher V. Alvino, Alexander J. Smola, and Justin Basilico. 2016. Using Navigation to Improve Recommendations in Real-Time. In Proceedings of the 10th ACM Conference on Recommender Systems, Boston, MA, USA, September 15-19, 2016, Shilad Sen, Werner Geyer, Jill Freyne, and Pablo Castells (Eds.). ACM, 341–348. https://doi.org/10.1145/2959100.2959174Google ScholarDigital Library
- Mi Zhang and Neil Hurley. 2008. Avoiding monotony: improving the diversity of recommendation lists. In Proceedings of the 2008 ACM Conference on Recommender Systems, RecSys 2008, Lausanne, Switzerland, October 23-25, 2008, Pearl Pu, Derek G. Bridge, Bamshad Mobasher, and Francesco Ricci (Eds.). ACM, 123–130. https://doi.org/10.1145/1454008.1454030Google ScholarDigital Library
- Tao Zhou, Zoltán Kuscsik, Jian-Guo Liu, Matúš Medo, Joseph Rushton Wakeling, and Yi-Cheng Zhang. 2010. Solving the apparent diversity-accuracy dilemma of recommender systems. National Academy of Sciences 107, 10 (2010), 4511–4515.Google ScholarCross Ref
Recommendations
Quantum computing via the Bethe ansatz
We recognize quantum circuit model of computation as factorisable scattering model and propose that a quantum computer is associated with a quantum many-body system solved by the Bethe ansatz. As an typical example to support our perspectives on quantum ...
Quantum computing and quantum simulation with group-II atoms
Recent experimental progress in controlling neutral group-II atoms for optical clocks, and in the production of degenerate gases with group-II atoms has given rise to novel opportunities to address challenges in quantum computing and quantum simulation. ...
Integrable quantum computation
Integrable quantum computation is defined as quantum computing via the integrable condition, in which two-qubit gates are either nontrivial unitary solutions of the Yang---Baxter equation or the Swap gate (permutation). To make the definition clear, in ...
Comments