Combining Predictors for Recommending Music: the False Positives' approach to KDD Cup track 2

Suhrid Balakrishnan, Rensheng Wang, Carlos Eduardo Scheidegger, Angus MacLellan, Yifan Hu, Aaron Archer, Shankar Krishnan, David L. Applegate, Guangqin Ma, S. Tom Au

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 music taxonomy hierarchy used for graph-based data augmentation, connecting tracks to albums, artists, and genres.

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.

Visualizing the hierarchical relationships between music entities, which allowed for rating diffusion across the taxonomy.

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

Abstract

We describe our solution for the KDD Cup 2011 track 2 challenge. Our solution relies heavily on ensembling together diverse individual models for the prediction task, and achieved a final leaderboa...
BibTeX
@inproceedings{balakrishnan2012combining,
  author = {Suhrid Balakrishnan and Rensheng Wang and Carlos Eduardo Scheidegger and Angus MacLellan and Yifan Hu and Aaron Archer and Shankar Krishnan and David L. Applegate and Guangqin Ma and S. Tom Au},
  title = {{Combining Predictors for Recommending Music: the False Positives' approach to KDD Cup track 2}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2012},
  url = {https://openreview.net/forum?id=lxCmalX-FdE},
}
Figure