waashk/dblp huggingface dataset:
semi-supervised classification with hybrid generative/discriminative methods. we compare two recently proposed frameworks for combining generative and discriminative probabilistic classifiers and apply them to semi-supervised classification. in both cases we explore the tradeoff between maximizing a discriminative likelihood of labeled data and a generative likelihood of labeled and unlabeled data. while prominent semi-supervised learning methods assume low density regions between classes or are subject to generative modeling assumptions, we conjecture that hybrid generative/discriminative methods allow semi-supervised learning in the presence of strongly overlapping classes and reduce the risk of modeling structure in the unlabeled data that is irrelevant for the specific classification task of interest. we apply both hybrid approaches within naively structured markov random field models and provide a thorough empirical comparison with two well-known semi-supervised learning methods on six text classification tasks. a semi-supervised hybrid generative/discriminative method provides the best accuracy in 75% of the experiments, and the multi-conditional learning hybrid approach achieves the highest overall mean accuracy across all tasks.
relational data pre-processing techniques for improved securities fraud detection. commercial datasets are often large, relational, and dynamic. they contain many records of people, places, things, events and their interactions over time. such datasets are rarely structured appropriately for knowledge discovery, and they often contain variables whose meanings change across different subsets of the data. we describe how these challenges were addressed in a collaborative analysis project undertaken by the university of massachusetts amherst and the national association of securities dealers(nasd). we describe several methods for data pre-processing that we applied to transform a large, dynamic, and relational dataset describing nearly the entirety of the u.s. securities industry, and we show how these methods made the dataset suitable for learning statistical relational models. to better utilize social structure, we first applied known consolidation and link formation techniques to associate individuals with branch office locations. in addition, we developed an innovative technique to infer professional associations by exploiting dynamic employment histories. finally, we applied normalization techniques to create a suitable class label that adjusts for spatial, temporal, and other heterogeneity within the data. we show how these pre-processing techniques combine to provide the necessary foundation for learning high-performing statistical models of fraudulent activity.
finding tribes: identifying close-knit individuals from employment patterns. we present a family of algorithms to uncover tribes-groups of individuals who share unusual sequences of affiliations. while much work inferring community structure describes large-scale trends, we instead search for small groups of tightly linked individuals who behave anomalously with respect to those trends. we apply the algorithms to a large temporal and relational data set consisting of millions of employment records from the national association of securities dealers. the resulting tribes contain individuals at higher risk for fraud, are homogenous with respect to risk scores, and are geographically mobile, all at significant levels compared to random or to other sets of individuals who share affiliations.
time-dependent event hierarchy construction. in this paper, an algorithm called time driven documents-partition (tdd) is proposed to construct an event hierarchy in a text corpus based on a given query. specifically, assume that a query contains only one feature - election. election is directly related to the events such as 2006 us midterm elections campaign, 2004 us presidential election campaign and 2004 taiwan presidential election campaign, where these events may further be divided into several smaller events (e.g. the 2006 us midterm elections campaign can be broken down into events such as campaign for vote, election results and the resignation of donald h. rumsfeld). as such, an event hierarchy is resulted. our proposed algorithm, tdd, tackles the problem by three major steps: (1)identify the features that are related to the query according to both the timestamps and the contents of the documents. the features identified are regarded as bursty features; (2) extract the documents that are highly related to the bursty features based on time; (3) partition the extracted documents to form events and organize them in a hierarchicalstructure. to the best of our knowledge, there is little works targeting for constructing a feature-based event hierarchy for a text corpus. practically, event hierarchies can assist us to efficiently locate our target information in a text corpus easily. again, assume that election is used for a query. without an event hierarchy, it is very difficult to identify what are the major events related to it, when do these events happened, as well as the features and the news articles that are related to each of these events. we have archived two-year news articles to evaluate the feasibility of tdd. the encouraging results indicated that tdd is practically sound and highly effective.
fast logistic regression for text categorization with variable-length n-grams. a common representation used in text categorization is the bag of words model (aka. unigram model). learning with this particular representation involves typically some preprocessing, e.g. stopwords-removal, stemming. this results in one explicit tokenization of the corpus. in this work, we introduce a logistic regression approach where learning involves automatic tokenization. this allows us to weaken the a-priori required knowledge about the corpus and results in a tokenization with variable-length (word or character) n-grams as basic tokens. we accomplish this by solving logistic regression using gradient ascent in the space of all ngrams. we show that this can be done very efficiently using a branch and bound approach which chooses the maximum gradient ascent direction projected onto a single dimension (i.e., candidate feature). although the space is very large, our method allows us to investigate variable-length n-gram learning. we demonstrate the efficiency of our approach compared to state-of-the-art classifiers used for text categorization such as cyclic coordinate descent logistic regression and support vector machines.
constraint-driven clustering. clustering methods can be either data-driven or need-driven. data-driven methods intend to discover the true structure of the underlying data while need-driven methods aims at organizing the true structure to meet certain application requirements. thus, need-driven (e.g. constrained) clustering is able to find more useful and actionable clusters in applications such as energy aware sensor networks, privacy preservation, and market segmentation. however, the existing methods of constrained clustering require users to provide the number of clusters, which is often unknown in advance, but has a crucial impact on the clustering result. in this paper, we argue that a more natural way to generate actionable clusters is to let the application-specific constraints decide the number of clusters. for this purpose, we introduce a novel cluster model, constraint-driven clustering (cdc), which finds an a priori unspecified number of compact clusters that satisfy all user-provided constraints. two general types of constraints are considered, i.e. minimum significance constraints and minimum variance constraints, as well as combinations of these two types. we prove the np-hardness of the cdc problem with different constraints. we propose a novel dynamic data structure, the cd-tree, which organizes data points in leaf nodes such that each leaf node approximately satisfies the cdc constraints and minimizes the objective function. based on cd-trees, we develop an efficient algorithm to solve the new clustering problem. our experimental evaluation on synthetic and real datasets demonstrates the quality of the generated clusters and the scalability of the algorithm.
trajectory pattern mining. the increasing pervasiveness of location-acquisition technologies (gps, gsm networks, etc.) is leading to the collection of large spatio-temporal datasets and to the opportunity of discovering usable knowledge about movement behaviour, which fosters novel applications and services. in this paper, we move towards this direction and develop an extension of the sequential pattern mining paradigm that analyzes the trajectories of moving objects. we introduce trajectory patterns as concise descriptions of frequent behaviours, in terms of both space (i.e., the regions of space visited during movements) and time (i.e., the duration of movements). in this setting, we provide a general formal statement of the novel mining problem and then study several different instantiations of different complexity. the various approaches are then empirically evaluated over real data and synthetic benchmarks, comparing their strengths and weaknesses.
the future of image search. there are billions of images on the internet. today, searching for a desired image is largely based on textual data such as filename or associated text on the web page; not much use is made of the image content. there are good reasons for this. the field of content-based image retrieval, which emerged during the 1990s, focused primarily on color and texture cues. these were easier to model than shape, but they turned out to be much less useful than originally hoped. i shall review some of the recent developments in the field of visual object recognition in the computer vision community that offer greater promise. much better image features for characterizing shape, advances in machine learning techniques, and the availability of large amounts of training data lie at the heart of these approaches.
cleaning disguised missing data: a heuristic approach. in some applications such as filling in a customer information form on the web, some missing values may not be explicitly represented as such, but instead appear as potentially valid data values. such missing values are known as disguised missing data, which may impair the quality of data analysis severely, such as causing significant biases and misleading results in hypothesis tests, correlation analysis and regressions. the very limited previous studies on cleaning disguised missing data use outlier mining and distribution anomaly detection. they highly rely on domain background knowledge in specific applications and may not work well for the cases where the disguise values are inliers. to tackle the problem of cleaning disguised missing data, in this paper, we first model the distribution of disguised missing data, and propose the embedded unbiased sample heuristic. then, we develop an effective and efficient method to identify the frequently used disguise values which capture the major body of the disguised missing data. our method does not require any domain background knowledge to find the suspicious disguise values. we report an empirical evaluation using real data sets, which shows that our method is effective - the frequently used disguise values found by our method match the values identified by the domain experts nicely. our method is also efficient and scalable for processing large data sets.
dynamic hybrid clustering of bioinformatics by incorporating text mining and citation analysis. to unravel the concept structure and dynamics of the bioinformatics field, we analyze a set of 7401 publications from the web of science and medline databases, publication years 1981-2004. for delineating this complex, interdisciplinary field, a novel bibliometric retrieval strategy is used. given that the performance of unsupervised clustering and classification of scientific publications is significantly improved by deeply merging textual contents with the structure of the citation graph, we proceed with a hybrid clustering method based on fisher's inverse chi-square. the optimal number of clusters is determined by a compound semiautomatic strategy comprising a combination of distance-based and stability-based methods. we also investigate the relationship between number of latent semantic indexing factors, number of clusters, and clustering performance. the hits and pagerank algorithms are used to determine representative publications in each cluster. next, we develop a methodology for dynamic hybrid clustering of evolving bibliographic data sets. the same clustering methodology is applied to consecutive periods defined by time windows on the set, and in a subsequent phase chains are formed by matching and tracking clusters through time. term networks for the eleven resulting cluster chains present the cognitive structure of the field. finally, we provide a view on how much attention the bioinformatics community has devoted to the different subfields through time.
detecting research topics via the correlation between graphs and texts. in this paper we address the problem of detecting topics in large-scale linked document collections. recently, topic detection has become a very active area of research due to its utility for information navigation, trend analysis, and high-level description of data. we present a unique approach that uses the correlation between the distribution of a term that represents a topic and the link distribution in the citation graph where the nodes are limited to the documents containing the term. this tight coupling between term and graph analysis is distinguished from other approaches such as those that focus on language models. we develop a topic score measure for each term, using the likelihood ratio of binary hypotheses based on a probabilistic description of graph connectivity. our approach is based on the intuition that if a term is relevant to a topic, the documents containing the term have denser connectivity than a random selection of documents. we extend our algorithm to detect a topic represented by a set of terms, using the intuition that if the co-occurrence of terms represents a new topic, the citation pattern should exhibit the synergistic effect. we test our algorithm on two electronic research literature collections,arxiv and citeseer.our evaluation shows that the approach is effective and reveals some novel aspects of topic detection.
extracting shared subspace for multi-label classification. multi-label problems arise in various domains such as multi-topic document categorization and protein function prediction. one natural way to deal with such problems is to construct a binary classifier for each label, resulting in a set of independent binary classification problems. since the multiple labels share the same input space, and the semantics conveyed by different labels are usually correlated, it is essential to exploit the correlation information contained in different labels. in this paper, we consider a general framework for extracting shared structures in multi-label classification. in this framework, a common subspace is assumed to be shared among multiple labels. we show that the optimal solution to the proposed formulation can be obtained by solving a generalized eigenvalue problem, though the problem is non-convex. for high-dimensional problems, direct computation of the solution is expensive, and we develop an efficient algorithm for this case. one appealing feature of the proposed framework is that it includes several well-known algorithms as special cases, thus elucidating their intrinsic relationships. we have conducted extensive experiments on eleven multi-topic web page categorization tasks, and results demonstrate the effectiveness of the proposed formulation in comparison with several representative algorithms.
correlation search in graph databases. correlation mining has gained great success in many application domains for its ability to capture the underlying dependency between objects. however, the research of correlation mining from graph databases is still lacking despite the fact that graph data, especially in various scientific domains, proliferate in recent years. in this paper, we propose a new problem of correlation mining from graph databases, called correlated graph search (cgs). cgs adopts pearson's correlation coefficient as a correlation measure to take into consideration the occurrence distributions of graphs. however, the problem poses significant challenges, since every subgraph of a graph in the database is a candidate but the number of subgraphs is exponential. we derive two necessary conditions which set bounds on the occurrence probability of a candidate in the database. with this result, we design an efficient algorithm that operates on a much smaller projected database and thus we are able to obtain a significantly smaller set of candidates. to further improve the efficiency, we develop three heuristic rules and apply them on the candidate set to further reduce the search space. our extensive experiments demonstrate the effectiveness of our method on candidate reduction. the results also justify the efficiency of our algorithm in mining correlations from large real and synthetic datasets.
practical guide to controlled experiments on the web: listen to your customers not to the hippo. the web provides an unprecedented opportunity to evaluate ideas quickly using controlled experiments, also called randomized experiments (single factor or factorial designs), a/b tests (and their generalizations), split tests, control/treatment tests, and parallel flights. controlled experiments embody the best scientific design for establishing a causal relationship between changes and their influence on user-observable behavior. we provide a practical guide to conducting online experiments, where end-users can help guide the development of features. our experience indicates that significant learning and return-on-investment (roi) are seen when development teams listen to their customers, not to the highest paid person's opinion (hippo). we provide several examples of controlled experiments with surprising results. we review the important ingredients of running controlled experiments, and discuss their limitations (both technical and organizational). we focus on several areas that are critical to experimentation, including statistical power, sample size, and techniques for variance reduction. we describe common architectures for experimentation systems and analyze their advantages and disadvantages. we evaluate randomization and hashing techniques, which we show are not as simple in practice as is often assumed. controlled experiments typically generate large amounts of data, which can be analyzed using data mining techniques to gain deeper understanding of the factors influencing the outcome of interest, leading to new hypotheses and creating a virtuous cycle of improvements. organizations that embrace controlled experiments with clear evaluation criteria can evolve their systems with automated optimizations and real-time analyses. based on our extensive practical experience with multiple systems and organizations, we share key lessons that will help practitioners in running trustworthy controlled experiments.
raising the baseline for high-precision text classifiers. many important application areas of text classifiers demand high precision andit is common to compare prospective solutions to the performance of naive bayes. this baseline is usually easy to improve upon, but in this work we demonstrate that appropriate document representation can make out performing this classifier much more challenging. most importantly, we provide a link between naive bayes and the logarithmic opinion pooling of the mixture-of-experts framework, which dictates a particular type of document length normalization. motivated by document-specific feature selection we propose monotonic constraints on document term weighting, which is shown as an effective method of fine-tuning document representation. the discussion is supported by experiments using three large email corpora corresponding to the problem of spam detection, where high precision is of particular importance.
a fast algorithm for finding frequent episodes in event streams. frequent episode discovery is a popular framework for mining data available as a long sequence of events. an episode is essentially a short ordered sequence of event types and the frequency of an episode is some suitable measure of how often the episode occurs in the data sequence. recently,we proposed a new frequency measure for episodes based on the notion of non-overlapped occurrences of episodes in the event sequence, and showed that, such a definition, in addition to yielding computationally efficient algorithms, has some important theoretical properties in connecting frequent episode discovery with hmm learning. this paper presents some new algorithms for frequent episode discovery under this non-overlapped occurrences-based frequency definition. the algorithms presented here are better (by a factor of n, where n denotes the size of episodes being discovered) in terms of both time and space complexities when compared to existing methods for frequent episode discovery. we show through some simulation experiments, that our algorithms are very efficient. the new algorithms presented here have arguably the least possible orders of spaceand time complexities for the task of frequent episode discovery.
cost-effective outbreak detection in networks. given a water distribution network, where should we place sensors toquickly detect contaminants? or, which blogs should we read to avoid missing important stories?. these seemingly different problems share common structure: outbreak detection can be modeled as selecting nodes (sensor locations, blogs) in a network, in order to detect the spreading of a virus or information asquickly as possible. we present a general methodology for near optimal sensor placement in these and related problems. we demonstrate that many realistic outbreak detection objectives (e.g., detection likelihood, population affected) exhibit the property of "submodularity". we exploit submodularity to develop an efficient algorithm that scales to large problems, achieving near optimal placements, while being 700 times faster than a simple greedy algorithm. we also derive online bounds on the quality of the placements obtained by any algorithm. our algorithms and bounds also handle cases where nodes (sensor locations, blogs) have different costs. we evaluate our approach on several large real-world problems,including a model of a water distribution network from the epa, andreal blog data. the obtained sensor placements are provably near optimal, providing a constant fraction of the optimal solution. we show that the approach scales, achieving speedups and savings in storage of several orders of magnitude. we also show how the approach leads to deeper insights in both applications, answering multicriteria trade-off, cost-sensitivity and generalization questions.