OpenRaiser/Intern-Atlas huggingface dataset:
Learning Tree Structure in Multi-Task Learning
Authors: Lei Han, Yu Zhang
Venue: KDD
Year: 2015

In multi-task learning (MTL), multiple related tasks are learned jointly by sharing information according to task relations. One promising approach is to utilize the given tree structure, which describes the hierarchical relations among tasks, to learn model parameters under the regularization framework. However, such a priori information is rarely available in most applications. To the best of our knowledge, there is no work to learn the tree structure among tasks and model parameters simultaneously under the regularization framework and in this paper, we develop a TAsk Tree (TAT) model for MTL to achieve this. By specifying the number of layers in the tree as H, the TAT method decomposes the parameter matrix into H component matrices, each of which corresponds to the model parameters in each layer of the tree. In order to learn the tree structure, we devise sequential constraints to make the distance between the parameters in the component matrices corresponding to each pair of tasks decrease over layers, and hence the component parameters will keep fused until the topmost layer, once they become fused in a layer. Moreover, to make the component parameters have chance to fuse in different layers, we develop a structural sparsity regularizer, which is the sum of the ℓ<sub>2</sub> norm on the pairwise difference among the component parameters, to learn layer-specific task structure. In order to solve the resulting non-convex objective function, we use the general iterative shrinkage and thresholding (GIST) method. By using the alternating direction method of multipliers (ADMM) method, we decompose the proximal problem in the GIST method into three independent subproblems, where a key subproblem with the sequential constraints has an efficient solution as the other two subproblems do. We also provide some theoretical analysis for the TAT model. Experiments on both synthetic and real-world datasets show the effectiveness of the TAT model.
Data Science at Visa
Authors: Waqar Hasan, Min Wang
Venue: KDD
Year: 2015

Visa is the payments technology that forms the backbone of the world's financial systems by handling more than 7 trillion dollars of payments annually and our data reflects how the world spends money. We will describe technical achievements we have made in the area of fraud and cover some open challenges in data science.
Real-Time Top-R Topic Detection on Twitter with Topic Hijack Filtering
Authors: Kohei Hayashi, Takanori Maehara, Masashi Toyoda, Ken-ichi Kawarabayashi
Venue: KDD
Year: 2015

Twitter is a "what's-happening-right-now" tool that enables interested parties to follow thoughts and commentary of individual users in nearly real-time. While it is a valuable source of information for real-time topic detection and tracking, Twitter data are not clean because of noisy messages and users, which significantly diminish the reliability of obtained results.
Focusing on the Long-term: It's Good for Users and Business
Authors: Henning Hohnhold, Deirdre O&apos, Brien, Diane Tang
Venue: KDD
Year: 2015

Over the past 10+ years, online companies large and small have adopted widespread A/B testing as a robust data-based method for evaluating potential product improvements. In online experimentation, it is straightforward to measure the short-term effect, i.e., the impact observed during the experiment. However, the short-term effect is not always predictive of the long-term effect, i.e., the final impact once the product has fully launched and users have changed their behavior in response. Thus, the challenge is how to determine the long-term user impact while still being able to make decisions in a timely manner.
Traffic Measurement and Route Recommendation System for Mass Rapid Transit (MRT)
Authors: Thomas Holleczek, Dang The Anh, Shanyang Yin, Yunye Jin, Spiros Antonatos, Han Leong Goh, Samantha Low, Amy Shi Nash
Venue: KDD
Year: 2015

Understanding how people use public transport is important for the operation and future planning of the underlying transport networks. We have therefore developed and deployed a traffic measurement system for a key player in the transportation industry to gain insights into crowd behavior for planning purposes. The system has been in operation for several months and reports, at hourly intervals, (1) the crowdedness of subway stations, (2) the flows of people inside interchange stations, and (3) the expected travel time for each possible route in the subway network of Singapore. The core of our system is an efficient algorithm which detects individual subway trips from anonymized real-time data generated by the location based system of Singtel, the country's largest telecommunications company. To assess the accuracy of our system, we engaged an independent market research company to conduct a field study--a manual count of the number of passengers boarding and disembarking at a selected station on three separate days. A strong correlation between the calculations of our algorithm and the manual counts was found. One of our key findings is that travelers do not always choose the route with the shortest travel time in the subway network of Singapore. We have therefore also been developing a mobile app which allows users to plan their trips based on the average travel time between stations.
Non-exhaustive, Overlapping Clustering via Low-Rank Semidefinite Programming
Authors: Yangyang Hou, Joyce Jiyoung Whang, David F. Gleich, Inderjit S. Dhillon
Venue: KDD
Year: 2015

Clustering is one of the most fundamental tasks in data mining. To analyze complex real-world data emerging in many data-centric applications, the problem of non-exhaustive, overlapping clustering has been studied where the goal is to find overlapping clusters and also detect outliers simultaneously. We propose a novel convex semidefinite program (SDP) as a relaxation of the non-exhaustive, overlapping clustering problem. Although the SDP formulation enjoys attractive theoretical properties with respect to global optimization, it is computationally intractable for large problem sizes. As an alternative, we optimize a low-rank factorization of the solution. The resulting problem is non-convex, but has a smaller number of solution variables. We construct an optimization solver using an augmented Lagrangian methodology that enables us to deal with problems with tens of thousands of data points. The new solver provides more accurate and reliable answers than other approaches. By exploiting the connection between graph clustering objective functions and a kernel k-means objective, our new low-rank solver can also compute overlapping communities of social networks with state-of-the-art accuracy.
Website Optimization Problem and Its Solutions
Authors: Shuhei Iitsuka, Yutaka Matsuo
Venue: KDD
Year: 2015

Online controlled experiments are widely used to improve the performance of websites by comparison of user behavior related to different variations of the given website. Although such experiments might have an important effect on the key metrics to maximize, small-scale websites have difficulty applying this methodology because they have few users. Furthermore, the candidate variations increase exponentially with the number of elements that must be optimized. A testing method that finds a high-performing variation with a few samples must be devised to address these problems. As described herein, we formalize this problem as a website optimization problem and provide a basis to apply existing search algorithms to this problem. We further organize existing testing methods and extract devices to make the experiments more effective. By combining organized algorithms and devices, we propose a rapid testing method that detects high-performing variations with few users. We evaluated our proposed method using simulation experiments. Results show that it outperforms existing methods at any website scale. Moreover, we implemented our proposed method as an optimizer program and used it on an actual small-scale website. Results show that our proposed method can achieve 57% higher performance variation than that of the generally used A/B testing method. Therefore, our proposed method can optimize a website with fewer samples. The website optimization problem has broad application possibilities that are applicable not only to websites but also to manufactured goods.
Real-Time Bid Prediction using Thompson Sampling-Based Expert Selection
Authors: Elena Ikonomovska, Sina Jafarpour, Ali Dasdan
Venue: KDD
Year: 2015

We study online meta-learners for real-time bid prediction that predict by selecting a single best predictor among several subordinate prediction algorithms, here called "experts". These predictors belong to the family of context-dependent past performance estimators that make a prediction only when the instance to be predicted falls within their areas of expertise. Within the advertising ecosystem, it is very common for the contextual information to be incomplete, hence, it is natural for some of the experts to abstain from making predictions on some of the instances. Experts' areas of expertise can overlap, which makes their predictions less suitable for merging; as such, they lend themselves better to the problem of best expert selection. In addition, their performance varies over time, which gives the expert selection problem a non-stochastic, adversarial flavor. In this paper we propose to use probability sampling (via Thompson Sampling) as a meta-learning algorithm that samples from the pool of experts for the purpose of bid prediction. We show performance results from the comparison of our approach to multiple state-of-the-art algorithms using exploration scavenging on a log file of over 300 million ad impressions, as well as comparison to a baseline rule-based model using production traffic from a leading DSP platform.
Visual Search at Pinterest
Authors: Yushi Jing, David C. Liu, Dmitry Kislyuk, Andrew Zhai, Jiajing Xu, Jeff Donahue, Sarah Tavel
Venue: KDD
Year: 2015

We demonstrate that, with the availability of distributed computation platforms such as Amazon Web Services and open-source tools, it is possible for a small engineering team to build, launch and maintain a cost-effective, large-scale visual search system. We also demonstrate, through a comprehensive set of live experiments at Pinterest, that content recommendation powered by visual search improves user engagement. By sharing our implementation details and learnings from launching a commercial visual search engine from scratch, we hope visual search becomes more widely incorporated into today's commercial applications.
How Artificial Intelligence and Big Data Created Rocket Fuel: A Case Study
Authors: George John
Venue: KDD
Year: 2015

In 2008, Rocket Fuel's founders saw a gap in the digital advertising market. None of the existing players were building autonomous systems based on big data and artificial intelligence, but instead they were offering fairly simple technology and relying on human campaign managers to drive success. Five years later in 2013, Rocket Fuel had the best technology IPO of the year on NASDAQ, reported $240 million in revenue, and was ranked by accounting firm Deloitte as the #1 fastest-growing technology company in North America. Along the way we learned that it's okay to be bold in our expectations of what is possible with fully autonomous systems, we learned that mainstream customers will buy advanced technology if it's delivered in a familiar way, and we also learned that it's incredibly difficult to debug the complex "robot psychology" when a number of complex autonomous systems interact. We also had excellent luck and timing: as we were building the company, real-time ad impression-level auctions with machine-to-machine buying and selling became commonplace, and marketers became increasingly focused on delivering better results for their company and delivering better personalized and relevant digital experiences for their customers. The case study presentation will present a fast-paced overview of the business and technology context for Rocket Fuel at inception and at present, key learnings and decisions, and the road ahead.
Structured Hedging for Resource Allocations with Leverage
Authors: Nicholas Johnson, Arindam Banerjee
Venue: KDD
Year: 2015

Data mining algorithms for computing solutions to online resource allocation (ORA) problems have focused on budgeting resources currently in possession, e.g., investing in the stock market with cash on hand or assigning current employees to projects. In several settings, one can leverage borrowed resources with which tasks can be accomplished more efficiently and cheaply. Additionally, a variety of opposing allocation types or positions may be available with which one can hedge the allocation to alleviate risk from external changes. In this paper, we present a formulation for hedging online resource allocations with leverage and propose an efficient data mining algorithm (SHERAL). We pose the problem as a constrained online convex optimization problem. The key novel components of our formulation are (1) a loss function for general leveraging and opposing allocation positions and (2) a penalty function which hedges between structurally dependent allocation positions to control risk. We instantiate the problem in the context of portfolio selection and evaluate the effectiveness of the formulation through extensive experiments on five datasets in comparison with existing algorithms and several variants.
Accelerated Alternating Direction Method of Multipliers
Authors: Mojtaba Kadkhodaie, Konstantina Christakopoulou, Maziar Sanjabi, Arindam Banerjee
Venue: KDD
Year: 2015

Recent years have seen a revival of interest in the Alternating Direction Method of Multipliers (ADMM), due to its simplicity, versatility, and scalability. As a first order method for general convex problems, the rate of convergence of ADMM is O(1=k) [4, 25]. Given the scale of modern data mining problems, an algorithm with similar properties as ADMM but faster convergence rate can make a big difference in real world applications. In this paper, we introduce the Accelerated Alternating Direction Method of Multipliers (A2DM2) which solves problems with the same structure as ADMM. When the objective function is strongly convex, we show that A2DM2 has a O(1=k2) convergence rate. Unlike related existing literature on trying to accelerate ADMM, our analysis does not need any additional restricting assumptions. Through experiments, we show that A2DM2 converges faster than ADMM on a variety of problems. Further, we illustrate the versatility of the general A2DM2 on the problem of learning to rank, where it is shown to be competitive with the state-of-the-art specialized algorithms for the problem on both scalability and accuracy.
Optimizing Marketing Impact through Data Driven Decisioning
Authors: Anil Kamath
Venue: KDD
Year: 2015

Is my marketing working, how much is marketing helping the business and which campaigns and channels are effective? The key challenge for the Chief Marketing Officer is to tie investment in marketing to business results. In an increasingly complex marketing environment -- marketing organizations are being called upon to prove and optimize the return on marketing investment across different paid earned and owned marketing channels. In this talk we will show how data science and optimization techniques can be applied to cross channel data to attribute marketing effectiveness, drive media planning and real-time optimization of campaigns. Using terabytes of multi-channel data we answer questions such as what is the impact of different marketing campaigns on our business, how should we allocate our marketing dollars between different channels and when should I spend them and how do we execute our marketing campaigns based on the synergies of the different channels.
Scalable Blocking for Privacy Preserving Record Linkage
Authors: Alexandros Karakasidis, Georgia Koloniari, Vassilios S. Verykios
Venue: KDD
Year: 2015

When dealing with sensitive and personal user data, the process of record linkage raises privacy issues. Thus, privacy preserving record linkage has emerged with the goal of identifying matching records across multiple data sources while preserving the privacy of the individuals they describe. The task is very resource demanding, considering the abundance of available data, which, in addition, are often dirty. Blocking techniques are deployed prior to matching to prune out unlikely to match candidate records so as to reduce processing time. However, when scaling to large datasets, such methods often result in quality loss. To this end, we propose Multi-Sampling Transitive Closure for Encrypted Fields (MS-TCEF), a novel privacy preserving blocking technique based on the use of reference sets. Our new method effectively prunes records based on redundant assignments to blocks, providing better fault-tolerance and maintaining result quality while scaling linearly with respect to the dataset size. We provide a theoretical analysis on the method's complexity and show how it outperforms state-of-the-art privacy preserving blocking techniques with respect to both recall and processing cost.
Real Time Recommendations from Connoisseurs
Authors: Noriaki Kawamae
Venue: KDD
Year: 2015

The information overload problem remains serious for both consumers and service/content providers, leading to heightened demands for personalized recommendations. For recommender systems, updating user models is one of the most important tasks to keep up with their changing preferences and trends. Especially since new consumers and items emerge every day, which are promptly rated or reviewed, updating lists of items and rankings is crucial. In this paper, we set the goal of real time recommendation, to present these items instantly. Unlike standard collaborative filtering algorithms, our offline approach focuses only innovative consumers for these predictions, and then uses as few consumers as possible while keeping the same precision. Since innovators exist in many communities, and their opinions will spread and then stimulate their followers to adopt the same behavior, our approach is based on the hypothesis that a set of innova- tive consumers is sufficient to represent the most representative opinions in each community. Following this hypothesis, we derive a scalable method to detect both communities and innovative consumers in each community from a web- scale data from a behavior log. Our evaluation shows that our proposed weighting method can accurately sample given logs, and be compatible only with previous algorithms for real time recommendations.
Towards Decision Support and Goal Achievement: Identifying Action-Outcome Relationships From Social Media
Authors: Emre Kiciman, Matthew Richardson
Venue: KDD
Year: 2015

Every day, people take actions, trying to achieve their personal, high-order goals. People decide what actions to take based on their personal experience, knowledge and gut instinct. While this leads to positive outcomes for some people, many others do not have the necessary experience, knowledge and instinct to make good decisions. What if, rather than making decisions based solely on their own personal experience, people could take advantage of the reported experiences of hundreds of millions of other people?
On Estimating the Swapping Rate for Categorical Data
Authors: Daniel Kifer
Venue: KDD
Year: 2015

When analyzing data, it is important to account for all sources of noise. Public use datasets, such as those provided by the Census Bureau, often undergo additional perturbations designed to protect confidentiality. This source of noise is generally ignored in data analysis because crucial parameters and details about its implementation are withheld. In this paper, we consider the problem of inferring such parameters from the data. Specifically, we target data swapping, a perturbation technique commonly used by the U.S. Census Bureau and which, barring practical breakthroughs in disclosure control, will be used in the foreseeable future. The vanilla version of data swapping selects pairs of records and exchanges some of their attribute values. The number of swapped records is kept secret even though it is needed for data analysis and investigations into the confidentiality protection of individual records. We propose algorithms for estimating the number of swapped records in categorical data, even when the true data distribution is unknown.
TOPTRAC: Topical Trajectory Pattern Mining
Authors: Younghoon Kim, Jiawei Han, Cangzhou Yuan
Venue: KDD
Year: 2015

With the increasing use of GPS-enabled mobile phones, geo-tagging, which refers to adding GPS information to media such as micro-blogging messages or photos, has seen a surge in popularity recently. This enables us to not only browse information based on locations, but also discover patterns in the location-based behaviors of users. Many techniques have been developed to find the patterns of people's movements using GPS data, but latent topics in text messages posted with local contexts have not been utilized effectively. In this paper, we present a latent topic-based clustering algorithm to discover patterns in the trajectories of geo-tagged text messages. We propose a novel probabilistic model to capture the semantic regions where people post messages with a coherent topic as well as the patterns of movement between the semantic regions. Based on the model, we develop an efficient inference algorithm to calculate model parameters. By exploiting the estimated model, we next devise a clustering algorithm to find the significant movement patterns that appear frequently in data. Our experiments on real-life data sets show that the proposed algorithm finds diverse and interesting trajectory patterns and identifies the semantic regions in a finer granularity than the traditional geographical clustering methods.
Discovering Collective Narratives of Theme Parks from Large Collections of Visitors' Photo Streams
Authors: Gunhee Kim, Leonid Sigal
Venue: KDD
Year: 2015

We present an approach for generating pictorial storylines from large collections of online photo streams shared by visitors to theme parks (e.g. Disneyland), along with publicly available information such as visitor's maps. The story graph visualizes various events and activities recurring across visitors' photo sets, in the form of hierarchically branching narrative structure associated with attractions and districts in theme parks. We first estimate story elements of each photo stream, including the detection of faces and supporting objects, and attraction-based localization. We then create spatio-temporal story graphs via an inference of sparse time-varying directed graphs. Through quantitative evaluation and crowdsourcing-based user studies via Amazon Mechanical Turk, we show that the story graphs serve as a more convenient mid-level data structure to perform photo-based recommendation tasks than other alternatives. We also present storybook-like demo examples regarding exploration, recommendation, and temporal analysis, which may be most beneficial uses of the story graphs to visitors.