waashk/dblp huggingface dataset:
structured learning for non-smooth ranking losses. learning to rank from relevance judgment is an active research area. itemwise score regression, pairwise preference satisfaction, and listwise structured learning are the major techniques in use. listwise structured learning has been applied recently to optimize important non-decomposable ranking criteria like auc (area under roc curve) and map (mean average precision). we propose new, almost-linear-time algorithms to optimize for two other criteria widely used to evaluate search systems: mrr (mean reciprocal rank) and ndcg (normalized discounted cumulative gain) in the max-margin structured learning framework. we also demonstrate that, for different ranking criteria, one may need to use different feature maps. search applications should not be optimized in favor of a single criterion, because they need to cater to a variety of queries. e.g., mrr is best for navigational queries, while ndcg is best for informational queries. a key contribution of this paper is to fold multiple ranking loss functions into a multi-criteria max-margin optimization. the result is a single, robust ranking model that is close to the best accuracy of learners trained on individual criteria. in fact, experiments over the popular letor and trec data sets show that, contrary to conventional wisdom, a test criterion is often not best served by training with the same individual criterion.
morpheus: interactive exploration of subspace clustering. data mining techniques extract interesting patterns out of large data resources. meaningful visualization and interactive exploration of patterns are crucial for knowledge discovery. visualization techniques exist for traditional clustering in low dimensional spaces. in high dimensional data, clusters typically only exist in subspace projections. this subspace clustering, however, lacks interactive visualization tools. challenges arise from typically large result sets in different subspace projections that hinder comparability, visualization and understandability. in this work, we describe morpheus, a tool that supports the knowledge discovery process through visualization and interactive exploration of subspace clusterings. users may browse an overview of the entire subspace clustering, analyze subspace cluster characteristics in-depth and zoom into object groupings. bracketing of different parameter settings enables users to immediately see the effects of parameters and to provide feedback to further improve the subspace clustering. furthermore, morpheus may serve as a teaching and exploration tool for the data mining community to visually assess different subspace clustering paradigms.
sax: indexing and mining terabyte sized time series. current research in indexing and mining time series data has produced many interesting algorithms and representations. however, the algorithms and the size of data considered have generally not been representative of the increasingly massive datasets encountered in science, engineering, and business domains. in this work, we show how a novel multi-resolution symbolic representation can be used to index datasets which are several orders of magnitude larger than anything else considered in the literature. our approach allows both fast exact search and ultra fast approximate search. we show how to exploit the combination of both types of search as sub-routines in data mining algorithms, allowing for the exact mining of truly massive real world datasets, containing millions of time series.
regularization paths and coordinate descent. in a statistical world faced with an explosion of data, regularization has become an important ingredient. in a wide variety of problems we have many more input features than observations, and the lasso penalty and its hybrids have become increasingly useful for both feature selection and regularization. this talk presents some effective algorithms based on coordinate descent for fitting large scale regularization paths for a variety of problems.
learning from multi-topic web documents for contextual advertisement. contextual advertising on web pages has become very popular recently and it poses its own set of unique text mining challenges. often advertisers wish to either target (or avoid) some specific content on web pages which may appear only in a small part of the page. learning for these targeting tasks is difficult since most training pages are multi-topic and need expensive human labeling at the sub-document level for accurate training. in this paper we investigate ways to learn for sub-document classification when only page level labels are available - these labels only indicate if the relevant content exists in the given page or not. we propose the application of multiple-instance learning to this task to improve the effectiveness of traditional methods. we apply sub-document classification to two different problems in contextual advertising. one is "sensitive content detection" where the advertiser wants to avoid content relating to war, violence, pornography, etc. even if they occur only in a small part of a page. the second problem involves opinion mining from review sites - the advertiser wants to detect and avoid negative opinion about their product when positive, negative and neutral sentiments co-exist on a page. in both these scenarios we present experimental results to show that our proposed system is able to get good block level labeling for free and improve the performance of traditional learning methods.
learning classifiers from only positive and unlabeled data. the input to an algorithm that learns a binary classifier normally consists of two sets of examples, where one set consists of positive examples of the concept to be learned, and the other set consists of negative examples. however, it is often the case that the available training data are an incomplete set of positive examples, and a set of unlabeled examples, some of which are positive and some of which are negative. the problem solved in this paper is how to learn a standard binary classifier given a nontraditional training set of this nature. under the assumption that the labeled examples are selected randomly from the positive examples, we show that a classifier trained on positive and unlabeled examples predicts probabilities that differ by only a constant factor from the true conditional probabilities of being positive. we show how to use this result in two different ways to learn a classifier from a nontraditional training set. we then apply these two new methods to solve a real-world problem: identifying protein records that should be included in an incomplete specialized molecular biology database. our experiments in this domain show that models trained using the new methods perform better than the current state-of-the-art biased svm method for learning from positive and unlabeled examples.
colibri: fast mining of large static and dynamic graphs. low-rank approximations of the adjacency matrix of a graph are essential in finding patterns (such as communities) and detecting anomalies. additionally, it is desirable to track the low-rank structure as the graph evolves over time, efficiently and within limited storage. real graphs typically have thousands or millions of nodes, but are usually very sparse. however, standard decompositions such as svd do not preserve sparsity. this has led to the development of methods such as cur and cmd, which seek a non-orthogonal basis by sampling the columns and/or rows of the sparse matrix. however, these approaches will typically produce overcomplete bases, which wastes both space and time. in this paper we propose the family of colibri methods to deal with these challenges. our version for static graphs, colibri-s, iteratively finds a non-redundant basis and we prove that it has no loss of accuracy compared to the best competitors (cur and cmd), while achieving significant savings in space and time: on real data, colibri-s requires much less space and is orders of magnitude faster (in proportion to the square of the number of non-redundant columns). additionally, we propose an efficient update algorithm for dynamic, time-evolving graphs, colibri-d. our evaluation on a large, real network traffic dataset shows that colibri-d is over 100 times faster than the best published competitor (cmd).
discrimination-aware data mining. in the context of civil rights law, discrimination refers to unfair or unequal treatment of people based on membership to a category or a minority, without regard to individual merit. rules extracted from databases by data mining techniques, such as classification or association rules, when used for decision tasks such as benefit or credit approval, can be discriminatory in the above sense. in this paper, the notion of discriminatory classification rules is introduced and studied. providing a guarantee of non-discrimination is shown to be a non trivial task. a naive approach, like taking away all discriminatory attributes, is shown to be not enough when other background knowledge is available. our approach leads to a precise formulation of the redlining problem along with a formal result relating discriminatory rules with apparently safe ones by means of background knowledge. an empirical assessment of the results on the german credit dataset is also provided.
knowledge transfer via multiple model local structure mapping. the effectiveness of knowledge transfer using classification algorithms depends on the difference between the distribution that generates the training examples and the one from which test examples are to be drawn. the task can be especially difficult when the training examples are from one or several domains different from the test domain. in this paper, we propose a locally weighted ensemble framework to combine multiple models for transfer learning, where the weights are dynamically assigned according to a model's predictive power on each test example. it can integrate the advantages of various learning algorithms and the labeled information from multiple training domains into one unified classification model, which can then be applied on a different domain. importantly, different from many previously proposed methods, none of the base learning method is required to be specifically designed for transfer learning. we show the optimality of a locally weighted ensemble framework as a general approach to combine multiple models for domain transfer. we then propose an implementation of the local weight assignments by mapping the structures of a model onto the structures of the test domain, and then weighting each model locally according to its consistency with the neighborhood structure around the test example. experimental results on text classification, spam filtering and intrusion detection data sets demonstrate significant improvements in classification accuracy gained by the framework. on a transfer learning task of newsgroup message categorization, the proposed locally weighted ensemble framework achieves 97% accuracy when the best single model predicts correctly only on 73% of the test examples. in summary, the improvement in accuracy is over 10% and up to 30% across different problems.
effective label acquisition for collective classification. information diffusion, viral marketing, and collective classification all attempt to model and exploit the relationships in a network to make inferences about the labels of nodes. a variety of techniques have been introduced and methods that combine attribute information and neighboring label information have been shown to be effective for collective labeling of the nodes in a network. however, in part because of the correlation between node labels that the techniques exploit, it is easy to find cases in which, once a misclassification is made, incorrect information propagates throughout the network. this problem can be mitigated if the system is allowed to judiciously acquire the labels for a small number of nodes. unfortunately, under relatively general assumptions, determining the optimal set of labels to acquire is intractable. here we propose an acquisition method that learns the cases when a given collective classification algorithm makes mistakes, and suggests acquisitions to correct those mistakes. we empirically show on both real and synthetic datasets that this method significantly outperforms a greedy approximate inference approach, a viral marketing approach, and approaches based on network structural measures such as node degree and network clustering. in addition to significantly improving accuracy with just a small amount of labeled data, our method is tractable on large networks.
effective and efficient itemset pattern summarization: regression-based approaches. in this paper, we propose a set of novel regression-based approaches to effectively and efficiently summarize frequent itemset patterns. specifically, we show that the problem of minimizing the restoration error for a set of itemsets based on a probabilistic model corresponds to a non-linear regression problem. we show that under certain conditions, we can transform the nonlinear regression problem to a linear regression problem. we propose two new methods, k-regression and tree-regression, to partition the entire collection of frequent itemsets in order to minimize the restoration error. the k-regression approach, employing a k-means type clustering method, guarantees that the total restoration error achieves a local minimum. the tree-regression approach employs a decision-tree type of top-down partition process. in addition, we discuss alternatives to estimate the frequency for the collection of itemsets being covered by the k representative itemsets. the experimental evaluation on both real and synthetic datasets demonstrates that our approaches significantly improve the summarization performance in terms of both accuracy (restoration error), and computational cost.
learning methods for lung tumor markerless gating in image-guided radiotherapy. in an idealized gated radiotherapy treatment, radiation is delivered only when the tumor is at the right position. for gated lung cancer radiotherapy, it is difficult to generate accurate gating signals due to the large uncertainties when using external surrogates and the risk of pneumothorax when using implanted fiducial markers. in this paper, we investigate machine learning algorithms for markerless gated radiotherapy with fluoroscopic images. previous approach utilizes template matching to localize the tumor position. here, we investigate two ways to improve the precision of tumor target localization by applying: (1) an ensemble of templates where the representative templates are selected by gaussian mixture clustering, and (2) a support vector machine (svm) classifier with radial basis kernels. template matching only considers images inside the gating window, but images outside the gating window might provide additional information. we take advantage of both states and re-cast the gating problem into a classification problem. thus, we are able to use the svm classifier for gated radiotherapy. to verify the effectiveness of the two proposed techniques, we apply them on five sequences of fluoroscopic images from five lung cancer patients against the gating signal of manually contoured tumors as ground truth. our five-patient case study shows that both ensemble template matching and svm are reasonable tools for image-guided markerless gated radiotherapy with an average of approximately 95% precision in terms of delivered target dose at approximately 35% duty cycle.
a visual-analytic toolkit for dynamic interaction graphs. in this article we describe a visual-analytic tool for the interrogation of evolving interaction network data such as those found in social, bibliometric, www and biological applications. the tool we have developed incorporates common visualization paradigms such as zooming, coarsening and filtering while naturally integrating information extracted by a previously described event-driven framework for characterizing the evolution of such networks. the visual front-end provides features that are specifically useful in the analysis of interaction networks, capturing the dynamic nature of both individual entities as well as interactions among them. the tool provides the user with the option of selecting multiple views, designed to capture different aspects of the evolving graph from the perspective of a node, a community or a subset of nodes of interest. standard visual templates and cues are used to highlight critical changes that have occurred during the evolution of the network. a key challenge we address in this work is that of scalability - handling large graphs both in terms of the efficiency of the back-end, and in terms of the efficiency of the visual layout and rendering. two case studies based on bibliometric and wikipedia data are presented to demonstrate the utility of the toolkit for visual knowledge discovery.
using ghost edges for classification in sparsely labeled networks. we address the problem of classification in partially labeled networks (a.k.a. within-network classification) where observed class labels are sparse. techniques for statistical relational learning have been shown to perform well on network classification tasks by exploiting dependencies between class labels of neighboring nodes. however, relational classifiers can fail when unlabeled nodes have too few labeled neighbors to support learning (during training phase) and/or inference (during testing phase). this situation arises in real-world problems when observed labels are sparse. in this paper, we propose a novel approach to within-network classification that combines aspects of statistical relational learning and semi-supervised learning to improve classification performance in sparse networks. our approach works by adding "ghost edges" to a network, which enable the flow of information from labeled to unlabeled nodes. through experiments on real-world data sets, we demonstrate that our approach performs well across a range of conditions where existing approaches, such as collective classification and semi-supervised learning, fail. on all tasks, our approach improves area under the roc curve (auc) by up to 15 points over existing approaches. furthermore, we demonstrate that our approach runs in time proportional to l • e, where l is the number of labeled nodes and e is the number of edges.
reconstructing chemical reaction networks: data mining meets system identification. we present an approach to reconstructing chemical reaction networks from time series measurements of the concentrations of the molecules involved. our solution strategy combines techniques from numerical sensitivity analysis and probabilistic graphical models. by modeling a chemical reaction system as a markov network (undirected graphical model), we show how systematically probing for sensitivities between molecular species can identify the topology of the network. given the topology, our approach next uses detailed sensitivity profiles to characterize properties of reactions such as reversibility, enzyme-catalysis, and the precise stoichiometries of the reactants and products. we demonstrate applications to reconstructing key biological systems including the yeast cell cycle. in addition to network reconstruction, our algorithm finds applications in model reduction and model comprehension. we argue that our reconstruction algorithm can serve as an important primitive for data mining in systems biology applications.
classification with partial labels. in this paper, we address the problem of learning when some cases are fully labeled while other cases are only partially labeled, in the form of partial labels. partial labels are represented as a set of possible labels for each training example, one of which is the correct label. we introduce a discriminative learning approach that incorporates partial label information into the conventional margin-based learning framework. the partial label learning problem is formulated as a convex quadratic optimization minimizing the l2-norm regularized empirical risk using hinge loss. we also present an efficient algorithm for classification in the presence of partial labels. experiments with different data sets show that partial label information improves the performance of classification when there is traditional fully-labeled data, and also yields reasonable performance in the absence of any fully labeled data.
internet advertising and optimal auction design. this talk describes the optimal (revenue maximizing) auction for sponsored search advertising. we show that a search engine's optimal reserve price is independent of the number of bidders. using simulations, we consider the changes that result from a search engine's choice of reserve price and from changes in the number of participating advertisers.
automatic identification of quasi-experimental designs for discovering causal knowledge. researchers in the social and behavioral sciences routinely rely on quasi-experimental designs to discover knowledge from large data-bases. quasi-experimental designs (qeds) exploit fortuitous circumstances in non-experimental data to identify situations (sometimes called "natural experiments") that provide the equivalent of experimental control and randomization. qeds allow researchers in domains as diverse as sociology, medicine, and marketing to draw reliable inferences about causal dependencies from non-experimental data. unfortunately, identifying and exploiting qeds has remained a painstaking manual activity, requiring researchers to scour available databases and apply substantial knowledge of statistics. however, recent advances in the expressiveness of databases, and increases in their size and complexity, provide the necessary conditions to automatically identify qeds. in this paper, we describe the first system to discover knowledge by applying quasi-experimental designs that were identified automatically. we demonstrate that qeds can be identified in a traditional database schema and that such identification requires only a small number of extensions to that schema, knowledge about quasi-experimental design encoded in first-order logic, and a theorem-proving engine. we describe several key innovations necessary to enable this system, including methods for automatically constructing appropriate experimental units and for creating aggregate variables on those units. we show that applying the resulting designs can identify important causal dependencies in real domains, and we provide examples from academic publishing, movie making and marketing, and peer-production systems. finally, we discuss the integration of qeds with other approaches to causal discovery, including joint modeling and directed experimentation.
genesis of postal address reading, current state and future prospects: thirty years of pattern recognition on duty of postal services. abstract intro: an overview is given of the largest industrial ocr application world wide: postal address reading, how it came into being, how it evolved rapidly to its current state-of-the-art and what are its future prospects. some prominent historical-, system-, methodological-, cultural- and social aspects are illuminated.