MULTIMEDIA RETRIEVAL
Semester 1, 2022
Recommender Systems
Background
Copyright By PowCoder代写 加微信 powcoder
Recommendation algorithms
Collaborative filtering
User based
Model based
Matrix factorization
Content-based
Product, document, image, video, audio
Learning based
Context Aware Recommendation Evaluation
School of Computer Science
Recommendation is everywhere
School of Computer Science
Recommendation is everywhere
eCommerce
Amazon, eBay, …
Facebook, LinkedIn, …
Friends, groups, jobs Media
Youtube, Netflix, Spotify, … News
Advertisement
MOOC, tourism, …
School of Computer Science
Benefits of RecSys
For customers or users
Find relevant things
Narrow down the set of choices Help explore the space of options Discover new things
For providers or vendors
Additional and probably unique personalized or customized service Increase trust and customer loyalty
Increase sales (30% – 70%), click through rates, conversion etc.
Opportunities for promotion, persuasion
Obtain more knowledge about customers
School of Computer Science
Problem Statement
User model and profile (e.g., ratings, preferences, and
other meta data)
Items (with or without attributes)
Recommend items to potential users
Relevance score in terms of various criteria (e.g., context) Obtain missing values between users and items
Netflix: 100K movies, 10M users, 1B ratings
School of Computer Science
Paradigms of RecSys
Personalized: who you are Opinions of my peers
Similar products Knowledge: my need
School of Computer Science
Collaborative Filtering
Input: users provide ratings for some items (explicitly or
implicitly)
Output: produce missing ratings between users and items
Users having similar ratings have similar interests or
preferences
Recommend items rated highly by similar users, but not rated by the current user
Nappy vs Beer
The most practical and prominent approach!
D. Goldberg, D. Nichols, B. M. Oki, and D. Terry, Using collaborative filtering to weave an information tapestry, Communications of the ACM, 35(12): 61-70, Dec 1992.
School of Computer Science
User based Nearest-neighbour CF
Select to most similar users (peers) to the active user over a target item
Aggregate (e.g. average) the ratings of the peers
School of Computer Science
School of Computer Science
User based Nearest-neighbour CF
Given an “active user” Alice and an item i not yet seen by Alice
To estimate Alice’s rating (i.e. interest) over this item i
Find a set of users (peers) who liked the same items as Alice in the past AND who have rated i
Aggregate the ratings of the peers for producing the ratings of Alice over i
Perform this for all the items Alice has not seen and identify the best rated items
School of Computer Science
User based Nearest-neighbour CF
Questions
How to decide peers
Who and how many How to aggregate
School of Computer Science
Similarity metric: correlation
The similarity of two users(’ history)
Consider only the items which have been
rated by both of them Pearson correlation: sim(X, Y) =
School of Computer Science
Similarity metric
Alice vs User 1
sim(Alice,
𝑠𝑖𝑚𝑎, 𝑏
∑𝑟, 𝑟𝑟, 𝑟
∑𝑟, 𝑟
∑𝑟, 𝑟
School of Computer Science
Works well in usual domains, compared with alternatives
Cosine similarity
School of Computer Science
Recommendation
Users: a and b
: the average rating of a
rb,p: the rating on item p from user b
Similarity weight
sim(a,b): correlation between a and b
School of Computer Science
Recommendation
School of Computer Science
Recommendation
School of Computer Science
Improving the metrics
Not all neighbor ratings might be equally “valuable”
Agreement on commonly liked items is not so informative as agreement
on controversial items
Possible solution: Give more weight to items that have a higher variance
Value of number of co-rated items
Use “significance weighting”, by e.g., linearly reducing the weight when
the number of co-rated items is low Case amplification
Intuition: Give more weight to “very similar” neighbors, i.e., where the similarity value is close to 1.
Neighborhood selection
Use similarity threshold or fixed number of neighbors
More recently, social recommenders use social relations (e.g. friendship) to select “similar” users rather than the full set of users
School of Computer Science
Rating Prediction
Predict a rating, pa,i, for each item i, for active user, a, by using the n selected neighbor users, u {1,2,…n}.
To account for users different ratings levels, base predictions on differences from a user’s average rating.
Weight users’ ratings contribution by their similarity to the active user.
p ru1 a,ia n
School of Computer Science
Significance Weighting
Do not to trust correlations based on very few co-rated items
Include significance weights, sa,u, based on number of co-rated items, m.
w s csim(a,u) a,u a,u a,u
1if m 50
sa,u m if m50 50
School of Computer Science
Memory based (user based) vs Model based (item based)
User-based CF is said to be “memory-based”
the rating matrix is directly used to find “similar” users to make
predictions
does not scale for most real-world scenarios (unless we know something about the users, other than the previous purchases)
large e-commerce sites (Amazon, NeSlix) have tens of millions of customers and millions of items (but they are just a few companies, while many companies are interested in recommending but have cold- start problem)
Model-based CF approaches
based on an offline pre-processing or “model-learning” phase at runtime, only the learned model is used to make predictions models are updated / re-trained periodically
large variety of techniques used
model-building and updating can be computationally expensive
School of Computer Science
Item-based CF
Basic idea
Item-based (model-based) CF exploits relationships between items first, instead of between users
Relationship between items can be computed offline
B. Sarwar et al., Item-based collaborative filtering recommendation algorithms, WWW 2001.
School of Computer Science
Item-based CF
Basic idea
User the similarity between items to make predictions
However, we need to know something about the items (e.g., descriptions)
Look for items that are similar to Item 5 (as for rating)
School of Computer Science
Cosine Similarity
School of Computer Science
Problems with CF
Cold Start: There needs to be enough other users already in the system to find a match.
Sparsity: If there are many items to be recommended, even if there are many users, the user/ratings matrix is sparse, and it is hard to find users that have rated the same items.
First Rater: Cannot recommend an item that has not been previously rated.
New items
Esoteric items
Popularity Bias: Cannot recommend items to someone with unique tastes.
Tends to recommend popular items.
School of Computer Science
User cold-start
School of Computer Science
Item Cold-Start
School of Computer Science
Solutions for Cold-Start
Use better algorithms
Beyond nearest-neighbour approach
Use weaker notions of similarity (e.g., recursive collaborative filtering)
Matrix factorization (e.g., singular value decomposition) Association rule mining
Probabilistic models
Clustering models, Bayesian networks,
Various other machine learning approaches
Deep learning
School of Computer Science
Matrix Factorization
Exploring latent features (e.g., attributes) of rating matrix R of U users and D items.
K latent features P (of size U×K) Q (of size D×K)
Koren et al. Matrix factorization techniques for recommender systems. Computer, 2009. https://towardsdatascience.com/paper-summary-matrix-factorization-techniques-for-recommender-systems-82d1a7ace74
School of Computer Science
Matrix Factorization
Exploring latent features (e.g., attributes)
Koren et al. Matrix factorization techniques for recommender systems. Computer, 2009. https://towardsdatascience.com/paper-summary-matrix-factorization-techniques-for-recommender-systems-82d1a7ace74
School of Computer Science
Matrix Factorization
Iterative optimization through gradient descent Error
Partial derivative
Update rules
Koren et al. Matrix factorization techniques for recommender systems. Computer, 2009. https://towardsdatascience.com/paper-summary-matrix-factorization-techniques-for-recommender-systems-82d1a7ace74
School of Computer Science
Matrix Factorization
Convergence
Tr is the training set (i.e., where rij is available).
Regularization
Avoid overfitting by penalizing the magnititudes of
School of Computer Science
Matrix Factorization
A sample result
http://www.albertauyeung.com/post/python-matrix-factorization/
School of Computer Science
Collaborative Filtering – Summary
Intuitive, well understood
Performs well in practice
No need for feature engineering
Requires user community with a critical mass
Computational challenges because of the
huge matrix…
Incorporating external information is difficult
School of Computer Science
Content-based (CB) RecSys
Attributes/content of an item
Movie: actors, director, category, description, …
Independent of the opinions of other users
Identifying items similar to those a user has rated Matching an item with a user’s profile
School of Computer Science
Content-based RecSys – Summary
Independent from other users (no need for critical mass)
Recommendation can be given for a single user
The cold start problem is smaller
No need for handling a huge matrix
It recommends from the long tail
It can give you a “user model”
Keywords/description may not be sufficient
School of Computer Science
Content-based RecSys – Summary
Feature engineering is domain-specific and requires external data collection
The filter bubble problem:
The greatest predicted rating might be a wrong
recommendation as it “overfits” to the user’s preferences
if the user rated only Hungarian and Chinese restaurants the system won’t recommend a Greek restaurant (even it’s the best in the town)
A new user has to be modeled, i.e. a sufficient personal training data is needed
School of Computer Science
Knowledge-based (KB) RecSys
Products with low number of available ratings
Time span plays an important role
Five-year-old ratings for computers
User lifestyle or family situation changes
Customers want to define their requirements explicitly
The color of the car should be black.
School of Computer Science
Three RecSys Paradigms
School of Computer Science
Context-aware RecSys (CARS)
Recommendation can also be influenced by context
Time, location, weather, social information, mood, device, …
Fine grained recommendation
Contextual information will add extra
dimensions to existing frameworks Extending matrix to tensor
School of Computer Science
Sample Data
School of Computer Science
Evaluation of RecSys
What is a good recommendation?
School of Computer Science
Purpose and success criteria
Different perspectives/aspects
Depends on domain and purpose
No holistic evaluation scenario exists
Retrieval perspective
Reduce search costs
Provide “correct” proposals
Assumption: Users know in advance what they want
Recommendation perspective
Serendipity – identify items from the Long Tail – not
obvious recommendations!
Users did not know about their existence
School of Computer Science
Sample case
School of Computer Science
Purpose and success criteria
Prediction perspective
Predict to what degree users like an item
Most popular evaluation scenario in research
Interaction perspective
Give users a “good feeling”
Educate users about the product domain Convince/persuade users – explain
Finally, conversion perspective
Commercial situations
Increase “hit”, “clickthrough”, “lookers to bookers” rates Optimize sales margins and profit
School of Computer Science
How do we know?
Test with real users
A/B tests
Example measures: sales increase, click through rates – as we said, real users are often not available for new types of recommenders (e.g., recommending places to visit during a trip)
Laboratory studies
Controlled experiments: recruit a number of possible users
Example measures: satisfaction with the system (questionnaires)
Offline experiments
Based on historical data (predict the “known” future: remove items from a user’s purchase list, learn a recommendation model based on these “purged” data, and then test if system would recommend removed items)
Example measures: prediction accuracy, coverage
School of Computer Science
Offline experimentation needs large datasets
Netflix prize dataset
Web-based movie rental
Prize of $1,000,000 for accuracy improvement (RMSE) of 10% compared to own Cinematch system.
Movilens
11 million ratings of 8500 movies
https://en.wikipedia.org/wiki/MovieLens
Million song dataset
https://labrosa.ee.columbia.edu/millionsong/
Wiki-MED
the largest multi-domain
http://iswc2018.semanticweb.org/sessions/wiki-mid-a-very-large- multi-domain-interests-dataset-of-twitter-users-with-mappings-to- wikipedia/
School of Computer Science
Need to Know
Recommendation algorithms Collaborative filtering
Content-based
Learning based
Context Aware Recommendation Time, location, …
Evaluation
School of Computer Science
References
D. Jannah, M. Zanker, and G. Friedrich, Recommender Systems, IJCAI 2017 Tutorial.
B. Mobasher, Context aware Recommendation, KDD 2014 Tutorial.
Must-read papers on Recommender System https://github.com/hongleizhang/RSPapers
School of Computer Science
[Hariri et al., 2012] Context-aware music recommendation based on latent topic sequential patterns, RecSys.
School of Computer Science
More advanced techniques
Locality sensitive hashing Multi-modal hashing
Cross-modal retrieval
School of Computer Science
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com