waashk/dblp huggingface dataset:
gsml: a unified framework for sparse metric learning. there has been significant recent interest in sparse metric learning (sml) in which we simultaneously learn both a good distance metric and a low-dimensional representation. unfortunately, the performance of existing sparse metric learning approaches is usually limited because the authors assumed certain problem relaxations or they target the sml objective indirectly. in this paper, we propose a generalized sparse metric learning method (gsml). this novel framework offers a unified view for understanding many of the popular sparse metric learning algorithms including the sparse metric learning framework proposed, the large margin nearest neighbor (lmnn), and the d-ranking vector machine (d-ranking vm). moreover, gsml also establishes a close relationship with the pairwise support vector machine. furthermore, the proposed framework is capable of extending many current non-sparse metric learning models such as relevant vector machine (rca) and a state-of-the-art method proposed into their sparse versions. we present the detailed framework, provide theoretical justifications, build various connections with other models, and propose a practical iterative optimization method, making the framework both theoretically important and practically scalable for medium or large datasets. a series of experiments show that the proposed approach can outperform previous methods in terms of both test accuracy and dimension reduction, on six real-world benchmark datasets.
a framework for computing the privacy scores of users in online social networks. a large body of work has been devoted to address corporate-scale privacy concerns related to social networks. the main focus was on how to share social networks owned by organizations without revealing the identities or sensitive relationships of the users involved. not much attention has been given to the privacy risk of users posed by their information sharing activities. in this paper, we approach the privacy concerns arising in online social networks from the individual users’ viewpoint: we propose a framework to compute a privacy score of a user, which indicates the potential privacy risk caused by his participation in the network. our definition of privacy score satisfies the following intuitive properties: the more sensitive the information revealed by a user, the higher his privacy risk. also, the more visible the disclosed information becomes in the network, the higher the privacy risk. we develop mathematical models to estimate both sensitivity and visibility of the information. we apply our methods to synthetic and real-world data and demonstrate their efficacy and practical utility.
accurate estimation of the degree distribution of private networks. we describe an efficient algorithm for releasing a provably private estimate of the degree distribution of a network. the algorithm satisfies a rigorous property of differential privacy, and is also extremely efficient, running on networks of 100 million nodes in a few seconds. theoretical analysis shows that the error scales linearly with the number of unique degrees, whereas the error of conventional techniques scales linearly with the number of nodes. we complement the theoretical analysis with a thorough empirical analysis on real and synthetic graphs, showing that the algorithm's variance and bias is low, that the error diminishes as the size of the input graph increases, and that common analyses like fitting a power-law can be carried out very accurately.
regression learning vector quantization. learning vector quantization (lvq) is a popular class of nearest prototype classifiers for multiclass classification. learning algorithms from this family are widely used because of their intuitively clear learning process and ease of implementation. in this paper we propose an extension of the lvq algorithm to regression. just like the lvq algorithm, the proposed modification uses a supervised learning procedure to learn the best prototype positions, but unlike lvq algorithm for classification, it also learns the best prototype target values. this results in the effective partition of the feature space, similar to the one the k-means algorithm would make. experimental results on benchmark datasets showed that the proposed regression lvq algorithm performs better than the nearest prototype competitors that choose prototypes randomly or through k-means clustering, classification lvq on quantized target values, and similarly to the memory-based parzen window and nearest neighbor algorithms.
joint emotion-topic modeling for social affective text mining. this paper is concerned with the problem of social affective text mining, which aims to discover the connections between social emotions and affective terms based on user-generated emotion labels. we propose a joint emotion-topic model by augmenting latent dirichlet allocation with an additional layer for emotion modeling. it first generates a set of latent topics from emotions, followed by generating affective terms from each topic. experimental results on an online news collection show that the proposed model can effectively identify meaningful latent topics for each emotion. evaluation on emotion prediction further verifies the effectiveness of the proposed model.
scalable algorithms for distribution search. distribution data naturally arise in countless domains, such as meteorology, biology, geology, industry and economics. however, relatively little attention has been paid to data mining for large distribution sets. given n distributions of multiple categories and a query distribution q, we want to find similar clouds (i.e., distributions), to discover patterns, rules and outlier clouds. for example, consider the numerical case of sales of items, where, for each item sold, we record the unit price and quantity; then, each customer is represented as a distribution of 2-d points (one for each item he/she bought). we want to find similar users, e.g., for market segmentation, anomaly/fraud detection. we propose to address this problem and present d-search, which includes fast and effective algorithms for similarity search in large distribution datasets. our main contributions are (1) approximate kl divergence, which can speed up cloud-similarity computations, (2) multi-step sequential scan, which efficiently prunes a significant number of search candidates and leads to a direct reduction in the search cost. we also introduce an extended version of d-search: (3) time-series distribution mining, which finds similar subsequences in time-series distribution datasets. extensive experiments on real multi-dimensional datasets show that our solution achieves up to 2,300 faster wall-clock time over the naive implementation while it does not sacrifice accuracy.
a local scalable distributed expectation maximization algorithm for large peer-to-peer networks. this paper describes a local and distributed expectation maximization algorithm for learning parameters of gaussian mixture models (gmm) in large peer-to-peer (p2p) environments. the algorithm can be used for a variety of well-known data mining tasks in distributed environments such as clustering, anomaly detection, target tracking, and density estimation to name a few, necessary for many emerging p2p applications in bioinformatics, webmining and sensor networks. centralizing all or some of the data to build global models is impractical in such p2p environments because of the large number of data sources, the asynchronous nature of the p2p networks, and dynamic nature of the data/network. the proposed algorithm takes a two-step approach. in the monitoring phase, the algorithm checks if the model ‘quality’ is acceptable by using an efficient local algorithm. this is then used as a feedback loop to sample data from the network and rebuild the gmm when it is outdated. we present thorough experimental results to verify our theoretical claims.
on the (in)security and (im)practicality of outsourcing precise association rule mining. the recent interest in outsourcing it services onto the cloud raises two main concerns: security and cost. one task that could be outsourced is data mining. in vldb 2007, wong et al. propose an approach for outsourcing association rule mining. their approach maps a set of real items into a set of pseudo items, then maps each transaction non-deterministically. this paper, analyzes both the security and costs associated with outsourcing association rule mining. we show how to break the encoding scheme from wong et al. without using context specific information and reduce the security to a one-to-one mapping. we present a stricter notion of security than used by wong et al., and then consider the practicality of outsourcing association rule mining. our results indicate that outsourcing association rule mining may not be practical, if the data owner is concerned with data confidentiality.
mining data streams with labeled and unlabeled training examples. in this paper, we propose a framework to build prediction models from data streams which contain both labeled and unlabeled examples. we argue that due to the increasing data collection ability but limited resources for labeling, stream data collected at hand may only have a small number of labeled examples, whereas a large portion of data remain unlabeled but can be beneficial for learning. unleashing the full potential of the unlabeled instances for stream data mining is, however, a significant challenge, consider that even fully labeled data streams may suffer from the concept drifting, and inappropriate uses of the unlabeled samples may only make the problem even worse. to build prediction models, we first categorize the stream data into four different categories, each of which corresponds to the situation where concept drifting may or may not exist in the labeled and unlabeled data. after that, we propose a relational k-means based transfer semi-supervised svm learning framework (rk-ts3vm), which intends to leverage labeled and unlabeled samples to build prediction models. experimental results and comparisons on both synthetic and real-world data streams demonstrate that the proposed framework is able to help build prediction models more accurate than other simple approaches can offer.
a global-model naive bayes approach to the hierarchical prediction of protein functions. in this paper we propose a new global--model approach for hierarchical classification, where a single global classification model is built by considering all the classes in the hierarchy -- rather than building a number of local classification models as it is more usual in hierarchical classification. the method is an extension of the flat classification algorithm naive bayes. we present the extension made to the original algorithm as well as its evaluation on eight protein function hierarchical classification datasets. the achieved results are positive and show that the proposed global model is better than using a local model approach.
?-anomica: a fast support vector based novelty detection technique. in this paper we propose ν-anomica, a novel anomaly detection technique that can be trained on huge data sets with much reduced running time compared to the benchmark one-class support vector machines algorithm. in ν-anomica, the idea is to train the machine such that it can provide a close approximation to the exact decision plane using fewer training points and without losing much of the generalization performance of the classical approach. we have tested the proposed algorithm on a variety of continuous data sets under different conditions. we show that under all test conditions the developed procedure closely preserves the accuracy of standard one- class support vector machines while reducing both the training time and the test time by 5 − 20 times.
active learning with generalized queries. active learning can actively select or construct examples to label to reduce the number of labeled examples needed for building accurate classifiers. however, previous works of active learning can only ask specific queries. for example, to predict osteoarthritis from a patient dataset with 30 attributes, specific queries always contain values of all these 30 attributes, many of which may be irrelevant. a more natural way is to ask "generalized queries" with don't-care attributes, such as "are people over 50 with knee pain likely to have osteoarthritis?" (with only two attributes: age and type of pain). we assume that the oracle (and human experts) can readily answer those generalized queries by returning probabilistic labels. the power of such generalized queries is that one generalized query may be equivalent to many specific ones. however, overly general queries may receive highly uncertain labels from the oracle, and this makes learning difficult. in this paper, we propose a novel active learning algorithm that asks generalized queries. we demonstrate experimentally that our new method asks significantly fewer queries compared with the previous works of active learning. our method can be readily deployed in real-world tasks where obtaining labeled examples is costly.
a new clustering algorithm based on regions of influence with self-detection of the best number of clusters. clustering methods usually require to know the best number of clusters, or another parameter, e.g. a threshold, which is not ever easy to provide. this paper proposes a new graph-based clustering method called gbc which detects automatically the best number of clusters, without requiring any other parameter. in this method based on regions of influence, a graph is constructed and the edges of the graph having the higher values are cut according to a hierarchical divisive procedure. an index is calculated from the size average of the cut edges which self-detects the more appropriate number of clusters. the results of gbc for 3 quality indices (dunn, silhouette and davies-bouldin) are compared with those of k-means, ward's hierarchical clustering method and dbscan on 8 benchmarks. the experiments show the good performance of gbc in the case of well separated clusters, even if the data are unbalanced, non-convex or with presence of outliers, whatever the shape of the clusters.
conditional models for non-smooth ranking loss functions. learning to rank is an important area at the interface of machine learning, information retrieval and web search. the central challenge in optimizing various measures of ranking loss is that the objectives tend to be non-convex and discontinuous. to make such functions amenable to gradient based optimization procedures one needs to design clever bounds. in recent years, boosting, neural networks, support vector machines, and many other techniques have been applied. however, there is little work on directly modeling a conditional probability pr(y|x_q) where y is a permutation of the documents to be ranked and x_q represents their feature vectors with respect to a query q. a major reason is that the space of y is huge: n! if n documents must be ranked. we first propose an intuitive and appealing expected loss minimization objective, and give an efficient shortcut to evaluate it despite the huge space of ys. unfortunately, the optimization is non-convex, so we propose a convex approximation. we give a new, efficient monte carlo sampling method to compute the objective and gradient of this approximation, which can then be used in a quasi-newton optimizer like lbfgs. extensive experiments with the widely-used letor dataset show large ranking accuracy improvements beyond recent and competitive algorithms.
automatically extracting dialog models from conversation transcripts. there is a growing need for task-oriented natural language dialog systems that can interact with a user to accomplish a given objective. recent work on building task-oriented dialog systems have emphasized the need for acquiring task-specific knowledge from un-annotated conversational data. in our work we acquire task-specific knowledge by defining \textit{sub-task} as the key unit of a task-oriented conversation. we propose an unsupervised, apriori like algorithm that extracts the sub-tasks and their valid orderings from un-annotated human-human conversations. modeling dialogues as a combination of sub-tasks and their valid orderings easily captures the variability in conversations. it also provides us the ability to map our dialogue model to aiml constructs and therefore use off-the-shelf aiml interpreters to build task-oriented chat-bots. we conduct experiments on real world data sets to establish the effectiveness of the sub-task extraction process. we codify the extracted sub-tasks in an aiml knowledge base and build a chatbot using this knowledge base. we also show the usefulness of the chatbot in automatically handling customer requests by performing a user evaluation study.
sparse norm-regularized reconstructive coefficients learning. inspired by the fact that the final decision rule is mainly affected by a small subset of the training samples, i.e., support vector machine(svm) shows that the decision function relies on the few samples that are on or over the margin. we propose a new framework that explicitly strengthen this intuitive fact by adding an $l_1$-norm regularizer. we give different formulations for our framework in different scenarios, and the experiments show that our framework can not only lead to high sparse solutions but also better performance than traditional methods.
unsupervised relation extraction by massive clustering. the goal of information extraction is to automatically generate structured pieces of information from the relevant information contained in text documents. machine learning techniques have been applied to reduce the cost of information extraction system adaptation. however, elements of human supervision strongly bias the learning process. unsupervised learning approaches can avoid these biases. in this paper, we propose an unsupervised approach to learning for relation detection, based on the use of massive clustering ensembles. the results obtained on the ace relation mention detection task outperform in terms of f1 score by 5 points the state of the art of unsupervised techniques for this evaluation framework, in addition to being simpler and more flexible.
projective clustering ensembles. recent advances in data clustering concern clustering ensembles and projective clustering methods, each addressing different issues in clustering problems. in this paper, we consider for the first time the projective clustering ensemble (pce) problem, whose main goal is to derive a proper projective consensus partition from an ensemble of projective clustering solutions. we formalize pce as an optimization problem which does not rely on any particular clustering ensemble algorithm, and which has the ability to handle hard as well as soft data clustering, and different feature weightings. we provide two formulations for pce, namely a two-objective and a single-objective problem, in which the object-based and feature-based representations of the ensemble solutions are taken into account differently. experiments have demonstrated that the proposed methods for pce show clear improvements in terms of accuracy of the output consensus partition.
self-adaptive anytime stream clustering. clustering streaming data requires algorithms which are capable of updating clustering results for the incoming data. as data is constantly arriving, time for processing is limited. clustering has to be performed in a single pass over the incoming data and within the possibly varying inter-arrival times of the stream. likewise, memory is limited, making it impossible to store all data. for clustering, we are faced with the challenge of maintaining a current result that can be presented to the user at any given time. in this work, we propose a parameter free algorithm that automatically adapts to the speed of the data stream. it makes best use of the time available under the current constraints to provide a clustering of the objects seen up to that point. our approach incorporates the age of the objects to reflect the greater importance of more recent data. moreover, we are capable of detecting concept drift, novelty and outliers in the stream. for efficient and effective handling, we introduce the clustree, a compact and self-adaptive index structure for maintaining stream summaries. our experiments show that our approach is capable of handling a multitude of different stream characteristics for accurate and scalable anytime stream clustering.
unsupervised class separation of multivariate data through cumulative variance-based ranking. this paper introduces a new extension of outlier detection approaches and a new concept, class separation through variance. we show that accumulating information about the outlierness of points in multiple subspaces leads to a ranking in which classes with differing variance naturally tend to separate. exploiting this leads to a highly effective and efficient unsupervised class separation approach, especially useful in the difficult case of heavily overlapping distributions. unlike typical outlier detection algorithms, this method can be applied beyond the `rare classes' case with great success. two novel algorithms that implement this approach are provided. additionally, experiments show that the novel methods typically outperform other state-of-the-art outlier detection methods on high dimensional data such as feature bagging, soe1, lof, orca and robust mahalanobis distance and competes even with the leading supervised classification methods.
efficient discovery of confounders in large data sets. given a large transaction database, association analysis is concerned with efficiently finding strongly related objects. unlike traditional associate analysis, where relationships among variables are searched at a global level, we examine confounding factors at a local level. indeed, many real-world phenomena are localized to specific regions and times. these relationships may not be visible when the entire data set is analyzed. specially, confounding effects that change the direction of correlation is the most significant. along this line, we propose to efficiently find confounding effects attributable to local associations. specifically, we derive an upper bound by a necessary condition of confounders, which can help us prune the search space and efficiently identify confounders. experimental results show that the proposed confound algorithm can effectively identify confounders and the computational performance is an order of magnitude faster than benchmark methods.
a deep non-linear feature mapping for large-margin knn classification. knn is one of the most popular data mining methods for classification, but it often fails to work well with inappropriate choice of distance metric or due to the presence of numerous class-irrelevant features. linear feature transformation methods have been widely applied to extract class-relevant information to improve knn classification, which is very limited in many applications. kernels have also been used to learn powerful non-linear feature transformations, but these methods fail to scale to large datasets. in this paper, we present a scalable non-linear feature mapping method based on a deep neural network pretrained with restricted boltzmann machines for improving knn classification in a large-margin framework, which we call dnet-knn. dnet-knn can be used for both classification and for supervised dimensionality reduction. the experimental results on two benchmark handwritten digit datasets and one newsgroup text dataset show that dnet-knn has much better performance than large-margin knn using a linear mapping and knn based on a deep autoencoder pretrained with restricted boltzmann machines.