waashk/dblp huggingface dataset:
from mining the web to inventing the new sciences underlying the internet. this is an abstract of the invited keynote presentation to be presented at kdd-07. as the internet continues to change the way we live, find information, communicate, and do business, it has also been taking on a dramatically increasing role in marketing and advertising. unlike any prior mass medium, the internet is a unique medium when it comes to interactivity and offers an ability to target and program messaging at the individual level. coupled with its uniqueness in the richness of the data that is available for measurability, in the variety of ways to utilize the data, and in the great dependence of effective marketing on applications that are heavily data-driven, makes data mining and statistical data analysis, modeling, and reporting an essential mission-critical part of running the on-line business. however, because of its novelty and the scale of data sets involved, few companies have figured out how to properly make use of this data. in this talk, i will review some of the challenges and opportunities in the utilization of data to drive this new generation of marketing systems. i will provide several examples of how data is utilized in critical ways to drive some of these capabilities. the discussion will be framed with the more general framework of grand challenges for data mining: pragmatic and technical. i will conclude this presentation witha consideration of the larger issues surrounding the internet as a technology that is ubiquitous in our lives, yet one where very little is understood, at the scientific level, in defining and understanding many of the basics the internet enables: community, personalization, and the new microeconomics of the web. this leads to an overview of the new yahoo! research organization and its aims: inventing the new sciences underlying what we do on the internet, focusing on areas that have received little attention in the traditional academic circles. some illustrative examples will be reviewed to make the ultimate goals more concrete.
a scalable modular convex solver for regularized risk minimization. a wide variety of machine learning problems can be described as minimizing a regularized risk functional, with different algorithms using different notions of risk and different regularizers. examples include linear support vector machines (svms), logistic regression, conditional random fields (crfs), and lasso amongst others. this paper describes the theory and implementation of a highly scalable and modular convex solver which solves all these estimation problems. it can be parallelized on a cluster of workstations, allows for data-locality, and can deal with regularizers such as l1 and l2 penalties. at present, our solver implements 20 different estimation problems, can be easily extended, scales to millions of observations, and is up to 10 times faster than specialized solvers for many applications. the open source code is freely available as part of the elefant toolbox.
xrules: an effective structural classifier for xml data. xml documents have recently become ubiquitous because of their varied applicability in a number of applications. classification is an important problem in the data mining domain, but current classification methods for xml documents use ir-based methods in which each document is treated as a bag of words. such techniques ignore a significant amount of information hidden inside the documents. in this paper we discuss the problem of rule based classification of xml data by using frequent discriminatory substructures within xml documents. such a technique is more capable of finding the classification characteristics of documents. in addition, the technique can also be extended to cost sensitive classification. we show the effectiveness of the method with respect to other classifiers. we note that the methodology discussed in this paper is applicable to any kind of semi-structured data.
graphscope: parameter-free mining of large time-evolving graphs. how can we find communities in dynamic networks of socialinteractions, such as who calls whom, who emails whom, or who sells to whom? how can we spot discontinuity time-points in such streams of graphs, in an on-line, any-time fashion? we propose graphscope, that addresses both problems, using information theoretic principles. contrary to the majority of earlier methods, it needs no user-defined parameters. moreover, it is designed to operate on large graphs, in a streaming fashion. we demonstrate the efficiency and effectiveness of our graphscope on real datasets from several diverse domains. in all cases it produces meaningful time-evolving patterns that agree with human intuition.
fast vertical mining using diffsets. a number of vertical mining algorithms have been proposed recently for association mining, which have shown to be very effective and usually outperform horizontal approaches. the main advantage of the vertical format is support for fast frequency counting via intersection operations on transaction ids (tids) and automatic pruning of irrelevant data. the main problem with these approaches is when intermediate results of vertical tid lists become too large for memory, thus affecting the algorithm scalability.in this paper we present a novel vertical data representation called diffset, that only keeps track of differences in the tids of a candidate pattern from its generating frequent patterns. we show that diffsets drastically cut down the size of memory required to store intermediate results. we show how diffsets, when incorporated into previous vertical mining methods, increase the performance significantly.
reasoning about sets using redescription mining. redescription mining is a newly introduced data mining problem that seeks to find subsets of data that afford multiple definitions. it can be viewed as a generalization of association rule mining, from finding implications to equivalences; as a form of conceptual clustering, where the goal is to identify clusters that afford dual characterizations; and as a form of constructive induction, to build features based on given descriptors that mutually reinforce each other. in this paper, we present the use of redescription mining as an important tool to reason about a collection of sets, especially their overlaps, similarities, and differences. we outline algorithms to mine all minimal (non-redundant) redescriptions underlying a dataset using notions of minimal generators of closed itemsets. we also show the use of these algorithms in an interactive context, supporting constraint-based exploration and querying. specifically, we showcase a bioinformatics application that empowers the biologist to define a vocabulary of sets underlying a domain of genes and to reason about these sets, yielding significant biological insight.
influence and correlation in social networks. in many online social systems, social ties between users play an important role in dictating their behavior. one of the ways this can happen is through social influence, the phenomenon that the actions of a user can induce his/her friends to behave in a similar way. in systems where social influence exists, ideas, modes of behavior, or new technologies can diffuse through the network like an epidemic. therefore, identifying and understanding social influence is of tremendous interest from both analysis and design points of view. this is a difficult task in general, since there are factors such as homophily or unobserved confounding variables that can induce statistical correlation between the actions of friends in a social network. distinguishing influence from these is essentially the problem of distinguishing correlation from causality, a notoriously hard statistical problem. in this paper we study this problem systematically. we define fairly general models that replicate the aforementioned sources of social correlation. we then propose two simple tests that can identify influence as a source of social correlation when the time series of user actions is available. we give a theoretical justification of one of the tests by proving that with high probability it succeeds in ruling out influence in a rather general model of social correlation. we also simulate our tests on a number of examples designed by randomly generating actions of nodes on a real social network (from flickr) according to one of several models. simulation results confirm that our test performs well on these data. finally, we apply them to real tagging data on flickr, exhibiting that while there is significant social correlation in tagging behavior on this system, this correlation cannot be attributed to social influence.
event summarization for system management. in system management applications, an overwhelming amount of data are generated and collected in the form of temporal events. while mining temporal event data to discover interesting and frequent patterns has obtained rapidly increasing research efforts, users of the applications are overwhelmed by the mining results. the extracted patterns are generally of large volume and hard to interpret, they may be of no emphasis, intricate and meaningless to non-experts, even to domain experts. while traditional research efforts focus on finding interesting patterns, in this paper, we take a novel approach called event summarization towards the understanding of the seemingly chaotic temporal data. event summarization aims at providing a concise interpretation of the seemingly chaotic data, so that domain experts may take actions upon the summarized models. event summarization decomposes the temporal information into many independent subsets and finds well fitted models to describe each subset.
active exploration for learning rankings from clickthrough data. we address the task of learning rankings of documents from search enginelogs of user behavior. previous work on this problem has relied onpassively collected clickthrough data. in contrast, we show that anactive exploration strategy can provide data that leads to much fasterlearning. specifically, we develop a bayesian approach for selectingrankings to present users so that interactions result in more informativetraining data. our results using the trec-10 web corpus, as well assynthetic data, demonstrate that a directed exploration strategy quicklyleads to users being presented improved rankings in an online learningsetting. we find that active exploration substantially outperformspassive observation and random exploration.
making generative classifiers robust to selection bias. this paper presents approaches to semi-supervised learning when the labeled training data and test data are differently distributed. specifically, the samples selected for labeling are a biased subset of some general distribution and the test set consists of samples drawn from either that general distribution or the distribution of the unlabeled samples. an example of the former appears in loan application approval, where samples with repay/default labels exist only for approved applicants and the goal is to model the repay/default behavior of all applicants. an example of the latter appears in spam filtering, in which the labeled samples can be out-dated due to the cost of labeling email by hand, but an unlabeled set of up-to-date emails exists and the goal is to build a filter to sort new incoming email.most approaches to overcoming such bias in the literature rely on the assumption that samples are selected for labeling depending only on the features, not the labels, a case in which provably correct methods exist. the missing labels are said to be "missing at random" (mar). in real applications, however, the selection bias can be more severe. when the mar conditional independence assumption is not satisfied and missing labels are said to be "missing not at random" (mnar), and no learning method is provably always correct.we present a generative classifier, the shifted mixture model (smm), with separate representations of the distributions of the labeled samples and the unlabeled samples. the smm makes no conditional independence assumptions and can model distributions of semi-labeled data sets with arbitrary bias in the labeling. we present a learning method based on the expectation maximization (em) algorithm that, while not always able to overcome arbitrary labeling bias, learns smms with higher test-set accuracy in real-world data sets (with mnar bias) than existing learning methods that are proven to overcome mar bias.
detecting anomalous records in categorical datasets. we consider the problem of detecting anomalies in high aritycategorical datasets. in most applications, anomalies are defined as datapoints that are "abnormal". quite often we have access to data which consists mostly of normal records, a long with a small percentage of unlabelled anomalous records. we are interested in the problem of unsupervised anomaly detection, where we use the unlabelled data for training, and detect records that do not follow the definition of normality. a standard approach is to create a model of normal data, and compare test records against it. a probabilistic approach builds a likelihood model from the training data. records are tested for anomalies based on the complete record likelihood given the probability model. for categorical attributes, bayes nets give a standard representation of the likelihood. while this approach is good at finding outliers in the dataset, it often tends to detect records with attribute values that are rare. sometimes, just detecting rare values of an attribute is not desired and such outliers are not considered as anomalies in that context. we present an alternative definition of anomalies, and propose an approach of comparing against marginal distribution of attribute subsets. we show that this is a more meaningful way of detecting anomalies, and has a better performance over semi-synthetic as well as real world datasets.
permu-pattern: discovery of mutable permutation patterns with proximity constraint. pattern discovery in sequences is an important problem in many applications, especially in computational biology and text mining. however, due to the noisy nature of data, the traditional sequential pattern model may fail to reflect the underlying characteristics of sequence data in these applications. there are two challenges: first, the mutation noise exists in the data, and therefore symbols may be misrepresented by other symbols; secondly, the order of symbols in sequences could be permutated. to address the above problems, in this paper we propose a new sequential pattern model called mutable permutation patterns. since the apriori property does not hold for our permutation pattern model, a novel permu-pattern algorithm is devised to mine frequent mutable permutation patterns from sequence databases. a reachability property is identified to prune the candidate set. last but not least, we apply the permutation pattern model to a real genome dataset to discover gene clusters, which shows the effectiveness of the model. a large amount of synthetic data is also utilized to demonstrate the efficiency of the permu-pattern algorithm.
privacy-preservation for gradient descent methods. gradient descent is a widely used paradigm for solving many optimization problems. stochastic gradient descent performs a series of iterations to minimize a target function in order to reach a local minimum. in machine learning or data mining, this function corresponds to a decision model that is to be discovered. the gradient descent paradigm underlies many commonly used techniques in data mining and machine learning, such as neural networks, bayesian networks, genetic algorithms, and simulated annealing. to the best of our knowledge, there has not been any work that extends the notion of privacy preservation or secure multi-party computation to gradient-descent-based techniques. in this paper, we propose a preliminary approach to enable privacy preservation in gradient descent methods in general and demonstrate its feasibility in specific gradient descent methods.
imds: intelligent malware detection system. the proliferation of malware has presented a serious threat to the security of computer systems. traditional signature-based anti-virus systems fail to detect polymorphic and new, previously unseen malicious executables. in this paper, resting on the analysis of windows api execution sequences called by pe files, we develop the intelligent malware detection system (imds) using objective-oriented association (ooa) mining based classification. imds is an integrated system consisting of three major modules: pe parser, ooa rule generator, and rule based classifier. an ooa_fast_fp-growth algorithm is adapted to efficiently generate ooa rules for classification. a comprehensive experimental study on a large collection of pe files obtained from the anti-virus laboratory of king-soft corporation is performed to compare various malware detection approaches. promising experimental results demonstrate that the accuracy and efficiency of our imds system out perform popular anti-virus software such as norton antivirus and mcafee virusscan, as well as previous data mining based detection systems which employed naive bayes, support vector machine (svm) and decision tree techniques.
mining complex power networks for blackout prevention. following the recent devastating blackouts in north america, uk and italy, blackout prevention has attracted significant attention, though it is known as a notoriously difficult task. to prevent the blackout, it is essential to accurately predict the instable status of power network components. in the large-scale power network however, existing analysis tools fail to perform accurate and in-time prediction of component instability, because of the sophisticated structure of real-world power networks and the huge amount of system variables to be analyzed. to prevent the blackout, we need an accurate and efficient method that (a) can discover interesting features and patterns relevant to the blackout, from the highly complex structure and ten thousands of system variables of a power network, and (b) can give accurate and fast prediction of system instability whenever required, so that the network operator can take necessary actions in time. in this paper, we report our tool developed for power network instability prediction. the proposed method consists of two major stages. in the first stage,a novel type of patterns namely local correlation network pattern (lcnp) is mined from the structure and system variables of the power network. correlation rules, which are useful for the network operator to locate potentially instable components, can be further generated from the lcnp. in the second stage, a kernel based network classification method is developed to predict the system instability. by testing on a real world power network (the new england system), we demonstrate that the proposed tool is effective in predicting system instability and thus highly useful for blackout prevention.
learning subspace kernels for classification. kernel methods have been applied successfully in many data mining tasks. subspace kernel learning was recently proposed to discover an effective low-dimensional subspace of a kernel feature space for improved classification. in this paper, we propose to construct a subspace kernel using the hilbert-schmidt independence criterion (hsic). we show that the optimal subspace kernel can be obtained efficiently by solving an eigenvalue problem. one limitation of the existing subspace kernel learning formulations is that the kernel learning and classification are independent and the subspace kernel may not be optimally adapted for classification. to overcome this limitation, we propose a joint optimization framework, in which we learn the subspace kernel and subsequent classifiers simultaneously. in addition, we propose a novel learning formulation that extracts an uncorrelated subspace kernel to reduce the redundant information in a subspace kernel. following the idea from multiple kernel learning, we extend the proposed formulations to the case when multiple kernels are available and need to be combined. we show that the integration of subspace kernels can be formulated as a semidefinite program (sdp) which is computationally expensive. to improve the efficiency of the sdp formulation, we propose an equivalent semi-infinite linear program (silp) formulation which can be solved efficiently by the column generation technique. experimental results on a collection of benchmark data sets demonstrate the effectiveness of the proposed algorithms.
fast best-effort pattern matching in large attributed graphs. we focus on large graphs where nodes have attributes, such as a social network where the nodes are labelled with each person's job title. in such a setting, we want to find subgraphs that match a user query pattern. for example, a "star" query would be, "find a ceo who has strong interactions with a manager, a lawyer,and an accountant, or another structure as close to that as possible". similarly, a "loop" query could help spot a money laundering ring. traditional sql-based methods, as well as more recent graph indexing methods, will return no answer when an exact match does not exist. this is the first main feature of our method. it can find exact-, as well as near-matches, and it will present them to the user in our proposed "goodness" order. for example, our method tolerates indirect paths between, say, the "ceo" and the "accountant" of the above sample query, when direct paths don't exist. its second feature is scalability. in general, if the query has nq nodes and the data graph has n nodes, the problem needs polynomial time complexity o(n n q), which is prohibitive. our g-ray ("graph x-ray") method finds high-quality subgraphs in time linear on the size of the data graph. experimental results on the dlbp author-publication graph (with 356k nodes and 1.9m edges) illustrate both the effectiveness and scalability of our approach. the results agree with our intuition, and the speed is excellent. it takes 4 seconds on average fora 4-node query on the dblp graph.
model-shared subspace boosting for multi-label classification. typical approaches to the multi-label classification problem require learning an independent classifier for every label from all the examples and features. this can become a computational bottleneck for sizeable datasets with a large label space. in this paper, we propose an efficient and effective multi-label learning algorithm called model-shared subspace boosting (mssboost) as an attempt to reduce the information redundancy in the learning process. this algorithm automatically finds, shares and combines a number of base models across multiple labels, where each model is learned from random feature subspace and boots trap data samples. the decision functions for each label are jointly estimated and thus a small number of shared subspace models can support the entire label space. our experimental results on both synthetic data and real multimedia collections have demonstrated that the proposed algorithm can achieve better classification performance than the non-ensemble baselineclassifiers with a significant speedup in the learning and prediction processes. it can also use a smaller number of base models to achieve the same classification performance as its non-model-shared counterpart.