OpenRaiser/Intern-Atlas huggingface dataset:
Online Controlled Experiments: Lessons from Running A/B/n Tests for 12 Years
Authors: Ron Kohavi
Venue: KDD
Year: 2015

The Internet provides developers of connected software, including web sites, applications, and devices, an unprecedented opportunity to accelerate innovation by evaluating ideas quickly and accurately using trustworthy controlled experiments (e.g., A/B tests and their generalizations). From front-end user-interface changes to backend recommendation systems and relevance algorithms, from search engines (e.g., Google, Microsoft's Bing, Yahoo) to retailers (e.g., Amazon, eBay, Netflix, Etsy) to social networking services (e.g., Facebook, LinkedIn, Twitter) to Travel services (e.g., Expedia, Airbnb, Booking.com) to many startups, online controlled experiments are now utilized to make data-driven decisions at a wide range of companies. While the theory of a controlled experiment is simple, and dates back to Sir Ronald A. Fisher's experiments at the Rothamsted Agricultural Experimental Station in England in the 1920s, the deployment and mining of online controlled experiments at scale (e.g., hundreds of experiments run every day at Bing) and deployment of online controlled experiments across dozens of web sites and applications has taught us many lessons. We provide an introduction, share real examples, key lessons, and cultural challenges.
MOOCS: What Have We Learned?
Authors: Daphne Koller
Venue: KDD
Year: 2015

It has been nearly four years since the first MOOCs (massive open online courses) were offered by Stanford University. MOOCs are now offered to tens of millions of learners worldwide, by hundreds of top universities. MOOCs are no longer an experiment - the learning, reach, and value they offer are now a reality. I will show how MOOCs provide opportunities for open-ended projects, intercultural learner interactions, and collaborative learning. I will discuss some of data that we are collecting from MOOCs, and what we are learning from these data about both courses and learners. Finally, I will discuss both data and examples of the kind of transformative impact that can be derived from providing millions of people with access to the world's best education.
Unified and Contrasting Cuts in Multiple Graphs: Application to Medical Imaging Segmentation
Authors: Chia-Tung Kuo, Xiang Wang, Peter B. Walker, Owen T. Carmichael, Jieping Ye, Ian Davidson
Venue: KDD
Year: 2015

The analysis of data represented as graphs is common having wide scale applications from social networks to medical imaging. A popular analysis is to cut the graph so that the disjoint subgraphs can represent communities (for social network) or background and foreground cognitive activity (for medical imaging). An emerging setting is when multiple data sets (graphs) exist which opens up the opportunity for many new questions. In this paper we study two such questions: i) For a collection of graphs find a single cut that is good for all the graphs and ii) For two collections of graphs find a single cut that is good for one collection but poor for the other. We show that existing formulations of multiview, consensus and alternative clustering cannot address these questions and instead we provide novel formulations in the spectral clustering framework. We evaluate our approaches on functional magnetic resonance imaging (fMRI) data to address questions such as: "What common cognitive network does this group of individuals have?" and "What are the differences in the cognitive networks for these two groups?" We obtain useful results without the need for strong domain knowledge.
Probabilistic Graphical Models of Dyslexia
Authors: Yair Lakretz, Gal Chechik, Naama Friedmann, Michal Rosen-Zvi
Venue: KDD
Year: 2015

Reading is a complex cognitive process, errors in which may assume diverse forms. In this study, introducing a novel approach, we use two families of probabilistic graphical models to analyze patterns of reading errors made by dyslexic people: an LDA-based model and two Naëve Bayes models which differ by their assumptions about the generation process of reading errors. The models are trained on a large corpus of reading errors. Results show that a Naëve Bayes model achieves highest accuracy compared to labels given by clinicians (AUC = 0.801 ± 0.05), thus providing the first automated and objective diagnosis tool for dyslexia which is solely based on reading errors data. Results also show that the LDA-based model best captures patterns of reading errors and could therefore contribute to the understanding of dyslexia and to future improvement of the diagnostic procedure. Finally, we draw on our results to shed light on a theoretical debate about the definition and heterogeneity of dyslexia. Our results support a model assuming multiple dyslexia subtypes, that of a heterogeneous view of dyslexia.
Reducing the Unlabeled Sample Complexity of Semi-Supervised Multi-View Learning
Authors: Chao Lan, Jun Huan
Venue: KDD
Year: 2015

In semi-supervised multi-view learning, unlabeled sample complexity (u.s.c.) specifies the size of unlabeled training sample that guarantees a desired learning error. In this paper, we improve the state-of-art u.s.c. from O(1/ε) to O(log 1/ε) for small error ε, under mild conditions. To obtain the improved result, as a primary step we prove a connection between the generalization error of a classifier and its incompatibility, which measures the fitness between the classifier and the sample distribution. We then prove that with a sufficiently large unlabeled sample, one is able to find classifiers with low incompatibility. Combining the two observations, we manage to prove a probably approximately correct (PAC) style learning bound for semi-supervised multi-view learning. We empirically verified our theory by designing two proof-of-concept multi-view learning algorithms, one based on active view sensing and the other based on online co-regularization, with real-world data sets.
Generic and Scalable Framework for Automated Time-series Anomaly Detection
Authors: Nikolay Laptev, Saeed Amizadeh, Ian Flint
Venue: KDD
Year: 2015

This paper introduces a generic and scalable framework for automated anomaly detection on large scale time-series data. Early detection of anomalies plays a key role in maintaining consistency of person's data and protects corporations against malicious attackers. Current state of the art anomaly detection approaches suffer from scalability, use-case restrictions, difficulty of use and a large number of false positives. Our system at Yahoo, EGADS, uses a collection of anomaly detection and forecasting models with an anomaly filtering layer for accurate and scalable anomaly detection on time-series. We compare our approach against other anomaly detection systems on real and synthetic data with varying time-series characteristics. We found that our framework allows for 50-60% improvement in precision and recall for a variety of use-cases. Both the data and the framework are being open-sourced. The open-sourcing of the data, in particular, represents the first of its kind effort to establish the standard benchmark for anomaly detection.
Leveraging Knowledge Bases for Contextual Entity Exploration
Authors: Joonseok Lee, Ariel Fuxman, Bo Zhao, Yuanhua Lv
Venue: KDD
Year: 2015

Users today are constantly switching back and forth from applications where they consume or create content (such as e-books and productivity suites like Microsoft Office and Google Docs) to search engines where they satisfy their information needs. Unfortunately, though, this leads to a suboptimal user experience as the search engine lacks any knowledge about the content that the user is authoring or consuming in the application. As a result, productivity suites are starting to incorporate features that let the user "explore while they work". Existing work in the literature that can be applied to this problem takes a standard bag-of-words information retrieval approach, which consists of automatically creating a query that includes not only the target phrase or entity chosen by the user but also relevant terms from the context. While these approaches have been successful, they are inherently limited to returning results (documents) that have a syntactic match with the keywords in the query. We argue that the limitations of these approaches can be overcome by leveraging semantic signals from a knowledge graph built from knowledge bases such as Wikipedia. We present a system called Lewis for retrieving contextually relevant entity results leveraging a knowledge graph, and perform a large scale crowdsourcing experiment in the context of an e-reader scenario, which shows that Lewis can outperform the state-of-the-art contextual entity recommendation systems by more than 20% in terms of the MAP score.
Maximum Likelihood Postprocessing for Differential Privacy under Consistency Constraints
Authors: Jaewoo Lee, Yue Wang, Daniel Kifer
Venue: KDD
Year: 2015

When analyzing data that has been perturbed for privacy reasons, one is often concerned about its usefulness. Recent research on differential privacy has shown that the accuracy of many data queries can be improved by post-processing the perturbed data to ensure consistency constraints that are known to hold for the original data. Most prior work converted this post-processing step into a least squares minimization problem with customized efficient solutions. While improving accuracy, this approach ignored the noise distribution in the perturbed data.
0-Bit Consistent Weighted Sampling
Authors: Ping Li
Venue: KDD
Year: 2015

We develop 0-bit consistent weighted sampling (CWS) for efficiently estimating min-max kernel, which is a generalization of the resemblance kernel originally designed for binary data. Because the estimator of 0-bit CWS constitutes a positive definite kernel, this method can be naturally applied to large-scale data mining problems. Basically, if we feed the sampled data from 0-bit CWS to a highly efficient linear classifier (e.g., linear SVM), we effectively (and approximately) train a nonlinear classifier based on the min-max kernel. The accuracy improves as we increase the sample size.
Predicting Voice Elicited Emotions
Authors: Ying Li, Jose D. Contreras, Luis J. Salazar
Venue: KDD
Year: 2015

We present the research, and product development and deployment, of Voice Analyzer' by Jobaline Inc. This is a patent pending technology that analyzes voice data and predicts human emotions elicited by the paralinguistic elements of a voice. Human voice characteristics, such as tone, complement the verbal communication. In several contexts of communication, "how" things are said is just as important as "what" is being said. This paper provides an overview of our deployed system, the raw data, the data processing steps, and the prediction algorithms we experimented with. A case study is included where, given a voice clip, our model predicts the degree in which a listener will find the voice "engaging". Our prediction results were verified through independent market research with 75% in agreement on how an average listener would feel. One application of Jobaline Voice Analyzer technology is for assisting companies to hire workers in the service industry where customers' emotional response to workers' voice may affect the service outcome. Jobaline Voice Analyzer is deployed in production as a product offer to our clients to help them identify workers who will better engage with their customers. We will also share some discoveries and lessons learned.
MASCOT: Memory-efficient and Accurate Sampling for Counting Local Triangles in Graph Streams
Authors: Yongsub Lim, U Kang
Venue: KDD
Year: 2015

How can we estimate local triangle counts accurately in a graph stream without storing the whole graph? The local triangle counting which counts triangles for each node in a graph is a very important problem with wide applications in social network analysis, anomaly detection, web mining, etc.
Social Media Anomaly Detection: Challenges and Solutions
Authors: Yan Liu, Sanjay Chawla
Venue: KDD
Year: 2015

Anomaly detection is of critical importance to prevent malicious activities such as bullying, terrorist attack planning, and fraud information dissemination. With the recent popularity of social media, new types of anomalous behaviors arise, causing concerns from various parties. While a large body of work haven been dedicated to traditional anomaly detection problems, we observe a surge of research interests in the new realm of social media anomaly detection. In this tutorial, we survey existing work on social media anomaly detection, focusing on the new anomalous phenomena in social media and most recent techniques to detect those special types of anomalies. We aim to provide a general overview of the problem domain, common formulations, existing methodologies and future directions.
Spectral Ensemble Clustering
Authors: Hongfu Liu, Tongliang Liu, Junjie Wu, Dacheng Tao, Yun Fu
Venue: KDD
Year: 2015

Ensemble clustering, also known as consensus clustering, is emerging as a promising solution for multi-source and/or heterogeneous data clustering. The co-association matrix based method, which redefines the ensemble clustering problem as a classical graph partition problem, is a landmark method in this area. Nevertheless, the relatively high time and space complexity preclude it from real-life large-scale data clustering. We therefore propose SEC, an efficient Spectral Ensemble Clustering method based on co-association matrix. We show that SEC has theoretical equivalence to weighted K-means clustering and results in vastly reduced algorithmic complexity. We then derive the latent consensus function of SEC, which to our best knowledge is among the first to bridge co-association matrix based method to the methods with explicit object functions. The robustness and generalizability of SEC are then investigated to prove the superiority of SEC in theory. We finally extend SEC to meet the challenge rising from incomplete basic partitions, based on which a scheme for big data clustering can be formed. Experimental results on various real-world data sets demonstrate that SEC is an effective and efficient competitor to some state-of-the-art ensemble clustering methods and is also suitable for big data clustering.
Influence at Scale: Distributed Computation of Complex Contagion in Networks
Authors: Brendan Lucier, Joel Oren, Yaron Singer
Venue: KDD
Year: 2015

We consider the task of evaluating the spread of influence in large networks in the well-studied independent cascade model. We describe a novel sampling approach that can be used to design scalable algorithms with provable performance guarantees. These algorithms can be implemented in distributed computation frameworks such as MapReduce. We complement these results with a lower bound on the query complexity of influence estimation in this model. We validate the performance of these algorithms through experiments that demonstrate the efficacy of our methods and related heuristics.
Dimensionality Reduction Via Graph Structure Learning
Authors: Qi Mao, Li Wang, Steve Goodison, Yijun Sun
Venue: KDD
Year: 2015

We present a new dimensionality reduction setting for a large family of real-world problems. Unlike traditional methods, the new setting aims to explicitly represent and learn an intrinsic structure from data in a high-dimensional space, which can greatly facilitate data visualization and scientific discovery in downstream analysis. We propose a new dimensionality-reduction framework that involves the learning of a mapping function that projects data points in the original high-dimensional space to latent points in a low-dimensional space that are then used directly to construct a graph. Local geometric information of the projected data is naturally captured by the constructed graph. As a showcase, we develop a new method to obtain a discriminative and compact feature representation for clustering problems. In contrast to assumptions used in traditional clustering methods, we assume that centers of clusters should be close to each other if they are connected in a learned graph, and other cluster centers should be distant. Extensive experiments are performed that demonstrate that the proposed method is able to obtain discriminative feature representations yielding superior clustering performance, and correctly recover the intrinsic structures of various real-world datasets including curves, hierarchies and a cancer progression path.
Robust Treecode Approximation for Kernel Machines
Authors: William B. March, Bo Xiao, Sameer Tharakan, Chenhan D. Yu, George Biros
Venue: KDD
Year: 2015

Since exact evaluation of a kernel matrix requires O(N2) work, scalable learning algorithms using kernels must approximate the kernel matrix. This approximation must be robust to the kernel parameters, for example the bandwidth for the Gaussian kernel. We consider two approximation methods: Nystrom and an algebraic treecode developed in our group. Nystrom methods construct a global low-rank approximation of the kernel matrix. Treecodes approximate just the off-diagonal blocks, typically using a hierarchical decomposition.
Discovery of Glaucoma Progressive Patterns Using Hierarchical MDL-Based Clustering
Authors: Shigeru Maya, Kai Morino, Hiroshi Murata, Ryo Asaoka, Kenji Yamanishi
Venue: KDD
Year: 2015

In this paper, we propose a method to cluster the spacial patterns of the visual field in glaucoma patients to analyze the progression patterns of glaucoma. The degree of progression in the visual field of glaucoma patients can be divided into several regions by straight line boundaries, we call this specific structure Direct Product Structure in this paper. Since we can observe the direct product structure in the visual fields, we propose a bottom-up hierarchical clustering method to embed this structure into the clustering structure. In our method, according to the minimum description length (MDL) principle, we select the best cluster division so that the total code length required for encoding the data as well as the clustering structure is minimum. We can thereby select the clusters that are robust to the noise in the position of the direct product structure for clustering. We demonstrate the effectiveness of our method using an artificial dataset and a real glaucoma dataset. Our proposed method performed better than existing methods for both datasets. For the real glaucoma dataset in particular, our method discovered the characteristic progressive patterns of glaucoma as specific features of clusters. These patterns agree with clinical knowledge. Furthermore, we show that our clusters can be applied to improve the accuracy of predicting glaucoma progression. Thus, our clusters contain rich information of glaucoma, and hence can contribute to further development in glaucoma research.
Distributed Personalization
Authors: Xu Miao, Chun-Te Chu, Lijun Tang, Yitong Zhou, Joel Young, Anmol Bhasin
Venue: KDD
Year: 2015

Personalization is a long-standing problem in data mining and machine learning. Companies make personalized product recommendations to millions of users every second. In addition to the recommendation problem, with the emerging of personal devices, many conventional problems, e.g., recognition, need to be personalized as well. Moreover, as the number of users grows huge, solving personalization becomes quite challenging. In this paper, we formalize the generic personalization problem as an optimization problem. We propose several ADMM algorithms to solve this problem in a distributed way including a new Asynchronous ADMM that removes all synchronous barriers to maximize the training throughput. We provide a mathematical analysis to show that the proposed Asynchronous ADMM algorithm holds a linear convergence rate which is the best to our knowledge. The distributed personalization allows training to be performed in either a cluster or even on a user's device. This can improve the privacy protection as no personal data is uploaded, while personal models can still be shared with each other. We apply this approach to two industry problems, \emph{Facial Expression Recognition} and \emph{Job Recommendation}. Experiments demonstrate more than 30\% relative error reduction on both problems. Asynchronous ADMM allows faster training for problems with millions of users since it eliminates all network I/O waiting time to maximize the cluster CPU throughput. Experiments demonstrate 4 times faster than original synchronous ADMM algorithm.
Data-Driven Activity Prediction: Algorithms, Evaluation Methodology, and Applications
Authors: Bryan David Minor, Janardhan Rao Doppa, Diane J. Cook
Venue: KDD
Year: 2015

We consider a novel problem called Activity Prediction, where the goal is to predict the future activity occurrence times from sensor data. In this paper, we make three main contributions. First, we formulate and solve the activity prediction problem in the framework of imitation learning and reduce it to simple regression learning problem. This approach allows us to leverage powerful regression learners; is easy to implement; and can reason about the relational and temporal structure of the problem with negligible computational overhead. Second, we present several evaluation metrics to evaluate a given activity predictor, and discuss their pros and cons in the context of real-world applications. Third, we evaluate our approach using real sensor data collected from 24 smart home testbeds. We also embed the learned predictor into a mobile device based activity prompter and evaluate the app on multiple participants living in smart homes. Our experimental results indicate that the activity predictor learned with our approach performs better than the baseline methods, and offers a simple and reliable approach to prediction of activities from sensor data.
Voltage Correlations in Smart Meter Data
Authors: Rajendu Mitra, Ramachandra Kota, Sambaran Bandyopadhyay, Vijay Arya, Brian Sullivan, Richard Mueller, Heather Storey, Gerard Labut
Venue: KDD
Year: 2015

The connectivity model of a power distribution network can easily become outdated due to system changes occurring in the field. Maintaining and sustaining an accurate connectivity model is a key challenge for distribution utilities worldwide. This work shows that voltage time series measurements collected from customer smart meters exhibit correlations that are consistent with the hierarchical structure of the distribution network. These correlations may be leveraged to cluster customers based on common ancestry and help verify and correct an existing connectivity model. Additionally, customers may be clustered in combination with voltage data from circuit metering points, spatial data from the geographical information system, and any existing but partially accurate connectivity model to infer customer to transformer and phase connectivity relationships with high accuracy.
Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling
Authors: Michael Mitzenmacher, Jakub Pachocki, Richard Peng, Charalampos E. Tsourakakis, Shen Chen Xu
Venue: KDD
Year: 2015

Extracting dense subgraphs from large graphs is a key primitive in a variety of graph mining applications, ranging from mining social networks and the Web graph to bioinformatics [41]. In this paper we focus on a family of poly-time solvable formulations, known as the k-clique densest subgraph problem (k-Clique-DSP) [57]. When k=2, the problem becomes the well-known densest subgraph problem (DSP) [22, 31, 33, 39]. Our main contribution is a sampling scheme that gives densest subgraph sparsifier, yielding a randomized algorithm that produces high-quality approximations while providing significant speedups and improved space complexity. We also extend this family of formulations to bipartite graphs by introducing the (p,q)-biclique densest subgraph problem ((p,q)-Biclique-DSP), and devise an exact algorithm that can treat both clique and biclique densities in a unified way.