waashk/dblp huggingface dataset:
balanced allocation with succinct representation. motivated by applications in guaranteed delivery in computational advertising, we consider the general problem of balanced allocation in a bipartite supply-demand setting. our formulation captures the notion of deviation from being balanced by a convex penalty function. while this formulation admits a convex programming solution, we strive for more robust and scalable algorithms. for the case of l1 penalty functions we obtain a simple combinatorial algorithm based on min-cost flow in graphs and show how to precompute a linear amount of information such that the allocation along any edge can be approximated in constant time. we then extend our combinatorial solution to any convex function by solving a convex cost flow. these scalable methods may have applications in other contexts stipulating balanced allocation. we study the performance of our algorithms on large real-world graphs and show that they are efficient, scalable, and robust in practice.
feature selection for support vector regression using probabilistic prediction. this paper presents a novel wrapper-based feature selection method for support vector regression (svr) using its probabilistic predictions. the method computes the importance of a feature by aggregating the difference, over the feature space, of the conditional density functions of the svr prediction with and without the feature. as the exact computation of this importance measure is expensive, two approximations are proposed. the effectiveness of the measure using these approximations, in comparison to several other existing feature selection methods for svr, is evaluated on both artificial and real-world problems. the result of the experiment shows that the proposed method generally performs better, and at least as well as the existing methods, with notable advantage when the data set is sparse.
transfer metric learning by learning task relationships. distance metric learning plays a very crucial role in many data mining algorithms because the performance of an algorithm relies heavily on choosing a good metric. however, the labeled data available in many applications is scarce and hence the metrics learned are often unsatisfactory. in this paper, we consider a transfer learning setting in which some related source tasks with labeled data are available to help the learning of the target task. we first propose a convex formulation for multi-task metric learning by modeling the task relationships in the form of a task covariance matrix. then we regard transfer learning as a special case of multi-task learning and adapt the formulation of multi-task metric learning to the transfer learning setting for our method, called transfer metric learning (tml). in tml, we learn the metric and the task covariances between the source tasks and the target task under a unified convex formulation. to solve the convex optimization problem, we use an alternating method in which each subproblem has an efficient solution. experimental results on some commonly used transfer learning applications demonstrate the effectiveness of our method.
semi-supervised sparse metric learning using alternating linearization optimization. in plenty of scenarios, data can be represented as vectors and then mathematically abstracted as points in a euclidean space. because a great number of machine learning and data mining applications need proximity measures over data, a simple and universal distance metric is desirable, and metric learning methods have been explored to produce sensible distance measures consistent with data relationship. however, most existing methods suffer from limited labeled data and expensive training. in this paper, we address these two issues through employing abundant unlabeled data and pursuing sparsity of metrics, resulting in a novel metric learning approach called semi-supervised sparse metric learning. two important contributions of our approach are: 1) it propagates scarce prior affinities between data to the global scope and incorporates the full affinities into the metric learning; and 2) it uses an efficient alternating linearization method to directly optimize the sparse metric. compared with conventional methods, ours can effectively take advantage of semi-supervision and automatically discover the sparse metric structure underlying input data patterns. we demonstrate the efficacy of the proposed approach with extensive experiments carried out on six datasets, obtaining clear performance gains over the state-of-the-arts.
frequent regular itemset mining. concise representations of frequent itemsets sacrifice readability and direct interpretability by a data analyst of the concise patterns extracted. in this paper, we introduce an extension of itemsets, called regular, with an immediate semantics and interpretability, and a conciseness comparable to closed itemsets. regular itemsets allow for specifying that an item may or may not be present; that any subset of an itemset may be present; and that any non-empty subset of an itemset may be present. we devise a procedure, called regularmine, for mining a set of regular itemsets that is a concise representation of frequent itemsets. the procedure computes a covering, in terms of regular itemsets, of the frequent itemsets in the class of equivalence of a closed one. we report experimental results on several standard dense and sparse datasets that validate the proposed approach.
extracting temporal signatures for comprehending systems biology models. systems biology has made massive strides in recent years, with capabilities to model complex systems including cell division, stress response, energy metabolism, and signaling pathways. concomitant with their improved modeling capabilities, however, such biochemical network models have also become notoriously complex for humans to comprehend. we propose network comprehension as a key problem for the kdd community, where the goal is to create explainable representations of complex biological networks. we formulate this problem as one of extracting temporal signatures from multi-variate time series data, where the signatures are composed of ordinal comparisons between time series components. we show how such signatures can be inferred by formulating the data mining problem as one of feature selection in rank-order space. we propose five new feature selection strategies for rank-order space and assess their selective superiorities. experimental results on budding yeast cell cycle models demonstrate compelling results comparable to human interpretations of the cell cycle.
medical coding classification by leveraging inter-code relationships. medical coding or classification is the process of transforming information contained in patient medical records into standard predefined medical codes. there are several worldwide accepted medical coding conventions associated with diagnoses and medical procedures; however, in the united states the ninth revision of icd(icd-9) provides the standard for coding clinical records. accurate medical coding is important since it is used by hospitals for insurance billing purposes. since after discharge a patient can be assigned or classified to several icd-9 codes, the coding problem can be seen as a multi-label classification problem. in this paper, we introduce a multi-label large-margin classifier that automatically learns the underlying inter-code structure and allows the controlled incorporation of prior knowledge about medical code relationships. in addition to refining and learning the code relationships, our classifier can also utilize this shared information to improve its performance. experiments on a publicly available dataset containing clinical free text and their associated medical codes showed that our proposed multi-label classifier outperforms related multi-label models in this problem.
clustering by synchronization. synchronization is a powerful basic concept in nature regulating a large variety of complex processes ranging from the metabolism in the cell to social behavior in groups of individuals. therefore, synchronization phenomena have been extensively studied and models robustly capturing the dynamical synchronization process have been proposed, e.g. the extensive kuramoto model. inspired by the powerful concept of synchronization, we propose sync, a novel approach to clustering. the basic idea is to view each data object as a phase oscillator and simulate the interaction behavior of the objects over time. as time evolves, similar objects naturally synchronize together and form distinct clusters. inherited from synchronization, sync has several desirable properties: the clusters revealed by dynamic synchronization truly reflect the intrinsic structure of the data set, sync does not rely on any distribution assumption and allows detecting clusters of arbitrary number, shape and size. moreover, the concept of synchronization allows natural outlier handling, since outliers do not synchronize with cluster objects. for fully automatic clustering, we propose to combine sync with the minimum description length principle. extensive experiments on synthetic and real world data demonstrate the effectiveness and efficiency of our approach.
temporal recommendation on graphs via long- and short-term preference fusion. accurately capturing user preferences over time is a great practical challenge in recommender systems. simple correlation over time is typically not meaningful, since users change their preferences due to different external events. user behavior can often be determined by individual's long-term and short-term preferences. how to represent users' long-term and short-term preferences? how to leverage them for temporal recommendation? to address these challenges, we propose session-based temporal graph (stg) which simultaneously models users' long-term and short-term preferences over time. based on the stg model framework, we propose a novel recommendation algorithm injected preference fusion (ipf) and extend the personalized random walk for temporal recommendation. finally, we evaluate the effectiveness of our method using two real datasets on citations and social bookmarking, in which our proposed method ipf gives 15%-34% improvement over the previous state-of-the-art.
probably the best itemsets. one of the main current challenges in itemset mining is to discover a small set of high-quality itemsets. in this paper we propose a new and general approach for measuring the quality of itemsets. the method is solidly founded in bayesian statistics and decreases monotonically, allowing for efficient discovery of all interesting itemsets. the measure is defined by connecting statistical models and collections of itemsets. this allows us to score individual itemsets with the probability of them occuring in random models built on the data. as a concrete example of this framework we use exponential models. this class of models possesses many desirable properties. most importantly, occam's razor in bayesian model selection provides a defence for the pattern explosion. as general exponential models are infeasible in practice, we use decomposable models; a large sub-class for which the measure is solvable. for the actual computation of the score we sample models from the posterior distribution using an mcmc approach. experimentation on our method demonstrates the measure works in practice and results in interpretable and insightful itemsets for both synthetic and real-world data.
tiara: a visual exploratory text analytic system. in this paper, we present a novel exploratory visual analytic system called tiara (text insight via automated responsive analytics), which combines text analytics and interactive visualization to help users explore and analyze large collections of text. given a collection of documents, tiara first uses topic analysis techniques to summarize the documents into a set of topics, each of which is represented by a set of keywords. in addition to extracting topics, tiara derives time-sensitive keywords to depict the content evolution of each topic over time. to help users understand the topic-based summarization results, tiara employs several interactive text visualization techniques to explain the summarization results and seamlessly link such results to the original text. we have applied tiara to several real-world applications, including email summarization and patient record analysis. to measure the effectiveness of tiara, we have conducted several experiments. our experimental results and initial user feedback suggest that tiara is effective in aiding users in their exploratory text analytic tasks.
growing a tree in the forest: constructing folksonomies by integrating structured metadata. many social web sites allow users to annotate the content with descriptive metadata, such as tags, and more recently to organize content hierarchically. these types of structured metadata provide valuable evidence for learning how a community organizes knowledge. for instance, we can aggregate many personal hierarchies into a common taxonomy, also known as a folksonomy, that will aid users in visualizing and browsing social content, and also to help them in organizing their own content. however, learning from social metadata presents several challenges, since it is sparse, shallow, ambiguous, noisy, and inconsistent. we describe an approach to folksonomy learning based on relational clustering, which exploits structured metadata contained in personal hierarchies. our approach clusters similar hierarchies using their structure and tag statistics, then incrementally weaves them into a deeper, bushier tree. we study folksonomy learning using social metadata extracted from the photo-sharing site flickr, and demonstrate that the proposed approach addresses the challenges. moreover, comparing to previous work, the approach produces larger, more accurate folksonomies, and in addition, scales better.
using data mining techniques to address critical information exchange needs in disaster affected public-private networks. crisis management and disaster recovery have gained immense importance in the wake of recent man and nature inflicted calamities. a critical problem in a crisis situation is how to efficiently discover, collect, organize, search and disseminate real-time disaster information. in this paper, we address several key problems which inhibit better information sharing and collaboration between both private and public sector participants for disaster management and recovery. we design and implement a web based prototype implementation of a business continuity information network (bcin) system utilizing the latest advances in data mining technologies to create a user-friendly, internet-based, information-rich service and acting as a vital part of a company's business continuity process. specifically, information extraction is used to integrate the input data from different sources; the content recommendation engine and the report summarization module provide users personalized and brief views of the disaster information; the community generation module develops spatial clustering techniques to help users build dynamic community in disasters. currently, bcin has been exercised at miami-dade county emergency management.
class-specific error bounds for ensemble classifiers. the generalization error, or probability of misclassification, of ensemble classifiers has been shown to be bounded above by a function of the mean correlation between the constituent (i.e., base) classifiers and their average strength. this bound suggests that increasing the strength and/or decreasing the correlation of an ensemble's base classifiers may yield improved performance under the assumption of equal error costs. however, this and other existing bounds do not directly address application spaces in which error costs are inherently unequal. for applications involving binary classification, receiver operating characteristic (roc) curves, performance curves that explicitly trade off false alarms and missed detections, are often utilized to support decision making. to address performance optimization in this context, we have developed a lower bound for the entire roc curve that can be expressed in terms of the class-specific strength and correlation of the base classifiers. we present empirical analyses demonstrating the efficacy of these bounds in predicting relative classifier performance. in addition, we specify performance regions of the roc curve that are naturally delineated by the class-specific strengths of the base classifiers and show that each of these regions can be associated with a unique set of guidelines for performance optimization of binary classifiers within unequal error cost regimes.
boosting with structure information in the functional space: an application to graph classification. boosting is a very successful classification algorithm that produces a linear combination of "weak" classifiers (a.k.a. base learners) to obtain high quality classification models. in this paper we propose a new boosting algorithm where base learners have structure relationships in the functional space. though such relationships are generic, our work is particularly motivated by the emerging topic of pattern based classification for semi-structured data including graphs. towards an efficient incorporation of the structure information, we have designed a general model where we use an undirected graph to capture the relationship of subgraph-based base learners. in our method, we combine both l1 norm and laplacian based l2 norm penalty with logit loss function of logit boost. in this approach, we enforce model sparsity and smoothness in the functional space spanned by the basis functions. we have derived efficient optimization algorithms based on coordinate decent for the new boosting formulation and theoretically prove that it exhibits a natural grouping effect for nearby spatial or overlapping features. using comprehensive experimental study, we have demonstrated the effectiveness of the proposed learning methods.
inferring networks of diffusion and influence. information diffusion and virus propagation are fundamental processes talking place in networks. while it is often possible to directly observe when nodes become infected, observing individual transmissions (i.e., who infects whom or who influences whom) is typically very difficult. furthermore, in many applications, the underlying network over which the diffusions and propagations spread is actually unobserved. we tackle these challenges by developing a method for tracing paths of diffusion and influence through networks and inferring the networks over which contagions propagate. given the times when nodes adopt pieces of information or become infected, we identify the optimal network that best explains the observed infection times. since the optimization problem is np-hard to solve exactly, we develop an efficient approximation algorithm that scales to large datasets and in practice gives provably near-optimal performance. we demonstrate the effectiveness of our approach by tracing information cascades in a set of 170 million blogs and news articles over a one year period to infer how information flows through the online media space. we find that the diffusion network of news tends to have a core-periphery structure with a small set of core media sites that diffuse information to the rest of the web. these sites tend to have stable circles of influence with more general news media sites acting as connectors between them.
grafting-light: fast, incremental feature selection and structure learning of markov random fields. feature selection is an important task in order to achieve better generalizability in high dimensional learning, and structure learning of markov random fields (mrfs) can automatically discover the inherent structures underlying complex data. both problems can be cast as solving an l1-norm regularized parameter estimation problem. the existing grafting method can avoid doing inference on dense graphs in structure learning by incrementally selecting new features. however, grafting performs a greedy step to optimize over free parameters once new features are included. this greedy strategy results in low efficiency when parameter learning is itself non-trivial, such as in mrfs, in which parameter learning depends on an expensive subroutine to calculate gradients. the complexity of calculating gradients in mrfs is typically exponential to the size of maximal cliques. in this paper, we present a fast algorithm called grafting-light to solve the l1-norm regularized maximum likelihood estimation of mrfs for efficient feature selection and structure learning. grafting-light iteratively performs one-step of orthant-wise gradient descent over free parameters and selects new features. this lazy strategy is guaranteed to converge to the global optimum and can effectively select significant features. on both synthetic and real data sets, we show that grafting-light is much more efficient than grafting for both feature selection and structure learning, and performs comparably with the optimal batch method that directly optimizes over all the features for feature selection but is much more efficient and accurate for structure learning of mrfs.
metric forensics: a multi-level approach for mining volatile graphs. advances in data collection and storage capacity have made it increasingly possible to collect highly volatile graph data for analysis. existing graph analysis techniques are not appropriate for such data, especially in cases where streaming or near-real-time results are required. an example that has drawn significant research interest is the cyber-security domain, where internet communication traces are collected and real-time discovery of events, behaviors, patterns, and anomalies is desired. we propose metricforensics, a scalable framework for analysis of volatile graphs. metricforensics combines a multi-level "drill down" approach, a collection of user-selected graph metrics, and a collection of analysis techniques. at each successive level, more sophisticated metrics are computed and the graph is viewed at finer temporal resolutions. in this way, metricforensics scales to highly volatile graphs by only allocating resources for computationally expensive analysis when an interesting event is discovered at a coarser resolution first. we test metricforensics on three real-world graphs: an enterprise ip trace, a trace of legitimate and malicious network traffic from a research institution, and the mit reality mining proximity sensor data. our largest graph has 3m vertices and 32m edges, spanning 4.5 days. the results demonstrate the scalability and capability of metricforensics in analyzing volatile graphs; and highlight four novel phenomena in such graphs: elbows, broken correlations, prolonged spikes, and lightweight stars.