{"id":13846,"date":"2017-12-10T07:07:45","date_gmt":"2017-12-10T07:07:45","guid":{"rendered":"https:\/\/www.revoscience.com\/en\/?p=13846"},"modified":"2017-12-10T07:08:21","modified_gmt":"2017-12-10T07:08:21","slug":"try-researchers-devise-better-recommendation-algorithm","status":"publish","type":"post","link":"https:\/\/www.revoscience.com\/en\/try-researchers-devise-better-recommendation-algorithm\/","title":{"rendered":"Try this! Researchers devise better recommendation algorithm"},"content":{"rendered":"

Approach should work especially well when ratings data is \u201csparse.\u201d\u00a0<\/strong><\/em><\/span><\/p>\n

\"\"
To determine what products a given customer might like, recommendation systems at websites such as Amazon and Netflix look for other customers who have assigned similar ratings to a similar range of products, and extrapolate from there.
Image: Chelsea Turner\/MIT<\/figcaption><\/figure>\n

CAMBRIDGE, Mass. —\u00a0The recommendation systems at websites such as Amazon and Netflix use a technique called \u201ccollaborative filtering.\u201d To determine what products a given customer might like, they look for other customers who have assigned similar ratings to a similar range of products, and extrapolate from there.<\/span><\/p>\n

The success of this approach depends vitally on the notion of similarity. Most recommendation systems use a measure called cosine similarity, which seems to work well in practice. Last year, at the Conference on Neural Information Processing Systems, MIT researchers used a new theoretical framework to demonstrate why, indeed, cosine similarity yields such good results.<\/span><\/p>\n

This week, at the same conference,\u00a0they are reporting<\/a>\u00a0that they have used their framework to construct a new recommendation algorithm that should work better than those in use today, particularly when ratings data is \u201csparse\u201d \u2014 that is, when there is little overlap between the products reviewed and the ratings assigned by different customers.<\/span><\/p>\n

The algorithm\u2019s basic strategy is simple: When trying to predict a customer\u2019s rating of a product, use not only the ratings from people with similar tastes but also the ratings from people who are similar to those people, and so on.<\/span><\/p>\n

The idea is intuitive, but in practice, everything again hinges on the specific measure of similarity.<\/span><\/p>\n

\u201cIf we\u2019re really generous, everybody will effectively look like each other,\u201d says Devavrat Shah, a professor of electrical engineering and computer science and senior author on the paper. \u201cOn the other hand, if we\u2019re really stringent, we\u2019re back to effectively just looking at nearest neighbors. Or putting it another way, when you move from a friend\u2019s preferences to a friend of a friend\u2019s, what is the noise introduced in the process, and is there a right way to quantify that noise so that we balance the signal we gain with the noise we introduce? Because of our model, we knew exactly what is the right thing to do.\u201d<\/span><\/p>\n

All the angles<\/strong><\/span><\/p>\n

As it turns out, the right thing to do is to again use cosine similarity. Essentially, cosine similarity represents a customer\u2019s preferences as a line in a very high-dimensional space and quantifies similarity as the angle between two lines.<\/span><\/p>\n

Suppose, for instance, that you have two points in a Cartesian plane, the two-dimensional coordinate system familiar from high school algebra. If you connect the points to the origin \u2014 the point with coordinates (0, 0) \u2014 you define an angle, and its cosine can be calculated from the point coordinates themselves.<\/span><\/p>\n

If a movie-streaming service has, say, 5,000 titles in its database, then the ratings that any given user has assigned some subset of them defines a single point in a 5,000-dimensional space. Cosine similarity measures the angle between any two sets of ratings in that space.<\/span><\/p>\n

When data is sparse, however, there may be so little overlap between users\u2019 ratings that cosine similarity is essentially meaningless. In that context, aggregating the data of many users becomes necessary.<\/span><\/p>\n

The researchers\u2019 analysis is theoretical, but here\u2019s an example of how their algorithm might work in practice. For any given customer, it would select a small set \u2014 say, five \u2014 of those customers with the greatest cosine similarity and average their ratings. Then, for each of those customers, it would select five similar customers, average their ratings, and fold that average into the cumulative average. It would continue fanning out in this manner, building up an increasingly complete set of ratings, until it had enough data to make a reasonable estimate about the rating of the product of interest.<\/span><\/p>\n

Filling in blanks<\/strong><\/span><\/p>\n

For Shah and his colleagues \u2014 first author Christina Lee PhD \u201917, who is a postdoc at Microsoft Research, and two of her Microsoft colleagues, Christian Borgs and Jennifer Chayes \u2014 devising such an algorithm wasn\u2019t the hard part. The challenge was proving that it would work well, and that\u2019s what the paper concentrates on.<\/span><\/p>\n

Imagine a huge 2-D grid that maps all of a movie-streaming service\u2019s users against all its titles, with a number in each cell that corresponds to a movie that a given user has rated. Most users have rated only a handful of movies, so most of the grid is empty. The goal of a recommendation engine is to fill in the empty grid cells as accurately as possible.<\/span><\/p>\n

Ordinarily, Shah says, a machine-learning system learns two things: the features of the data set that are useful for prediction, and the mathematical function that computes a prediction from those features. For purposes of predicting movie tastes, useful features might include a movie\u2019s genre, its box office performance, the number of Oscar nominations it received, the historical box-office success of its leads, its distributor, or any number of other things.<\/span><\/p>\n

Each of a movie-streaming service\u2019s customers has his or her own value function: One might be inclined to rate a movie much more highly if it fits in the action genre and has a big budget; another might give a high rating to a movie that received numerous Oscar nominations and has a small, arty distributor.<\/span><\/p>\n

Playing the odds<\/strong><\/span><\/p>\n

In the new analytic scheme, \u201cYou don\u2019t learn features; you don\u2019t learn functions,\u201d Shah says. But the researchers do assume that each user\u2019s value function stays the same: The relative weight that a user assigns to, say, genre and distributor doesn\u2019t change. The researchers also assume that each user\u2019s function is operating on the same set of movie features.<\/span><\/p>\n

This, it turns out, provides enough consistency that it\u2019s possible to draw statistical inferences about the likelihood that one user\u2019s ratings will predict another\u2019s.<\/span><\/p>\n

\u201cWhen we sample a movie, we don\u2019t actually know what its feature is, so if we wanted to exactly predict the function, we wouldn\u2019t be able to,\u201d Lee says. \u201cBut if we just wanted to estimate the difference between users\u2019 functions, we can compute that difference.\u201d<\/span><\/p>\n

Using their analytic framework, the researchers showed that, in cases of sparse data \u2014 which describes the situation of most online retailers \u2014 their \u201cneighbor\u2019s-neighbor\u201d algorithm should yield more accurate predictions than any known algorithm.<\/span><\/p>\n

Translating between this type of theoretical algorithmic analysis and working computer systems, however, often requires some innovative engineering, so the researchers\u2019 next step is to try to apply their algorithm to real data.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

Approach should work especially well when ratings data is \u201csparse.\u201d\u00a0 CAMBRIDGE, Mass. —\u00a0The recommendation systems at websites such as Amazon and Netflix use a technique called \u201ccollaborative filtering.\u201d To determine what products a given customer might like, they look for other customers who have assigned similar ratings to a similar range of products, and extrapolate […]<\/p>\n","protected":false},"author":6,"featured_media":13847,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[22,17],"tags":[],"class_list":["post-13846","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-other","category-research"],"featured_image_urls":{"full":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0.jpg",639,426,false],"thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0-150x150.jpg",150,150,true],"medium":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0-300x200.jpg",300,200,true],"medium_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0.jpg",639,426,false],"large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0.jpg",639,426,false],"1536x1536":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0.jpg",639,426,false],"2048x2048":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0.jpg",639,426,false],"ultp_layout_landscape_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0.jpg",639,426,false],"ultp_layout_landscape":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0.jpg",639,426,false],"ultp_layout_portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0.jpg",600,400,false],"ultp_layout_square":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0.jpg",600,400,false],"newspaper-x-single-post":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0.jpg",639,426,false],"newspaper-x-recent-post-big":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0.jpg",540,360,false],"newspaper-x-recent-post-list-image":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0.jpg",95,63,false],"web-stories-poster-portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0.jpg",639,426,false],"web-stories-publisher-logo":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0.jpg",96,64,false],"web-stories-thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2017\/12\/MIT-Better-Recommendations_0.jpg",150,100,false]},"author_info":{"info":["Amrita Tuladhar"]},"category_info":"Other<\/a> Research<\/a>","tag_info":"Research","comment_count":"0","_links":{"self":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/13846","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/comments?post=13846"}],"version-history":[{"count":0,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/13846\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media\/13847"}],"wp:attachment":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media?parent=13846"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/categories?post=13846"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/tags?post=13846"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}