Friday, January 25, 2013

Linear Bandits in High Dimension and Recommendation Systems

I recently stumbled on a presentation by Andrea Montanari on Collaborative Filtering: Models and Algorithms where I learned that his team won the 2011 CAMrA competition 

If an AMP beat the netflix winner, I wonder if another AMP instance could beat SVDFeature at the latest KDD cups ? The seocnd part of the presentation is provided in more detail in Linear Bandits in High Dimension and Recommendation Systems by Yash Deshpande and Andrea Montanari

A large number of online services provide automated recommendations to help users to navigate through a large collection of items. New items (products, videos, songs, advertisements) are suggested on the basis of the user’s past history and –when available– her demographic profile. Recommendations have to satisfy the dual goal of helping the user to explore the space of available items, while allowing the system to probe the user’s preferences.We model this trade-off using linearly parametrized multi-armed bandits, propose a policy and prove upper and lower bounds on the cumulative “reward” that coincide up to constants in the data poor(high-dimensional) regime. Prior work on linear bandits has focused on the data rich (low-dimensional)regime and used cumulative “risk” as the figure of merit. For this data rich regime, we provide a simple modification for our policy that achieves near-optimal risk performance under more restrictive assumptions on the geometry of the problem. We test (a variation of) the scheme used for establishing achievability on the Netflix and MovieLens datasets and obtain good agreement with the qualitative predictions of the theory we develop.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.


Zeno said...

Hi Igor,

where do they beat the Netflix winners? Have not found anything in the presentation, nor in the paper.

Igor said...

From the paper

"..In Section 5 we present numerical simulations of our policy on synthetic as well as realistic data from the Netflix and MovieLens datasets..."

It's a subset and the code has not been releasesd so it is still fictional at this point.


Yash Deshpande said...

Hi Igor,

Just to clarify things a bit: the presentation deals with two essentially independent challenges in
recommendation systems: privacy and interactivity. The paper you link deals strictly with the latter. As for the former perhaps the following would be more useful:

The paper detailing the work on the 2011 CAMrA challenge is available here:

Earlier work on matrix completion is detailed in papers with Raghu Keshavan. His thesis contains all the necessary references.

Igor said...

Thanks Yash !