Introductio Recommender Systems o What is this lecture about? What is the purpose of a recommender system? Alban galland b What are the key features What are the main challenges? When to use it 18 March 2010 How to design it? 03/18/20101/ 03/18/20102/4 Content Content O Who uses a recommender system? O Who uses a recommender system? Q What tasks and data correspond to a recommendation problem? e What tasks an o Content-filter . Collaborative-filtering algorithms o Collabo No o User-based o Item-based ● Hybrid methods furthe O To go o Interesting issues o Interesting iss
Recommender Systems Alban Galland INRIA-Saclay 18 March 2010 A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 1 / 42 Introduction What is this lecture about? I What is the purpose of a recommender system? I What are the key features? I How does it work? I What are the main challenges? I When to use it? I How to design it? A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 2 / 42 Content 1 Who uses a recommender system? 2 What tasks and data correspond to a recommendation problem? 3 How to do it? Content-filtering algorithms Collaborative-filtering algorithms Not personalized User-based Item-based Hybrid methods 4 To go further Interesting issues Bibliography A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 3 / 42 Who uses a recommender system? Content 1 Who uses a recommender system? 2 What tasks and data correspond to a recommendation problem? 3 How to do it? Content-filtering algorithms Collaborative-filtering algorithms Not personalized User-based Item-based Hybrid methods 4 To go further Interesting issues Bibliography A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 4 / 42
Content site e Commerce site o Example: Amazon, Netflix t, The Ar a cat g Examples: Allo Cine, Zagat, o Task: build group of products Library Thing, Last. fm, Pandora generally find a list of products g Task: predict ratings of items by ven user or find a list of o Data: list of purchases and owning history for all users o Data: precise conter 爵 description, explicit rating for 03/18/20105 03/18/20106/4 e Commerce site Advertisement o The Netflix challenge Sponsored Links o Example: google AdSense SIM prize competition Double Click lew car Input: huge training dataset Goal: improve root mean square prediction error rate of 10% compare g Task: find a list of iew New Used Local Listings Now to Netflix agorithm 40000+teams from 186 countries(5000+ teams with valid according to expected income Own car o Data: browsing history for al Begins October 2006, winners in June 2009 ww thefreecar com
Who uses a recommender system? Content site Examples: AlloCine, Zagat, LibraryThing, Last.fm, Pandora, StumbleUpon Task: predict ratings of items by a given user or find a list of interesting items Data: precise content description, explicit rating for some user Recommendation on LibraryThing A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 5 / 42 Who uses a recommender system? eCommerce site Example: Amazon, Netflix Task: build group of products for bundle sales or more generally find a list of products that the user is likely to buy Data: list of purchases and browsing history for all users Recommendation on Amazon A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 6 / 42 Who uses a recommender system? eCommerce site The Netflix challenge I $1M prize competition I Input: huge training dataset I Goal: improve root mean square prediction error rate of 10% compare to Netflix algorithm I 40000+ teams from 186 countries (5000+ teams with valid submissions) I Begins October 2006, winners in June 2009 A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 7 / 42 Who uses a recommender system? Advertisement Example: Google AdSense, DoubleClick Task: find a list of advertisements optimized according to expected income Data: browsing history for all users Recommendation on Google A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 8 / 42
Content What to do with data? e What tasks and data correspond to a recommendation problem? o Two kinds of problem with data Information retrieval (IR): static content, dynamic query= modeling o Content-filtering algorithms content(organized with index Collabor Information filtering(IF): dynamic content, static query = modeling N query(organized as filters o Recommendation is between IR and IF since the content varies slowly IF are then used to reduce computation at query time OtA and the queries depend of few parameters. Methods of both IR and 03/18/20109/42 03/18/201010/4 Task(1) Task(2) ● General purpose g Degree of personalization Top-k filtering: list of "best"items(main usage) or anti-spam everyone receives same b items correlation: find similar items nographic: everyone in the same category receives same Prediction of rating: predict affinity between any pair of an user and an Contextual: recommendation depends only on current activity Persistent: recommendation depends on long-term interests
What tasks and data correspond to a recommendation problem? Content 1 Who uses a recommender system? 2 What tasks and data correspond to a recommendation problem? 3 How to do it? Content-filtering algorithms Collaborative-filtering algorithms Not personalized User-based Item-based Hybrid methods 4 To go further Interesting issues Bibliography A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 9 / 42 What tasks and data correspond to a recommendation problem? What to do with data? Two kinds of problem with data: I Information retrieval (IR): static content, dynamic query ⇒ modeling content (organized with index) I Information filtering (IF): dynamic content, static query ⇒ modeling query (organized as filters) Recommendation is between IR and IF since the content varies slowly and the queries depend of few parameters. Methods of both IR and IF are then used to reduce computation at query time. A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 10 / 42 What tasks and data correspond to a recommendation problem? Task(1) General purpose I Top-k filtering: list of “best” items (main usage) or anti-spam I Items correlation: find similar items I Prediction of rating: predict affinity between any pair of an user and an item (more general) A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 11 / 42 What tasks and data correspond to a recommendation problem? Task(2) Degree of personalization I Generic: everyone receives same recommendations I Demographic: everyone in the same category receives same recommendations I Contextual: recommendation depends only on current activity I Persistent: recommendation depends on long-term interests A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 12 / 42
Data(1) Data(2) o Context of the current page(current request, item currently explored and structured content about this context o History of the current user on the system(explicit or implicit ratings) of all user Users Items of the current user on multiple systems, the whole web or even on its computer o History of all users on multiple systems, the whole web or even their puter 03/18/20 03/18/201014/42 Explicit ratings Implicit ratings o Numeric ratings Numeric scale, usually between 2(thumb up/ thumb down )and 15 o Based teraction and time (between A+ and E-)levels purchase The more levels you have, the much data you get but the much variance you have on these data browsing( page view time) Numeric ratings should be normalized cursor on the page o Partial order: comparison between two items o Used to generate an implicit nu rating o Semantic information: tags, labels
What tasks and data correspond to a recommendation problem? Data (1) Context of the current page (current request, item currently explored and structured content about this context) History of the current user on the system (explicit or implicit ratings) History of all users on the system History of the current user on multiple systems, the whole web or even on its computer History of all users on multiple systems, the whole web or even their computer A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 13 / 42 What tasks and data correspond to a recommendation problem? Data (2) In general, three matrix as input: I Users attributes I Items attributes I Rating matrix A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 14 / 42 What tasks and data correspond to a recommendation problem? Explicit ratings Numeric ratings: I Numeric scale, usually between 2 (thumb up/thumb down) and 15 (between A+ and E-) levels. I The more levels you have, the much data you get but the much variance you have on these data. I Numeric ratings should be normalized. Partial order: comparison between two items Semantic information: tags, labels A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 15 / 42 What tasks and data correspond to a recommendation problem? Implicit ratings Based on interaction and time I purchase I clicks I browsing (page view time) I cursor on the page Used to generate an implicit numeric rating A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 16 / 42
Content General scope a Who uses a re 3 How to do it o Purely editorial(still used for some advertisement) o Collaborative-filtering algorithms o Content filtering: depending on attributes of items g Collaborative filtering: depending on ratings of all users o User-based o Hybrid o Item-based ● Hybrid methods o Interesting 03/18/201017/42 03/18/201018/42 ontent filtering algorithms do it? Collaborative-filtering algorithms Content-filtering algorithms Direct aggregation o Usually, content-filtering algorithms means an algorithm based on the g Usually, collaborative filtering algorithm means an algorithm based on attributes of the items and the ratings of the targeted user the rating matrix. g Interpretation of the preferences of users as a function of the g The recommender system displays some statistics summary attributes e the average rating of the users o Two main methods. age rating of professional Heuristic-based: Use common techniques of information retrieval set of reviews of the users or of professional reviewer presented earlier in the course: TF/IDF, cosine, clusterin o Some basic techniques such as explicit voting or date are used to rank Model-based: Use a probabilistic model to learn prediction of users
How to do it? Content 1 Who uses a recommender system? 2 What tasks and data correspond to a recommendation problem? 3 How to do it? Content-filtering algorithms Collaborative-filtering algorithms Not personalized User-based Item-based Hybrid methods 4 To go further Interesting issues Bibliography A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 17 / 42 How to do it? General scope Purely editorial (still used for some advertisement) Content filtering: depending on attributes of items Collaborative filtering: depending on ratings of all users Hybrid A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 18 / 42 How to do it? Content-filtering algorithms Content-filtering algorithms Usually, content-filtering algorithms means an algorithm based on the attributes of the items and the ratings of the targeted user Interpretation of the preferences of users as a function of the attributes Two main methods: I Heuristic-based: Use common techniques of information retrieval presented earlier in the course : TF/IDF, cosine, clustering... I Model-based: Use a probabilistic model to learn prediction of users from attributes A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 19 / 42 How to do it? Collaborative-filtering algorithms Direct aggregation Usually, collaborative filtering algorithm means an algorithm based on the rating matrix. The recommender system displays some statistics summary I the average rating of the users I the average rating of professional reviewers. I a set of reviews of the users or of professional reviewer Some basic techniques such as explicit voting or date are used to rank reviews. A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 20 / 42
User-based collaborative filtering Some correlation methods o Let U; be the vector of ratings of user u;(see as a line). correlation users ratings Scalar product similarity sim(u;, ui)=U; U o For each user u;, compute correlation with others users o For each item ik, aggregate the ratings of ik by the users highly correlated with Ui sim(u;,uj)=UlllUill o Problem: sparsity of data(little information about each user)=bad Another one correlation, easy to attack(cf. cold start and attacks issues) sually, as to lized to get meaningful results 03/18/201021/ 03/18/201022/4 Collaborativefiltering algorithms do it? Collaborative-filtering algorithms Some aggregations methods Application on an example o Let r(;, ik)the rating prediction of user u; and item ik o Let St(ui=uj, sim u;, U;)>t the users highly correlated with u for a threshold t b Means on the best users o What would you predict for userl on item5, item and item7? er item1 item2 item3 item4 item5 item item 4)=5(c7,4) Weighted average on the bests users 55514 4 sim(ui, ur(Uj, ik) 4)-255 5(a)Sm(u,丐 o Usually, choice of St(ui) is sensitive since it is a trade-off between
How to do it? Collaborative-filtering algorithms User-based collaborative filtering user users correlation ratings aggregation For each user ui , compute correlation with others users For each item ik , aggregate the ratings of ik by the users highly correlated with ui Problem: sparsity of data (little information about each user) ⇒ bad correlation, easy to attack (cf. cold start and attacks issues) A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 21 / 42 How to do it? Collaborative-filtering algorithms Some correlation methods Let Ui be the vector of ratings of user ui (see as a line). I Scalar product similarity: sim(ui , uj) = Ui tUj I Cosine similarity: sim(ui , uj) = Ui tUj kUikkUjk I Another one: sim(ui , uj) = Ui tUj kUik 2 Usually, Ui has to be normalized to get meaningful results A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 22 / 42 How to do it? Collaborative-filtering algorithms Some aggregations methods Let ˆr(ui , ik ) the rating prediction of user ui and item ik Let St(ui) = {uj ,sim(ui , uj) > t} the users highly correlated with ui for a threshold t I Means on the best users ˆr(ui , ik ) = 1 |St(ui)| X St (ui ) r(uj , ik ) I Weighted average on the bests users ˆr(ui , ik ) = P St (ui ) sim(ui , uj)r(uj , ik ) P St (ui ) sim(ui , uj) Usually, choice of St(ui) is sensitive since it is a trade-off between sparsity and noise. A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 23 / 42 How to do it? Collaborative-filtering algorithms Application on an example What would you predict for user1 on item5, item6 and item7? user item1 item2 item3 item4 item5 item6 item7 user1 5 3 4 1 ? ? ? user2 5 3 4 1 5 2 5 user3 5 ? 4 1 5 3 ? user4 1 3 2 5 1 4 2 user5 4 ? 4 4 4 ? 4 A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 24 / 42
Item-based collaborative filtering Application on an example user items relation o What would you predict for userl on item and item? user item1 item2 item3 item4 tem6 item o For each item ik, compute correlation with others items o For each user Uj, aggregate her ratings of the items highly correlated with ik 5551 4424 1154 551 3 o For items, sparsity of data is less important= less problems with cold start and attacks 25 03/18/201026/42 to do it? Collaborative-filtering algorithms Matrix representation Model-based techniques (out of the scope of this course) RERRR o R is the normalized predicted rating matrix. o Learn the ratings using a probabilistic model of generation(e. g o R is the normalized rating matrix where unknown values have been Latent-class generative model) and estimation of the parameters(e.g using Expectation Maximization) o This computation correspond to both user-based and item-based collaborative filtering with scalar product correlation using all intermediate seeds One could use classic matrix dimensionality reduction such as singular alue decomposition to decrease the computational cost and improve
How to do it? Collaborative-filtering algorithms Item-based collaborative filtering user user_items ratings items correlation For each item ik , compute correlation with others items For each user ui , aggregate her ratings of the items highly correlated with ik For items, sparsity of data is less important ⇒ less problems with cold start and attacks A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 25 / 42 How to do it? Collaborative-filtering algorithms Application on an example What would you predict for user1 on item5, item6 and item7? user item1 item2 item3 item4 item5 item6 item7 user1 5 3 4 1 ? ? ? user2 5 3 4 1 5 2 5 user3 5 ? 4 1 5 3 ? user4 1 3 2 5 1 4 2 user5 4 ? 4 4 4 ? 4 A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 26 / 42 How to do it? Collaborative-filtering algorithms Matrix representation R 0 = R tR R (1) R 0 is the normalized predicted rating matrix. R is the normalized rating matrix where unknown values have been set to 0 This computation correspond to both user-based and item-based collaborative filtering with scalar product correlation using all intermediate seeds. One could use classic matrix dimensionality reduction such as singular value decomposition to decrease the computational cost and improve results. A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 27 / 42 How to do it? Collaborative-filtering algorithms Model-based techniques (out of the scope of this course) Learn the ratings using a probabilistic model of generation (e.g. Latent-class generative model) and estimation of the parameters (e.g. using Expectation Maximization) A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 28 / 42
ybrid metho Hybrid methods Content O Who uses a r o Usually, hybrid algorithms use both items attributes and the ratings of all users O How to do it? o Generals methods o Content-filtering algorithms Heuristic combination of content-filtering and collaborative-filtering Collaborative-filtering algorithm methods N For the model-based techniques, modification of the model to take into account both kinds of data.(E.g. Hierarchical Bayesian model of users and items heterogeneity and estimation via Markov Chain Monte Carlo O To go further o Interesting issues 03/18/201029/42 03/18/201030/42 Data Quality Confidence and display (1) o How to manage the cold start problem(new user, new item)or more generally o How to improve the confidence in the recommender system? The system must have a special behavior for user with few ratings(eg By providing good recommendations not personalized recommendation) By providing information about each recommendation(eg. ratings, The system may use bot-users to rate new items according to the
How to do it? Hybrid methods Hybrid methods Usually, hybrid algorithms use both items attributes and the ratings of all users Generals methods I Heuristic combination of content-filtering and collaborative-filtering methods I For the model-based techniques, modification of the model to take into account both kinds of data. (E.g. Hierarchical Bayesian model of users and items heterogeneity and estimation via Markov Chain Monte Carlo) A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 29 / 42 To go further Content 1 Who uses a recommender system? 2 What tasks and data correspond to a recommendation problem? 3 How to do it? Content-filtering algorithms Collaborative-filtering algorithms Not personalized User-based Item-based Hybrid methods 4 To go further Interesting issues Bibliography A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 30 / 42 To go further Interesting issues Data Quality How to manage the cold start problem (new user, new item) or more generally data sparsity? I The system must have a special behavior for user with few ratings (eg. not personalized recommendation) I The system may use bot-users to rate new items according to the content A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 31 / 42 To go further Interesting issues Confidence and display(1) How to improve the confidence in the recommender system? I By providing good recommendations! I By providing information about each recommendation (eg. ratings, explanation) A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 32 / 42
Confidence and display(2) Interaction and time (1) o How to interact with the user? o How to display recommendations? You may ask the user to correct a prediction The item recommended must be easy to identify and evaluate by the must update your rating matrix with this prediction and update Ir recommendation accordingly Ratings must be easy to understand and meaningful You may want to learn the key parameters of your algorithm using the Explanations must provide a quick way for the user to evaluate the feedback recommendation on the ex You may ask the user to provide more context for the current task(eg by using categories) 03/18/20 03/18/201034/4 Interaction and time (2) Data and security (1) o How to manage scalability Applications usually need real-time prediction computation The computation time has to scale with number of users and items o How to insure privacy? g How to manage temporal changes? If the profile is public, there is no privacy issues You can not run your algorithms each time a modification occurs If the profile is private, the system should avoid to give too much The off-line computation must be robust to small modification and nformation using anonymity techniques. scheduled accordingly This problem is even worse in cross-system The on-line computation must benefit from modifications The computation must be done incrementally when possible The system may "forget"older information
To go further Interesting issues Confidence and display(2) How to display recommendations? I The item recommended must be easy to identify and evaluate by the user I Ratings must be easy to understand and meaningful I Explanations must provide a quick way for the user to evaluate the recommendation A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 33 / 42 To go further Interesting issues Interaction and time(1) How to interact with the user? I You may ask the user to correct a prediction I You must update your rating matrix with this prediction and update your recommendation accordingly I You may want to learn the key parameters of your algorithm using the feedback I You may ask the user to provide feedback on the explanation I You may ask the user to provide more context for the current task (eg. by using categories) A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 34 / 42 To go further Interesting issues Interaction and time(2) How to manage scalability I Applications usually need real-time prediction computation I The computation time has to scale with number of users and items How to manage temporal changes? I You can not run your algorithms each time a modification occurs I The off-line computation must be robust to small modification and scheduled accordingly I The on-line computation must benefit from modifications I The computation must be done incrementally when possible I The system may “forget” older information A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 35 / 42 To go further Interesting issues Data and security(1) How to insure privacy? I If the profile is public, there is no privacy issues I If the profile is private, the system should avoid to give too much information using anonymity techniques. I This problem is even worse in cross-systems A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 36 / 42
Data and security (2) Improving recommendation (1) Attacks are characterized by number of false users and knowledge on o How to manage diversity? he syste Recommending very close items could be counter-productive(since The attacker want to modify the distribution of th they may be substitute)= Systems can use correlation between items being easy to detect (eg. base on content) to filter items There is a lot of known attacks such as sampling attack, random Recommending what everybody like and what the user already know is attack, average attack, bandwagon attack not really interesting=> Systems can try more risky prediction(eg ot of techniques to detect attack: find profiles which are unlikely high score with low confidence) according to the global distribution of profiles, find profiles update hich are unlikely according to the global distribution of updates. 03/18/20 03/18/201038/4 teresting Interesting Improving recommendation (2) Improving recommendation( 3) o How to use social networks to improve recommendations? g How to recommend for a group? Users are likely The recommendation for the group could be an aggregation of the Exploring the social graph is a direct way to do recommendation recommendation for the members Correlation between user could be biased by the social graph The group could be seen as a user(with aggregation functions to Potential friends could be suggested using recommendation techniques. reconciliate ratings
To go further Interesting issues Data and security(2) How to design algorithms that are robust against manipulation? I Attacks are characterized by number of false users and knowledge on the system. I The attacker want to modify the distribution of the ratings without being easy to detect I There is a lot of known attacks such as sampling attack, random attack, average attack, bandwagon attack... I Lot of techniques to detect attack : find profiles which are unlikely according to the global distribution of profiles, find profiles updates which are unlikely according to the global distribution of updates... A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 37 / 42 To go further Interesting issues Improving recommendation(1) How to manage diversity? I Recommending very close items could be counter-productive (since they may be substitute) ⇒ Systems can use correlation between items (eg. base on content) to filter items I Recommending what everybody like and what the user already know is not really interesting ⇒ Systems can try more risky prediction (eg. high score with low confidence) A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 38 / 42 To go further Interesting issues Improving recommendation(2) How to use social networks to improve recommendations? I Users are likely to like what their friends like. I Exploring the social graph is a direct way to do recommendation I Correlation between user could be biased by the social graph I Potential friends could be suggested using recommendation techniques. A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 39 / 42 To go further Interesting issues Improving recommendation(3) How to recommend for a group? I The recommendation for the group could be an aggregation of the recommendation for the members. I The group could be seen as a user (with aggregation functions to reconciliate ratings) A. Galland (INRIA-Saclay) Recommender Systems 03/18/2010 40 / 42