waashk/dblp huggingface dataset:
bbm: bayesian browsing model from petabyte-scale data. given a quarter of petabyte click log data, how can we estimate the relevance of each url for a given query? in this paper, we propose the bayesian browsing model (bbm), a new modeling technique with following advantages: (a) it does exact inference; (b) it is single-pass and parallelizable; (c) it is effective. we present two sets of experiments to test model effectiveness and efficiency. on the first set of over 50 million search instances of 1.1 million distinct queries, bbm out-performs the state-of-the-art competitor by 29.2% in log-likelihood while being 57 times faster. on the second click-log set, spanning a quarter of petabyte data, we showcase the scalability of bbm: we implemented it on a commercial mapreduce cluster, and it took only 3 hours to compute the relevance for 1.15 billion distinct query-url pairs.
address standardization with latent semantic association. address standardization is a very challenging task in data cleansing. to provide better customer relationship management and business intelligence for customer-oriented cooperates, millions of free-text addresses need to be converted to a standard format for data integration, de-duplication and householding. existing commercial tools usually employ lots of hand-craft, domain-specific rules and reference data dictionary of cities, states etc. these rules work better for the region they are designed. however, rule-based methods usually require more human efforts to rewrite these rules for each new domain since address data are very irregular and varied with countries and regions. supervised learning methods usually are more adaptable than rule-based approaches. however, supervised methods need large-scale labeled training data. it is a labor-intensive and time-consuming task to build a large-scale annotated corpus for each target domain. for minimizing human efforts and the size of labeled training data set, we present a free-text address standardization method with latent semantic association (lasa). lasa model is constructed to capture latent semantic association among words from the unlabeled corpus. the original term space of the target domain is projected to a concept space using lasa model at first, then the address standardization model is active learned from lasa features and informative samples. the proposed method effectively captures the data distribution of the domain. experimental results on large-scale english and chinese corpus show that the proposed method significantly enhances the performance of standardization with less efforts and training data.
an association analysis approach to biclustering. the discovery of biclusters, which denote groups of items that show coherent values across a subset of all the transactions in a data set, is an important type of analysis performed on real-valued data sets in various domains, such as biology. several algorithms have been proposed to find different types of biclusters in such data sets. however, these algorithms are unable to search the space of all possible biclusters exhaustively. pattern mining algorithms in association analysis also essentially produce biclusters as their result, since the patterns consist of items that are supported by a subset of all the transactions. however, a major limitation of the numerous techniques developed in association analysis is that they are only able to analyze data sets with binary and/or categorical variables, and their application to real-valued data sets often involves some lossy transformation such as discretization or binarization of the attributes. in this paper, we propose a novel association analysis framework for exhaustively and efficiently mining "range support" patterns from such a data set. on one hand, this framework reduces the loss of information incurred by the binarization- and discretization-based approaches, and on the other, it enables the exhaustive discovery of coherent biclusters. we compared the performance of our framework with two standard biclustering algorithms through the evaluation of the similarity of the cellular functions of the genes constituting the patterns/biclusters derived by these algorithms from microarray data. these experiments show that the real-valued patterns discovered by our framework are better enriched by small biologically interesting functional classes. also, through specific examples, we demonstrate the ability of the rap framework to discover functionally enriched patterns that are not found by the commonly used biclustering algorithm isa. the source code and data sets used in this paper, as well as the supplementary material, are available at http://www.cs.umn.edu/vk/gaurav/rap.
randomization methods in data mining. data mining research has developed many algorithms for various analysis tasks on large and complex datasets. however, assessing the significance of data mining results has received less attention. analytical methods are rarely available, and hence one has to use computationally intensive methods. randomization approaches based on null models provide, at least in principle, a general approach that can be used to obtain empirical p-values for various types of data mining approaches. i review some of the recent work in this area, outlining some of the open questions and problems.
probabilistic frequent itemset mining in uncertain databases. probabilistic frequent itemset mining in uncertain transaction databases semantically and computationally differs from traditional techniques applied to standard "certain" transaction databases. the consideration of existential uncertainty of item(sets), indicating the probability that an item(set) occurs in a transaction, makes traditional techniques inapplicable. in this paper, we introduce new probabilistic formulations of frequent itemsets based on possible world semantics. in this probabilistic context, an itemset x is called frequent if the probability that x occurs in at least minsup transactions is above a given threshold τ. to the best of our knowledge, this is the first approach addressing this problem under possible worlds semantics. in consideration of the probabilistic formulations, we present a framework which is able to solve the probabilistic frequent itemset mining (pfim) problem efficiently. an extensive experimental evaluation investigates the impact of our proposed techniques and shows that our approach is orders of magnitude faster than straight-forward approaches.
efficient methods for topic model inference on streaming document collections. topic models provide a powerful tool for analyzing large text collections by representing high dimensional data in a low dimensional subspace. fitting a topic model given a set of training documents requires approximate inference techniques that are computationally expensive. with today's large-scale, constantly expanding document collections, it is useful to be able to infer topic distributions for new documents without retraining the model. in this paper, we empirically evaluate the performance of several methods for topic inference in previously unseen documents, including methods based on gibbs sampling, variational inference, and a new method inspired by text classification. the classification-based inference method produces results similar to iterative inference methods, but requires only a single matrix multiplication. in addition to these inference methods, we present sparselda, an algorithm and data structure for evaluating gibbs sampling distributions. empirical results indicate that sparselda can be approximately 20 times faster than traditional lda and provide twice the speedup of previously published fast sampling methods, while also using substantially less memory.
ranking-based clustering of heterogeneous information networks with star network schema. a heterogeneous information network is an information network composed of multiple types of objects. clustering on such a network may lead to better understanding of both hidden structures of the network and the individual role played by every object in each cluster. however, although clustering on homogeneous networks has been studied over decades, clustering on heterogeneous networks has not been addressed until recently. a recent study proposed a new algorithm, rankclus, for clustering on bi-typed heterogeneous networks. however, a real-world network may consist of more than two types, and the interactions among multi-typed objects play a key role at disclosing the rich semantics that a network carries. in this paper, we study clustering of multi-typed heterogeneous networks with a star network schema and propose a novel algorithm, netclus, that utilizes links across multityped objects to generate high-quality net-clusters. an iterative enhancement method is developed that leads to effective ranking-based clustering in such heterogeneous networks. our experiments on dblp data show that netclus generates more accurate clustering results than the baseline topic model algorithm plsa and the recently proposed algorithm, rankclus. further, netclus generates informative clusters, presenting good ranking and cluster membership information for each attribute object in each net-cluster.
named entity mining from click-through data using weakly supervised latent dirichlet allocation. this paper addresses named entity mining (nem), in which we mine knowledge about named entities such as movies, games, and books from a huge amount of data. nem is potentially useful in many applications including web search, online advertisement, and recommender system. there are three challenges for the task: finding suitable data source, coping with the ambiguities of named entity classes, and incorporating necessary human supervision into the mining process. this paper proposes conducting nem by using click-through data collected at a web search engine, employing a topic model that generates the click-through data, and learning the topic model by weak supervision from humans. specifically, it characterizes each named entity by its associated queries and urls in the click-through data. it uses the topic model to resolve ambiguities of named entity classes by representing the classes as topics. it employs a method, referred to as weakly supervised latent dirichlet allocation (ws-lda), to accurately learn the topic model with partially labeled named entities. experiments on a large scale click-through data containing over 1.5 billion query-url pairs show that the proposed approach can conduct very accurate nem and significantly outperforms the baseline.
new ensemble methods for evolving data streams. advanced analysis of data streams is quickly becoming a key area of data mining research as the number of applications demanding such processing increases. online mining when such data streams evolve over time, that is when concepts drift or change completely, is becoming one of the core issues. when tackling non-stationary concepts, ensembles of classifiers have several advantages over single classifier methods: they are easy to scale and parallelize, they can adapt to change quickly by pruning under-performing parts of the ensemble, and they therefore usually also generate more accurate concept descriptions. this paper proposes a new experimental data stream framework for studying concept drift, and two new variants of bagging: adwin bagging and adaptive-size hoeffding tree (asht) bagging. using the new experimental framework, an evaluation study on synthetic and real-world datasets comprising up to ten million examples shows that the new ensemble methods perform very well compared to several known methods.
modeling and predicting user behavior in sponsored search. implicit user feedback, including click-through and subsequent browsing behavior, is crucial for evaluating and improving the quality of results returned by search engines. several recent studies [1, 2, 3, 13, 25] have used post-result browsing behavior including the sites visited, the number of clicks, and the dwell time on site in order to improve the ranking of search results. in this paper, we first study user behavior on sponsored search results (i.e., the advertisements displayed by search engines next to the organic results), and compare this behavior to that of organic results. second, to exploit post-result user behavior for better ranking of sponsored results, we focus on identifying patterns in user behavior and predict expected on-site actions in future instances. in particular, we show how post-result behavior depends on various properties of the queries, advertisement, sites, and users, and build a classifier using properties such as these to predict certain aspects of the user behavior. additionally, we develop a generative model to mimic trends in observed user activity using a mixture of pareto distributions. we conduct experiments based on billions of real navigation trails collected by a major search engine's browser toolbar.
mining for the most certain predictions from dyadic data. in several applications involving regression or classification, along with making predictions it is important to assess how accurate or reliable individual predictions are. this is particularly important in cases where due to finite resources or domain requirements, one wants to make decisions based only on the most reliable rather than on the entire set of predictions. this paper introduces novel and effective ways of ranking predictions by their accuracy for problems involving large-scale, heterogeneous data with a dyadic structure, i.e., where the independent variables can be naturally decomposed into three groups associated with two sets of elements and their combination. these approaches are based on modeling the data by a collection of localized models learnt while simultaneously partitioning (co-clustering) the data. for regression this leads to the concept of "certainty lift". we also develop a robust predictive modeling technique that identifies and models only the most coherent regions of the data to give high predictive accuracy on the selected subset of response values. extensive experimentation on real life datasets highlights the utility of our proposed approaches.
catching the drift: learning broad matches from clickthrough data. identifying similar keywords, known as broad matches, is an important task in online advertising that has become a standard feature on all major keyword advertising platforms. effective broad matching leads to improvements in both relevance and monetization, while increasing advertisers' reach and making campaign management easier. in this paper, we present a learning-based approach to broad matching that is based on exploiting implicit feedback in the form of advertisement clickthrough logs. our method can utilize arbitrary similarity functions by incorporating them as features. we present an online learning algorithm, amnesiac averaged perceptron, that is highly efficient yet able to quickly adjust to the rapidly-changing distributions of bidded keywords, advertisements and user behavior. experimental results obtained from (1) historical logs and (2) live trials on a large-scale advertising platform demonstrate the effectiveness of the proposed algorithm and the overall success of our approach in identifying high-quality broad match mappings.
efficient influence maximization in social networks. influence maximization is the problem of finding a small subset of nodes (seed nodes) in a social network that could maximize the spread of influence. in this paper, we study the efficient influence maximization from two complementary directions. one is to improve the original greedy algorithm of [5] and its improvement [7] to further reduce its running time, and the second is to propose new degree discount heuristics that improves influence spread. we evaluate our algorithms by experiments on two large academic collaboration graphs obtained from the online archival database arxiv.org. our experimental results show that (a) our improved greedy algorithm achieves better running time comparing with the improvement of [7] with matching influence spread, (b) our degree discount heuristics achieve much better influence spread than classic degree and centrality-based heuristics, and when tuned for a specific influence cascade model, it achieves almost matching influence thread with the greedy algorithm, and more importantly (c) the degree discount heuristics run only in milliseconds while even the improved greedy algorithms run in hours in our experiment graphs with a few tens of thousands of nodes. based on our results, we believe that fine-tuned heuristics may provide truly scalable solutions to the influence maximization problem with satisfying influence spread and blazingly fast running time. therefore, contrary to what implied by the conclusion of [5] that traditional heuristics are outperformed by the greedy approximation algorithm, our results shed new lights on the research of heuristic algorithms.
towards efficient mining of proportional fault-tolerant frequent itemsets. fault-tolerant frequent itemsets (ftfi) are variants of frequent itemsets for representing and discovering generalized knowledge. however, despite growing interest in this field, no previous approach mines proportional ftfis with their exact support (ft-support). this problem is difficult because of two concerns: (a) non anti-monotonic property of ft-support when relaxation is proportional, and (b) difficulty in computing ft-support. previous efforts on this problem either simplify the general problem by adding constraints, or provide approximate solutions without any error guarantees. in this paper, we address these concerns in the general ftfi mining problem. we limit the search space by providing provably correct anti monotone bounds for ft-support and develop practically efficient means of achieving them. besides, we also provide an efficient and exact ft-support counting procedure. extensive experiments using real datasets validate that our solution is reasonably efficient for completely mining ftfis. implementations for the algorithms are available from www.cais.ntu.edu.sg/~vivek/pubs/ftfim09.
regression-based latent factor models. we propose a novel latent factor model to accurately predict response for large scale dyadic data in the presence of features. our approach is based on a model that predicts response as a multiplicative function of row and column latent factors that are estimated through separate regressions on known row and column features. in fact, our model provides a single unified framework to address both cold and warm start scenarios that are commonplace in practical applications like recommender systems, online advertising, web search, etc. we provide scalable and accurate model fitting methods based on iterated conditional mode and monte carlo em algorithms. we show our model induces a stochastic process on the dyadic space with kernel (covariance) given by a polynomial function of features. methods that generalize our procedure to estimate factors in an online fashion for dynamic applications are also considered. our method is illustrated on benchmark datasets and a novel content recommendation application that arises in the context of yahoo! front page. we report significant improvements over several commonly used methods on all datasets.
classification of software behaviors for failure detection: a discriminative pattern mining approach. software is a ubiquitous component of our daily life. we often depend on the correct working of software systems. due to the difficulty and complexity of software systems, bugs and anomalies are prevalent. bugs have caused billions of dollars loss, in addition to privacy and security threats. in this work, we address software reliability issues by proposing a novel method to classify software behaviors based on past history or runs. with the technique, it is possible to generalize past known errors and mistakes to capture failures and anomalies. our technique first mines a set of discriminative features capturing repetitive series of events from program execution traces. it then performs feature selection to select the best features for classification. these features are then used to train a classifier to detect failures. experiments and case studies on traces of several benchmark software systems and a real-life concurrency bug from mysql server show the utility of the technique in capturing failures and anomalies. on average, our pattern-based classification technique outperforms the baseline approach by 24.68% in accuracy.
mining rich session context to improve web search. user browsing information, particularly their non-search related activity, reveals important contextual information on the preferences and the intent of web users. in this paper, we expand the use of browsing information for web search ranking and other applications, with an emphasis on analyzing individual user sessions for creating aggregate models. in this context, we introduce clickrank, an efficient, scalable algorithm for estimating web page and web site importance from browsing information. we lay out the theoretical foundation of clickrank based on an intentional surfer model and analyze its properties. we evaluate its effectiveness for the problem of web search ranking, showing that it contributes significantly to retrieval performance as a novel web search feature. we demonstrate that the results produced by clickrank for web search ranking are highly competitive with those produced by other approaches, yet achieved at better scalability and substantially lower computational costs. finally, we discuss novel applications of clickrank in providing enriched user web search experience, highlighting the usefulness of our approach for non-ranking tasks.
can we learn a template-independent wrapper for news article extraction from a single training site? automatic news extraction from news pages is important in many web applications such as news aggregation. however, the existing news extraction methods based on template-level wrapper induction have three serious limitations. first, the existing methods cannot correctly extract pages belonging to an unseen template. second, it is costly to maintain up-to-date wrappers for a large amount of news websites, because any change of a template may invalidate the corresponding wrapper. last, the existing methods can merely extract unformatted plain texts, and thus are not user friendly. in this paper, we tackle the problem of template-independent web news extraction in a user-friendly way. we formalize web news extraction as a machine learning problem and learn a template-independent wrapper using a very small number of labeled news pages from a single site. novel features dedicated to news titles and bodies are developed. correlations between news titles and news bodies are exploited. our template-independent wrapper can extract news pages from different sites regardless of templates. moreover, our approach can extract not only texts, but also images and animates within the news bodies and the extracted news articles are in the same visual style as in the original pages. in our experiments, a wrapper learned from 40 pages from a single news site achieved an accuracy of 98.1% on 3,973 news pages from 12 news sites.