CS代写 WWW 2001.

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 ru1  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 m50  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