ai algorithm business cinema.netflix coding collaboration csci4830 development filtering innovation mod3 netflix netflix_prize prize recommendation recommendationengine technology tutorial

My tags:

From Wikipedia, the free encyclopedia

The Netflix Prize is an ongoing open competition for the best collaborative filtering algorithm that predicts user ratings for films, based on previous ratings. The competition is held by Netflix, an online DVD-rental service, and is opened for anyone (with some exceptions)^[1]. The grand prize of $1,000,000 is reserved for the entry which bests Netflix's own algorithm for predicting ratings by 10%.^[2]

Contents 1 Problem and data sets 2 Prizes 3 End of the contest 4 Progress and current status 4.1 2007 Progress Prize 4.2 2008 Progress Prize 5 References 6 External links

[edit] Problem and data sets

Netflix provided a training data set of over 100 million ratings that over 480,000 users gave to nearly 18,000 movies. Each training rating is a quadruplet <user, movie, date of grade, grade>. The user and movie fields are integer IDs, while grades are from 1 to 5 (integral) stars.^[3]

The qualifying data set contains over 2.8 million triplets <user, movie, date of grade>, with grades known only to the jury. A participating team's algorithm must predict grades on the entire qualifying set, but they are only informed of the score for half of the data, the quiz set. The other half is the test set, and performance on this is used by the jury to determine potential prize winners. Only the judges know which ratings are in the quiz set, and which are in the test set—this arrangement is intended to make it difficult to hill climb on the test set. Submitted predictions are scored against the true grades in terms of root mean squared error (RMSE), and the goal is to reduce this error as much as possible. Note that while the actual grades are integers in the range 1 to 5, submitted predictions need not be.

For each movie, title and year of release are provided in a separate dataset. No information at all is provided about users.^[2]

In order to protect the privacy of customers, "some of the rating data for some customers in the training and qualifying sets have been deliberately perturbed in one or more of the following ways: deleting ratings; inserting alternative ratings and dates; and modifying rating dates".^[2]

The training set is such that the average user rated over 200 movies, and the average movie was rated by over 5000 users. But there is wide variance in the data—some movies in the training set have as little as 3 ratings,^[4] while one user rated over 17,000 movies.^[5]

There was some controversy as to the chosen metric (root mean squared error). Would a reduction of the RMSE by 10% really benefit the users? It has been claimed that even as small an improvement as 1% RMSE result is a significant difference in the ranking of the "top-10" most recommended movies for a user.^[6].

[edit] Prizes

Prizes are based on improvement over the Cinematch algorithm or the previous year's score if a team has made improvement beyond a certain threshold. A trivial algorithm that predicts for each movie in the quiz set its average grade from the training data produces an RMSE of 1.0540. Netflix's own algorithm, called Cinematch, uses "straightforward statistical linear models with a lot of data conditioning".^[7] Using only the training data, Cinematch scores an RMSE of 0.9514 on the quiz data, roughly a 10% improvement over the trivial algorithm. Cinematch has a similar performance on the test set, 0.9525. In order to win the grand prize of $1,000,000, a participating team must improve this by another 10%, to achieve 0.8572 on the test set.^[2] (Such an improvement on the quiz set corresponds to an RMSE of 0.8563.)

If no team wins the grand prize, a progress prize of $50,000 is awarded every year for the best result thus far. However, in order to win this prize, an algorithm must improve the RMSE on the quiz set by at least 1% over the previous progress prize winner (or over Cinematch, the first year). If no submission succeeds, the progress prize is not awarded for that year.

To win a progress or grand prize a participant must provide source code and a description of the algorithm to the jury within one week after being contacted by them. Following verification the winner must also provide a non-exclusive license to Netflix. Netflix will publish only the description, not the source code, of the system. A team may choose to not claim a prize, in order to keep their algorithm and source code secret. The jury also keeps their predictions secret from other participants. A team may send as many attempts to predict grades as they wish. Originally submissions were limited to once a week, but the interval was quickly modified to once a day. A team's best submission so far counts as their current submission.

When one of the teams succeeds to improve the RMSE by 10% or more, the jury issues a last call, giving all teams 30 days to send their submissions. Only then, the team with best submission is asked for the algorithm description, source code, and non-exclusive license, and, after successful verification; declared a grand prize winner.

[edit] End of the contest

The contest lasts till the grand prize winner is declared. If no one receives the grand prize, it lasts for at least five years (until October 2, 2011). After that date, the contest may be terminated any time to Netflix sole discretion.

[edit] Progress and current status

The competition began on October 2, 2006. By October 8, a team called WXYZConsulting had already beaten Cinematch's results.^[8] By October 15, there were three teams who had beaten Cinematch, one of them by 1.06%, enough to qualify for the annual progress prize.^[9] By June, 2007, over 20,000 teams had registered for the competition from over 150 countries. 2,000 teams had submitted over 13,000 prediction sets.^[3]

Over the first year of the competition, a handful of front-runners traded first place; the more prominent ones were:

• WXYZConsulting, a team by Yi Zhang and Wei Xu. (A front runner during Nov-Dec 2006.)
• ML@UToronto A, a team from the University of Toronto led by Prof. Geoffrey Hinton. (A front runner during parts of Oct-Dec 2006.)
• Gravity, a team of four scientists from the Budapest University of Technology (A front runner during Jan-May 2007.)
• BellKor, a group of scientists from AT&T Labs. (A front runner since May 2007.)

See also a chart ^[10] showing the progress through the first year of the competition.

On August 12, 2007, many contestants gathered at the KDD Cup and Workshop 2007.^[11] which was held at San Jose, CA. During the workshop all four of the top teams on the leaderboard at that time presented their techniques.

On September 2, 2007, the competition entered the "last call" period for the 2007 Progress Prize. Teams had thirty days to tender submissions for consideration. At the beginning of this period the leading team was BellKor, with an RMSE of 0.8728 (8.26% improvement). followed by Dinosaur Planet (RMSE=0.8769; 7.83% improvement), and Gravity (RMSE=0.8785; 7.66% improvement). In the last hour of the last call period, an entry by "KorBell" took first place. This turned out to be an alternate name for Team BellKor.

Over the second year of the competition, only three teams reached the leading position:

• BellKor, a group of scientists from AT&T Labs. (front runner during May 2007 - Sept 2008.)
• BigChaos, a team of Austrian scientists from commendo research & consulting (single team front runner since Oct 2008)
• BellKor in BigChaos, a joint team of the two leading single teams (A front runner since Sept. 2008)

[edit] 2007 Progress Prize

On November 13, 2007, team KorBell (aka BellKor) was declared the winner of the $50,000 Progress Prize^[12] with an RMSE of 0.8712 (8.43% improvement). The team consisted of three researchers from AT&T Labs, Yehuda Koren, Robert Bell, and Chris Volinsky.^[13] As required, they published a description of their algorithm.^[14]

[edit] 2008 Progress Prize

The 2008 Progress Prize was awarded to the team BellKor in BigChaos. The winning submission achieved a 9.44% improvement over Cinematch (an RSME of 0.8616).^[15]

There will be no future Progress Prizes because obtaining the required 1% improvement over the 2008 Progress Prize would be sufficient to qualify for the Grand Prize.

[edit] References

[edit] External links

• Prize home page
• Kate Greene (2006-10-06). "The $1 million Netflix challenge". Technology Review. http://www.technologyreview.com/read_article.aspx?id=17587&ch=biztech.