Publications

Publications
Publications
We strongly believe in open source and giving to our community. We work directly with researchers in academia and seek out new perspectives with our intern and fellowship programs. We generalize our solutions and release them to the world as open source projects. We host discussions and publish our results.

Publications

To appear in Proceedings of IEEE International Conference on Computer Vision & Pattern Recognition (CVPR) 2013

Dense Non-Rigid Point-Matching Using Random Projections

Raffay Hamid, Dennis DeCoste, Chih-Jen Lin

We present a robust and efficient technique for matching dense sets of points undergoing non-rigid spatial transformations. Our main intuition is that the subset of points that can be matched with high confidence should be used to guide the matching procedure for the rest.

We propose a novel algorithm that incorporates these high-confidence matches as a spatial prior to learn a discriminative subspace that simultaneously encodes both the feature similarity as well as their spatial arrangement.

Conventional subspace learning usually requires spectral decomposition of the pair-wise distance matrix across the point-sets, which can become inefficient even for moderately sized problems. To this end, we propose the use of random projections for approximate subspace learning, which can provide significant time improvements at the cost of minimal precision loss.

This efficiency gain allows us to iteratively find and remove high-confidence matches from the point sets, resulting in high recall. To show the effectiveness of our approach, we present a systematic set of experiments and results for the problem of dense non-rigid image-feature matching.

Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (ACL), 2012.

Structuring E-Commerce Inventory

Karin Maugé, Khashayar Rohanimanesh, Jean-David Ruvini

Large e-commerce enterprises feature millions of items entered daily by a large variety of sellers. While some sellers provide rich, structured descriptions of their items, a vast majority of them provide unstructured natural language descriptions.

In the paper we present a 2 steps method for structuring items into descriptive properties. The first step consists in unsupervised property discovery and extraction. The second step involves supervised property synonym discovery using a maximum entropy based clustering algorithm.

We evaluate our method on a year worth of eCommerce data and show that it achieves excellent precision with good recall.

Keywords
ACL 2012: 805-814

Structuring E-Commerce Inventory

Karin Maugé, Khashayar Rohanimanesh, Jean-David Ruvini

Large e-commerce enterprises feature millions of items entered daily by a large variety of sellers. While some sellers provide rich, structured descriptions of their items, a vast majority of them provide unstructured natural language descriptions.

In the paper we present a 2 steps method for structuring items into descriptive properties. The first step consists in unsupervised property discovery and extraction. The second step involves supervised property synonym discovery using a maximum entropy based clustering algorithm.

We evaluate our method on a year worth of eCommerce data and show that it achieves excellent precision with good recall.

Keywords
CIKM 2012:596-604

Large-scale Item Categorization for e-Commerce

Dan Shen, Jean-David Ruvini, Badrul Sarwar

This paper studies the problem of leveraging computationally intensive classification algorithms for large scale text categorization problems. We propose a hierarchical approach which decomposes the classification problem into a coarse level task and a fine level task.

A simple yet scalable classifier is applied to perform the coarse level classification while a more sophisticated model is used to separate classes at the fine level. However, instead of relying on a human-defined hierarchy to decompose the problem, we use a graph algorithm to discover automatically groups of highly similar classes.

As an illustrative example, we apply our approach to real-world industrial data from eBay, a major e-commerce site where the goal is to classify live items into a large taxonomy of categories.

In such industrial setting, classification is very challenging due to the number of classes, the amount of training data, the size of the feature space and the real world requirements on the response time. We demonstrate through extensive experimental evaluation that (1) the proposed hierarchical approach is superior to flat models, and (2) the data-driven extraction of latent groups works significantly better than the existing human-defined hierarchy.

Keywords
SDM 2012

Multi-Skill Collaborative Teams based on Densest Subgraphs

Atish Das Sarma, Amita Gajewar, Atish Das Sarma, Amita Gajewar

We consider the problem of identifying a team of skilled individuals for collaboration, in the presence of a social network, with the goal to maximize the collaborative compatibility of the team. Each node in the social network is associated with skills, and edge-weights specify affinity between respective nodes. We measure collaborative compatibility objective as the density of the induced subgraph on selected nodes.

This problem is NP-hard even when the team requires individuals of only one skill. We present a 3-approximation algorithm for the single-skill team formulation problem. We show the same approximation can be extended to a special case of multiple skills.

Our problem generalizes the formulation studied by Lappas et al. [KDD ’09] who measure team compatibility in terms of diameter or spanning tree. The experimental results show that the density-based algorithms outperform the diameter-based objective on several metrics.

Keywords
Second International ICST Conference, AMMA 2011. Vol. 80, Lecture Notes of the Institute for Computer Science, Social Informatics and Telecommunications Engineering. Springer, 2012. (Revised Selected Papers.)

Auctions, Market Mechanisms, and Their Applications

Sanmay Das, Sebastien Lahaie, Boleslaw Szymanski

No Information

Keywords
WSDM 2012

Online selection of diverse results

Debmalya Panigrahi, Atish Das Sarma, Gagan Aggarwal, Andrew Tomkins

The phenomenal growth in the volume of easily accessible information via various web-based services has made it essential for service providers to provide users with personalized representative summaries of such information.

Further, online commercial services including social networking and micro-blogging websites, e-commerce portals, leisure and entertainment websites, etc. recommend interesting content to users that is simultaneously diverse on many different axes such as topic, geographic specificity, etc.

The key algorithmic question in all these applications is the generation of a succinct, representative, and relevant summary from a large stream of data coming from a variety of sources. In this paper, we formally model this optimization problem, identify its key structural characteristics, and use these observations to design an extremely scalable and efficient algorithm.

We analyze the algorithm using theoretical techniques to show that it always produces a nearly optimal solution. In addition, we perform large-scale experiments on both real-world and synthetically generated datasets, which confirm that our algorithm performs even better than its analytical guarantees in practice, and also outperforms other candidate algorithms for the problem by a wide margin.

Keywords

Pages