Recommender Systems
COMPSCI 753 Kaiqi Zhao
Recommendation algorithms
§ Content-based
§ Recommend based on the attributes of items, e.g., functionality,
topics, types, etc.
§ Collaborative Filtering (CF)
§ User-based: recommend items that similar users liked
§ Item-based: recommend similar items to the items the user liked
10
Content-based recommendation
§ Content-based methods look for the information of items, e.g., description, attributes, etc.
§ Idea: recommend similar items to those have been highly rated by the user, for instance:
§ Movies with the same actors
§ News with the same topic
§ Items within the same category
§ May need to do feature engineering / machine learning to model the content information
11
Content of items
§ The content of items varies
§ Textual content
§ Amazon – reviews, description of items § Twitter – message
§ Attributes
§ Amazon – for computer, we have brand, type, screen, etc. § Netflix – year, genre, actors
§ Multimedia
§ Instagram – images, videos
12
Content-based recommendation
Main steps:
Ø Item profiling – use machine learning (e.g., topic models) or statistic methods (TF-IDF) to extract features of items based on the content
Ø User profiling – gather all the items of a user, and aggregate the features of those items
Ø Compute the “similarity” between the user and item profiles to compute a recommendation score
Ø Rank the items by the recommendation score and return top 𝑁 items to the target user
Item profiles
likes
recommend match
aggregate
Red
Circles Triangles
User profile
13
Item profiles
§ Each item has a profile
§ The profile is often a vector, where each dimension represents a “feature”:
§ menu of a restaurant
§ topics or important words of a doc
§ Features should contribute differently to an item
§ TF-IDF: measure the importance of a a feature
Item profiles
likes
recommend match
aggregate
Red
Circles Triangles
User profile
14
Recap: TF-IDF
§ Term frequency – inverse document frequency (TF-IDF) is a well-known measure in information retrieval
§ It models the importance of each word in the content of an item: 𝑇𝐹−𝐼𝐷𝐹 𝑤,𝑑 =𝑡𝑓 𝑤,𝑑 ×𝑖𝑑𝑓(𝑤)
𝑡𝑓𝑤,𝑑 =𝑓”,$, 𝑖𝑑𝑓(𝑤)=log 𝑁
|{𝑑 ∈ 𝐷: 𝑤 ∈ 𝑑}|
§ Item profile 𝒑𝒗: each item is a “document” represented by a word vector, where each dimension is the tf-idf of the word if it appears in the text of the item, otherwise 0.
15
User profiles
§ User profile 𝒒𝒖: aggregate the features of rated items
§ Unweighted: concatenate all rated item “documents” and compute the
TF-IDF vector of user 𝑢
§ Weighted average: use rating to weight the item profiles
§ Recommendation score 𝑟 𝑢, 𝑣 : cosine similarity
𝒒𝒖 ⋅ 𝒑𝒗 𝒒𝒖 ⋅ 𝒑𝒗
𝒓𝒖,𝒗=𝒄𝒐𝒔𝒒𝒖,𝒑𝒗 =
16
Pros and cons – content-based approach
§ Pros
J Can recommend new items without any ratings J Unpopular items can also be recommended
J Suitable for users with unique taste
J Easy to interpret the recommendation results
§ Cons
L Sensitive to feature selection and need to have the same set of
features for all items
L Not work for new users
L Not suitable for users with multiple interests
17
Collaborative filtering
§ Idea: learns the user preferences from the feedbacks
§ Suppose we have the historical data of users
§ Explicit feedback – user ratings on items
§ Implicit feedback – clicks, scroll, time spent on a page
§ Types of collaborative filtering § User-based
§ Item-based
§ Model-based
18
User-based collaborative filtering
Liked
Similar taste
Liked
Recommend
19
User-based collaborative filtering
§ Basic steps:
§ Search similar users – according to a similarity function over the
historical behaviors on the items
§ Prediction – for each item adopted by similar users, compute estimate the rating that would be given by the user
§ Ranking – Pick the top 𝑁 items and recommend them to the user Item 1
𝑤
Target user
Item 2
Similar users
Weighted average
Item 1: 5 Item 2: 4.5
20
Similarity calculation
§ Let 𝑈 = {𝑢&:(} be the set of users and 𝑃 = {𝑝&:)} be the set of items. 𝑟*+ be the rating from user 𝑢* to item 𝑝+
§ Similarity between two users (𝑢* and 𝑢,): § Cosine similarity
∑+ 𝑟*+𝑟,+
∑𝑟-⋅ ∑𝑟- + *+ + ,+
§ Problem: Treats missing ratings as “negative”
𝑤*, =
21
Example
§ Cosine similarity
5
?
2
?
3
4
?
?
4
?
1
4
?
3
?
2
5
?
?
5
!! ∑# 𝑟!#𝑟”# !”
𝑤!” =
# !# # “# !$
∑𝑟$⋅ ∑𝑟$ !# !%
𝒓! = 5,0,2,0 , 𝒓” = (3,4,0,0)
𝒓! ⋅ 𝒓” 𝒓! ⋅ 𝒓”
=5⋅3+0⋅4+2⋅0+0⋅0 5″+2″ 3″+4″
3 29
𝑤!” =
=
“!
“” “# “$
22
Similarity calculation
§ Let 𝑈 = {𝑢&:(} be the set of users and 𝑃 = {𝑝&:)} be the set of items. 𝑟*+ be the rating from user 𝑢* to item 𝑝+
§ Similarity between two users (𝑢* and 𝑢,): § Pearson correlation coefficient
∑ 𝑟−𝑟̅𝑟−𝑟̅ +∈;!” *+ * ,+ ,
𝑤*, =
+∈;!” *+ * +∈;!” ,+ ,
∑ 𝑟 −𝑟̅ -⋅ ∑ 𝑟 −𝑟̅ –
§ 𝑆*, – the set of items rated by both users 𝑢* and 𝑢,
§ 𝑟̅ and 𝑟̅ — the average ratings of users 𝑢 and 𝑢 *, *,
23
Example
§ Pearson correlation coefficient
!!
5
?
2
?
3
4
?
?
4
?
1
4
?
3
?
2
5
?
?
5
𝑤!” =
∑ 𝑟−𝑟̅𝑟−𝑟̅ ! #∈&!” !# ! “# ” ”
∑ 𝑟 −𝑟̅ $⋅ ∑
𝑟 −𝑟̅ $ !#
!%
“!
#∈&!” !#
!
#∈&!”
“# ”
!$
Common item – 1st item
𝑟 −𝑟̅ 𝑟 −𝑟̅ !! ! “! ”
𝑤!” =
!!! “!!
𝑟 −𝑟̅ “⋅ 𝑟 −𝑟̅ ”
5−3.5 3−3.5 5−3.5 |3−3.5|
=
= −1
“” “# “$
24
Prediction
§ Prediction – use the similarity to weight the ratings of items from other user 𝑢*
𝑟̂ = ∑B”∈C# 𝑤*,𝑟,+
*+
𝑈+ – set of most similar users who rated item 𝑝+
∑B”∈C# 𝑤*,
25
User-based collaborative filtering
§ User-based CF example
Step 1:
𝑤)” = cos(𝑢), 𝑢”)
Step 2: 𝑟̂ )#
= ∑”∈+# 𝑤)”𝑟”# ∑”∈+# 𝑤)”
5
?
2
?
3
4
?
?
4
?
1
4
?
3
?
2
5
?
?
5
𝑢’ 𝑢$
𝑢( 𝑢)
𝑢*
𝑝’
𝑤#$ 𝑟$%
0 0.67
0.39 0.39
–
𝑝$ 𝑝( 𝑝) 𝑢)
When predicting the rating, we can either consider 1) all the users or 2) only k most similar users
2
1.54
–
26
–
–
1.96
3.8
–
3
?
0.39
?
–
1
2
Item-based collaborative filtering
Another view:
Liked
Liked
Similar items
Recommend
27
Item-based collaborative filtering
§ Basic steps:
§ Search similar items – use the historical ratings from other users
§ Prediction – Weighted average on the most similar items that have been rated by the target user.
§ Ranking – Pick the top 𝑁 items and recommend them to the user
Item 1: 2
Item 2: 5
Weighted sum
Item 3: 4.5
Target user
Item 4: ?
4.2
28
Item-based collaborative filtering
§ Let 𝑈 = {𝑢”:$} be the set of users and 𝑃 = {𝑝”:%} be the set of items. 𝑟&’ be the rating from user 𝑢& to item 𝑝’
§ Finding similar items
§ Similarity – correlation between two items (𝑝! and 𝑝”)
∑
𝑤%&=
∑
𝑟 −𝑟̅ 𝑟 −𝑟̅ ‘!∈) $% % $& &
or 𝑤%&=
∑’ ∈)𝑟$%𝑟$& !
∑ 𝑟”⋅∑ 𝑟” ‘!∈) $% ‘!∈) $&
𝑟 −𝑟̅ $% %
”
⋅ ∑
𝑟 −𝑟̅ ” $& &
‘!∈)
‘!∈)
Pearson correlation
§ Prediction – use the item similarity to weight the ratings from the
other items rated by target user 𝑢&
𝑟̂ =∑E∈F!𝑤+E𝑟*E *+ ∑E∈F! 𝑤+E
𝑃* – set of most similar items rated by user 𝑢* 29
Cosine similarity
Item-based collaborative filtering
§ Item-based CF example
𝑤#,=cos(𝑝#,𝑝,)
𝑢 𝑝$ 𝑝 ‘)
Step 1:
Step 2:
𝑟̂ =∑&∈+”𝑤%&𝑟*&
*%
∑&∈+” 𝑤%&
2
?
?
?
1
4
?
2
?
5
5
0.28
0.71
0
0.27
𝑢$
𝑢( 𝑢)
𝑢*
𝑝’
𝑝’ 𝑝(
3
2.28
3
2
2
4
?
?
3
?
2
5
?
4
?
3
?
𝑝$ 𝑝( 𝑝)
30
Pros and cons – collaborative filtering
§ Pros
J Don’t need extra information from items
J Leverage the information from other users/items
§ Cons
L Cold-start problem
§ New users – user that has no/limited ratings, we need many rating records to construct accurate user profiles
§ New items – item that has no/limited ratings will not be recommended until it has been rated several times by users.
L Biased on popular items
31
Implementation details: global and local effects
§ Global effect:
§ Mean pizza stores rating: 3.5 stars
§ Pizzahut (item) is 0.5 stars above avg.
§ Kate (user) rates 0.2 stars below avg. Þ Kate may rate Pizzahut 3.8 stars
§ Local neighborhood (CF):
§ Other users share similar interests with
Kate had low ratings to Pizzahut
Þ Kate may rate Pizzahut 3.6 stars
32
Distinguish global and local terms
§ Global terms
§ 𝑏J – Bias on all users and items
§𝑏* -Biasonauser𝑖overallitems § 𝑏+ – Bias on an item 𝑗 over all users
⇒ 𝑏*+ = 𝑏J + 𝑏* + 𝑏+
§ Local terms from CF
𝑟̂ = ∑B”∈C# 𝑤*,𝑟,+ *+ ∑B”∈C# 𝑤*,
By distinguishing global and local terms, we often get better accuracy!
𝑟̂ = 𝑏 + ∑B”∈C# 𝑤*,(𝑟,+ − 𝑏,+) *+ *+ ∑B”∈C# 𝑤*,
33