Abstract
This paper details the winning strategy of team "False Positives" for the KDD Cup 2011 Track 2 challenge. The solution centers on a massive ensemble of diverse models, including matrix factorization and taxonomy-based classifiers. A key innovation was "Leaderboard Ensembling," a technique that used public leaderboard feedback to reverse-engineer optimal model weights. The final ensemble achieved a misclassification rate of 3.8863%, significantly outperforming individual models.
The Recommendation Challenge
The KDD Cup 2011 Track 2 presented a unique binary classification problem. Unlike standard recommendation tasks that predict star ratings, participants had to determine if a user would rate a track highly (label 1) or not at all (label 0).
The evaluation was structured around a "3-out-of-6" constraint: for each test user, six tracks were provided, exactly three of which were highly rated by the user. This transformed the problem from absolute rating prediction into a ranking and selection task, where the goal was to correctly identify the three positive items out of the six.
Methodology
Matrix Factorization (MF)
The team utilized several MF variants, such as Probabilistic Matrix Factorization (PMF) and CofiRank. To handle the binary nature of the task, they trained these models on "Balanced" datasets (equal proportions of positive and sampled negative ratings) and "Augmented" sets to improve robustness.
Taxonomy-based Classification
A core component of the solution was leveraging the rich metadata provided in the challenge. The dataset organized music into a hierarchy: Track $\rightarrow$ Album $\rightarrow$ Artist $\rightarrow$ Genre.
The team used this structure for Graph-based Data Augmentation. By "diffusing" ratings through the taxonomy graph, they could impute missing values and create features for Random Forests and SVMs. For example, a track's score could be influenced by the average rating of other tracks on the same album or by the same artist.
Leaderboard Ensembling
The most novel contribution was the team's approach to ensembling. Recognizing that the misclassification metric is mathematically related to Mean Squared Error for binary outcomes, they treated the ensemble as a linear regression problem. By submitting different combinations of models and observing the resulting public leaderboard scores, they were able to estimate the "sufficient statistics" needed to solve for the optimal weights ($\beta$) of their linear ensemble. This effectively turned the leaderboard into a validation set without requiring access to the ground truth labels.
Key Insights and Results
The "False Positives" approach highlighted several critical factors for success in large-scale recommendation:
- Diversity is Key: While a single Random Forest model achieved a 5.7% error rate, combining it with MF models—which capture different latent patterns—led to substantial gains.
- Regularization via Diffusion: Smoothing ratings across the taxonomy graph provided a powerful way to handle "cold-start" items.
- Ranking over Rating: The team realized that absolute scores were less important than the relative ranking of the six items per user, allowing them to optimize for ranking-specific losses.
The final ensemble reached a leaderboard error rate of 3.8863%. This success was achieved despite challenges like the computational cost of k-Nearest Neighbor approaches (requiring a 1.4TB similarity matrix) and the difficulty of implementing sophisticated randomized rounding techniques.
Conclusion
The "False Positives" solution demonstrates the power of ensembling heterogeneous models and the strategic use of competition leaderboards. By combining collaborative filtering with deep taxonomic features, the team created a robust system capable of high-precision music recommendation under strict ranking constraints.
Summary updated