Netflix Prize

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

[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 is 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 RMS by 10% really benefit the users? It has been claimed that even as small an improvement as .01 RMSE result in a significant difference in the ranking of the "top-10" most recommended movies for a user.[6].

[edit] Prizes

Prizes are based on certain levels of improvement over several baseline algorithms. 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 5 years (till 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.

[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]

In order to win the 2008 Progress Prize, a participant should obtain an RMSE of 0.8625 or better on the quiz set.

[edit] References

  1. ^ People who are connected with Netflix (current and former employees, agents, close relatives of Netflix employees, etc.), residents of Quebec, and residents of Cuba, Iran, Syria, North Korea, Myanmar, or Sudan may not participate in the contest.
  2. ^ a b c d "The Netflix Prize Rules". Retrieved on 2007-08-21.
  3. ^ a b James Bennett; Stan Lanning (August 12, 2007). "The Netflix Prize". Proceedings of KDD Cup and Workshop 2007. Retrieved on 2007-08-25. 
  4. ^ Sigmoid Curve (2006-10-08). "Miss Congeniality". Netflix Prize Forum. Retrieved on 2007-08-25.
  5. ^ prodigious (2006-10-06). "A single customer that rated 17,000 movies". Netflix Prize Forum. Retrieved on 2007-08-25.
  6. ^ YehudaKoren (2007-12-18). How useful is a lower RMSE?. Netflix Prize Forum.
  7. ^ "Netflix Prize Frequently Asked Questions". Retrieved on 2007-08-21.
  8. ^ "Netflix Prize Rankings". Hacking NetFlix (October 9, 2006). Retrieved on 2007-08-21.
  9. ^ "Netflix Prize (I tried to resist, but...)". Juho Snellman's Weblog (October 15, 2006). Retrieved on 2007-08-21.
  10. ^ Top contenders for Progress Prize 2007 chart.
  11. ^ The KDD Cup and Workshop 2007.
  12. ^ Prizemaster (2007-11-13). Netflix Progress Prize 2007 awarded to team KorBell. Netflix Prize Forum.
  13. ^ $50,000 Progress Prize is Awarded on First Anniversary of $1 Million Netflix Prize.
  14. ^ R. Bell, Y. Koren, C. Volinsky (2007). "The BellKor solution to the Netflix Prize".

[edit] External links

Languages