Algorithms on Hadoop

I gave a talk last night on some fun things we do with our Hadoop cluster at Last.fm including

• topic modelling with LDA
  
• graph-based recommendation with Label Propagation
  
• audio analysis
  

Here are the slides.

Algorithms on Hadoop at Last.fm

View more presentations from Mark Levy

RecSys 2010: music

How do teenagers learn about new music?  Audrey LaPlante has spent some time actually asking them, and presented some of their answers at the Workshop on Music Recommendation and Discovery.

Some of her findings were extremely interesting.  All of the teenagers she spoke to said that their tastes had changed substantially over time, and that the changes were due to changes in their social network.  Most had music geek friends whom they actively consulted for music recommendations, even though they were not influential people in other respects.  Although close contacts were most likely to be sources of new music, those chosen to play that role were "almost always those whose social network were more different from theirs, mostly those who were going to a different school".

I'll be interested to follow Audrey's research and see how we can learn to make online social networks an equally great place for young people to discover new music.

RecSys 2010: YouTube

The YouTube team had a poster at RecSys descibing their recommender in some detail.  The design is intentionally simple, and apparently entirely implemented as a series of MapReduce jobs.

They first compute fixed-length lists of related videos, based in principle on simple co-occurrence counts in a short period i.e. given a video i, the count for a candidate related video j could be the number of users who viewed both i and j within the last 24 hours.  The counts are normalised to take into account the relative popularity of different videos, and no doubt massaged in numerous other ways to remove noise and bias.  As the paper says, "this is a simplified description".

At recommendation time they build a set of seed videos representing the query user, based on the user's views, favourites, playlists, etc.  They then assemble a candidate pool containing the related videos for all of the seeds.  If the pool is too small, they expand it by adding the related videos of all the videos already in the pool, though always keeping track of the original seed video for messaging purposes.  The candidates in the pool are reranked based on a linear combination of values expressing the popularity of a given candidate video, the importance of its seed to the user, the overall popularity of the candidate and its freshness.  Finally the recommended videos are diversified, using simple constraints on the number of recommended videos that can be associated with any one seed, or have been uploaded by any one user.  Diversification is particularly important as related videos are typically very tightly associated with their seed.

Precomputed recommendations are cached and served up a few at a time to a user each time they visit the site.  Each recommendation is easily associated with an explanation based on its seed video: "recommended because you favorited abc".  While this system isn't going to win any best paper prizes it is certainly effective: 60% of all video clicks from the YouTube homepage are for recommendations.

RecSys 2010: social recommendations

Mohsen Jamali won the best paper award at RecSys for his presentation on SocialMF, a model-based recommender designed to improve ratings-based recommendations for users who have made few ratings but who have friends, or friends of friends, who have provided plenty.  Mohsen's previous solution to the same problem was TrustWalker.  TrustWalker predicts ratings from a set of item-item similarities and a social graph, where nodes are users and edges represent trust or friendship relationships.  The rating for item i for user u is predicted by taking a short random walk on the graph, stopping at some friend-of-a-friend v and returning v's rating for item j, where j is the most similar item to i which v has rated.  Closed form expressions for these predictions don't scale at all well, so to make a prediction TrustWalker actually executes the random walk a few times and returns the average rating.  On a test set of ratings by 50k users for 100k product reviews from the Epinions website, TrustWalker does indeed show a significant benefit in both coverage and prediction accuracy for cold start users over baseline methods that don't leverage the social graph.

SocialMF is a Bayesian model-based solution to the same problem: latent factors for all users and items are learned jointly from ratings and the social graph.  Ratings for cold start users can then be predicted from their learned factors.  When tested on the epinions dataset, and a new one of ratings by 1M users for 50k movies crawled from Flixster, SocialMF again does indeed improve the accuracy of predicted ratings for cold start users over latent factor models that don't take the social graph into account.

The model-based approach is elegant and perhaps even scalable: learning time is linear in the number of users, and the paper reports a runtime of 5.5 hours for 1M users.  But it lacks the powerful explanations of the simpler system: "recommended for you because your friend xyz likes it".

RecSys 2010: industry

One striking feature of this year's ACM Recommender Systems conference was a large industry presence: from SAP, Bloomberg, IBM and Sony, to Yahoo! and Google, as well as a host of smaller outfits. I particularly enjoyed comparing notes with the teams from YouTube, Microsoft Bing, and the b2b recommendation company MediaUnbound (now Rovi), which has provided music recommendation services for MTV and Ericsson. Some clear themes emerged from those conversations, as well as the various panels in which we were speaking.

Some researchers in the field might be surprised to hear that the predominant industry view is that predicting ratings for items isn't a very useful way to build or evaluate a recommender system. This is partly because "users don't get ratings", as Palash Nandy from Google put it at the opening panel, "they always rate 1 or 5", and partly because improving prediction of users' ratings is at best weakly aligned with the business aims of most systems. In fact all of the industry people I spoke to were suspicious of offline evaluation metrics for recommendations in general. The YouTube team had even compared some standard offline metrics evaluating two recommendation algorithms with results from online controlled experiments on their live system. They found no correlation between the two: this means that the offline metrics had no value whatsoever in telling which algorithm would do better in practice. Finally there was a strong industry concern that the design of the Netflix Prize competition had led many researchers into developing methods that could not possibly scale to real world scenarios.  Most industry people I spoke to described scalability as their number one consideration.

There were two strong beliefs that I heard stated many times in the last few days: improvements in the overall user experience dominate likely enhancements of current algorithms; and recommendations from friends remain far more powerful than those from machines.  So the sort of research that will excite industry in the near future is likely to focus on topics such as:

• providing more compelling explanations for machine recommendations
• exploiting social relationships to make better recommendations
• optimising the user's interaction with particular recommenders

Where does this leave the academic researcher with good ideas but no access to real users? This question was raised eloquently by Jo Konstan from the pioneering GroupLens team at the University of Minnesota, in a panel debating the value of competitions for scientific research. Jo's plea was for someone to offer researchers not a big cash prize or even a huge dataset, but rather an experimental platform where their systems can be deployed on a modest group of users under controlled conditions, the uptake of their recommendations recorded, and users in the test group asked directly to give feedback. This approach would meet most of industry's concerns about academic research head on.  But it raises obvious issues of privacy, security, maintenance, and trust between businesses and their customers - probably enough to scare away even the most research-friendly commercial organisation.

One final thing that might interest researchers with concerns about any of these issues: pretty much everyone said that they were hiring.

ISMIR 2010: code

The Best Paper award went to Ron Weiss and Juan Bello of NYU for their work on finding repeating patterns in musical audio with Probabilistic Latent Component Analysis (aka Convolutive Non-Negative Matrix Factorisation) applied to chroma features. This finds a best fit decomposition of the features considered as a linear mixture of some number of latent components convolved with corresponding activation weights that vary over time during the course of the track. Weiss and Bello apply priors to enforce sparsity in the activations, so that only a small number of components are active at any given time. Better still this means that you can start with a large number of latent components, and the activations for most of them drop to zero throughout the track as the learning algorithm proceeds, meaning that the effective number of underlying components can be learned rather than having to be specified in advance. Finally you can estimate the high-level repeat structure of the track by picking a simple viterbi path through the activations. I thought the paper was well worth the prize: an original approach, convincing results, clear presentation at the conference, and, best of all, published python code at http://ronw.github.com/siplca-segmentation.

Ron Weiss also had a hand in the appealing Gordon Music Collection Database Management System available from http://bitbucket.org/ronw/gordon. This looks like a great lightweight framework for managing experiments based on audio feature extraction, with a python api, support for sql-like queries, automatic feature caching, and a clean web interface which includes automatic best-effort visualisations of the features for each track. I'm really looking forward to trying it out. The name Gordon apparently refers to the character in Nick Hornby's novel High Fidelity.

Opinion is increasingly divided about the pros and cons of using Flash on your website. If you still love Flash, then the Audio Processing Library for Flash, available from http://code.google.com/p/alf, now lets you do audio feature extraction in realtime, directly from your Flash movies. The developers even have a suprisingly funky example game, in which the graphics, and even some of the gameplay, are based directly on features extracted from the soundtrack as it plays: presumably this is one game which MIR researchers will always win!

ISMIR 2010: recommendation

Brian McFee presented a poster on Learning Similarity from Collaborative Filters describing a method of addressing the cold start problem. The idea is to learn to rank tag representations of artists or tracks, so that the ranks agree with similarity scores given by collaborative filtering, using Metric Learning to Rank, an extension of the ranking SVM. This shows a modest improvement when applied to autotags inferred from audio, but really good results when applied to musicological tags scraped from Pandora. Conclusion: if you have musicological tags then you may not need CF data to get really good artist similarities.

Although at the moment musicological tags are probably even harder to come by than CF data, there are encouraging signs of progress in autotagging. A nice paper by James Bergstra, Mike Mandel and Doug Eck on Scalable Genre and Tag Prediction with Spectral Covariance shows impressive results with a scalable framework that learns from simple spectral features.

Along with several submissions to the MIREX evaluation tasks, this paper also illustrates another small trend at ISMIR 2010, which is a move away from known flawed features, in this case MFCCs used to represent musical timbre.