A Latent Source Model for Online Collaborative Filtering
Despite the prevalence of collaborative filtering in recommendation systems, there has been little theoretical development on why and how well it works, especially in the “online” setting, where items are recommended to users over time. We address this theoretical gap by introducing a model for onli...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Neural Information Processing Systems Foundation, Inc.
2014
|
| Online Access: | http://hdl.handle.net/1721.1/91678 https://orcid.org/0000-0003-0737-3259 https://orcid.org/0000-0003-1303-582X |
| _version_ | 1826206077859921920 |
|---|---|
| author | Bresler, Guy Chen, George Shah, Devavrat |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bresler, Guy Chen, George Shah, Devavrat |
| author_sort | Bresler, Guy |
| collection | MIT |
| description | Despite the prevalence of collaborative filtering in recommendation systems, there has been little theoretical development on why and how well it works, especially in the “online” setting, where items are recommended to users over time. We address this theoretical gap by introducing a model for online recommendation systems, cast item recommendation under the model as a learning problem, and analyze the performance of a cosine-similarity collaborative filtering method. In our model, each of n users either likes or dislikes each of m items. We assume there to be k types of users, and all the users of a given type share a common string of probabilities determining the chance of liking each item. At each time step, we recommend an item to each user, where a key distinction from related bandit literature is that once a user consumes an item (e.g., watches a movie), then that item cannot be recommended to the same user again. The goal is to maximize the number of likable items recommended to users over time. Our main result establishes that after nearly log(km) initial learning time steps, a simple collaborative filtering algorithm achieves essentially optimal performance without knowing k. The algorithm has an exploitation step that uses cosine similarity and two types of exploration steps, one to explore the space of items (standard in the literature) and the other to explore similarity between users (novel to this work). |
| first_indexed | 2024-09-23T13:23:44Z |
| format | Article |
| id | mit-1721.1/91678 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:23:44Z |
| publishDate | 2014 |
| publisher | Neural Information Processing Systems Foundation, Inc. |
| record_format | dspace |
| spelling | mit-1721.1/916782022-09-28T13:51:43Z A Latent Source Model for Online Collaborative Filtering Bresler, Guy Chen, George Shah, Devavrat Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Bresler, Guy Chen, George Shah, Devavrat Despite the prevalence of collaborative filtering in recommendation systems, there has been little theoretical development on why and how well it works, especially in the “online” setting, where items are recommended to users over time. We address this theoretical gap by introducing a model for online recommendation systems, cast item recommendation under the model as a learning problem, and analyze the performance of a cosine-similarity collaborative filtering method. In our model, each of n users either likes or dislikes each of m items. We assume there to be k types of users, and all the users of a given type share a common string of probabilities determining the chance of liking each item. At each time step, we recommend an item to each user, where a key distinction from related bandit literature is that once a user consumes an item (e.g., watches a movie), then that item cannot be recommended to the same user again. The goal is to maximize the number of likable items recommended to users over time. Our main result establishes that after nearly log(km) initial learning time steps, a simple collaborative filtering algorithm achieves essentially optimal performance without knowing k. The algorithm has an exploitation step that uses cosine similarity and two types of exploration steps, one to explore the space of items (standard in the literature) and the other to explore similarity between users (novel to this work). National Science Foundation (U.S.) (Grant CNS-1161964) United States. Army Research Office. Multidisciplinary University Research Initiative (Award W911NF-11-1-0036) American Society for Engineering Education. National Defense Science and Engineering Graduate Fellowship 2014-11-21T16:33:23Z 2014-11-21T16:33:23Z 2014-12 Article http://purl.org/eprint/type/ConferencePaper http://hdl.handle.net/1721.1/91678 Bresler, Guy, George H. Chen, and Devavrat Shah. "A Latent Source Model for Online Collaborative Filtering." Advances in Neural Information Processing Systems 27 (NIPS 2014), pp.1-9. https://orcid.org/0000-0003-0737-3259 https://orcid.org/0000-0003-1303-582X en_US http://papers.nips.cc/paper/5330-a-latent-source-model-for-online-collaborative-filtering Proceedings of the 2014 Neural Information Processing Systems Foundation Conference (NIPS 2014) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Neural Information Processing Systems Foundation, Inc. Chen |
| spellingShingle | Bresler, Guy Chen, George Shah, Devavrat A Latent Source Model for Online Collaborative Filtering |
| title | A Latent Source Model for Online Collaborative Filtering |
| title_full | A Latent Source Model for Online Collaborative Filtering |
| title_fullStr | A Latent Source Model for Online Collaborative Filtering |
| title_full_unstemmed | A Latent Source Model for Online Collaborative Filtering |
| title_short | A Latent Source Model for Online Collaborative Filtering |
| title_sort | latent source model for online collaborative filtering |
| url | http://hdl.handle.net/1721.1/91678 https://orcid.org/0000-0003-0737-3259 https://orcid.org/0000-0003-1303-582X |
| work_keys_str_mv | AT breslerguy alatentsourcemodelforonlinecollaborativefiltering AT chengeorge alatentsourcemodelforonlinecollaborativefiltering AT shahdevavrat alatentsourcemodelforonlinecollaborativefiltering AT breslerguy latentsourcemodelforonlinecollaborativefiltering AT chengeorge latentsourcemodelforonlinecollaborativefiltering AT shahdevavrat latentsourcemodelforonlinecollaborativefiltering |