November 16th, 2011 @ 1130am Srikanth Jagabathula (NYU)

Sparse distributions over permutations: applications to non-parametric choice modeling

Distributions over permutations are fundamental modeling tools in several practical applications. A particularly rich application domain in this context is the modeling of preferences of users over objects (such as products, election candidates, webpages, etc). Most of these applications make available only partial preference information (think of historical sales transaction data in the context of products or click-through data in the context of webpages). As a result, the core problem reduces to learning the underlying distribution over permutations from the available partial/marginal information.

Most of the literature in this context (dating back to at least the 1920s) considers parametric approaches in which a specific parametric structure is imposed on the underlying distribution over permutations and the parameters are learnt from the partial/marginal information. We deviate from this approach and consider sparsity (as measured by the support size of the distribution) as the model selection criterion. This results in a non-parametric approach where our goal would be to learn an `appropriate' sparse distribution over permutations given the data and the application context. Apart from the usual advantages, the primary strength of such a nonparametric model is its ability to scale with the data.

In this talk, I will first present our model selection criteria and their justification. Distributions over permutations result in huge computational challenges due to their factorial size. Hence, I will next talk about the algorithms we propose and their associated guarantees in order to address the computational challenges. Finally, I will present empirical results demonstrating the efficacy of our approach by testing our methods on the popular American Psychological Association (APA) dataset and the sales transaction data from a major US automaker.

This is joint work with Vivek Farias, MIT Sloan, and Devavrat Shah, MIT EECS.

seminars/seminaritems/2011-11-16.txt · Last modified: 2011/10/31 23:39 by silberman