waashk/dblp huggingface dataset:
structured metric learning for high dimensional problems. the success of popular algorithms such as k-means clustering or nearest neighbor searches depend on the assumption that the underlying distance functions reflect domain-specific notions of similarity for the problem at hand. the distance metric learning problem seeks to optimize a distance function subject to constraints that arise from fully-supervised or semisupervised information. several recent algorithms have been proposed to learn such distance functions in low dimensional settings. one major shortcoming of these methods is their failure to scale to high dimensional problems that are becoming increasingly ubiquitous in modern data mining applications. in this paper, we present metric learning algorithms that scale linearly with dimensionality, permitting efficient optimization, storage, and evaluation of the learned metric. this is achieved through our main technical contribution which provides a framework based on the log-determinant matrix divergence which enables efficient optimization of structured, low-parameter mahalanobis distances. experimentally, we evaluate our methods across a variety of high dimensional domains, including text, statistical software analysis, and collaborative filtering, showing that our methods scale to data sets with tens of thousands or more features. we show that our learned metric can achieve excellent quality with respect to various criteria. for example, in the context of metric learning for nearest neighbor classification, we show that our methods achieve 24% higher accuracy over the baseline distance. additionally, our methods yield very good precision while providing recall measures up to 20% higher than other baseline methods such as latent semantic analysis.
cuts3vm: a fast semi-supervised svm algorithm. semi-supervised support vector machine (s3vm) attempts to learn a decision boundary that traverses through low data density regions by maximizing the margin over labeled and unlabeled examples. traditionally, s3vm is formulated as a non-convex integer programming problem and is thus difficult to solve. in this paper, we propose the cutting plane semi-supervised support vector machine (cuts3vm) algorithm, to solve the s3vm problem. specifically, we construct a nested sequence of successively tighter relaxations of the original s3vm problem, and each optimization problem in this sequence could be efficiently solved using the constrained concave-convex procedure (cccp). moreover, we prove theoretically that the cuts3vm algorithm takes time o(sn) to converge with guaranteed accuracy, where n is the total number of samples in the dataset and s is the average number of non-zero features, i.e. the sparsity. experimental evaluations on several real world datasets show that cuts3vm performs better than existing s3vm methods, both in efficiency and accuracy.
model-based document clustering with a collapsed gibbs sampler. model-based algorithms are emerging as a preferred method for document clustering. as computing resources improve, methods such as gibbs sampling have become more common for parameter estimation in these models. gibbs sampling is well understood for many applications, but has not been extensively studied for use in document clustering. we explore the convergence rate, the possibility of label switching, and chain summarization methodologies for document clustering on a particular model, namely a mixture of multinomials model, and show that fairly simple methods can be employed, while still producing clusterings of superior quality compared to those produced with the em algorithm.
weighted graphs and disconnected components: patterns and a generator. the vast majority of earlier work has focused on graphs which are both connected (typically by ignoring all but the giant connected component), and unweighted. here we study numerous, real, weighted graphs, and report surprising discoveries on the way in which new nodes join and form links in a social network. the motivating questions were the following: how do connected components in a graph form and change over time? what happens after new nodes join a network -- how common are repeated edges? we study numerous diverse, real graphs (citation networks, networks in social media, internet traffic, and others); and make the following contributions: (a) we observe that the non-giant connected components seem to stabilize in size, (b) we observe the weights on the edges follow several power laws with surprising exponents, and (c) we propose an intuitive, generative model for graph growth that obeys observed patterns.
mobile call graphs: beyond power-law and lognormal distributions. we analyze a massive social network, gathered from the records of a large mobile phone operator, with more than a million users and tens of millions of calls. we examine the distributions of the number of phone calls per customer; the total talk minutes per customer; and the distinct number of calling partners per customer. we find that these distributions are skewed, and that they significantly deviate from what would be expected by power-law and lognormal distributions. to analyze our observed distributions (of number of calls, distinct call partners, and total talk time), we propose powertrack , a method which fits a lesser known but more suitable distribution, namely the double pareto lognormal (dpln) distribution, to our data and track its parameters over time. using powertrack , we find that our graph changes over time in a way consistent with a generative process that naturally results in the dpln distributions we observe. furthermore, we show that this generative process lends itself to a natural and appealing social wealth interpretation in the context of social networks such as ours. we discuss the application of those results to our model and to forecasting.
banded structure in binary matrices. a 0--1 matrix has a banded structure if both rows and columns can be permuted so that the non-zero entries exhibit a staircase pattern of overlapping rows. the concept of banded matrices has its origins in numerical analysis, where entries can be viewed as descriptions between the problem variables; the bandedness corresponds to variables that are coupled over short distances. banded data occurs also in other applications, for example in the physical mapping problem of the human genome, in paleontological data, in network data and in the discovery of overlapping communities without cycles. we study in this paper the banded structure of binary matrices, give a formal definition of the concept and discuss its theoretical properties. we consider the algorithmic problems of computing how far a matrix is from being banded, and of finding a good submatrix of the original data that exhibits approximate bandedness. finally, we show by experiments on real data from ecology and other applications the usefulness of the concept. our results reveal that bands exist in real datasets and that the final obtained ordering of rows and columns have natural interpretations.
a software system for buzz-based recommendations. in this paper, we present an outline of a software system for buzz-based recommendations. this system is based on a large source of queries in an ecommerce application. the buzz events are detected based on query bursts linked to external entities like news and inventory information. a semantic neighborhood of the chosen buzz query is selected and appropriate recommendations are made on products that relate to this neighborhood. the system follows the paradigm of limited quantity merchandizing, in the sense that on a per-day basis the system shows recommendations around a single buzz query with the intent of increasing user curiosity and promoting user activity and stickiness. the system demonstrates the deployment of an interesting application based on kdd principles applied to a high volume industrial context.
spotting out emerging artists using geo-aware analysis of p2p query strings. record label companies would like to identify potential artists as early as possible in their careers, before other companies approach the artists with competing contracts. the vast number of candidates makes the process of identifying the ones with high success potential time consuming and laborious. this paper demonstrates how datamining of p2p query strings can be used in order to mechanize most of this detection process. using a unique intercepting system over the gnutella network, we were able to capture an unprecedented amount of geographically identified (geo-aware) queries, allowing us to investigate the diffusion of music related queries in time and space. our solution is based on the observation that emerging artists, especially rappers, have a discernible stronghold of fans in their hometown area, where they are able to perform and market their music. in a file sharing network, this is reflected as a delta function spatial distribution of content queries. using this observation, we devised a detection algorithm for emerging artists, that looks for performers with sharp increase in popularity in a small geographic region though still unnoticable nation wide. the algorithm can suggest a short list of artists with breakthrough potential, from which we showed that about 30% translate the potential to national success.
cut-and-stitch: efficient parallel learning of linear dynamical systems on smps. multi-core processors with ever increasing number of cores per chip are becoming prevalent in modern parallel computing. our goal is to make use of the multi-core as well as multi-processor architectures to speed up data mining algorithms. specifically, we present a parallel algorithm for approximate learning of linear dynamical systems (lds), also known as kalman filters (kf). ldss are widely used in time series analysis such as motion capture modeling, visual tracking etc. we propose cut-and-stitch (cas), a novel method to handle the data dependencies from the chain structure of hidden variables in lds, so as to parallelize the em-based parameter learning algorithm. we implement the algorithm using openmp on both a supercomputer and a quad-core commercial desktop. the experimental results show that parallel algorithms using cut-and-stitch achieve comparable accuracy and almost linear speedups over the serial version. in addition, cut-and-stitch can be generalized to other models with similar linear structures such as hidden markov models (hmm) and switching kalman filters (skf).
relational learning via collective matrix factorization. relational learning is concerned with predicting unknown values of a relation, given a database of entities and observed relations among entities. an example of relational learning is movie rating prediction, where entities could include users, movies, genres, and actors. relations encode users' ratings of movies, movies' genres, and actors' roles in movies. a common prediction technique given one pairwise relation, for example a #users x #movies ratings matrix, is low-rank matrix factorization. in domains with multiple relations, represented as multiple matrices, we may improve predictive accuracy by exploiting information from one relation while predicting another. to this end, we propose a collective matrix factorization model: we simultaneously factor several matrices, sharing parameters among factors when an entity participates in multiple relations. each relation can have a different value type and error distribution; so, we allow nonlinear relationships between the parameters and outputs, using bregman divergences to measure error. we extend standard alternating projection algorithms to our model, and derive an efficient newton update for the projection. furthermore, we propose stochastic optimization methods to deal with large, sparse matrices. our model generalizes several existing matrix factorization methods, and therefore yields new large-scale optimization algorithms for these problems. our model can handle any pairwise relational schema and a wide variety of error models. we demonstrate its efficiency, as well as the benefit of sharing parameters among relations.
detecting privacy leaks using corpus-based association rules. detecting inferences in documents is critical for ensuring privacy when sharing information. in this paper, we propose a refined and practical model of inference detection using a reference corpus. our model is inspired by association rule mining: inferences are based on word co-occurrences. using the model and taking the web as the reference corpus, we can find inferences and measure their strength through web-mining algorithms that leverage search engines such as google or yahoo!. our model also includes the important case of private corpora, to model inference detection in enterprise settings in which there is a large private document repository. we find inferences in private corpora by using analogues of our web-mining algorithms, relying on an index for the corpus rather than a web search engine. we present results from two experiments. the first experiment demonstrates the performance of our techniques in identifying all the keywords that allow for inference of a particular topic (e.g. "hiv") with confidence above a certain threshold. the second experiment uses the public enron e-mail dataset. we postulate a sensitive topic and use the enron corpus and the web together to find inferences for the topic. these experiments demonstrate that our techniques are practical, and that our model of inference based on word co-occurrence is well-suited to efficient inference detection.
volatile correlation computation: a checkpoint view. recent years have witnessed increased interest in computing strongly correlated pairs in very large databases. most previous studies have been focused on static data sets. however, in real-world applications, input data are often dynamic and must continually be updated. with such large and growing data sets, new research efforts are expected to develop an incremental solution for correlation computing. along this line, in this paper, we propose a check-point algorithm that can efficiently incorporate new transactions for correlation computing as they become available. specifically, we set a checkpoint to establish a computation buffer, which can help us determine an upper bound for the correlation. this checkpoint bound can be exploited to identify a list of candidate pairs, which will be maintained and computed for correlations as new transactions are added into the database. however, if the total number of new transactions is beyond the buffer size, a new upper bound is computed by the new checkpoint and a new list of candidate pairs is identified. experimental results on real-world data sets show that check-point can significantly reduce the correlation computing cost in dynamic data sets and has the advantage of compacting the use of memory space.
: a system for online review structurization. in this paper, we present a system called cro (chinese review observer) for online product review structurization. by structurization, we mean identifying, extracting and summarizing information from unstructured review text to a structured table. the core tasks include review collection, product feature and user opinion extraction, and polarity analysis of opinions. existing research in this area is mainly english text oriented. to deal with chinese effectively, we propose several novel approaches for fulfilling the core tasks. then we integrated these approaches and implement the whole procedure of review structurization in the system cro. running results for reviews of real products show its performance is satisfactory.
hypergraph spectral learning for multi-label classification. a hypergraph is a generalization of the traditional graph in which the edges are arbitrary non-empty subsets of the vertex set. it has been applied successfully to capture high-order relations in various domains. in this paper, we propose a hypergraph spectral learning formulation for multi-label classification, where a hypergraph is constructed to exploit the correlation information among different labels. we show that the proposed formulation leads to an eigenvalue problem, which may be computationally expensive especially for large-scale problems. to reduce the computational cost, we propose an approximate formulation, which is shown to be equivalent to a least squares problem under a mild condition. based on the approximate formulation, efficient algorithms for solving least squares problems can be applied to scale the formulation to very large data sets. in addition, existing regularization techniques for least squares can be incorporated into the model for improved generalization performance. we have conducted experiments using large-scale benchmark data sets, and experimental results show that the proposed hypergraph spectral learning formulation is effective in capturing the high-order relations in multi-label problems. results also indicate that the approximate formulation is much more efficient than the original one, while keeping competitive classification performance.
composition attacks and auxiliary information in data privacy. privacy is an increasingly important aspect of data publishing. reasoning about privacy, however, is fraught with pitfalls. one of the most significant is the auxiliary information (also called external knowledge, background knowledge, or side information) that an adversary gleans from other channels such as the web, public records, or domain knowledge. this paper explores how one can reason about privacy in the face of rich, realistic sources of auxiliary information. specifically, we investigate the effectiveness of current anonymization schemes in preserving privacy when multiple organizations independently release anonymized data about overlapping populations. 1. we investigate composition attacks, in which an adversary uses independent anonymized releases to breach privacy. we explain why recently proposed models of limited auxiliary information fail to capture composition attacks. our experiments demonstrate that even a simple instance of a composition attack can breach privacy in practice, for a large class of currently proposed techniques. the class includes k-anonymity and several recent variants. 2. on a more positive note, certain randomization-based notions of privacy (such as differential privacy) provably resist composition attacks and, in fact, the use of arbitrary side information.this resistance enables "stand-alone" design of anonymization schemes, without the need for explicitly keeping track of other releases. we provide a precise formulation of this property, and prove that an important class of relaxations of differential privacy also satisfy the property. this significantly enlarges the class of protocols known to enable modular design.
fast collapsed gibbs sampling for latent dirichlet allocation. in this paper we introduce a novel collapsed gibbs sampling method for the widely used latent dirichlet allocation (lda) model. our new method results in significant speedups on real world text corpora. conventional gibbs sampling schemes for lda require o(k) operations per sample where k is the number of topics in the model. our proposed method draws equivalent samples but requires on average significantly less then k operations per sample. on real-word corpora fastlda can be as much as 8 times faster than the standard collapsed gibbs sampler for lda. no approximations are necessary, and we show that our fast sampling scheme produces exactly the same results as the standard (but slower) sampling scheme. experiments on four real world data sets demonstrate speedups for a wide range of collection sizes. for the pubmed collection of over 8 million documents with a required computation time of 6 cpu months for lda, our speedup of 5.7 can save 5 cpu months of computation.
anonymizing transaction databases for publication. this paper considers the problem of publishing "transaction data" for research purposes. each transaction is an arbitrary set of items chosen from a large universe. detailed transaction data provides an electronic image of one's life. this has two implications. one, transaction data are excellent candidates for data mining research. two, use of transaction data would raise serious concerns over individual privacy. therefore, before transaction data is released for data mining, it must be made anonymous so that data subjects cannot be re-identified. the challenge is that transaction data has no structure and can be extremely high dimensional. traditional anonymization methods lose too much information on such data. to date, there has been no satisfactory privacy notion and solution proposed for anonymizing transaction data. this paper proposes one way to address this issue.
using for condensing navigable tag hierarchies from tag clouds. we present the tagflake system, which supports semantically informed navigation within a tag cloud. tagflake relies on tmine for organizing tags extracted from textual content in hierarchical organizations, suitable for navigation, visualization, classification, and tracking. tmine extracts the most significant tag/terms from text documents and maps them onto a hierarchy in such a way that descendant terms are contextually dependent on their ancestors within the given corpus of documents. this provides tagflake with a mechanism for enabling navigation within the tag space and for classification of the text documents based on the contextual structure captured by the created hierarchy. tagflake is language neutral, since it does not rely on any natural language processing technique and is unsupervised.
customer targeting models using actively-selected web content. we consider the problem of predicting the likelihood that a company will purchase a new product from a seller. the statistical models we have developed at ibm for this purpose rely on historical transaction data coupled with structured firmographic information like the company revenue, number of employees and so on. in this paper, we extend this methodology to include additional text-based features based on analysis of the content on each company's website. empirical results demonstrate that incorporating such web content can significantly improve customer targeting. furthermore, we present methods to actively select only the web content that is likely to improve our models, while reducing the costs of acquisition and processing.
a family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances. this work introduces a new family of link-based dissimilarity measures between nodes of a weighted directed graph. this measure, called the randomized shortest-path (rsp) dissimilarity, depends on a parameter θ and has the interesting property of reducing, on one end, to the standard shortest-path distance when θ is large and, on the other end, to the commute-time (or resistance) distance when θ is small (near zero). intuitively, it corresponds to the expected cost incurred by a random walker in order to reach a destination node from a starting node while maintaining a constant entropy (related to θ) spread in the graph. the parameter θ is therefore biasing gradually the simple random walk on the graph towards the shortest-path policy. by adopting a statistical physics approach and computing a sum over all the possible paths (discrete path integral), it is shown that the rsp dissimilarity from every node to a particular node of interest can be computed efficiently by solving two linear systems of n equations, where n is the number of nodes. on the other hand, the dissimilarity between every couple of nodes is obtained by inverting an n x n matrix. the proposed measure can be used for various graph mining tasks such as computing betweenness centrality, finding dense communities, etc, as shown in the experimental section.