Monday, July 27, 2009

If you hated this, you'll love that

Most internet shoppers are familiar with recommendations of the form "users who liked X also liked Y". Most Netflix Prize competitors are familiar with the k-nearest-neighbors algorithm as the classic and most typical implementation of such a system. One computes the correlations between all pairs of movies and then predicts a user's reaction to a movie based on the user's available ratings of movies most correlated with that movie.

It was interesting but ultimately not that surprising to me to find that there were also some strong negative correlations between many pairs of movies. Yehuda Koren's recently developed neighborhood algorithm infers predictive relationships between all possible pairs of movies and therefore takes into account negatively correlated pairs as well as positively correlated pairs, but there's very little emphasis on the negative correlations in the presentation of the method. I doubt I'm the only person to have observed the strength of the negative correlations, but I haven't seen them discussed much, so I thought I'd mention a few of my findings (I'll refer to the correlation level as "rho").

For instance, Titanic is positively correlated with Ghost (rho=0.245) and Pearl Harbor (rho=0.238) but negatively correlated with Fight Club (rho= -0.190) and Lost in Translation (rho=-0.189) . Harry Potter and the Sorcerer's Stone is positively correlated with Star Wars, The Phantom Menace (rho=0.152) but negatively correlated with Taxi Driver (-0.142) and Pulp Fiction (-0.138). Saving Private Ryan is positively correlated with Braveheart (rho=0.169) and Platoon (rho=0.168) but negatively correlated with Sex and the City, Season II (rho =-0.135), The Rocky Horror Picture Show (rho =-0.135) and Dirty Dancing (rho=-0.1347).

I implemented the "negative" version of a nearest neighbor algorithm -a "furthest opposities" algorithm, if you will, which relied only on negative correlations. It achieved an RMSE of 0.9562. That score is fairly competitive with the 0.9513 which Netflix's algorithm, Cinematch, had achieved prior to the start of the competition. I suspect I could have improved it further if I had done more than minimal tuning. I would have loved to see Netflix run a recommendation system which generated predictions with reasoning like "since you hated Armageddon and Lethal Weapon 3, you'll probably love Being John Malkovich".