WIXLIB

11/26/2018COMP 345: Data MiningMore on Recommender SystemsSlides Adapted From: www.mmds.org (Mining Massive Datasets) Training data 100 million ratings, 480,000 users, 17,770 movies 6 years of data: 2000-2005 Test data Last few ratings of each user (2.8 million) Evaluation criterion: Root Mean Square Error (RMSE) 1𝑅σ(𝑖,𝑥) 𝑅 𝑟𝑥𝑖Ƹ 𝑟𝑥𝑖2 Netflix’s system RMSE: 0.9514 Competition 2,700 teams 1 million prize for 10% improvement on NetflixJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org21

11/26/2018480,000 usersMatrix R13435455522317,700movies325211331J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.orgMatrix R3480,000 g Data SetTest Data Set?231?True rating ofuser x on item i1RMSE 1Rσ(𝑖,𝑥) 𝑅 𝑟𝑥𝑖Ƹ 𝑟𝑥𝑖2Predicted rating42

11/26/2018 Training data 100 million ratings, 480,000 users, 17,770 movies 6 years of data: 2000-2005 Test data Last few ratings of each user (2.8 million) Evaluation criterion: Root Mean Square Error (RMSE) 1𝑅σ(𝑖,𝑥) 𝑅 𝑟𝑥𝑖Ƹ 𝑟𝑥𝑖2 Netflix’s system RMSE: 0.9514 Competition 2,700 teams 1 million prize for 10% improvement on NetflixJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org The winner of the Netflix Challenge! Multi-scale modeling of the data:Combine top level, “regional”modeling of the data, witha refined, local view: Global:5Global effectsFactorization Overall deviations of users/movies Factorization:Collaborativefiltering Addressing “regional” effects Collaborative filtering: Extract local patternsJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org63

11/26/2018 Global: Mean movie rating: 3.7 stars The Sixth Sense is 0.5 stars above avg. Joe rates 0.2 stars below avg. Baseline estimation:Joe will rate The Sixth Sense 4 stars Local neighborhood (CF/NN): Joe didn’t like related movie Signs Final estimate:Joe will rate The Sixth Sense 3.8 starsJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org7Earliest and most popular collaborativefiltering method Derive unknown ratings from those of “similar”movies (item-item variant) Define similarity measure sij of items i and j Select k-nearest neighbors, compute the rating N(i; x): items most similar to i that were rated by xrˆxi s rxjj N ( i ; x ) ijsj N ( i ; x ) ijsij similarity of items i and jrxj rating of user x on item jN(i;x) set of items similar toitem i that were rated by xJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org84

11/26/2018 In practice we get better estimates if wemodel deviations: rxi bxi s (rxj bxj )j N ( i ; x ) ij baseline estimate for rxi𝒃𝒙𝒊 𝝁 𝒃𝒙 𝒃𝒊μ overall mean ratingbx rating deviation of user x (avg. rating of user x) – μbi (avg. rating of movie i) – μsj N ( i ; x ) ijProblems/Issues:1) Similarity measures are “arbitrary”2) Pairwise similarities neglectinterdependencies among users3) Taking a weighted average can berestrictingSolution: Instead of sij use wij thatwe estimate directly from dataJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org9Global average: 1.1296User average: 1.0651Movie average: 1.0533Netflix: 0.9514Basic Collaborative filtering: 0.94CF Biases learned weights: 0.91Grand Prize: 0.8563J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org105

11/26/2018 1 3 43 54 53322Goal: Make good recommendations Quantify goodness using RMSE:Lower RMSE better recommendations Want to make good recommendations on itemsthat user has not yet seen. Can’t really do this!12 13552513 Let’s set build a system such that it works wellon known (user, item) ratingsAnd hope the system will also predict well theunknown ratingsJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org “SVD” on Netflix data: R Q ·2421441434235344423421353 222R 7.3usersfactorsitems3SVD: A U 3.4.8.7-.6.1PTQFor now let’s assume we can approximate therating matrix R as a product of “thin” Q · PT R has missing entries but let’s ignore that for now! Basically, we will want the reconstruction error to be small on knownratings and we don’t care about the values on the missing onesJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org126

11/26/2018SeriousThe ColorPurpleLethalWeaponSense sOcean’s 11GearedtowardsmalesThe Lion KingThe PrincessDiariesIndependenceDayDumb andDumberFunnyJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.orgHow to estimate the missing rating ofuser x for item i?𝒓ො 𝒙𝒊 𝒒𝒊 .5-.2.3.51.12.1.3-.72.1-2factors 𝒇5qi row i of Qpx column x of PT4.1.7 𝒒𝒊𝒇 𝒑𝒙𝒇3223-142usersfactorsitems1items J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org147

11/26/2018How to estimate the missing rating ofuser x for item i?𝒓ො 𝒙𝒊 𝒒𝒊 423 222 𝒒𝒊𝒇 𝒑𝒙𝒇3𝒇5qi row i of Qpx column x of sfactors orsJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.orgHow to estimate the missing rating ofuser x for item i?𝒓ො 𝒙𝒊 𝒒𝒊 𝒑𝒙users3524252.4?41234415453344413522 𝒇5qi row i of Qpx column x of PT4.1-.4.2-.5.6.5-.2.3.51.12.1.3-.72.1-2.7 𝒒𝒊𝒇 𝒑𝒙𝒇3223-142usersf factorsitems1items -.71.2-.11.32.1-.4.61.72.4.9-.3.4.8.7-.6.1PT.3f factors1.1QJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org168

11/26/2018SeriousThe thalWeaponSense andSensibilityOcean’s 11GearedFactor 1towardsmalesFactor 2The Lion KingThe PrincessDiariesIndependenceDayDumb andDumberFunnyJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.orgSeriousThe LethalWeaponSense andSensibilityOcean’s 11GearedFactor 1towardsmalesThe PrincessDiariesFactor 2The Lion KingIndependenceDayFunnyJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.orgDumb andDumber189

11/26/2018nn SVD: A: Input data matrixU: Left singular vecsV: Right singular vecs : Singular valuesmA mVTUSo in our case:“SVD” on Netflix data: R Q · PTA R, Q U, PT VT𝒓ො 𝒙𝒊 𝒒𝒊 𝒑𝒙J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org SVD gives minimum reconstruction error(Sum of Squared Errors):min 𝐴𝑖𝑗 𝑈Σ𝑉 T𝑈,V,Σ 192𝑖𝑗𝑖𝑗 𝐴Note two things: SSE and RMSE are monotonically related: 𝑹𝑴𝑺𝑬 𝟏𝒄𝑺𝑺𝑬 Great news: SVD is minimizing RMSE Complication: The sum in SVD error term is overall entries (no-rating in interpreted as zero-rating).But our R has missing entries!J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org2010

11/26/2018factorsusers3242144143 424342353544231 ctorsitems55items1PTQSVD isn’t defined when entries are missing!Use specialized methods to find P, Q min σ 𝑖,𝑥𝑃,𝑄 R𝑟𝑥𝑖 𝑞𝑖 𝑝𝑥2𝑟𝑥𝑖Ƹ 𝑞𝑖 𝑝𝑥 Note: We don’t require cols of P, Q to be orthogonal/unit length P, Q map users/movies to a latent space The most popular model among Netflix contestantsJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org2111

11/26/2018 Sudden rise in theaverage movie rating(early 2004) Improvements in Netflix GUI improvements Meaning of rating changed Movie age Users prefer new movieswithout any reasons Older movies are justinherently better thannewer onesY. Koren, Collaborative filtering withtemporal dynamics, KDD ’09J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org0.92CF (no time bias)Basic Latent Factors0.915CF (time bias)0.91Latent Factors w/ Biases0.905RMSE23 Linear time factors Per-day user biases0.9 CF0.8950.890.8850.880.875110100Millions of parameters1000J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org100002412

11/26/2018Global average: 1.1296User average: 1.0651Movie average: 1.0533Netflix: 0.9514Basic Collaborative filtering: 0.94Collaborative filtering : 0.91Latent factors: 0.90Latent factors Biases: 0.89Latent factors Biases Time: 0.876Still no prize! Getting desperate.Try a “kitchensink” approach!Grand Prize: 0.8563J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org25June 26th submission triggers 30-day “last call”J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org2613

11/26/2018 Ensemble team formed Group of other teams on leaderboard forms a new team Relies on combining their models Quickly also get a qualifying score over 10% BellKor Continue to get small improvements in their scores Realize that they are in direct competition with Ensemble Strategy Both teams carefully monitoring the leaderboard Only sure way to check for improvement is to submit a setof predictions This alerts the other team of your latest scoreJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org 27Submissions limited to 1 a day Only 1 final submission could be made in the last 24h 24 hours before deadline BellKor team member in Austria notices (by chance) thatEnsemble posts a score that is slightly better than BellKor’s Frantic last 24 hours for both teams Much computer time on final optimization Carefully calibrated to end about an hour before deadline Final submissions BellKor submits a little early (on purpose), 40 mins beforedeadline Ensemble submits their final entry 20 mins later .and everyone waits .J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org2814

11/26/2018J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org29J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org3015

11/26/2018 “This is how Netflix’s secret recommendationsystem works” Article in Wired Sept/Oct. 2018 Issue Netflix is constantly collecting data on its usersA/B Tests ( 250 tests per year) Presents users with two slightly different experiencesto see how they respond Landing Cards – images shown as you scrollthrough showsRecommended Shows – based on viewing history31“The Netflix Recommender System: Algorithms,Business Value, and Innovation” by Carlos A. GomezUribe and Neil Hunt, Netflix, Inc. ACM Transactions onManagement Information Systems, Vol. 6, No. 4,Article 13, Publication date: December 2015.3216

11/26/2018 2 1 3 4 3 5 5 4 5 5 3 3 2 2 2 5 2 1 1 3 3 1 480,000 users 17,700 movies J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org 3