Movie data. Most of the top teams competing in the netflix challenge must have had to answer a lot of questions about movie data. Here is an actual conversation I had with a friend a couple of weeks ago (Note that I had had a few beers at the time, so don't go to court with any of these quotes).
"[Lay Person - Not the actual name of the person]: Hey, so I heard you're competing in that netflix challenge thing. Pretty cool.
[Pragmatic Theory]: Yeah.
[LP]: So what kind of data do you get?
[PT]: Movie titles and years, user identification number, rating and date of rating.
[LP]: That's it? No information on movie genre or anything?
[PT]: Nope.
[LP]: That's strange... isn't it really important to predict user ratings?
[PT]: (*having a sip, knowing where this is going*)
[LP]: Hey! I have an idea! Did you guys think of mining this information on IMDB or something?
[PT]: Well, actually, external movie data is not useful. The algorithms find the proper classifications automatically.
[LP]: (*pause*) Huh?
[PT]: For example, the movie genre on a site like Netflix, Amazon or IMDB is the opinion of one person on how movies should be categorized. The algorithms actually find categories that indicate how movies influence all users.
[LP]: (*dumb look* - LP has also had a few drinks) But wouldn't your algorithms just be better with more data?
[PT]: Believe me, movie data is really not useful.
[LP]: (*looking unconvinced*) OK... you're sure?... huh.... Really?
[PT]: (*having a bigger sip*)
[LP]: OK then... What about user information? Do you have any of that? I'm sure if you knew user's sex, age group and such, that would help to make predictions... and I'm sure netflix asks that when you register... men and women don't have the same tastes in movies, that's for sure (*unconfortable laugh*)
[PT]: Nope, no user information either. And that wouldn't be useful anyway. The algorithms actually find these type of user classifications automatically too...
[LP]: (*dumb struck*) Wha?
[PT]: Movie or user data is just not helpful because the different algorithms are just too good at capturing the details and nuances that influence user ratings... Believe me, we tried!
[LP]: (*stares in disbelief and walks away thinking that I don't understand this problem and that he would do better...*)
[PT]: (*chugging the rest of my beer*)"
A couple of months ago, that could have been me arguing with someone about the usefulness of external movie data. Team PragmaticTheory was actually founded with the belief that we could do better than other teams because we did not have this pre-conceived notion that movie data was useless. We would implement all the machine learning algorithms, then add some data from various sources... and we would surely beat out the top teams and win the million... Boy, were we wrong!
One of the first things I did on this project was to mine a couple of sites (talk to my lawyers to find out how and which ones) to see if we could get good coverage on the movies in the dataset. I actually did pretty well and we got a good set of movie data to play with. This data was actually useful in the first few weeks. The models using it did better than some of our early pure machine learning algorithms. Unfortunately, as soon as we started implementing some of the more common, documented algorithms, the movie-data-based models got pruned out of the mix. We tried to get a bit fancier and build some more complex algorithms around the movie data. Still, the pure machine learning ones are systematically better.
Why? Well, my interpretation is that movie data is just too black and white. User tastes are infinite shades of grey (think floating point shades of grey). It's not true that someone likes all sci-fi movies. And no one can enjoy all the Tom Hanks movies equally. But the algorithms can figure out the subtle nuances that define user rating patterns. It can figure out that you really like sci-fi comedies that have a happy ending, but that you enjoy the sci-fi/horror genre, where one of the main characters dies, a bit less. It can also figure out that you're a huge fan of Tom Hanks, but that you hate sappy girly flicks... so even if your favorite man is there, there's no saving Sleepless In Seattle and You've Got Mail from being sent to the junk pile.
My explanation is a bit simplistic, but honestly, to anyone out there that still has any doubts that extra movie data may be useful to predict user ratings, I say that you have to have faith in the machine. It's just smarter than we are.
Sunday, August 3, 2008
Saturday, July 26, 2008
Blending 101
(a.k.a. why one submission a day is enough)
Serious attempts at the Netflix challenge require blending results from many algorithms. Blending is an operation that transforms multiple estimates into a single higher accuracy estimate. This is a brief tutorial of the steps involved. Experienced Netflix participants should not bother to read further.
Step 1: construct a reduced training set
To blend the models, you need to construct a reduced training set by excluding from Netflix provided training set all ratings present in the probe set.
Step 2: train you different models on the reduced training set
For now we train each individual model on the reduced training set. Later we will re-train all the models on the full training set. To re-train in a consistent way, it is critical to record carefully at this step all the parameters used, the number of training epoch, etc.
Step 3: predict the probe set
For each model trained on the reduced training set, predict the probe set.
Step 4: select you favorite blending recipe
This step receives as input the predicted probe set results from each model, and the real probe set ratings. The output is a function that mixes the individual model predictions into a blended prediction, hopefully better than any individual result. A simple linear regression will get you a long way, but feel free to experiment with your favorite machine learning algorithm. What is key here, is that any unknown coefficient (for example the linear regression coefficients) can be selected to minimize the error between the blended prediction and the real probe set scores.
N.B. If over fitting the blending function is an issue, partition the probe set in two. Use one part for training the function, and the other for cross-validation.
Step 5: re-train all models using the full training set
At this point, we are preparing for our final predictions. To get the best possible accuracy, we re-train all models using the full training set. The addition of the probe set data in the training data can result in an accuracy boost of 0.0060 or more.
Step 6: blend the re-trained models
Here's the leap of fate. We assume that the blending function we computed at step 4 is still a valid function to blend the re-trained models. For this to work, the two sets of models must be computed with a rigorously equivalent methodology. Also, the selected function from step 4 must be a valid generalization and avoid over fitting. This is not an issue with a simple linear regression, but may become problematic for complex machine learning methods with many degrees of freedom.
Step 7: clamp the final predictions
Here's a hint: clamping values between 1 and 5 is not optimal.
If this well done, then improvements in the models can be measured after step 4 by comparing the accuracy on the probe set. Values on the qualifying set will be better by 0.0060 or more, but this offset should be very consistent from one submission to another. Lately I have been getting 0.0068 +/- 0.0001.
Serious attempts at the Netflix challenge require blending results from many algorithms. Blending is an operation that transforms multiple estimates into a single higher accuracy estimate. This is a brief tutorial of the steps involved. Experienced Netflix participants should not bother to read further.
Step 1: construct a reduced training set
To blend the models, you need to construct a reduced training set by excluding from Netflix provided training set all ratings present in the probe set.
Step 2: train you different models on the reduced training set
For now we train each individual model on the reduced training set. Later we will re-train all the models on the full training set. To re-train in a consistent way, it is critical to record carefully at this step all the parameters used, the number of training epoch, etc.
Step 3: predict the probe set
For each model trained on the reduced training set, predict the probe set.
Step 4: select you favorite blending recipe
This step receives as input the predicted probe set results from each model, and the real probe set ratings. The output is a function that mixes the individual model predictions into a blended prediction, hopefully better than any individual result. A simple linear regression will get you a long way, but feel free to experiment with your favorite machine learning algorithm. What is key here, is that any unknown coefficient (for example the linear regression coefficients) can be selected to minimize the error between the blended prediction and the real probe set scores.
N.B. If over fitting the blending function is an issue, partition the probe set in two. Use one part for training the function, and the other for cross-validation.
Step 5: re-train all models using the full training set
At this point, we are preparing for our final predictions. To get the best possible accuracy, we re-train all models using the full training set. The addition of the probe set data in the training data can result in an accuracy boost of 0.0060 or more.
Step 6: blend the re-trained models
Here's the leap of fate. We assume that the blending function we computed at step 4 is still a valid function to blend the re-trained models. For this to work, the two sets of models must be computed with a rigorously equivalent methodology. Also, the selected function from step 4 must be a valid generalization and avoid over fitting. This is not an issue with a simple linear regression, but may become problematic for complex machine learning methods with many degrees of freedom.
Step 7: clamp the final predictions
Here's a hint: clamping values between 1 and 5 is not optimal.
If this well done, then improvements in the models can be measured after step 4 by comparing the accuracy on the probe set. Values on the qualifying set will be better by 0.0060 or more, but this offset should be very consistent from one submission to another. Lately I have been getting 0.0068 +/- 0.0001.
Tuesday, July 22, 2008
A little humor to start things off...
Here is the text from the web page we initially wanted to put up:
PragmaticTheory : Solving the netflix challenge through divination...
Following the concepts of numerology, team PragmaticTheory was formed on July 7th, 2007 (7/7/7) and started working on the netflix challenge 7 months, 7 weeks and 7 days later. The team consists of 2 human beings with respectively 2 eyes, 2 arms, 2 legs and, most importantly, 2 powerfully energized shakras.
Our strategy is not to use un-proven techniques such as mathematics, matrixes and algorithms. Instead, we are tapping into the universe's hidden powers to uncover user's force fields in order to forecast their ratings with high accuracy. Skeptics will most likely dismiss our techniques as mere superstition, but we think that the progress that we've made so far on the netflix leaderboard speaks for itself.
Here are some more details on the divination methods that our team uses:
- Saggitarius Virgo Decomposition (SVD) : The astralogical signs of the users in the dataset are captured through astral vibration sensors and cross-referenced with star maps and tide charts to predict future movie ratings.
- Asymmetrical Tea-Leaf Models : An array of tea kettles and cups were used to generate 50 million tea-leaf patterns which were individually digitally photographed. A pattern recognition software was implemented to detect assymetries and assign weights accordingly.
- Red-King Black-Queen Machine (RBM) : Tarot spreads were simulated for each user in the dataset and their fate interpreted through an automated karma analyser. Sadly, thousands of users were declared dead at the time of their predicted rating, yielding major sparsness issues...
PragmaticTheory : Solving the netflix challenge through divination...
Following the concepts of numerology, team PragmaticTheory was formed on July 7th, 2007 (7/7/7) and started working on the netflix challenge 7 months, 7 weeks and 7 days later. The team consists of 2 human beings with respectively 2 eyes, 2 arms, 2 legs and, most importantly, 2 powerfully energized shakras.
Our strategy is not to use un-proven techniques such as mathematics, matrixes and algorithms. Instead, we are tapping into the universe's hidden powers to uncover user's force fields in order to forecast their ratings with high accuracy. Skeptics will most likely dismiss our techniques as mere superstition, but we think that the progress that we've made so far on the netflix leaderboard speaks for itself.
Here are some more details on the divination methods that our team uses:
- Saggitarius Virgo Decomposition (SVD) : The astralogical signs of the users in the dataset are captured through astral vibration sensors and cross-referenced with star maps and tide charts to predict future movie ratings.
- Asymmetrical Tea-Leaf Models : An array of tea kettles and cups were used to generate 50 million tea-leaf patterns which were individually digitally photographed. A pattern recognition software was implemented to detect assymetries and assign weights accordingly.
- Red-King Black-Queen Machine (RBM) : Tarot spreads were simulated for each user in the dataset and their fate interpreted through an automated karma analyser. Sadly, thousands of users were declared dead at the time of their predicted rating, yielding major sparsness issues...
Subscribe to:
Posts (Atom)
