Data Analysis
Andrey Shestakov (avshestakov@hse.ru)
Introduction to Recommender Systems1
1. Some materials are taken from machine learning course of Victor Kitov
Introductuction to RecSys¶
Motivation¶
Everyday people have to make decisions:
- what music to listen
- what movies to see
- what books to read
- what food to eat
- what games to play
- ...
Multitude of choices
- Spotify - 30kk. songs
- Netflix - 20k. movies and series
- Amazon - 500k. books
- Steam - 20k games
To filter out the seach people can rely on recommendations
- of their friends (if there are friends)
- of some reviews
These recommendations are too narrow and standard
- rely on information of a handful of people
- not tuned for individual user tastes
Need automatic recommendation system!
Long Tail Phenomenon¶
Few words on history¶
Netflix prize¶
- Competition for the best recommendation algirithm
- October 2007 - September 2009
- Prize: 1 000 000 $
- 480 000 users
- 17 770 movies
- format: [user, movie, datetime, rating]
- grades: 1,2,3,4,5
- quality measure: RMSE
Netflix Prize¶
Collaborative filtering¶
Collaborative filtering¶
A method of making automatic predictions about the interests of a user by collecting prefences or taste information from similar users
- Generic CF algorithm
- Look for users who share the same rating patterns with current user
- Use their ratings to predict currently unknown user ratings
- Main assumption: if person A has the same opinion as a persion B on an issue, A is more likely to have B's opinion on a different issue.
- Have you already seen this idea?
Collaborative filtering¶
Challenges¶
- Scalability
- many users and items
- Cold start
- new user has not rated many items - hard to predict his preferences
- new item was not rated by many users - hard to predict its characteristics
- Shilling attacks
- shop representatives may give lots of positive ratings for their own items ang negative ratings for theis competitors
- Learning Loop
- once the model have been relearned it may relearned its previous predictions - does not gain new knowledge
- Obvious recommendations
Core concepts¶
- Users give ratings to items
- Users give ratings to items
- Binary
- "Stars"
- Implicit
- Tasks of RecSys:
- Fill missing values of the ratings
- Recommend items to user
- may not be the highest ranked!
Notations¶
- U - set of all users
- I - set of all items
- u, v - some users
- i, j - some items
- Ui - set of users, that rated item i
- Iu - set of items, that have been rated by user u
- Rui - actual rating of item i by user u
- ˆRui - predicted rating of item i by user u
Baseline¶
Baseline ideas¶
- bui=μ, (μ=1n∑u,iRui)
- bui=ˉRu=1|Iu|∑i∈IuRui
- bui=ˉRi=1|Ui|∑u∈UiRui
General baseline¶
- bui=μ+bu+bi,
- bu=1|Iu|∑i∈Iu(Rui−μ)
- bi=1|Ui|∑u∈Ui(Rui−bu−μ)
Intuition
- bu is how much higher user rates items than on average
- bi is how much item i is rated higher than average user rating
General baseline¶
- bui=μ+bu+bi,
- bu=1|Iu|+α∑i∈Iu(Rui−μ)
- bi=1|Ui|+β∑u∈Ui(Rui−bu−μ)
- What is the idea behind α and β?
Motivation¶
- Compare accuracy with advanced model
- Can compute missing values with baseline values
- Normalization: predict Rui−bui instead of Rui
User-based Collaborative filteting¶
User-based CF¶
User-based CF¶
- Also known as K-NN CF
Define similarity function on users: s∈RU×U
Algorithm with level normalization:
- For user u find a neighbourhood of similar users N(u)
- Generate rating predictions by averaging over N(u) ˆRui=ˉRu+∑v∈N(u)suv(Rvi−ˉRv)∑v∈N(u)|suv|
ˉRu - adjustment to compensate average rating behaviour of u
- skeptics/optimists normalization
User-based CF¶
Algorithm with level and scale normalization:
- For user u find a neighbourhood of similar users N(u)
- Generate rating predictions by averaging over N(u) ˆRui=ˉRu+σu∑v∈N(u)suv(Rvi−ˉRv)/σv∑v∈N(u)|suv|
where σu is standard deviation of user u ratings
Number of NN¶
- In general 20-50 is suggested
- Also possible
- Take all
- Top-k
- suv>θ
Similarity measures¶
For each pair (u,v) the intersection of rated items should be considered!
Pearson correlation suv=∑i∈Iu∩Iv(Rui−ˉRu)(Rvi−ˉRv)√∑i∈Iu∩Iv(Rui−ˉRu)2√∑i∈Iu∩Iv(Rvi−ˉRv)2
tends to give high similarity for users with few ratings
- solution s′uv=suv⋅min{|Iu∩Iv|/50,1}
Other possible measures¶
- Spearman correlation
- correlatino between ranks of ratings
- captures the level of monotone dependencies
- Cosine similarity suv=∑i∈Iu∩IvRuiRvi√∑i∈Iu∩IvR2ui√∑i∈Iu∩IvR2vi
Item-based Collaborative filteting¶
Item-based CF¶
Item-based CF¶
- Also determine similarity function between items s∈RI×I
For item i find a set of items similar to it and rated by user u: N(i)
Predict Rui by averaging over N(i) ˆRui=∑j∈N(i)sijRuj∑j∈N(i)|sij|(1)
Similarities for Item-based CF¶
- Conditional probability of purchase sij=nijni
- Dependency sij=nijninj
Benefits of item-based CF¶
- We need to generate recomendations for user u in real-time when he is active
When user is active - his ratings change
- User-based CF: after changes in rating we need to recalculate all nearest neighbours or user - long!
- Item-based CF: for each pair of items we precalculate similarities sij and find nearest neighbours of each item. Change in user ratings affects only the weights in (1)
Due to possible precomputations, item-item becomes more efficient
- user profile is more dynamic
- item profile is more static
Latent variable models¶
Latent variables models¶
For each user u build a vector pu∈Rk and for each item i - a vector qi∈Rk s.t.: Rui≈p⊤uqi
- pu's components sometimes can be iterpreted as user's interests in topic
- qi's components sometimes can be iterpreted as items's relevance to topic
Singular Value Decomposition¶
Each matrix X∈Rn×d with rank r can be decomposed as X=UΣV⊤, where
- U - unitary matrix, which contains eigenvectors of XX⊤
- V - unitary matrix, which contains eigenvectors of X⊤X
- Σ - diagonal matrix with singular values σi=√λi
Truncated SVD¶
Truncated SVD with rank K X≈ˆX=UkΣkV⊤k, where
- Uk contains first k columns of U
- Vk contains first k columns of V
- Σk contains first k diagonal elements of Σ
SVD разложение¶
It turns out that ˆX=argminA∈Rn×d,rank(A)≤k‖X−A‖Frobenius
Problems¶
- Have to fill missing values
- with 0
- with baseline predictions
- Optionally
- R′=R−B and fill with 0
- In the end:
- P=UΣ1/2
- Q=Σ1/2V⊤
- ˆR=P⊤Q
- How do we calculate pu for new user u given his rating vector ru?
Recalculation for new user¶
pu=argminp‖ru−Vp‖2={OLS solution}=(V⊤V)−1V⊤ru=V⊤ru
- pu=V⊤ru is a vector of scalar products [⟨v1,ru⟩,⟨v2,ru⟩,…,⟨vk,ru⟩]
- Backward transformation from low-dimensional representation pu to initial representation ˆru: ˆru=Vpu
Latent Factor Model (Sparse SVD)¶
- Lets optimize ∑u,i(Rui−ˉRu−ˉRi−⟨pu,qi⟩)2→minP,Q
- Using SGD and going through pairs (u,i) with known Rui: puk=puk+2α(qik(Rui−ˉRu−ˉRi−⟨pu,qi⟩) qik=qik+2α(puk(Rui−ˉRu−ˉRi−⟨pu,qi⟩)
Latent Factor Model (Sparse SVD)¶
- Add regularization ∑u,i(Rui−ˉRu−ˉRi−⟨pu,qi⟩)2+λ∑u‖pu‖2+μ∑i‖qi‖2→minP,Q
- Using SGD and going through pairs (u,i) with known Rui: puk=puk+2α(qik(Rui−ˉRu−ˉRi−⟨pu,qi⟩)−λpuk) qik=qik+2α(puk(Rui−ˉRu−ˉRi−⟨pu,qi⟩)−μqik)
Classification-based models¶
- How can we adapt simple classification task to recommendation system domain?
- Any problems here?
Measuring Quality¶
- Ratings accuracy
- MAE, MSE
- Event quality
- F-score, ROC-AUC, PR-AUC
- precision@k, recall@k
- Ranking quality
- DCG@k(u)=k∑p=1rel(i,p)log(p+1)
- nDCG@k(u)=DCG@k(u)max(DCG@k(u))
Data Analysis
Andrey Shestakov (avshestakov@hse.ru)
Introduction to Recommender Systems11. Some materials are taken from machine learning course of Victor Kitov