OpenRaiser/Intern-Atlas huggingface dataset:
Personalized search result diversification via structured learning
Authors: Shangsong Liang, Zhaochun Ren, Maarten de Rijke
Venue: KDD
Year: 2014

This paper is concerned with the problem of personalized diver-sification of search results, with the goal of enhancing the perfor-mance of both plain diversification and plain personalization al-gorithms. In previous work, the problem has mainly been tack-led by means of unsupervised learning. To further enhance the performance, we propose a supervised learning strategy. Specif-ically, we set up a structured learning framework for conducting supervised personalized diversification, in which we add features extracted directly from the tokens of documents and those utilized by unsupervised personalized diversification algorithms, and, im-portantly, those generated from our proposed user-interest latent Dirichlet topic model. Based on our proposed topic model whether a document can cater to a user’s interest can be estimated in our learning strategy. We also define two constraints in our structured learning framework to ensure that search results are both diversi-fied and consistent with a user’s interest. We conduct experiments on an open personalized diversification dataset and find that our su-pervised learning strategy outperforms unsupervised personalized diversification methods as well as other plain personalization and plain diversification methods.
Modeling human location data with mixtures of kernel densities
Authors: Moshe Lichman, Padhraic Smyth
Venue: KDD
Year: 2014

Location-based data is increasingly prevalent with the rapid increase and adoption of mobile devices. In this paper we address the problem of learning spatial density models, focusing specifically on individual-level data. Modeling and predicting a spatial distribution for an individual is a challenging problem given both (a) the typical sparsity of data at the individual level and (b) the heterogeneity of spatial mobility patterns across individuals. We investigate the application of kernel density estimation (KDE) to this problem using a mixture model approach that can interpolate between an individual's data and broader patterns in the population as a whole. The mixture-KDE approach is evaluated on two large geolocation/check-in data sets, from Twitter and Gowalla, with comparisons to non-KDE baselines, using both log-likelihood and detection of simulated identity theft as evaluation metrics. Our experimental results indicate that the mixture-KDE method provides a useful and accurate methodology for capturing and predicting individual-level spatial patterns in the presence of noisy and sparse data.
Unveiling clusters of events for alert and incident management in large-scale enterprise it
Authors: Derek Lin, Rashmi Raghu, Vivek Ramamurthy, Jin Yu, Regunathan Radhakrishnan, Joseph Fernandez
Venue: KDD
Year: 2014

Large enterprise IT (Information Technology) infrastructure components generate large volumes of alerts and incident tickets. These are manually screened, but it is otherwise difficult to extract information automatically from them to gain insights in order to improve operational efficiency. We propose a framework to cluster alerts and incident tickets based on the text in them, using unsupervised machine learning. This would be a step towards eliminating manual classification of the alerts and incidents, which is very labor intense and costly. Our framework can handle the semi-structured text in alerts generated by IT infrastructure components such as storage devices, network devices, servers etc., as well as the unstructured text in incident tickets created manually by operations support personnel. After text pre-processing and application of appropriate distance metrics, we apply different graph-theoretic approaches to cluster the alerts and incident tickets, based on their semi-structured and unstructured text respectively. For automated interpretation and read-ability on semi-structured text clusters, we propose a method to visualize clusters that preserves the structure and human-readability of the text data as compared to traditional word clouds where the text structure is not preserved; for unstructured text clusters, we find a simple way to define prototypes of clusters for easy interpretation. This framework for clustering and visualization will enable enterprises to prioritize the issues in their IT infrastructure and improve the reliability and availability of their services.
Proactive workflow modeling by stochastic processes with application to healthcare operation and management
Authors: Chuanren Liu, Yong Ge, Hui Xiong, Keli Xiao, Wei Geng, Matt Perkins
Venue: KDD
Year: 2014

Advances in real-time location system (RTLS) solutions have enabled us to collect massive amounts of fine-grained semantically rich location traces, which provide unparalleled opportunities for understanding human activities and discovering useful knowledge. This, in turn, delivers intelligence for real-time decision making in various fields, such as workflow management. Indeed, it is a new paradigm for workflow modeling by the knowledge discovery in location traces. To that end, in this paper, we provide a focused study of workflow modeling by the integrated analysis of indoor location traces in the hospital environment. In comparison with conventional workflow modeling based on passive workflow logs, one salient feature of our approach is that it can proactively unravel the workflow patterns hidden in the location traces, by automatically constructing the workflow states and estimating parameters describing the transition patterns of moving objects. Specifically, to determine a meaningful granularity for the model, the workflow states are first constructed as regions associated with specific healthcare activities. Then, we transform the original indoor location traces to the sequences of workflow states and model the workflow transition patterns by finite state machines. Furthermore, we leverage the correlations in the location traces between related types of medical devices to reinforce the modeling performance and enable more applications. The results show that the proposed framework can not only model the workflow patterns effectively, but also have managerial applications in workflow monitoring, auditing, and inspection of workflow compliance, which are critical in the healthcare industry.
Online chinese restaurant process
Authors: Chien-Liang Liu, Tsung-Hsun Tsai, Chia-Hoang Lee
Venue: KDD
Year: 2014

Processing large volumes of streaming data in near-real-time is becoming increasingly important as the Internet, sensor networks and network traffic grow. Online machine learning is a typical means of dealing with streaming data, since it allows the classification model to learn one instance of data at a time. Although many online learning methods have been developed since the development of the Perceptron algorithm, existing online methods assume that the number of classes is available in advance of classification process. However, this assumption is unrealistic for large scale or streaming data sets. This work proposes an online Chinese restaurant process (CRP) algorithm, which is an online and nonparametric algorithm, to tackle this problem. This work proposes a relaxing function as part of the prior and updates the parameters with the likelihood function in terms of the consistency between the true label information and predicted result. This work presents two Gibbs sampling algorithms to perform posterior inference. In the experiments, the online CRP is applied to three massive data sets, and compared with several online learning and batch learning algorithms. One of the data sets is obtained from Wikipedia, which comprises approximately two million documents. The experimental results reveal that the proposed online CRP performs well and efficiently on massive data sets. Finally, this work proposes two methods to update the hyperparameter $\alpha$ of the online CRP. The first method is based on the posterior distribution of $\alpha$, and the second exploits the property of online learning, namely adapting to change, to adjust $\alpha$ dynamically.
An efficient algorithm for weak hierarchical lasso
Authors: Yashu Liu, Jie Wang, Jieping Ye
Venue: KDD
Year: 2014

Linear regression is a widely used tool in data mining and machine learning. In many applications, fitting a regression model with only linear effects may not be sufficient for predictive or explanatory purposes. One strategy which has recently received increasing attention in statistics is to include feature interactions to capture the nonlinearity in the regression model. Such model has been applied successfully in many biomedical applications. One major challenge in the use of such model is that the data dimensionality is significantly higher than the original data, resulting in the small sample size large dimension problem. Recently, weak hierarchical Lasso, a sparse interaction regression model, is proposed that produces sparse and hierarchical structured estimator by exploiting the Lasso penalty and a set of hierarchical constraints. However, the hierarchical constraints make it a non-convex problem and the existing method finds the solution of its convex relaxation, which needs additional conditions to guarantee the hierarchical structure. In this paper, we propose to directly solve the non-convex weak hierarchical Lasso by making use of the GIST (General Iterative Shrinkage and Thresholding) optimization framework which has been shown to be efficient for solving non-convex sparse formulations. The key step in GIST is to compute a sequence of proximal operators. One of our key technical contributions is to show that the proximal operator associated with the non-convex weak hierarchical Lasso admits a closed form solution. However, a naive approach for solving each subproblem of the proximal operator leads to a quadratic time complexity, which is not desirable for large size problems. To this end, we further develop an efficient algorithm for computing the subproblems with a linearithmic time complexity. We have conducted extensive experiments on both synthetic and real data sets. Results show that our proposed algorithm is much more efficient and effective than its convex relaxation.
Temporal skeletonization on sequential data: patterns, categorization, and visualization
Authors: Chuanren Liu, Kai Zhang, Hui Xiong, Geoff Jiang, Qiang Yang
Venue: KDD
Year: 2014

Sequential pattern analysis targets on finding statistically relevant temporal structures where the values are delivered in a sequence. With the growing complexity of real-world dynamic scenarios, more and more symbols are often needed to encode a meaningful sequence. This is so-called 'curse of cardinality', which can impose significant challenges to the design of sequential analysis methods in terms of computational efficiency and practical use. Indeed, given the overwhelming scale and the heterogeneous nature of the sequential data, new visions and strategies are needed to face the challenges. To this end, in this paper, we propose a 'temporal skeletonization' approach to proactively reduce the representation of sequences to uncover significant, hidden temporal structures. The key idea is to summarize the temporal correlations in an undirected graph. Then, the 'skeleton' of the graph serves as a higher granularity on which hidden temporal patterns are more likely to be identified. In the meantime, the embedding topology of the graph allows us to translate the rich temporal content into a metric space. This opens up new possibilities to explore, quantify, and visualize sequential data. Our approach has shown to greatly alleviate the curse of cardinality in challenging tasks of sequential pattern mining and clustering. Evaluation on a Business-to-Business (B2B) marketing application demonstrates that our approach can effectively discover critical buying paths from noisy customer event data.
FAST-PPR: scaling personalized pagerank estimation for large graphs
Authors: Peter Lofgren, Siddhartha Banerjee, Ashish Goel, Seshadhri Comandur
Venue: KDD
Year: 2014

We propose a new algorithm, FAST-PPR, for computing personalized PageRank: given start node s and target node t in a directed graph, and given a threshold δ, it computes the Personalized PageRank π_s(t) from s to t, guaranteeing that the relative error is small as long πs(t) > δ. Existing algorithms for this problem have a running-time of Ω(1/δ in comparison, FAST-PPR has a provable average running-time guarantee of O(√d/δ) (where d is the average in-degree of the graph). This is a significant improvement, since δ is often O(1/n) (where n is the number of nodes) for applications. We also complement the algorithm with an Ω(1/√δ) lower bound for PageRank estimation, showing that the dependence on δ cannot be improved. We perform a detailed empirical study on numerous massive graphs, showing that FAST-PPR dramatically outperforms existing algorithms. For example, on the 2010 Twitter graph with 1.5 billion edges, for target nodes sampled by popularity, FAST-PPR has a 20 factor speedup over the state of the art. Furthermore, an enhanced version of FAST-PPR has a 160 factor speedup on the Twitter graph, and is at least 20 times faster on all our candidate graphs.
Optimal recommendations under attraction, aversion, and social influence
Authors: Wei Lu, Stratis Ioannidis, Smriti Bhagat, Laks V. S. Lakshmanan
Venue: KDD
Year: 2014

People's interests are dynamically evolving, often affected by external factors such as trends promoted by the media or adopted by their friends. In this work, we model interest evolution through dynamic interest cascades: we consider a scenario where a user's interests may be affected by (a) the interests of other users in her social circle, as well as (b) suggestions she receives from a recommender system. In the latter case, we model user reactions through either attraction or aversion towards past suggestions. We study this interest evolution process, and the utility accrued by recommendations, as a function of the system's recommendation strategy. We show that, in steady state, the optimal strategy can be computed as the solution of a semi-definite program (SDP). Using datasets of user ratings, we provide evidence for the existence of aversion and attraction in real-life data, and show that our optimal strategy can lead to significantly improved recommendations over systems that ignore aversion and attraction.
Exponential random graph estimation under differential privacy
Authors: Wentian Lu, Gerome Miklau
Venue: KDD
Year: 2014

The effective analysis of social networks and graph-structured data is often limited by the privacy concerns of individuals whose data make up these networks. Differential privacy offers individuals a rigorous and appealing guarantee of privacy. But while differentially private algorithms for computing basic graph properties have been proposed, most graph modeling tasks common in the data mining community cannot yet be carried out privately.
Computational epidemiology
Authors: Madhav V. Marathe, Anil Kumar S. Vullikanti
Venue: KDD
Year: 2014

As recent pandemics such as SARS and the Swine Flu outbreak have shown, diseases spread very fast in today's interconnected world, making public health an important research area. Some of the basic questions are: How can an outbreak be contained before it becomes an epidemic, and what disease surveillance strategies should be implemented? These problems have been studied traditionally using differential equation methods, which are amenable to analysis and closed form solutions. However, these models are based on complete mixing assumptions, which do not hold for realistic populations, thereby limiting their utility.
Shallow semantic parsing of product offering titles (for better automatic hyperlink insertion)
Authors: Gabor Melli
Venue: KDD
Year: 2014

With billions of database-generated pages on the Web where consumers can readily add priced product offerings to their virtual shopping cart, several opportunities will become possible once we can automatically recognize what exactly is being offered for sale on each page. We present a case study of a deployed data-driven system that first chunks individual titles into semantically classified sub-segments, and then uses this information to improve a hyperlink insertion service.
Bugbears or legitimate threats?: (social) scientists' criticisms of machine learning?
Authors: Sendhil Mullainathan
Venue: KDD
Year: 2014

Social scientists increasingly criticize the use of machine learning techniques to understand human behavior. Criticisms include: (1) They are atheoretical and hence of limited scientific value; (2) They do not address causality and are hence of limited policy value; and (3) They are uninterpretable and hence of limited generalizability value (outside contexts very narrowly similar to the training dataset). These criticisms, I argue, miss the enormous opportunity offered by ML techniques to fundamentally improve the practice of empirical social science. Yet each criticism does contain a grain of truth and overcoming them will require innovations to existing methodologies. Some of these innovations are being developed today and some are yet to be tackled. I will in this talk sketch (1) what these innovations look like or should look like; (2) why they are needed; and (3) the technical challenges they raise. I will illustrate my points using a set of applications that range from financial markets to social policy problems to computational models of basic psychological processes. This talk describes joint work with Jon Kleinberg and individual projects with Himabindu Lakkaraju, Jure Leskovec, Jens Ludwig, Anuj Shah, Chenhao Tan, Mike Yeomans and Tom Zimmerman.
Bringing data science to the speakers of every language
Authors: Robert Munro
Venue: KDD
Year: 2014

Speakers of more than 5,000 languages have access to internet and communication technologies. The majority of phones, tablets and computers now ship with language-enabled capabilities like speech-recognition and intelligent auto-correction, and people increasingly interact with data-intensive cloud-based language technologies like search-engines and spam-filters. For both personal and large-scale technologies, the service quality drops or disappears entirely outside of a handful of languages. Speakers of low-resource languages correlate with lower access to healthcare, education and higher vulnerability to disasters. Serving the broadest possible range of languages is crucial to ensuring equitable participation in the global information economy.
Inside the atoms: ranking on a network of networks
Authors: Jingchao Ni, Hanghang Tong, Wei Fan, Xiang Zhang
Venue: KDD
Year: 2014

Networks are prevalent and have posed many fascinating research questions. How can we spot similar users, e.g., virtual identical twins, in Cleveland for a New Yorker? Given a query disease, how can we prioritize its candidate genes by incorporating the tissue-specific protein interaction networks of those similar diseases? In most, if not all, of the existing network ranking methods, the nodes are the ranking objects with the finest granularity. In this paper, we propose a new network data model, a Network of Networks (NoN), where each node of the main network itself can be further represented as another (domain-specific) network. This new data model enables to compare the nodes in a broader context and rank them at a finer granularity. Moreover, such an NoN model enables much more efficient search when the ranking targets reside in a certain domain-specific network. We formulate ranking on NoN as a regularized optimization problem; propose efficient algorithms and provide theoretical analysis, such as optimality, convergence, complexity and equivalence. Extensive experimental evaluations demonstrate the effectiveness and the efficiency of our methods.
LUDIA: an aggregate-constrained low-rank reconstruction algorithm to leverage publicly released health data
Authors: Yubin Park, Joydeep Ghosh
Venue: KDD
Year: 2014

In the past few years, the government and other agencies have publicly released a prodigious amount of data that can be potentially mined to benefit the society at large. However, data such as health records are typically only provided at aggregated levels (e.g. per State, per Hospital Referral Region, etc.) to protect privacy. Unfortunately aggregation can severely diminish the utility of such data when modeling or analysis is desired at a per-individual basis. So, not surprisingly, despite the increasing abundance of aggregate data, there have been very few successful attempts in exploiting them for individual-level analyses. This paper introduces LUDIA, a novel low-rank approximation algorithm that utilizes aggregation constraints in addition to auxiliary information in order to estimate or "reconstruct" the original individual-level values from aggregate data. If the reconstructed data are statistically similar to the original individual-level data, off-the-shelf individual-level models can be readily and reliably applied for subsequent predictive or descriptive analytics. LUDIA is more robust to nonlinear estimates and random effects than other reconstruction algorithms. It solves a Sylvester equation and leverages multi-level (also known as hierarchical or mixed-effect) modeling approaches efficiently. A novel graphical model is also introduced to provide a probabilistic viewpoint of LUDIA. Experimental results using a Texas inpatient dataset show that individual-level data can be reasonably reconstructed from county-, hospital-, and zip code-level aggregate data. Several factors affecting the reconstruction quality are discussed, along with the implications of this work for current aggregation guidelines.
Predictive modeling in practice: a case study from sprint
Authors: Tracy De Poalo, Jeremy Howard
Venue: KDD
Year: 2014

It's not often we get to peer into the details of how big corporates use predictive modeling in practice. In this talk, Sprint's Head of Predictive Modeling, Tracey De Poalo, will talk about the process she developed using SAS and logistic regression to build a wide range of models. Jeremy Howard will discuss his experience as a consultant at Sprint comparing R and random forests to the existing process, and will show the pros and cons of each approach.
LaSEWeb: automating search strategies over semi-structured web data
Authors: Oleksandr Polozov, Sumit Gulwani
Venue: KDD
Year: 2014

We show how to programmatically model processes that humans use when extracting answers to queries (e.g., "Who invented typewriter?", "List of Washington national parks") from semi-structured Web pages returned by a search engine. This modeling enables various applications including automating repetitive search tasks, and helping search engine developers design micro-segments of factoid questions. We describe the design and implementation of a domain-specific language that enables extracting data from a webpage based on its structure, visual layout, and linguistic patterns. We also describe an algorithm to rank multiple answers extracted from multiple webpages. On 100,000+ queries (across 7 micro-segments) obtained from Bing logs, our system LaSEWeb answered queries with an average recall of 71%. Also, the desired answer(s) were present in top-3 suggestions for 95%+ cases.