waashk/dblp huggingface dataset:
learning with cost intervals. existing cost-sensitive learning methods require that the unequal misclassification costs should be given as precise values. in many real-world applications, however, it is generally difficult to have a precise cost value since the user maybe only knows that one type of mistake is much more severe than another type, yet it is infeasible to give a precise description. in such situations, it is more meaningful to work with a cost interval instead of a precise cost value. in this paper we report the first study along this direction. we propose the cisvm method, a support vector machine, to work with cost interval information. experiments show that when there are only cost intervals available, cisvm is significantly superior to standard cost-sensitive svms using any of the minimal cost, mean cost and maximal cost to learn. moreover, considering that in some cases other information about costs can be obtained in addition to cost intervals, such as the distribution of costs, we propose a general approach codis for using the distribution information to help improve performance. experiments show that this approach can reduce 60% more risks than the standard cost-sensitive svm which assumes the expected cost is the true value.
diagnosing memory leaks using graph mining on heap dumps. memory leaks are caused by software programs that prevent the reclamation of memory that is no longer in use. they can cause significant slowdowns, exhaustion of available storage space and, eventually, application crashes. detecting memory leaks is challenging because real-world applications are built on multiple layers of software frameworks, making it difficult for a developer to know whether observed references to objects are legitimate or the cause of a leak. we present a graph mining solution to this problem wherein we analyze heap dumps to automatically identify subgraphs which could represent potential memory leak sources. although heap dumps are commonly analyzed in existing heap profiling tools, our work is the first to apply a graph grammar mining solution to this problem. unlike classical graph mining work, we show that it suffices to mine the dominator tree of the heap dump, which is significantly smaller than the underlying graph. our approach identifies not just leaking candidates and their structure, but also provides aggregate information about the access path to the leaks. we demonstrate several synthetic as well as real-world examples of heap dumps for which our approach provides more insight into the problem than state-of-the-art tools such as eclipse's mat.
discovering significant relaxed order-preserving submatrices. mining order-preserving submatrix (opsm) patterns has received much attention from researchers, since in many scientific applications, such as those involving gene expression data, it is natural to express the data in a matrix and also important to find the order-preserving submatrix patterns. however, most current work assumes the noise-free opsm model and thus is not practical in many real situations when sample contamination exists. in this paper, we propose a relaxed opsm model called ropsm. the ropsm model supports mining more reasonable noise-corrupted opsm patterns than another well-known model called aopc (approximate order-preserving cluster). while opsm mining is known to be an np-hard problem, mining ropsm patterns is even a harder problem. we propose a novel method called ropsm-growth to mine ropsm patterns. specifically, two pattern growing strategies, such as column-centric strategy and row-centric strategy, are presented, which are effective to grow the seed opsms into significant ropsms. an effective median-rank based method is also developed to discover the underlying true order of conditions involved in an ropsm pattern. our experiments on a biological dataset show that the ropsm model better captures the characteristics of noise in gene expression data matrix compared to the aopc model. importantly, we find that our approach is able to detect more quality biologically significant patterns with comparable efficiency with the counterparts of aopc. specifically, at least 26.6% (75 out of 282) of the patterns mined by our approach are strongly associated with more than 10 gene categories (high biological significance), which is 3 times better than that obtained from using the aopc approach.
dust: a generalized notion of similarity between uncertain time series. large-scale sensor deployments and an increased use of privacy-preserving transformations have led to an increasing interest in mining uncertain time series data. traditional distance measures such as euclidean distance or dynamic time warping are not always effective for analyzing uncertain time series data. recently, some measures have been proposed to account for uncertainty in time series data. however, we show in this paper that their applicability is limited. in specific, these approaches do not provide an intuitive way to compare two uncertain time series and do not easily accommodate multiple error functions. in this paper, we provide a theoretical framework that generalizes the notion of similarity between uncertain time series. secondly, we propose dust, a novel distance measure that accommodates uncertainty and degenerates to the euclidean distance when the distance is large compared to the error. we provide an extensive experimental validation of our approach for the following applications: classification, top-k motif search, and top-k nearest-neighbor queries.
mining program workflow from interleaved traces. successful software maintenance is becoming increasingly critical due to the increasing dependence of our society and economy on software systems. one key problem of software maintenance is the difficulty in understanding the evolving software systems. program workflows can help system operators and administrators to understand system behaviors and verify system executions so as to greatly facilitate system maintenance. in this paper, we propose an algorithm to automatically discover program workflows from event traces that record system events during system execution. different from existing workflow mining algorithms, our approach can construct concurrent workflows from traces of interleaved events. our workflow mining approach is a three-step coarse-to-fine algorithm. at first, we mine temporal dependencies for each pair of events. then, based on the mined pair-wise tem-poral dependencies, we construct a basic workflow model by a breadth-first path pruning algorithm. after that, we refine the workflow by verifying it with all training event traces. the re-finement algorithm tries to find out a workflow that can interpret all event traces with minimal state transitions and threads. the results of both simulation data and real program data show that our algorithm is highly effective.
combined regression and ranking. many real-world data mining tasks require the achievement of two distinct goals when applied to unseen data: first, to induce an accurate preference ranking, and second to give good regression performance. in this paper, we give an efficient and effective combined regression and ranking method (crr) that optimizes regression and ranking objectives simultaneously. we demonstrate the effectiveness of crr for both families of metrics on a range of large-scale tasks, including click prediction for online advertisements. results show that crr often achieves performance equivalent to the best of both ranking-only and regression-only approaches. in the case of rare events or skewed distributions, we also find that this combination can actually improve regression performance due to the addition of informative ranking constraints.
an efficient causal discovery algorithm for linear models. bayesian network learning algorithms have been widely used for causal discovery since the pioneer work [13,18]. among all existing algorithms, three-phase dependency analysis algorithm (tpda) [5] is the most efficient one in the sense that it has polynomial-time complexity. however, there are still some limitations to be improved. first, tpda depends on mutual information-based conditional independence (ci) tests, and so is not easy to be applied to continuous data. in addition, tpda uses two phases to get approximate skeletons of bayesian networks, which is not efficient in practice. in this paper, we propose a two-phase algorithm with partial correlation-based ci tests: the first phase of the algorithm constructs a markov random field from data, which provides a close approximation to the structure of the true bayesian network; at the second phase, the algorithm removes redundant edges according to ci tests to get the true bayesian network. we show that two-phase algorithm with partial correlation-based ci tests can deal with continuous data following arbitrary distributions rather than only gaussian distribution.
on community outliers and their efficient detection in information networks. linked or networked data are ubiquitous in many applications. examples include web data or hypertext documents connected via hyperlinks, social networks or user profiles connected via friend links, co-authorship and citation information, blog data, movie reviews and so on. in these datasets (called "information networks"), closely related objects that share the same properties or interests form a community. for example, a community in blogsphere could be users mostly interested in cell phone reviews and news. outlier detection in information networks can reveal important anomalous and interesting behaviors that are not obvious if community information is ignored. an example could be a low-income person being friends with many rich people even though his income is not anomalously low when considered over the entire population. this paper first introduces the concept of community outliers (interesting points or rising stars for a more positive sense), and then shows that well-known baseline approaches without considering links or community information cannot find these community outliers. we propose an efficient solution by modeling networked data as a mixture model composed of multiple normal communities and a set of randomly generated outliers. the probabilistic model characterizes both data and links simultaneously by defining their joint distribution based on hidden markov random fields (hmrf). maximizing the data likelihood and the posterior of the model gives the solution to the outlier inference problem. we apply the model on both synthetic data and dblp data sets, and the results demonstrate importance of this concept, as well as the effectiveness and efficiency of the proposed approach.
data mining to predict and prevent errors in health insurance claims processing. health insurance costs across the world have increased alarmingly in recent years. a major cause of this increase are payment errors made by the insurance companies while processing claims. these errors often result in extra administrative effort to re-process (or rework) the claim which accounts for up to 30% of the administrative staff in a typical health insurer. we describe a system that helps reduce these errors using machine learning techniques by predicting claims that will need to be reworked, generating explanations to help the auditors correct these claims, and experiment with feature selection, concept drift, and active learning to collect feedback from the auditors to improve over time. we describe our framework, problem formulation, evaluation metrics, and experimental results on claims data from a large us health insurer. we show that our system results in an order of magnitude better precision (hit rate) over existing approaches which is accurate enough to potentially result in over $15-25 million in savings for a typical insurer. we also describe interesting research problems in this domain as well as design choices made to make the system easily deployable across health insurance companies.
evolutionary hierarchical dirichlet processes for multiple correlated time-varying corpora. mining cluster evolution from multiple correlated time-varying text corpora is important in exploratory text analytics. in this paper, we propose an approach called evolutionary hierarchical dirichlet processes (evohdp) to discover interesting cluster evolution patterns from such text data. we formulate the evohdp as a series of hierarchical dirichlet processes~(hdp) by adding time dependencies to the adjacent epochs, and propose a cascaded gibbs sampling scheme to infer the model. this approach can discover different evolving patterns of clusters, including emergence, disappearance, evolution within a corpus and across different corpora. experiments over synthetic and real-world multiple correlated time-varying data sets illustrate the effectiveness of evohdp on discovering cluster evolution patterns.
latent aspect rating analysis on review text data: a rating regression approach. in this paper, we define and study a new opinionated text data analysis problem called latent aspect rating analysis (lara), which aims at analyzing opinions expressed about an entity in an online review at the level of topical aspects to discover each individual reviewer's latent opinion on each aspect as well as the relative emphasis on different aspects when forming the overall judgment of the entity. we propose a novel probabilistic rating regression model to solve this new text mining problem in a general way. empirical experiments on a hotel review data set show that the proposed latent rating regression model can effectively solve the problem of lara, and that the detailed analysis of opinions at the level of topical aspects enabled by the proposed model can support a wide range of application tasks, such as aspect opinion summarization, entity ranking based on aspect ratings, and analysis of reviewers rating behavior.
multi-label learning by exploiting label dependency. in multi-label learning, each training example is associated with a set of labels and the task is to predict the proper label set for the unseen example. due to the tremendous (exponential) number of possible label sets, the task of learning from multi-label examples is rather challenging. therefore, the key to successful multi-label learning is how to effectively exploit correlations between different labels to facilitate the learning process. in this paper, we propose to use a bayesian network structure to efficiently encode the conditional dependencies of the labels as well as the feature set, with the feature set as the common parent of all labels. to make it practical, we give an approximate yet efficient procedure to find such a network structure. with the help of this network, multi-label learning is decomposed into a series of single-label classification problems, where a classifier is constructed for each label by incorporating its parental labels as additional features. label sets of unseen examples are predicted recursively according to the label ordering given by the network. extensive experiments on a broad range of data sets validate the effectiveness of our approach against other well-established methods.
learning to combine discriminative classifiers: confidence based. much of research in data mining and machine learning has led to numerous practical applications. spam filtering, fraud detection, and user query-intent analysis has relied heavily on machine learned classifiers, and resulted in improvements in robust classification accuracy. combining multiple classifiers (a.k.a. ensemble learning) is a well studied and has been known to improve effectiveness of a classifier. to address two key challenges in ensemble learning-- (1) learning weights of individual classifiers and (2) the combination rule of their weighted responses, this paper proposes a novel ensemble classifier, enlr, that computes weights of responses from discriminative classifiers and combines their weighted responses to produce a single response for a test instance. the combination rule is based on aggregating weighted responses, where a weight of an individual classifier is inversely based on their respective variances around their responses. here, variance quantifies the uncertainty of the discriminative classifiers' parameters, which in turn depends on the training samples. as opposed to other ensemble methods where the weight of each individual classifier is learned as a part of parameter learning and thus the same weight is applied to all testing instances, our model is actively adjusted as individual classifiers become confident at its decision for a test instance. our empirical experiments on various data sets demonstrate that our combined classifier produces "effective" results when compared with a single classifier. our novel classifier shows statistically significant better accuracy when compared to well known ensemble methods -- bagging and adaboost. in addition to robust accuracy, our model is extremely efficient dealing with high volumes of training samples due to the independent learning paradigm among its multiple classifiers. it is simple to implement in a distributed computing environment such as hadoop.
training and testing of recommender systems on data missing not at random. users typically rate only a small fraction of all available items. we show that the absence of ratings carries useful information for improving the top-k hit rate concerning all items, a natural accuracy measure for recommendations. as to test recommender systems, we present two performance measures that can be estimated, under mild assumptions, without bias from data even when ratings are missing not at random (mnar). as to achieve optimal test results, we present appropriate surrogate objective functions for efficient training on mnar data. their main property is to account for all ratings - whether observed or missing in the data. concerning the top-k hit rate on test data, our experiments indicate dramatic improvements over even sophisticated methods that are optimized on observed ratings only.
fast online learning through offline initialization for time-sensitive recommendation. recommender problems with large and dynamic item pools are ubiquitous in web applications like content optimization, online advertising and web search. despite the availability of rich item meta-data, excess heterogeneity at the item level often requires inclusion of item-specific "factors" (or weights) in the model. however, since estimating item factors is computationally intensive, it poses a challenge for time-sensitive recommender problems where it is important to rapidly learn factors for new items (e.g., news articles, event updates, tweets) in an online fashion. in this paper, we propose a novel method called fobfm (fast online bilinear factor model) to learn item-specific factors quickly through online regression. the online regression for each item can be performed independently and hence the procedure is fast, scalable and easily parallelizable. however, the convergence of these independent regressions can be slow due to high dimensionality. the central idea of our approach is to use a large amount of historical data to initialize the online models based on offline features and learn linear projections that can effectively reduce the dimensionality. we estimate the rank of our linear projections by taking recourse to online model selection based on optimizing predictive likelihood. through extensive experiments, we show that our method significantly and uniformly outperforms other competitive methods and obtains relative lifts that are in the range of 10-15% in terms of predictive log-likelihood, 200-300% for a rank correlation metric on a proprietary my yahoo! dataset; it obtains 9% reduction in root mean squared error over the previously best method on a benchmark movielens dataset using a time-based train/test data split.
online multiscale dynamic topic models. we propose an online topic model for sequentially analyzing the time evolution of topics in document collections. topics naturally evolve with multiple timescales. for example, some words may be used consistently over one hundred years, while other words emerge and disappear over periods of a few days. thus, in the proposed model, current topic-specific distributions over words are assumed to be generated based on the multiscale word distributions of the previous epoch. considering both the long-timescale dependency as well as the short-timescale dependency yields a more robust model. we derive efficient online inference procedures based on a stochastic em algorithm, in which the model is sequentially updated using newly obtained data; this means that past data are not required to make the inference. we demonstrate the effectiveness of the proposed method in terms of predictive performance and computational efficiency by examining collections of real documents with timestamps.
an energy-efficient mobile recommender system. the increasing availability of large-scale location traces creates unprecedent opportunities to change the paradigm for knowledge discovery in transportation systems. a particularly promising area is to extract energy-efficient transportation patterns (green knowledge), which can be used as guidance for reducing inefficiencies in energy consumption of transportation sectors. however, extracting green knowledge from location traces is not a trivial task. conventional data analysis tools are usually not customized for handling the massive quantity, complex, dynamic, and distributed nature of location traces. to that end, in this paper, we provide a focused study of extracting energy-efficient transportation patterns from location traces. specifically, we have the initial focus on a sequence of mobile recommendations. as a case study, we develop a mobile recommender system which has the ability in recommending a sequence of pick-up points for taxi drivers or a sequence of potential parking positions. the goal of this mobile recommendation system is to maximize the probability of business success. along this line, we provide a potential travel distance (ptd) function for evaluating each candidate sequence. this ptd function possesses a monotone property which can be used to effectively prune the search space. based on this ptd function, we develop two algorithms, lcp and skyroute, for finding the recommended routes. finally, experimental results show that the proposed system can provide effective mobile sequential recommendation and the knowledge extracted from location traces can be used for coaching drivers and leading to the efficient use of energy.
why label when you can search?: alternatives to active learning for applying human resources to build classification models under extreme class imbalance. this paper analyses alternative techniques for deploying low-cost human resources for data acquisition for classifier induction in domains exhibiting extreme class imbalance - where traditional labeling strategies, such as active learning, can be ineffective. consider the problem of building classifiers to help brands control the content adjacent to their on-line advertisements. although frequent enough to worry advertisers, objectionable categories are rare in the distribution of impressions encountered by most on-line advertisers - so rare that traditional sampling techniques do not find enough positive examples to train effective models. an alternative way to deploy human resources for training-data acquisition is to have them "guide" the learning by searching explicitly for training examples of each class. we show that under extreme skew, even basic techniques for guided learning completely dominate smart (active) strategies for applying human resources to select cases for labeling. therefore, it is critical to consider the relative cost of search versus labeling, and we demonstrate the tradeoffs for different relative costs. we show that in cost/skew settings where the choice between search and active labeling is equivocal, a hybrid strategy can combine the benefits.