Close but no Cigar for Netflix Recommender System

Ponca City, We Love You writes "In October 2006, Netflix, the online movie rental service, announced that it would award $1 million to the first team to improve the accuracy of Netflix's movie recommendations by 10% based on personal preferences. Each contestant was given a set of data from which three million predictions were made about how certain users rated certain movies and Netflix compared that list with the actual ratings and generated a score for each team. More than 27,000 contestants from 161 countries submitted their entries and some got close, but not close enough. Today Netflix announced that it is awarding an annual progress prize of $50,000 to a group of researchers at AT&T Labs, who improved the current recommendation system by 8.43 percent but the $1 million grand prize is still up for grabs and a $50,000 progress prize will be awarded every year until the 10 percent goal is met. As part of the rules of the competition, the team was required to disclose their solution publicly. (pdf)"

I'd say...

If the people who created Netflix's system are still with the company, I'd say they deserve some retroactive recognition (and bonuses). That's pretty damn good optimization if it's that hard to improve upon, and there seem to have been some really sophisticated people trying to beat them.

Re:I'd say...

Perhaps they should look at whatever chooses the slashdot page-bottom quotes for inspiration: Mosher's Law of Software Engineering: Don't worry if it doesn't work right. If everything did, you'd be out of a job.

Re:

It's hard to say. On the one hand, it could be that the current system is good enough that improvements are minutely incremental, though 8+% is pretty good if you ask me. On the other, it may be that the system is so fraught with dependencies and/or the relationships are so variable that it's hard to make gigantic leaps in sophistication. Look at Amazon's recommendation system: pretty good overall but still makes some egregious errors. Add the tagging system to the mix and it's possible to lead the recommen

Re:I'd say...

Customers who bought the items in your shopping cart also bought:

Empress Charmeuse Silk Sheet Set - Queen - Ivory ~ $399.00
Black Leather Victorian Vintage Shaper Corset Boned Lace Up corset ~ $119.99
Orgazyme Clitoral Stimulation Gel, Topical, 0.8 oz ~ $20.79
Pampers Cruisers, Size 4, Economy Plus Pack, 140 Cruisers ~ $38.99

I don't think Amazon has much room to improve their recommendation technology.

Re:I'd say...

ook at Amazon's recommendation system: pretty good overall but still makes some egregious errors.

Egregious errors? It's downright useless unless you pretty much buy only one genre of book/music/whatever. Their system is heavily weighted towards whatever you most recently bought - and drops huge slabs of quasi related stuff into your request list at the slightest provocation.
 
I buy (among other things) serious works of culinary history, sociology, etc... Yet my reccomendation list is clogged with food porn (coffee table cookbooks) and the latest crap offerings from whichever TV chef is the current flavor of the moment. It also doesn't recognize the difference between editions - if you buy a hardback, it'll happily reccomend you buy the paperback. If you buy a frequently reprinted SF novel, it'll happily add each new printing/edition to your queue.

Re:

Most everyone who tried was able to beat Netflix's existing system. I put together a little framework to help people get up and running faster. A lot of people seemed to be spending time just getting all the data into memory before they got to play with any algorithm ideas. I include a few algorithms including Simon Funk's which should be enough to get you started. http://www.icefox.net/programs/?program=NetflixRecommenderFramework [icefox.net]

Re:I'd say...

I think the problem is that (and I may be wrong) any new system that researchers come up with isn't allowed to ask the user for more information. This would make if very hard for any system to be acurate if it is based soley on what dvds you rented and how you rated them.
If I liked Die Hard 4, for example, did I like it because of Bruce Willis, the "I'm a Mac" guy, the special effects, the plot, or some other reason that even I don't know?
Personally, I know that I have rated something like 900 movies on the netflix site and nearly all the recommendations are things I've no interest in or they simply say, "Sorry we have no recommendations for you at this time."
I would like to think that if they could ask me why I rated one movie a 4 and another a 1 then they might have more accurate recommendations. Even if they just had a drop down menu with something like, "I liked this movie because of a) the starts, b) the plot, c) the genre and so on" it would make recommendations a lot easier.

Re:

Thats why they need to get multiple data points to make a recommendation. If you rented a lot of the "I'm a Mac Guy" movies and rated them highly, then there is a bigger chance that that is the reason you liked that movie. If you refused to rent, or rated poorly the movie "Rugrats Gone Wild" then you probably aren't a rabid Bruce Willis fan etc. The entire goal of the project is to find films you like without you having to do a mini-review of every movie you have rented/saw.

Re:I'd say...

Thats why they need to get multiple data points to make a recommendation. If you rented a lot of the "I'm a Mac Guy" movies and rated them highly, then there is a bigger chance that that is the reason you liked that movie. If you refused to rent, or rated poorly the movie "Rugrats Gone Wild" then you probably aren't a rabid Bruce Willis fan etc. The entire goal of the project is to find films you like without you having to do a mini-review of every movie you have rented/saw.

One of the common approaches to recommender systems is SVD, or Singular Value Decomposition [wikipedia.org]. SVD tries to isolate "features" in the training set that best represent a particular trait of the data and its value, such as the examples above. You may not have any idea what the feature actually represents, but that is fairly common in machine learning. It is an iterative process. Once you have defined one feature as well as you can, you move on to a new one. There are diminishing returns with this approach though, and identifying too many features can overspecialize your system and yield worse results. If your results are not good enough, you can try a different approach. Once you have tried several approaches that are almost good enough, you can try combining the different results to varying degrees to get a hopefully better result. That is what the leaders have done so far.

Re:

From the Netflix Prize FAQ, they say how they currently do it:

"Straightforward statistical linear models with a lot of data conditioning."

The Netflix programmers shouldn't necessarily get special recognition for using least-squares modeling, but feel free to pass on your praise to Gauss, Legendre, Galton, and Fisher.

What's amazing is how hard it is to improve drastically on these 150-year-old statistical techniques.

Moving target?

Will Netflix incorporate the near-winners' ideas into their current system? If so, won't future teams be aiming at a moving (improving) target? If not, won't current Netflix customers know that their recommendations could be better if Netflix just incorporated a now publicly-disclosed algorithm into their servers?

Re:

I had the same thought. And to what extent is the accuracy of a suggestion system important? Sometimes, throwing in a completely different suggestion might garner you a rental and possibly more rentals because you might like other movies of that type.

Re:Moving target?

It's not a moving target. It's a very fixed number (RMSE = 0.8563) that the winning algorithm has to come up with. The netflix algorithm never gets re-run on the data for the prize.

Netflix is free to merge any improvements into their actual system in the meantime.

Bad title

The prize was clearly a million dollars, not a cigar! I guess the editors don't even read the summary.

Re:

I don't think I'm mistaken in saying that $50,000 buys quite a few cigars too.

Re:Bad title

Money can be exchanged for goods and services.

no breaktrough - just blending

Most noteworthy aspect of the winning entry is that their winning method works by combining 107 different types of prediction strategies.

They state that you can get pretty far by blending the 3-4 best strategies, but of course doing so would not have netted them the progress prize

It is kind of sad realization that there actually is no better method. Your best bet is to use brute force and attempt to find some weighting methodology that combines known methods. By the way this is a well known issue in protein structure prediction competitions, for many years now so called meta-servers (predictions work by merely combining other predictions) win all the time. The joke is that we now need meta-meta-servers, combine the results of combiners

Also a clarification on the progress prize: to get it you need to have at least 1% improvement over the previous result. Considering that there is only 1.57% to go there is room for only one more progress prize until it hits the Grand Prize (10% improvement over the original results).

hmmm ....

if ($director eq "Michael Bay") {
        print "Not recommended";
}

That should improve the system by at least 20%

Here's an idea...

Why not give users more control over their recommendations? Heck, even a bunch of checkboxes would be useful.

For example, Netflix frequently recommends rated R movies to my family, but we have never rented a single R-rated movie and have no desire to do so. Moreover, every time we get a recommendation for an R-rated movie, we rate it "Not Interested." I've probably marked dozens of R-rated movies "Not Interested," but they continue to be recommended. (Either Netflix is trying to tell me to just give in and rent one already, or they really don't understand my family's movie preferences.)

A simple checkbox for "Do not recommend R-rated movies" would be all Netflix needs to substantially improve its accuracy for my family. I imagine Netflix could add checkboxes for similar criteria as well. In any case, I think a key point is giving more control over recommendations to the users themselves.

diminishing returns

From my experience with the Netflix Prize, and ML/stat.learning techniques in general, that last 1.57% is going to be the hardest. There is a diminishing returns effect going on here, i.e. the effort required for each successive 1% increase gets progressively larger.

Re:1.57%

Right - but the AT&T method is public - so if you can get that the rest of the way to 10%..... I guess step 3 is profit.

Not how it works

That's not how the contest works. It's based on the RMSE that the original netflix algorithm got at the beginning of the contest. This is fixed and does not change. See the contest site for more details.

Re:like trying to win the lottery

Two reasons I can think of. One is the challenge. I like to code but I'm not great with coming up with projects to do myself. This kind of thing would be nice for that.

The other is the experience. If you get second in this, no, you won't win the prize. But you can bet that having that on your resume would make getting many jobs much easier. Amazon would like your skills. So would many other retailers.

Also, as a side note, it's not a lottery. There is a three prong legal test in the US to determine if something is a lottery. I think the three parts are you have to pay to get it, everyone has an equal chance of winning, and there is no skill involved. I'm not positive about the second part. This is free to enter and is based quite a bit on skill, so it's not like a lottery.

Don't exaggerate.

This isn't a way to get free work. It's a way to get very smart job candidates to find you. It's a recruiting tool. You don't honestly think that they will take the winning idea, pay the $1m, and then just say "bye" do you? They will offer that person a job if at all reasonable (if it's a team of 500 students, obviously they couldn't).

Re:like trying to win the lottery

"Any contestants reading this? Maybe you could enlighten the rest of us on why you bothered competing?"

There are two immediate reasons I can think of why anyone would bother competing:

1) To win money.
2) Because they enjoy the challenge of trying to solve an interesting problem.

I'm just a simple coder, and knew that I didn't have any realistic chance of winning money. But I still found it very satisfying to try to come up with a solution and send it in and see how I did. I don't regret spending hours of my own leisure time on the project.

That said, eventually I gave it up. It was very clear that I'm not smart enough to meet the challenge. I had my fun, and it was time to move on to the next project. In summary, I don't think it's safe to assume that everyone is in it for the money.

"Pardon my cynicism, but seems like contests like this are a way to get a lot of ideas and work for very little money."

I call it "brilliant". Netflix probably put some pricetag on what it would pay to get >10% improvement on their system. That pricetag is probably more than $1 million. That means profit!

Sometimes throwing stuff away is good

I think you have to consider that netflix is working off a very large user base with a very large list of titles. In this sense, computation time is going to go way up the more you keep adding all these factors. I'm sure they've had projects internal to netflix to use more data, but found that it just didn't pay off with the increased computation time. It's much better to get good recommendations onto the page instantly than make the user wait 2 seconds for great recommendations. The same is possibly tr