Workshop at WSDM-2014
Personalization is central to most Internet experiences. Personalization is a data-driven process, whether the data are explicitly gathered (e.g., by asking people to fill out forms) or implicitly (e.g. through analysis of behavioral data). It is clear that designing for effective personalization poses interesting engineering and computer science challenges. However, personalization is also a user experience issue. We believe that encouraging dialogue and collaboration between data mining experts, content providers, and user-focused researchers will offer gains in the area of personalization for search and for other domains. This workshop is part of a larger effort we are developing: D2D: Data to Design - Design to Data. Our vision is to provide a forum for researchers and practitioners in computer and systems sciences, data sciences, machine learning, information retrieval, interaction and interface design, and human computer interaction to interact. Our goal is to explore issues surrounding content and presentation personalization across different devices, and to set an agenda for cross-discipline, collaborative engagement.
Tutorial at WWW-2014
The focus of this tutorial will be e-commerce product search. Several research challenges appear in this context, both from a research standpoint as well as an application standpoint. We will present various approaches adopted in the industry, review well-known research techniques developed over the last decade, draw parallels to traditional web search highlighting the new challenges in this setting, and dig deep into some of the algorithmic and technical approaches developed for this context. A specific approach that will involve a deep dive into literature, theoretical techniques, and practical impact is that of identifying most suited results quickly from a large database, with settings various across cold start users, and those for whom personalization is possible. In this context, top-k and skylines will be discussed specifically as they form a key approach that spans the web, data mining, and database communities and presents a powerful tool for search across multi-dimensional items with clear preferences within each attribute, like product search as opposed to regular web search.
A Study of Query Term Deletion using Large-scale E-commerce Search Logs
In ECIR 2014 (To Appear)
Query term deletion is one of the commonly used strategies for query rewriting. In this paper, we study the problem of query term deletion using large-scale e-commerce search logs. Especially we focus on queries that do not lead to user clicks and aim to predict a reduced and better query that can lead to clicks by term deletion. Accurate prediction of term deletion can potentially help users recover from poor search results and improve shopping experience. To achieve this,we use various term-dependent and query-dependent measures as features and build a classifier to predict which term is the most likely to be deleted from a given query. Different from previous work on query term deletion, we compute the features not only based on the query history and the available document collection, but also conditioned on the query category, which captures the high-level context of the query. We validate our approach using a large collection of query sessions logs from a leading e-commerce site, and show that it provides promising performance in term deletion prediction, and significantly outperforms baselines that rely on query history and corpus-based statistics without incorporating the query context information.
Beyond Modeling Private Actions: Predicting Social Shares
The “Expression Gap”: Do you Like what you Share?
Im2Depth: Scalable Exemplar Based Depth Transfer
WACV 2014: IEEE Winter Conference on Applications of Computer Vision
The rapid increase in number of high quality mobile cameras have opened up an array of new problems in mobile vision. Mobile cameras are predominantly monocular and are devoid of any sense of depth, making them heavily reliant on 2D image processing. Understanding 3D structure of scenes being imaged can greatly improve the performance of existing vision/graphics techniques. In this regard, recent availability of large scale RGB-D datasets beg for more effective data driven strategies to leverage the scale of data. We propose a depth recovery mechanism "im2depth", that is lightweight enough to run on mobile platforms, while leveraging the large scale nature of modern RGB-D datasets. Our key observation is to form a basis (dictionary) over the RGB and depth spaces, and represent depth maps by a sparse linear combination of weights over dictionary elements. Subsequently, a prediction function is estimated between weight vectors in RGB to depth space to recover depth maps from query images. A final superpixel post processor aligns depth maps with occlusion boundaries, creating physically plausible results. We conclude with thorough experimentation with four state of the art depth recovery algorithms, and observe an improvement of over 6.5 percent in shape recovery, and over 10cm reduction in average L1 error.
Categories: Publications, Vison COE’s
Furniture-Geek: Understanding Fine-Grained Furniture Attributes from Freely Associated Text and Tags
WACV 2014: IEEE Winter Conference on Applications of Computer Vision
As the amount of user generated content on the internet grows, it becomes ever more important to come up with vision systems that learn directly from weakly annotated and noisy data. We leverage a large scale collection of user generated content comprising of images, tags and title/captions of furniture inventory from an e-commerce website to discover and categorize learnable visual attributes. Furniture categories have long been the quintessential example of why computer vision is hard, and we make one of the first attempts to understand them through a large scale weakly annotated dataset. We focus on a handful of furniture categories that are associated with a large number of fine-grained attributes. We propose a set of localized feature representations built on top of state-of-the-art computer vision representations originally designed for fine-grained object categorization. We report a thorough empirical characterization on the visual identifiability of various fine-grained attributes using these representations and show encouraging results on finding iconic images and on multi-attribute prediction.
Categories: Publications, Vison COE’s
Shopping with Bonus Money: eBay, loyalty schemes and consumer spending
CHIMoney (Workshop at CHI-2014)
In proceedings of the Workshop on Log-based Personalization (the 4th WSCD workshop) at WSDM 2014.
Personalization offers the promise of improving online search and shopping experience. In this work, we perform a large scale analysis on the sample of eBay query logs, which involves 9.24 billion session data spanning 12 months (08/2012-07/2013) and address the following topics (1) What user information is useful for personalization; (2) Importance of per-query personalization (3) Importance of recency in query prediction. In this paper, we study these problems and provide some preliminary conclusions.
In this paper, we consider the natural arrival and departure of users in a social network, and ask whether the dynamics of arrival, which have been studied in some depth, also explain the dynamics of departure, which are not as well studied. Through study of the DBLP co-authorship network and a large online social network, we show that the dynamics of departure behave differently from the dynamics of formation. In particular, the probability of departure of a user with few friends may be understood most accurately as a function of the raw number of friends who are active. For users with more friends, however, the probability of departure is best predicted by the overall fraction of the user's neighborhood that is active, independent of size. We then study global properties of the sub-graphs induced by active and inactive users, and show that active users tend to belong to a core that is densifying and is significantly denser than the inactive users. Further, the inactive set of users exhibit a higher density and lower conductance than the degree distribution alone can explain. These two aspects suggest that nodes at the fringe are more likely to depart and subsequent departure are correlated among neighboring nodes in tightly-knit communities.
Invited Tutorial at ICDCN-2013
ICDCN-2013 (Invited to Special Issue of TCS)
Unsupervised models can provide supplementary soft constraints to help classify new target data under the assumption that similar objects in the target set are more likely to share the same class label. Such models can also help detect possible dierences between training and target distributions, which is useful in applications where concept drift may take place. This paper describes a Bayesian frame work that takes as input class labels from existing classefiers (designed based on labeled data from the source domain), as well as cluster labels from a cluster ensemble operating solely on the target data to be classified and yields a con-ensus labeling of the target data. This framework is particularly useful when the statistics of the target data drift or change from those of the training data. We also show that the proposed framework is privacy-aware and allows performing distributed learning when data/models have sharing restrictions. Experiments show that our framework can yield superior results to those provided by applying classifier ensembles only.
Chapter 20: Volume 31: Handbook of Statistics, 1st Edition : Machine Learning : Theory and Applications
Chapter 11: Volume 31: Handbook of Statistics, 1st Edition : Machine Learning : Theory and Applications
Journal of the Association for Computing Machinery (JACM) - 2013
Performing random walks in networks is a fundamental primitive that has found applications in many areas of computer science, including distributed computing. In this article, we focus on the problem of sampling random walks efficiently in a distributed network and its applications. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain random walk samples. All previous algorithms that compute a random walk sample of length ℓ as a subroutine always do so naively, that is, in O(ℓ) rounds. The main contribution of this article is a fast distributed algorithm for performing random walks. We present a sublinear time distributed algorithm for performing random walks whose time complexity is sublinear in the length of the walk. Our algorithm performs a random walk of length ℓ in Õ(√ℓD) rounds (Õ hides polylog n factors where n is the number of nodes in the network) with high probability on an undirected network, where D is the diameter of the network. For small diameter graphs, this is a significant improvement over the naive O(ℓ) bound. Furthermore, our algorithm is optimal within a poly-logarithmic factor as there exists a matching lower bound [Nanongkai et al. 2011]. We further extend our algorithms to efficiently perform k independent random walks in Õ(√kℓD + k) rounds. We also show that our algorithm can be applied to speedup the more general Metropolis-Hastings sampling. Our random-walk algorithms can be used to speed up distributed algorithms in applications that use random walks as a subroutine. We present two main applications. First, we give a fast distributed algorithm for computing a random spanning tree (RST) in an arbitrary (undirected unweighted) network which runs in Õ(√mD) rounds with high probability (m is the number of edges). Our second application is a fast decentralized algorithm for estimating mixing time and related parameters of the underlying network. Our algorithm is fully decentralized and can serve as a building block in the design of topologically-aware networks.
Learning bottom up text attention maps for text detection using stroke width transform
Learning top down scene context for visual attention modeling in natural images
in Proceedings of the 22nd international conference on World Wide Web (WWW '13)
Reuse and remarketing of content and products is an integral part of the internet. As E-commerce has grown, online resale and secondary markets form a signiﬁcant part of the commerce space. The intentions and methods for reselling are diverse. In this paper, we study an instance of such markets that aﬀords interesting data at large scale for mining purposes to understand the properties and patterns of this online market. As part of knowledge discovery of such a market, we ﬁrst formally propose criteria to reveal unseen resale behaviors by elastic matching identiﬁcation (EMI) based on the account transfer and item similarity properties of transactions. Then, we present a large-scale system that leverages MapReduce paradigm to mine millions of online resale activities from petabyte scale heterogeneous ecommerce data. With the collected data, we show that the number of resale activities leads to a power law distribution with a ‘long tail’, where a signiﬁcant share of users only resell in very low numbers and a large portion of resales come from a small number of highly active resellers. We further conduct a comprehensive empirical study from diﬀerent aspects of resales, including the temporal, spatial patterns, user demographics, reputation and the content of sale postings. Based on these observations, we explore the features related to “successful” resale transactions and evaluate if they can be predictable. We also discuss uses of this information mining for business insights and user experience on a real-world online marketplace.
RepRank: Reputation in a Peer-to-Peer Online System
accepted to WWW2013 poster.
To appear in Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2013.
Given the enormous growth in user-generated videos, it is becoming increasingly important to be able to navigate them efficiently. As these videos are generally of poor quality, summarization methods designed for well-produced videos do not generalize to them. To address this challenge, we propose to use web-images as a prior to facilitate summarization of user-generated videos. Our main intuition is that people tend to take pictures of objects to capture them in a maximally informative way. Such images could therefore be used as prior information to summarize videos containing a similar set of objects. In this work, we apply our novel insight to develop a summarization algorithm that uses the web-image based prior information in an unsupervised manner. Moreover, to automatically evaluate summarization algorithms on a large scale, we propose a framework that relies on multiple summaries obtained through crowdsourcing. We demonstrate the effectiveness of our evaluation framework by comparing its performance to that of multiple human evaluators. Finally, we present results for our framework tested on hundreds of user-generated videos.
To appear in Proceedings of IEEE International Conference on Computer Vision & Pattern Recognition (CVPR) 2013
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.
With the explosion of mobile devices with cameras, online search has moved beyond text to other modalities like images, voice, and writing. For many applications like Fashion, image-based search offers a compelling interface as compared to text forms by better capturing the visual attributes. In this paper we present a simple and fast search algorithm that uses color as the main feature for building visual search. We show that low level cues such as color can be used to quantify image similarity and also to discriminate among products with different visual appearances. We demonstrate the effectiveness of our approach through a mobile shopping application (eBay Fashion App available at https://itunes.apple.com/us/app/ebay-fashion/id378358380?mt=8 and eBay image swatch is the feature indexing millions of real world fashion images). Our approach outperforms several other state-of-the-art image retrieval algorithms for large scale image data.
Graph-based Topic-focused Retrieval in Distributed Camera Network
IEEE Transactions on Multimedia, in press
Wide-area wireless camera networks are being increasingly deployed in many urban scenarios. The large amount of data generated from these cameras pose significant information processing challenges. In this work we focus on representation, search and retrieval of moving objects in the scene, with emphasis on local camera node video analysis. We develop a graph model that captures the relationships among objects without the need to identify global trajectories. Specifically, two types of edges are defined in the graph: object edges linking the same object across the whole network and context edges linking different objects within a spatial-temporal proximity. We propose a manifold ranking method with a greedy diversification step to order the relevant items based on similarity as well as diversity within the database. Detailed experiments are carried out on a 10-camera network deployed on the bike paths within a university campus.
Synapse Classification and Localization in Electron Micrographs
Pattern Recognition Letters, in press
Classication and Detection of biological structures in Electron Micrographs (EM) is a relatively new large scale image analysis problem. The primary challenges are in characterizing diverse visual characteristics and develop- ment of scalable techniques. In this paper we propose novel methods for synapse detection and localization, an important problem in connectomics. We rst propose an attribute based descriptor for characterizing synaptic junctions. These descriptors are task specic, low dimensional and can be scaled across large image sizes. Subsequently, techniques for fast localization of these junctions are proposed. Experimental results on images acquired from a mammalian retinal tissue compare favourably with state of the art descriptors used for object detection.
To appear in Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Mobile Vision Workshop, 2013.
With the rapid proliferation of smartphones and tablet computers, search has moved beyond text to other modalities like images and voice. For many applications like Fashion, visual search offers a compelling interface that can capture stylistic visual elements beyond color and pattern that cannot be as easily described using text. However, extracting and matching such attributes remains an extremely challenging task due to high variability and deformability of clothing items. In this paper, we propose a fine-grained learning model and multimedia retrieval framework to address this problem. First, an attribute vocabulary is constructed using human annotations obtained on a novel fine-grained clothing dataset. This vocabulary is then used to train a fine-grained visual recognition system for clothing styles. We report benchmark recognition and retrieval results on Women's Fashion Coat Dataset and illustrate potential mobile applications for attribute-based multimedia retrieval of clothing items and image annotation.
Job Market Paper - Massachusetts Institute of Technology - January 2013
This study quantifies the efficiency of a real-world bargaining game with two-sided incomplete information. Myerson and Satterthwaite (1983) and Williams (1987) derived the theoretical efficient frontier for bilateral trade under two-sided uncertainty, but little is known about how well real-world bargaining performs relative to the frontier. The setting is wholesale used-auto auctions, an $80 billion industry where buyers and sellers participate in alternating-offer bargaining when the auction price fails to reach a secret reserve price. Using 300,000 auction/bargaining sequences, this study nonparametrically estimates bounds on the distributions of buyer and seller valuations and then estimates where bargaining outcomes lie relative to the efficient frontier. Findings indicate that the observed auction-followed-by-bargaining mechanism is quite efficient, achieving 88-96% of the surplus and 92-99% of the trade volume which can be achieved on the efficient frontier.
Occupational Licensing and Quality: Distributional and Heterogeneous Effects in the Teaching Profession
Massachusetts Institute of Technology - January 2013
This paper examines a common form of entry restriction: occupational licensing. The paper studies two questions: first, how occupational licensing laws affect the distribution of quality, and second, how the effects of licensing on quality vary across regions of differing income levels. The paper uses variation in state licensing requirements for teachers and two national datasets on teacher qualifications and student outcomes from 1983-2008. Two measures of quality are used: the qualifications of candidates entering the occupation (input quality) and the quality of service provided (output quality). Results show that more restrictive licensing laws may lead some first-year teachers of high input quality to opt out of the occupation. In the sample of teachers who remain in the occupation multiple years, stricter licensing appears to increase input quality at most quantiles of the teacher quality distribution. The distribution of student test scores also increases with stricter occupational licensing, primarily in the upper half of the distribution. For most forms of licensing studied, input and output quality improvements due to stricter licensing requirements occur in high-income rather than low-income school districts, consistent with theoretical predictions of Shapiro (1986)
Bid Takers or Market Makers: The Effect of Auctioneers on Auction Outcomes
A large literature in economics has studied how different auction designs (e.g, English, Dutch, second-price) affect market outcomes. There has been much less work, however, studying whether the process used in conducting these auctions matters. In particular, while open ascending bid (i.e., English) auctions are extremely important in practice and have received enormous attention in both theoretical and empirical auction literatures, there has been surprisingly little work studying whether the behavior of the auctioneers who conduct these auctions has any effect on outcomes. We use data from over 600,000 wholesale used-car auctions to address two questions: 1) Do the outcomes produced by individual auctioneers differ in a systematic fashion? and 2) What is the most likely mechanism for these differences in outcomes? We find substantial heterogeneities in auctioneer effects, even among a set of professional auctioneers with experienced bidders. We argue that both survey and empirical evidence suggest that this effect is driven by auctioneers being able to create a sense of urgency and excitement as opposed to information-based mechanisms.