waashk/dblp huggingface dataset:
detecting time series motifs under uniform scaling. time series motifs are approximately repeated patterns foundwithin the data. such motifs have utility for many data mining algorithms, including rule-discovery,novelty-detection, summarization and clustering. since the formalization of the problem and the introduction of efficient linear time algorithms, motif discovery has been successfully applied tomany domains, including medicine, motion capture, robotics and meteorology. in this work we show that most previous applications of time series motifs have been severely limited by the definition's brittleness to even slight changes of uniform scaling, the speed at which the patterns develop. we introduce a new algorithm that allows discovery of time series motifs with invariance to uniform scaling, and show that it produces objectively superior results in several important domains. apart from being more general than all other motifdiscovery algorithms, a further contribution of our work isthat it is simpler than previous approaches, in particular we have drastically reduced the number of parameters that need to be specified.
learning the kernel matrix in discriminant analysis via quadratically constrained quadratic programming. the kernel function plays a central role in kernel methods. in this paper, we consider the automated learning of the kernel matrix over a convex combination of pre-specified kernel matrices in regularized kernel discriminant analysis (rkda), which performs lineardiscriminant analysis in the feature space via the kernel trick. previous studies have shown that this kernel learning problem can be formulated as a semidefinite program (sdp), which is however computationally expensive, even with the recent advances in interior point methods. based on the equivalence relationship between rkda and least square problems in the binary-class case, we propose a quadratically constrained quadratic programming (qcqp) formulation for the kernel learning problem, which can be solved more efficiently than sdp. while most existing work on kernel learning deal with binary-class problems only, we show that our qcqp formulation can be extended naturally to the multi-class case. experimental results on both binary-class and multi-class benchmarkdata sets show the efficacy of the proposed qcqp formulations.
webpage understanding: an integrated approach. recent work has shown the effectiveness of leveraging layout and tag-tree structure for segmenting webpages and labeling html elements. however, how to effectively segment and label the text contents inside html elements is still an open problem. since many text contents on a webpage are often text fragments and not strictly grammatical, traditional natural language processing techniques, that typically expect grammatical sentences, are no longer directly applicable. in this paper, we examine how to use layout and tag-tree structure in a principled way to help understand text contents on webpages. we propose to segment and label the page structure and the text content of a webpage in a joint discriminative probabilistic model. in this model, semantic labels of page structure can be leveraged to help text content understanding, and semantic labels ofthe text phrases can be used in page structure understanding tasks such as data record detection. thus, integration of both page structure and text content understanding leads to an integrated solution of webpage understanding. experimental results on research homepage extraction show the feasibility and promise of our approach.
building semantic kernels for text classification using wikipedia. document classification presents difficult challenges due to the sparsity and the high dimensionality of text data, and to the complex semantics of the natural language. the traditional document representation is a word-based vector (bag of words, or bow), where each dimension is associated with a term of the dictionary containing all the words that appear in the corpus. although simple and commonly used, this representation has several limitations. it is essential to embed semantic information and conceptual patterns in order to enhance the prediction capabilities of classification algorithms. in this paper, we overcome the shortages of the bow approach by embedding background knowledge derived from wikipedia into a semantic kernel, which is then used to enrich the representation of documents. our empirical evaluation with real data sets demonstrates that our approach successfully achieves improved classification accuracy with respect to the bow technique, and to other recently developed methods.
local decomposition for rare class analysis. given its importance, the problem of predicting rare classes in large-scale multi-labeled data sets has attracted great attentions in the literature. however, the rare-class problem remains a critical challenge, because there is no natural way developed for handling imbalanced class distributions. this paper thus fills this crucial void by developing a method for classification using local clustering (cog). specifically, for a data set with an imbalanced class distribution, we perform clustering within each large class and produce sub-classes with relatively balanced sizes. then, we apply traditional supervised learning algorithms, such as support vector machines (svms), for classification. indeed, our experimental results on various real-world data sets show that our method produces significantly higher prediction accuracies on rare classes than state-of-the-art methods. furthermore, we show that cog can also improve the performance of traditional supervised learning algorithms on data sets with balanced class distributions.
the structure of information pathways in a social communication network. social networks are of interest to researchers in part because they are thought to mediate the flow of information in communities and organizations. here we study the temporal dynamics of communication using on-line data, including e-mail communication among the faculty and staff of a large university over a two-year period. we formulate a temporal notion of "distance" in the underlying social network by measuring the minimum time required for information to spread from one node to another - a concept that draws on the notion of vector-clocks from the study of distributed computing systems. we find that such temporal measures provide structural insights that are not apparent from analyses of the pure social network topology. in particular, we define the network backbone to be the subgraph consisting of edges on which information has the potential to flow the quickest. we find that the backbone is a sparse graph with a concentration of both highly embedded edges and long-range bridges - a finding that sheds new light on the relationship between tie strength and connectivity in social networks.
enhanced max margin learning on multimodal data mining in a multimedia database. the problem of multimodal data mining in a multimedia database can be addressed as a structured prediction problem where we learn the mapping from an input to the structured and interdependent output variables. in this paper, built upon the existing literature on the max margin based learning, we develop a new max margin learning approach called enhanced max margin learning (emml) framework. in addition, we apply emml framework to developing an effective and efficient solution to the multimodal data mining problem in a multimedia database. the main contributions include: (1) we have developed a new max margin learning approach - the enhanced max margin learning framework that is much more efficient in learning with a much faster convergence rate, which is verified in empirical evaluations; (2) we have applied this emml approach to developing an effective and efficient solution to the multimodal data mining problem that is highly scalable in the sense that the query response time is independent of the database scale, allowing facilitating a multimodal data mining querying to a very large scale multimedia database,and excelling many existing multimodal data mining methods in the literature that do not scale up at all; this advantage is also supported through the complexity analysis as well as empirical evaluations against a state-of-the-art multimodal data mining method from the literature. while emml is a general framework, for the evaluation purpose, we apply it to the berkeley drosophila embryo image database, and report the performance comparison with a state-of-the-art multimodal data mining method.
active learning with direct query construction. active learning may hold the key for solving the data scarcity problem in supervised learning, i.e., the lack of labeled data. indeed, labeling data is a costly process, yet an active learner may request labels of only selected instances, thus reducing labeling work dramatically. most previous works of active learning are, however, pool-based; that is, a pool of unlabeled examples is given and the learner can only select examples from the pool to query for their labels. this type of active learning has several weaknesses. in this paper we propose novel active learning algorithms that construct examples directly to query for labels. we study both a specific active learner based on the decision tree algorithm, and a general active learner that can work with any base learning algorithm. as there is no restriction on what examples to be queried, our methods are shown to often query fewer examples to reduce the predictive error quickly. this casts doubt on the usefulness of the pool in pool-based active learning. nevertheless, our methods can be easily adapted to work with a given pool of unlabeled examples.
association analysis-based transformations for protein interaction networks: a function prediction case study. protein interaction networks are one of the most promising types of biological data for the discovery of functional modules and the prediction of individual protein functions. however, it is known that these networks are both incomplete and inaccurate, i.e., they have spurious edges and lackbiologically valid edges. one way to handle this problem is by transforming the original interaction graph into new graphs that remove spurious edges, add biologically valid ones, and assign reliability scores to the edges constituting the final network. we investigate currently existing methods, as well as propose a robust association analysis-based method for this task. this method is based on the concept of h-confidence, which is a measure that can be used to extract groups of objects having high similarity with each other. experimental evaluation on several protein interaction data sets show that hyperclique-based transformations enhance the performance of standard function prediction algorithms significantly, and thus have merit.
data mining at the crossroads: successes, failures and learning from them. since the 1989 workshop on knowledge discovery in databases, the field has seen sustained growth and interest and has attained significant maturity. the main objectives of this panel will be to reflect on the successes and failures in the field of data mining over the last eighteen years and to examine what insights we can take with us as we move forward.
knowledge discovery of multiple-topic document using parametric mixture model with dirichlet prior. documents, such as those seen on wikipedia and folksonomy, have tended to be assigned with multiple topics as a meta-data.therefore, it is more and more important to analyze a relationship between a document and topics assigned to the document. in this paper, we proposed a novel probabilistic generative model of documents with multiple topics as a meta-data. by focusing on modeling the generation process of a document with multiple topics, we can extract specific properties of documents with multiple topics.proposed model is an expansion of an existing probabilistic generative model: parametric mixture model (pmm). pmm models documents with multiple topics by mixing model parameters of each single topic. since, however, pmm assigns the same mixture ratio to each single topic, pmm cannot take into account the bias of each topic within a document. to deal with this problem, we propose a model that considers dirichlet distribution as a prior distribution of the mixture ratio.we adopt variational bayes method to infer the bias of each topic within a document. we evaluate the proposed model and pmm using medline corpus.the results of f-measure, precision and recall show that the proposed model is more effective than pmm on multiple-topic classification. moreover, we indicate the potential of the proposed model that extracts topics and document-specific keywords using information about the assigned topics.
using hierarchical clustering for learning theontologies used in recommendation systems. ontologies are being successfully used to overcome semanticheterogeneity, and are becoming fundamental elements of the semanticweb. recently, it has also been shown that ontologies can be used tobuild more accurate and more personalized recommendation systems byinferencing missing user's preferences. however, these systemsassume the existence of ontologies, without considering theirconstruction. with product catalogs changing continuously, newtechniques are required in order to build these ontologies in realtime, and autonomously from any expert intervention.this paper focuses on this problem and show that it is possible tolearn ontologies autonomously by using clustering algorithms. results on the movielens and jester data sets show that recommendersystem with learnt ontologies significantly outperform the classical recommendation approach.
practical learning from one-sided feedback. in many data mining applications, online labeling feedback is only available for examples which were predicted to belong to the positive class. such applications includespam filtering in the case where users never checkemails marked "spam", document retrieval where users cannotgive relevance feedback on unretrieved documents,and online advertising where user behavior cannot beobserved for unshown advertisements. one-sided feedback can cripple the performance of classical mistake-driven online learners such as perceptron. previous work under the apple tasting framework showed how to transform standard online learners into successful learners from one sided feedback. however, we find in practice that this transformation may request more labels than necessary to achieve strong performance. in this paper,we employ two active learning methods which reduce the number of labels requested in practice. one method is the use of label efficient active learning. the other method,somewhat surprisingly, is the use of margin-based learners without modification, which we show combines implicit active learning and a greedy strategy to managing the exploration exploitation tradeoff. experimental results show that these methods can be significantly more effective in practice than those using the apple tasting transformation, even on minority class problems.
statistical change detection for multi-dimensional data. this paper deals with detecting change of distribution in multi-dimensional data sets. for a given baseline data set and a set of newly observed data points, we define a statistical test called the density test for deciding if the observed data points are sampled from the underlying distribution that produced the baseline data set. we define a test statistic that is strictly distribution-free under the null hypothesis. our experimental results show that the density test has substantially more power than the two existing methods for multi-dimensional change detection.
spiral: efficient and exact model identification for hidden markov models. hidden markov models (hmms) have received considerable attention in various communities (e.g, speech recognition, neurology and bioinformatic) since many applications that use hmm have emerged. the goal of this work is to identify efficiently and correctly the model in a given dataset that yields the state sequence with the highest likelihood with respect to the query sequence. we propose spiral, a fast search method for hmm datasets. to reduce the search cost, spiral efficiently prunes a significant number of search candidates by applying successive approximations when estimating likelihood. we perform several experiments to verify the effectiveness of spiral. the results show that spiral is more than 500 times faster than the naive method.
information genealogy: uncovering the flow of ideas in non-hyperlinked document databases. we now have incrementally-grown databases of text documents ranging back for over a decade in areas ranging from personal email, to news-articles and conference proceedings. while accessing individual documents is easy, methods for overviewing and understanding these collections as a whole are lacking in number and in scope. in this paper, we address one such global analysis task, namely the problem of automatically uncovering how ideas spread through the collection over time. we refer to this problem as information genealogy. in contrast to bibliometric methods that are limited to collections with explicit citation structure, we investigate content-based methods requiring only the text and timestamps of the documents. in particular, we propose a language-modeling approach and a likelihood ratio test to detect influence between documents in a statistically well-founded way. furthermore, we show how this method can be used to infer citation graphs and to identify the most influential documents in the collection. experiments on the nips conference proceedings and the physics arxiv show that our method is more effective than methods based on document similarity.
information distance from a question to an answer. we provide three key missing pieces of a general theory of information distance [3, 23, 24]. we take bold steps in formulating a revised theory to avoid some pitfalls in practical applications. the new theory is then used to construct a question answering system. extensive experiments are conducted to justify the new theory.
community evolution in dynamic multi-mode networks. a multi-mode network typically consists of multiple heterogeneous social actors among which various types of interactions could occur. identifying communities in a multi-mode network can help understand the structural properties of the network, address the data shortage and unbalanced problems, and assist tasks like targeted marketing and finding influential actors within or between groups. in general, a network and the membership of groups often evolve gradually. in a dynamic multi-mode network, both actor membership and interactions can evolve, which poses a challenging problem of identifying community evolution. in this work, we try to address this issue by employing the temporal information to analyze a multi-mode network. a spectral framework and its scalability issue are carefully studied. experiments on both synthetic data and real-world large scale networks demonstrate the efficacy of our algorithm and suggest its generality in solving problems with complex relationships.
high-quantile modeling for customer wallet estimation and other applications. in this paper we discuss the important practical problem of customer wallet estimation, i.e., estimation of potential spending by customers(rather than their expected spending). for this purpose we utilize quantile modeling, whose goal is to estimate a quantile of the discriminative conditional distribution of the response, rather than the mean, which is the implicit goal of most standard regression approaches. we argue that a notion of wallet can be captured through high quantile modeling (e.g, estimating the 90th percentile), and describe a wallet estimation implementation within ibm's market alignment program (map). we also discuss the wide range of domains where high-quantile modeling can be practically important: estimating opportunities in sales and marketing domains, defining 'surprising' patterns for outlier and fraud detection and more. we survey some existing approaches for quantile modeling, and propose adaptations of nearest-neighbor and regression-tree approaches to quantile modeling. we demonstrate the various models' performance in high quantile estimation in several domains, including our motivating problem of estimating the 'realistic' it wallets of ibm customers.
tracking multiple topics for finding interesting articles. we introduce multiple topic tracking (mtt) for iscore to better recommend news articles for users with multiple interests and to address changes in user interests over time. as an extension of the basic rocchio algorithm, traditional topic detection and tracking, and single-pass clustering, mtt maintains multiple interest profiles to identify interesting articles for a specific user given user-feedback. focusing on only interesting topics enables iscore to discard useless profiles to address changes in user interests and to achieve a balance between resource consumption and classification accuracy. also by relating a topic's interestingness to an article.s interestingness, iscore is able to achieve higher quality results than traditional methods such as the rocchio algorithm. we identify several operating parameters that work well for mtt. using the same parameters, we show that mtt alone yields high quality results for recommending interesting articles from several corpora. the inclusion of mtt improves iscore's performance by 9% in recommending news articles from the yahoo! news rss feeds and the trec11 adaptive filter article collection. and through a small user study, we show that iscore can still perform well when only provided with little user feedback.
a concept-based model for enhancing text categorization. most of text categorization techniques are based on word and/or phrase analysis of the text. statistical analysis of a term frequency captures the importance of the term within a document only. however, two terms can have the same frequency in their documents, but one term contributes moreto the meaning of its sentences than the other term. thus, the underlying model should indicate terms that capture these mantics of text. in this case, the model can capture terms that present the concepts of the sentence, which leads todiscover the topic of the document. a new concept-based model that analyzes terms on the sentence and document levels rather than the traditional analysis of document only is introduced. the concept-based model can effectively discriminate between non-important terms with respect to sentence semantics and terms which hold the concepts that represent the sentence meaning. the proposed model consists of concept-based statistical analyzer, conceptual ontological graph representation,and concept extractor. the term which contributes to the sentence semantics is assigned two different weights by the concept-based statistical analyzer and the conceptual ontological graph representation. these two weights are combined into a new weight. the concepts that have maximum combined weights are selected by the concept extractor. a set of experiments using the proposed concept-basedmodel on different datasets in text categorization is conducted. the experiments demonstrate the comparison between traditional weighting and the concept-based weighting obtained by the combined approach of the concept-based statistical analyzer and the conceptual ontological graph. the evaluation of results is relied on two quality measures, the macro-averaged f1 and the error rate. these quality measures are improved when the newly developedconcept-based model is used to enhance the quality of thetext categorization.