Quantum recommendation systems
A recommendation system uses the past purchases or ratings of n products by a group of m users, in order to provide personalized recommendations to individual users. The information is modeled as an m \times n preference matrix which is assumed to have a good rank-k approximation, for a small consta...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/89347 http://hdl.handle.net/10220/46208 |
| _version_ | 1826123661744013312 |
|---|---|
| author | Kerenidis, Iordanis Prakash, Anupam |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Kerenidis, Iordanis Prakash, Anupam |
| author_sort | Kerenidis, Iordanis |
| collection | NTU |
| description | A recommendation system uses the past purchases or ratings of n products by a group of m users, in order to provide personalized recommendations to individual users. The information is modeled as an m \times n preference matrix which is assumed to have a good rank-k approximation, for a small constant k. In this work, we present a quantum algorithm for recommendation systems that has running time O(\text{poly}(k)\text{polylog}(mn)). All known classical algorithms for recommendation systems that work through reconstructing an approximation of the preference matrix run in time polynomial in the matrix dimension. Our algorithm provides good recommendations by sampling efficiently from an approximation of the preference matrix, without reconstructing the entire matrix. For this, we design an efficient quantum procedure to project a given vector onto the row space of a given matrix. This is the first algorithm for recommendation systems that runs in time polylogarithmic in the dimensions of the matrix and provides an example of a quantum machine learning algorithm for a real world application. |
| first_indexed | 2024-10-01T06:08:18Z |
| format | Journal Article |
| id | ntu-10356/89347 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T06:08:18Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ntu-10356/893472023-02-28T19:36:11Z Quantum recommendation systems Kerenidis, Iordanis Prakash, Anupam School of Physical and Mathematical Sciences Centre for Quantum Technologies Quantum Machine Learning Recommendation Systems DRNTU::Science::Physics A recommendation system uses the past purchases or ratings of n products by a group of m users, in order to provide personalized recommendations to individual users. The information is modeled as an m \times n preference matrix which is assumed to have a good rank-k approximation, for a small constant k. In this work, we present a quantum algorithm for recommendation systems that has running time O(\text{poly}(k)\text{polylog}(mn)). All known classical algorithms for recommendation systems that work through reconstructing an approximation of the preference matrix run in time polynomial in the matrix dimension. Our algorithm provides good recommendations by sampling efficiently from an approximation of the preference matrix, without reconstructing the entire matrix. For this, we design an efficient quantum procedure to project a given vector onto the row space of a given matrix. This is the first algorithm for recommendation systems that runs in time polylogarithmic in the dimensions of the matrix and provides an example of a quantum machine learning algorithm for a real world application. NRF (Natl Research Foundation, S’pore) Published version 2018-10-03T06:57:50Z 2019-12-06T17:23:28Z 2018-10-03T06:57:50Z 2019-12-06T17:23:28Z 2017 Journal Article Kerenidis, I., & Prakash, A. (2017). Quantum recommendation systems. Leibniz International Proceedings in Informatics, 67, 49-. doi:10.4230/LIPIcs.ITCS.2017.49 https://hdl.handle.net/10356/89347 http://hdl.handle.net/10220/46208 10.4230/LIPIcs.ITCS.2017.49 en Leibniz International Proceedings in Informatics © 2017 Iordanis Kerenidis and Anupam Prakash; licensed under Creative Commons License CC-BY. 21 p. application/pdf |
| spellingShingle | Quantum Machine Learning Recommendation Systems DRNTU::Science::Physics Kerenidis, Iordanis Prakash, Anupam Quantum recommendation systems |
| title | Quantum recommendation systems |
| title_full | Quantum recommendation systems |
| title_fullStr | Quantum recommendation systems |
| title_full_unstemmed | Quantum recommendation systems |
| title_short | Quantum recommendation systems |
| title_sort | quantum recommendation systems |
| topic | Quantum Machine Learning Recommendation Systems DRNTU::Science::Physics |
| url | https://hdl.handle.net/10356/89347 http://hdl.handle.net/10220/46208 |
| work_keys_str_mv | AT kerenidisiordanis quantumrecommendationsystems AT prakashanupam quantumrecommendationsystems |