Recommendation Systems - Stanford University

1 Chapter 9 Recommendation SystemsThere is an extensive class of Web applications that involve predictinguserresponses to options. Such a facility is called arecommendation system. Weshall begin this chapter with a survey of the most important examples of thesesystems. However, to bring the problem into focus, two good examples ofrecommendation Systems are:1. Offering news articles to on-line newspaper readers, based on a predictionof reader Offering customers of an on-line retailer suggestions about whattheymight like to buy, based on their past history of purchases and/or Systems use a number of different technologies.

2 We canclassify these Systems into two broad groups. Content-based systemsexamine properties of the items recommended. Forinstance, if a Netflix user has watched many cowboy movies, then recom-mend a movie classified in the database as having the cowboy genre. Collaborative filteringsystems recommend items based on similarity mea-sures between users and/or items. The items recommended to a user arethose preferred by similar users. This sort of Recommendation system canuse the groundwork laid in Chapter 3 on similarity search and Chapter7on clustering.

3 However, these technologies by themselves are notsuffi-cient, and there are some new algorithms that have proven effective forrecommendation A Model for Recommendation SystemsIn this section we introduce a model for Recommendation Systems ,based ona utility matrix of preferences. We introduce the concept of a long-tail, 319320 CHAPTER 9. Recommendation Systems which explains the advantage of on-line vendors over conventional,brick-and-mortar vendors. We then briefly survey the sorts of applications inwhichrecommendation Systems have proved The Utility MatrixIn a Recommendation -system application there are two classes of entities, whichwe shall refer to asusersanditems.

4 Users have preferences for certain items,and these preferences must be teased out of the data. The dataitself is repre-sented as autility matrix, giving for each user-item pair, a value that representswhat is known about the degree of preference of that user for that item. Valuescome from an ordered set, , integers 1 5 representing the number of starsthat the user gave as a rating for that item. We assume that the matrix issparse, meaning that most entries are unknown. An unknown rating impliesthat we have no explicit information about the user s preference for the :In Fig.

5 We see an example utility matrix, representing users ratings of movies on a 1 5 scale, with 5 the highest rating. Blanks representthe situation where the user has not rated the movie. The movie names areHP1, HP2, and HP3 forHarry PotterI, II, and III, TW forTwilight, and SW1,SW2, and SW3 forStar Warsepisodes 1, 2, and 3. The users are representedby capital HP2 HP3 TW SW1 SW2 SW3A451B554C245D33 Figure : A utility matrix representing ratings of movies on a 1 5 scaleNotice that most user-movie pairs have blanks, meaning the user has notrated the movie.

6 In practice, the matrix would be even sparser, with the typicaluser rating only a tiny fraction of all available movies. The goal of a Recommendation system is to predict the blanks in the utilitymatrix. For example, would userAlike SW2? There is little evidence fromthe tiny matrix in Fig. We might design our Recommendation systemtotake into account properties of movies, such as their producer, director, stars,or even the similarity of their names. If so, we might then note the similaritybetween SW1 and SW2, and then conclude that sinceAdid not like SW1, theywere unlikely to enjoy SW2 either.

7 Alternatively, with much more data, wemight observe that the people who rated both SW1 and SW2 tended to givethem similar ratings. Thus, we could conclude thatAwould also give SW2 alow rating, similar toA s rating of A MODEL FOR Recommendation SYSTEMS321We should also be aware of a slightly different goal that makes sense inmanyapplications. It is not necessary to predict every blank entry in a utility , it is only necessary to discover some entries in each row that are likelyto be high. In most applications, the Recommendation system does not offerusers a ranking of all items, but rather suggests a few that the user should valuehighly.

8 It may not even be necessary to find all items with the highestexpectedratings, but only to find a large subset of those with the highest The Long TailBefore discussing the principal applications of Recommendation Systems , let usponder thelong tailphenomenon that makes Recommendation Systems neces-sary. Physical delivery Systems are characterized by a scarcity of stores have limited shelf space, and can show the customeronly a small fraction of all the choices that exist. On the other hand, on-linestores can make anything that exists available to the customer.

9 Thus, a physicalbookstore may have several thousand books on its shelves, but Amazon offersmillions of books. A physical newspaper can print several dozen articles perday, while on-line news services offer thousands per in the physical world is fairly simple. First, it is notpossible to tailor the store to each individual customer. Thus, the choice ofwhat is made available is governed only by the aggregate numbers. Typically, abookstore will display only the books that are most popular, and a newspaperwill print only the articles it believes the most people will be interested the first case, sales figures govern the choices, in the second case, editorialjudgement distinction between the physical and on-line worlds has been calledthelong tailphenomenon, and it is suggested in Fig.

10 The vertical axisrepresentspopularity(the number of times an item is chosen). The items areordered on the horizontal axis according to their popularity. Physical institu-tions provide only the most popular items to the left of the vertical line, whilethe corresponding on-line institutions provide the entire range of items: the tailas well as the popular long-tail phenomenon forces on-line institutions to recommenditemsto individual users. It is not possible to present all available items to the user,the way physical institutions can. Neither can we expect users to have heardof each of the items they might Applications of Recommendation SystemsWe have mentioned several important applications of Recommendation Systems ,but here we shall consolidate the list in a single recommendations : Perhaps the most important use of recom-mendation Systems is at on-line retailers.