waashk/dblp huggingface dataset:
meme-tracking and the dynamics of the news cycle. tracking new topics, ideas, and "memes" across the web has been an issue of considerable interest. recent work has developed methods for tracking topic shifts over long time scales, as well as abrupt spikes in the appearance of particular named entities. however, these approaches are less well suited to the identification of content that spreads widely and then fades over time scales on the order of days - the time scale at which we perceive news and events. we develop a framework for tracking short, distinctive phrases that travel relatively intact through on-line text; developing scalable algorithms for clustering textual variants of such phrases, we identify a broad class of memes that exhibit wide spread and rich variation on a daily basis. as our principal domain of study, we show how such a meme-tracking approach can provide a coherent representation of the news cycle - the daily rhythms in the news media that have long been the subject of qualitative interpretation but have never been captured accurately enough to permit actual quantitative analysis. we tracked 1.6 million mainstream media sites and blogs over a period of three months with the total of 90 million articles and we find a set of novel and persistent temporal patterns in the news cycle. in particular, we observe a typical lag of 2.5 hours between the peaks of attention to a phrase in the news media and in blogs respectively, with divergent behavior around the overall peak and a "heartbeat"-like pattern in the handoff between news and blogs. we also develop and analyze a mathematical model for the kinds of temporal variation that the system exhibits.
tangent: a novel, 'surprise me', recommendation algorithm. most of recommender systems try to find items that are most relevant to the older choices of a given user. here we focus on the "surprise me" query: a user may be bored with his/her usual genre of items (e.g., books, movies, hobbies), and may want a recommendation that is related, but off the beaten path, possibly leading to a new genre of books/movies/hobbies. how would we define, as well as automate, this seemingly selfcontradicting request? we introduce tangent, a novel recommendation algorithm to solve this problem. the main idea behind tangent is to envision the problem as node selection on a graph, giving high scores to nodes that are well connected to the older choices, and at the same time well connected to unrelated choices. the method is carefully designed to be (a) parameter-free (b) effective and (c) fast. we illustrate the benefits of tangent with experiments on both synthetic and real data sets. we show that tangent makes reasonable, yet surprising, horizon-broadening recommendations. moreover, it is fast and scalable, since it can easily use existing fast algorithms on graph node proximity.
collective annotation of wikipedia entities in web text. to take the first step beyond keyword-based search toward entity-based search, suitable token spans ("spots") on documents must be identified as references to real-world entities from an entity catalog. several systems have been proposed to link spots on web pages to entities in wikipedia. they are largely based on local compatibility between the text around the spot and textual metadata associated with the entity. two recent systems exploit inter-label dependencies, but in limited ways. we propose a general collective disambiguation approach. our premise is that coherent documents refer to entities from one or a few related topics or domains. we give formulations for the trade-off between local spot-to-entity compatibility and measures of global coherence between entities. optimizing the overall entity assignment is np-hard. we investigate practical solutions based on local hill-climbing, rounding integer linear programs, and pre-clustering entities followed by local optimization within clusters. in experiments involving over a hundred manually-annotated web pages and tens of thousands of spots, our approaches significantly outperform recently-proposed algorithms.
towards a universal marketplace over the web: statistical multi-label classification of service provider forms with simulated annealing. there is a growing number of service providers that a consumer can interact with over the web to learn their service terms. the service terms, such as price and time to completion of the service, depend on the consumer's particular specifications. for instance, a printing services provider would need from its customers specifications such as the size of paper, type of ink, proofing and perforation. in a few sectors, there exist marketplace sites that provide consumers with specifications forms, which the consumer can fill out to learn the service terms of multiple service providers. unfortunately, there are only a few such marketplace sites, and they cover a few sectors. at hp labs, we are working towards building a universal marketplace site, i.e., a marketplace site that covers thousands of sectors and hundreds of providers per sector. one issue in this domain is the automated discovery/retrieval of the specifications for each sector. we address it through extracting and analyzing content from the websites of the service providers listed in business directories. the challenge is that each service provider is often listed under multiple service categories in a business directory, making it infeasible to utilize standard supervised learning techniques. we address this challenge through employing a multilabel statistical clustering approach within an expectation-maximization framework. we implement our solution to retrieve specifications for 3000 sectors, representing more than 300,000 service providers. we discuss our results within the context of the services needed to design a marketing campaign for a small business.
grocery shopping recommendations based on basket-sensitive random walk. we describe a recommender system in the domain of grocery shopping. while recommender systems have been widely studied, this is mostly in relation to leisure products (e.g. movies, books and music) with non-repeated purchases. in grocery shopping, however, consumers will make multiple purchases of the same or very similar products more frequently than buying entirely new items. the proposed recommendation scheme offers several advantages in addressing the grocery shopping problem, namely: 1) a product similarity measure that suits a domain where no rating information is available; 2) a basket sensitive random walk model to approximate product similarities by exploiting incomplete neighborhood information; 3) online adaptation of the recommendation based on the current basket and 4) a new performance measure focusing on products that customers have not purchased before or purchase infrequently. empirical results benchmarking on three real-world data sets demonstrate a performance improvement of the proposed method over other existing collaborative filtering models.
constrained optimization for validation-guided conditional random field learning. conditional random fields(crfs) are a class of undirected graphical models which have been widely used for classifying and labeling sequence data. the training of crfs is typically formulated as an unconstrained optimization problem that maximizes the conditional likelihood. however, maximum likelihood training is prone to overfitting. to address this issue, we propose a novel constrained nonlinear optimization formulation in which the prediction accuracy of cross-validation sets are included as constraints. instead of requiring multiple passes of training, the constrained formulation allows the cross-validation be handled in one pass of constrained optimization. the new formulation is discontinuous, and classical lagrangian based constraint handling methods are not applicable. a new constrained optimization algorithm based on the recently proposed extended saddle point theory is developed to learn the constrained crf model. experimental results on gene and stock-price prediction tasks show that the constrained formulation is able to significantly improve the generalization ability of crf training.
large-scale graph mining using backbone refinement classes. we present a new approach to large-scale graph mining based on so-called backbone refinement classes. the method efficiently mines tree-shaped subgraph descriptors under minimum frequency and significance constraints, using classes of fragments to reduce feature set size and running times. the classes are defined in terms of fragments sharing a common backbone. the method is able to optimize structural inter-feature entropy as opposed to occurrences, which is characteristic for open or closed fragment mining. in the experiments, the proposed method reduces feature set sizes by >90 % and >30 % compared to complete tree mining and open tree mining, respectively. evaluation using crossvalidation runs shows that their classification accuracy is similar to the complete set of trees but significantly better than that of open trees. compared to open or closed fragment mining, a large part of the search space can be pruned due to an improved statistical constraint (dynamic upper bound adjustment), which is also confirmed in the experiments in lower running times compared to ordinary (static) upper bound pruning. further analysis using large-scale datasets yields insight into important properties of the proposed descriptors, such as the dataset coverage and the class size represented by each descriptor. a final cross-validation run confirms that the novel descriptors render large training sets feasible which previously might have been intractable.
a case study of behavior-driven conjoint analysis on yahoo!: front page today module. conjoint analysis is one of the most popular market research methodologies for assessing how customers with heterogeneous preferences appraise various objective characteristics in products or services, which provides critical inputs for many marketing decisions, e.g. optimal design of new products and target market selection. nowadays it becomes practical in e-commercial applications to collect millions of samples quickly. however, the large-scale data sets make traditional conjoint analysis coupled with sophisticated monte carlo simulation for parameter estimation computationally prohibitive. in this paper, we report a successful large-scale case study of conjoint analysis on click through stream in a real-world application at yahoo!. we consider identifying users' heterogenous preferences from millions of click/view events and building predictive models to classify new users into segments of distinct behavior pattern. a scalable conjoint analysis technique, known as tensor segmentation, is developed by utilizing logistic tensor regression in standard partworth framework for solutions. in offline analysis on the samples collected from a random bucket of yahoo! front page today module, we compare tensor segmentation against other segmentation schemes using demographic information, and study user preferences on article content within tensor segments. our knowledge acquired in the segmentation results also provides assistance to editors in content management and user targeting. the usefulness of our approach is further verified by the observations in a bucket test launched in dec. 2008.
improving classification accuracy using automatically extracted training data. classification is a core task in knowledge discovery and data mining, and there has been substantial research effort in developing sophisticated classification models. in a parallel thread, recent work from the nlp community suggests that for tasks such as natural language disambiguation even a simple algorithm can outperform a sophisticated one, if it is provided with large quantities of high quality training data. in those applications, training data occurs naturally in text corpora, and high quality training data sets running into billions of words have been reportedly used. we explore how we can apply the lessons from the nlp community to kdd tasks. specifically, we investigate how to identify data sources that can yield training data at low cost and study whether the quantity of the automatically extracted training data can compensate for its lower quality. we carry out this investigation for the specific task of inferring whether a search query has commercial intent. we mine toolbar and click logs to extract queries from sites that are predominantly commercial (e.g., amazon) and non-commercial (e.g., wikipedia). we compare the accuracy obtained using such training data against manually labeled training data. our results show that we can have large accuracy gains using automatically extracted training data at much lower cost.
issues in evaluation of stream learning algorithms. learning from data streams is a research area of increasing importance. nowadays, several stream learning algorithms have been developed. most of them learn decision models that continuously evolve over time, run in resource-aware environments, detect and react to changes in the environment generating data. one important issue, not yet conveniently addressed, is the design of experimental work to evaluate and compare decision models that evolve over time. there are no golden standards for assessing performance in non-stationary environments. this paper proposes a general framework for assessing predictive stream learning algorithms. we defend the use of predictive sequential methods for error estimate - the prequential error. the prequential error allows us to monitor the evolution of the performance of models that evolve over time. nevertheless, it is known to be a pessimistic estimator in comparison to holdout estimates. to obtain more reliable estimators we need some forgetting mechanism. two viable alternatives are: sliding windows and fading factors. we observe that the prequential error converges to an holdout estimator when estimated over a sliding window or using fading factors. we present illustrative examples of the use of prequential error estimators, using fading factors, for the tasks of: i) assessing performance of a learning algorithm; ii) comparing learning algorithms; iii) hypothesis testing using mcnemar test; and iv) change detection using page-hinkley test. in these tasks, the prequential error estimated using fading factors provide reliable estimators. in comparison to sliding windows, fading factors are faster and memory-less, a requirement for streaming applications. this paper is a contribution to a discussion in the good-practices on performance assessment when learning dynamic models that evolve over time.
large human communication networks: patterns and a utility-driven generator. given a real, and weighted person-to-person network which changes over time, what can we say about the cliques that it contains? do the incidents of communication, or weights on the edges of a clique follow any pattern? real, and in-person social networks have many more triangles than chance would dictate. as it turns out, there are many more cliques than one would expect, in surprising patterns. in this paper, we study massive real-world social networks formed by direct contacts among people through various personal communication services, such as phone-call, sms, im etc. the contributions are the following: (a) we discover surprising patterns with the cliques, (b) we report power-laws of the weights on the edges of cliques, (c) our real networks follow these patterns such that we can trust them to spot outliers and finally, (d) we propose the first utility-driven graph generator for weighted time-evolving networks, which match the observed patterns. our study focused on three large datasets, each of which is a different type of communication service, with over one million records, and spans several months of activity.
on compressing social networks. motivated by structural properties of the web graph that support efficient data structures for in memory adjacency queries, we study the extent to which a large network can be compressed. boldi and vigna (www 2004), showed that web graphs can be compressed down to three bits of storage per edge; we study the compressibility of social networks where again adjacency queries are a fundamental primitive. to this end, we propose simple combinatorial formulations that encapsulate efficient compressibility of graphs. we show that some of the problems are np-hard yet admit effective heuristics, some of which can exploit properties of social networks such as link reciprocity. our extensive experiments show that social networks and the web graph exhibit vastly different compressibility characteristics.
using graph-based metrics with empirical risk minimization to speed up active learning on networked data. active and semi-supervised learning are important techniques when labeled data are scarce. recently a method was suggested for combining active learning with a semi-supervised learning algorithm that uses gaussian fields and harmonic functions. this classifier is relational in nature: it relies on having the data presented as a partially labeled graph (also known as a within-network learning problem). this work showed yet again that empirical risk minimization (erm) was the best method to find the next instance to label and provided an efficient way to compute erm with the semi-supervised classifier. the computational problem with erm is that it relies on computing the risk for all possible instances. if we could limit the candidates that should be investigated, then we can speed up active learning considerably. in the case where the data is graphical in nature, we can leverage the graph structure to rapidly identify instances that are likely to be good candidates for labeling. this paper describes a novel hybrid approach of using of community finding and social network analytic centrality measures to identify good candidates for labeling and then using erm to find the best instance in this candidate set. we show on real-world data that we can limit the erm computations to a fraction of instances with comparable performance.
temporal mining for interactive workflow data analysis. in the past few years there has been an increasing interest in the analysis of process logs. several proposed techniques, such as workflow mining, are aimed at automatically deriving the underlying workflow models. however, current approaches only pay little attention on an important piece of information contained in process logs: the timestamps, which are used to define a sequential ordering of the performed tasks. in this work we try to overcome these limitations by explicitly including time in the extracted knowledge, thus making the temporal information a first-class citizen of the analysis process. this makes it possible to discern between apparently identical process executions that are performed with different transition times between consecutive tasks. this paper proposes a framework for the user-interactive exploration of a condensed representation of groups of executions of a given process. the framework is based on the use of an existing mining paradigm: temporally-annotated sequences (tas). these are aimed at extracting sequential patterns where each transition between two events is annotated with a typical transition time that emerges from input data. with the extracted tas, which represent sets of possible frequent executions with their typical transition times, a few factorizing operators are built. these operators condense such executions according to possible parallel or possible mutual exclusive executions. lastly, such condensed representation is rendered to the user via the exploration graph, namely the temporally-annotated graph (tag). the user, the domain expert, is allowed to explore the different and alternative factorizations corresponding to different interpretations of the actual executions. according to the user choices, the system discards or retains certain hypotheses on actual executions and shows the consequent scenarios resulting from the coresponding re-aggregation of the actual data.
mismatched models, wrong results, and dreadful decisions: on choosing appropriate data mining tools. data mining techniques use 'score functions' to quantify how well a model fits a given data set. parameters are estimated by optimising the fit, as measured by the chosen score function, and model choice is guided by the size of the scores for the different models. since different score functions summarise the fit in different ways, it is important to choose a function which matches the objectives of the data mining exercise. for predictive classification problems, a wide variety of score functions exist, including measures such as precision and recall, the f measure, misclassification rate, the area under the roc curve (the auc), and others. the first four of these require a 'classification threshold' to be chosen, a choice which may not be easy, or may even be impossible, especially when the classification rule is to be applied in the future. in contrast, the auc does not require the specification of a classification threshold, but summarises performance over the range of possible threshold choices. however, unfortunately, and despite the widespread use of the auc, it has a previously unrecognised fundamental incoherence lying at the core of its definition. this means that using the auc can lead to poor model choice and unecessary misclassifications. the auc is set in context, its deficiency explained and the implications illustrated - with the bottom line being that the auc should not be used. a family of coherent alternative scores is described. the ideas are illustrated with examples from bank loans, fraud, face recognition, and health screening.
turning down the noise in the blogosphere. in recent years, the blogosphere has experienced a substantial increase in the number of posts published daily, forcing users to cope with information overload. the task of guiding users through this flood of information has thus become critical. to address this issue, we present a principled approach for picking a set of posts that best covers the important stories in the blogosphere. we define a simple and elegant notion of coverage and formalize it as a submodular optimization problem, for which we can efficiently compute a near-optimal solution. in addition, since people have varied interests, the ideal coverage algorithm should incorporate user preferences in order to tailor the selected posts to individual tastes. we define the problem of learning a personalized coverage function by providing an appropriate user-interaction model and formalizing an online learning framework for this task. we then provide a no-regret algorithm which can quickly learn a user's preferences from limited feedback. we evaluate our coverage and personalization algorithms extensively over real blog data. results from a user study show that our simple coverage algorithm does as well as most popular blog aggregation sites, including google blog search, yahoo! buzz, and digg. furthermore, we demonstrate empirically that our algorithm can successfully adapt to user preferences. we believe that our technique, especially with personalization, can dramatically reduce information overload.