waashk/dblp huggingface dataset:
cooperative multi-robot localization under communication constraints. this paper addresses the problem of cooperative localization (cl) under severe communication constraints. specifically, we present minimum mean square error (mmse) and maximum a posteriori (map) estimators that can process measurements quantized with as little as one bit per measurement. during cl, each robot quantizes and broadcasts its measurements and receives the quantized observations of its teammates. the quantization process is based on the appropriate selection of thresholds, computed using the current state estimates, that minimize the estimation error metric considered. extensive simulations demonstrate that the proposed iteratively-quantized extended kalman filter (iqekf) and the iteratively quantized map (iqmap) estimator achieve performance indistinguishable of that of their real-valued counterparts (ekf and map, respectively) when using as few as 4 bits for quantizing each robot measurement.
learning to recognize familiar faces in the real world. we present an incremental and unsupervised face recognition system and evaluate it offline using data which were automatically collected by mertz, a robotic platform embedded in real human environment. in an eight-day-long experiment, the robot autonomously detects, tracks, and segments face images during spontaneous interactions with over 500 passersby in public spaces and automatically generates a data set of over 100,000 face images. we describe and evaluate a novel face clustering algorithm using these data (without any manual processing) and also on an existing face recognition database. the face clustering algorithm yields good and robust performance despite the extremely noisy data segmented from the realistic and difficult public environment. in an incremental recognition scheme evaluation, the system is correct 74% of the time when it declares "i don't know this person" and 75.1% of the time when it declares" i know this person, he/she is ..." the latter accuracy improves to 83.8% if the system is allowed some learning curve delay in the beginning.
local decomposition and observability properties for automatic calibration in mobile robotics. this paper considers the problem of sensor self-calibration in mobile robotics by only using a single point feature (e.g. a source of light). in particular, the problem of determining the extrinsic parameters of a bearing sensor mounted on a mobile platform (e.g. a camera) and simultaneously estimating the parameters describing the systematic error in the odometry system is discussed. special attention is devoted to investigate the dependence of the observability properties of these parameters on the chosen robot trajectory. the main contribution provided by this paper is the introduction of a new method to deal with estimation problems in the framework of mobile robotics. specifically, a calibration problem has been considered. however, the same method can be adopted to solve other fundamental estimation problems. the method is based on the theory of distributions which exploits all the system lie symmetries. regarding the considered calibration problem this method allows analytically detecting the combinations of the calibration parameters which are observable for a given robot trajectory. experiments are provided to validate the results.
execution anomaly detection in distributed systems through unstructured log analysis. detection of execution anomalies is very important for the maintenance, development, and performance refinement of large scale distributed systems. execution anomalies include both work flow errors and low performance problems. people often use system logs produced by distributed systems for troubleshooting and problem diagnosis. however, manually inspecting system logs to detect anomalies is unfeasible due to the increasing scale and complexity of distributed systems. therefore, there is a great demand for automatic anomalies detection techniques based on log analysis. in this paper, we propose an unstructured log analysis technique for anomalies detection. in the technique, we propose a novel algorithm to convert free form text messages in log files to log keys without heavily relying on application specific knowledge. the log keys correspond to the log-print statements in the source code which can provide cues of system execution behavior. after converting log messages to log keys, we learn a finite state automaton (fsa) from training log sequences to present the normal work flow for each system component. at the same time, a performance measurement model is learned to characterize the normal execution performance based on the log mes-sages’ timing information. with these learned models, we can automatically detect anomalies in newly input log files. experiments on hadoop and silk show that the technique can effectively detect running anomalies.
combining super-structuring and abstraction on sequence classification. we present an approach to adapting the data representation used by a learner on sequence classification tasks. our approach that exploits the complementary strengths of super-structuring (constructing complex features by combining existing features) and abstraction (grouping of similar features to generate more abstract features), yields smaller and, at the same time, accurate models. super-structuring provides a way to increase the predictive accuracy of the learned models by enriching the data representation (and hence, increases the complexity of the learned models) whereas abstraction helps reduce the number of model parameters by simplifying the data representation. the results of our experiments on two data sets drawn from macromolecular sequence classification applications show that adapting data representation by combining super-structuring and abstraction, makes it possible to construct predictive models that use significantly smaller number of features (by one to three orders of magnitude) than those that are obtained using super-structuring alone, without sacrificing predictive accuracy. our experiments also show that simplifying data representation using abstraction yields better performing models than those obtained using feature selection.
discovering organizational structure in dynamic social network. applying the concept of organizational structure to social network analysis may well represent the power of members and the scope of their power in a social network. in this paper, we propose a data structure, called community tree, to represent the organizational structure in the social network. we combine the pagerank algorithm and random walks on graph to derive the community tree from the social network. in the real world, a social network is constantly changing. hence, the organizational structure in the social network is also constantly changing. in order to present the organizational structure in a dynamic social network, we propose a tree learning algorithm to derive an evolving community tree. the evolving community tree enables a smooth transition between the two community trees and well represents the evolution of organizational structure in the dynamic social network. experiments conducted on real data show our methods are effective at discovering the organizational structure and representing the evolution of organizational structure in a dynamic social network.
topic modeling for sequences of temporal activities. temporally-ordered activity sequences are popular in many real-world domains. this paper presents an lda-style topic model for sequences of temporal activities that captures three features of such sequences: 1) the counts of unique activities, 2) the markov transition dependence and 3) the absolute or relative timestamp on each activity. in modeling the first two features we propose the concept of global transition probability and distinguish it with local transition probability used in previous work. in modeling the third feature, we employ a continuous time distribution to depict the time range of latent topics. the combination of the global transition probability and the temporal information helps to refine the mixture distribution over topics for temporal sequence analysis. we present results on the data of system call traces, showing better next activity prediction and sequence clustering.
vague one-class learning for data streams. in this paper, we formulate a new research problem of learning from vaguely labeled one-class data streams, where the main objective is to allow users to label instance groups, instead of single instances, as positive samples for learning. the batch-labeling, however, raises serious issues because labeled groups may contain non-positive samples, and users may change their labeling interests at any time. to solve this problem, we propose a vague one-class learning (vocl) framework which employs a double weighting approach, at both instance and classifier levels, to build an ensembling framework for learning. at instance level, both local and global filterings are considered for instance weight adjustment. two solutions are proposed to take instance weight values into the classifier training process. at classifier level, a weight value is assigned to each classifier of the ensemble to ensure that learning can quickly adapt to users’ interests. experimental results on synthetic and real-world data streams demonstrate that the proposed vocl framework significantly outperforms other methods for vaguely labeled one-class data streams.
vif regression: a fast regression algorithm for large data. we propose a fast regression algorithm that can substantially reduce the computational complexity of searching, yet retain good accuracy. it also guarantees to discover correlated features that are collectively predictive, and avoid model over-fitting. its capability of controlling mfdr (marginal false discovery rate) statistically enables the one-pass search of the fast algorithm and guarantees the accuracy of the sparse model chosen by the algorithm without cross validation. numerical results show that our algorithm is much faster than any other algorithm and is competitively as accurate as the best but slower algorithms.
accelerated gradient method for multi-task sparse learning problem. many real world learning problems can be recast as multi-task learning problems which utilize correlations among different tasks to obtain better generalization performance than learning each task individually. the feature selection problem in multi-task setting has many applications in fields of computer vision, text classification and bio-informatics. generally, it can be realized by solving a l-1-infinity regularized optimization problem. and the solution automatically yields the joint sparsity among different tasks. however, due to the nonsmooth nature of the l-1-infinity norm, there lacks an efficient training algorithm for solving such problem with general convex loss functions. in this paper, we propose an accelerated gradient method based on an ``optimal'' first order black-box method named after nesterov and provide the convergence rate for smooth convex loss functions. for nonsmooth convex loss functions, such as hinge loss, our method still has fast convergence rate empirically. moreover, by exploiting the structure of the l-1-infinity ball, we solve the black-box oracle in nesterov's method by a simple sorting scheme. our method is suitable for large-scale multi-task learning problem since it only utilizes the first order information and is very easy to implement. experimental results show that our method significantly outperforms the most state-of-the-art methods in both convergence speed and learning accuracy.
p-packsvm: parallel primal gradient descent kernel svm. it is an extreme challenge to produce a nonlinear svm classifier on very large scale data. in this paper we describe a novel p-packsvm algorithm that can solve the support vector machine (svm) optimization problem with an arbitrary kernel. this algorithm embraces the best known stochastic gradient descent method to optimize the primal objective, and has 1/ϵ dependency in complexity to obtain a solution of optimization error ϵ. the algorithm can be highly parallelized with a special packing strategy, and experiences sub-linear speed-up with hundreds of processors. we demonstrate that p-packsvm achieves accuracy sufficiently close to that of svm-light, and overwhelms the state-of-the-art parallel svm trainer psvm in both accuracy and efficiency. as an illustration, our algorithm trains ccat dataset with 800k samples in 13 minutes and 95% accuracy, while psvm needs 5 hours but only has 92% accuracy. we at last demonstrate the capability of p-packsvm on 8 million training samples.
modeling syntactic structures of topics with a nested hmm-lda. latent dirichlet allocation (lda) is a commonly used topic modeling method for text analysis and mining. standard lda treats documents as bags of words, ignoring the syntactic structures of sentences. in this paper, we propose a hybrid model that embeds hidden markov models (hmms) within lda topics to jointly model both the topics and the syntactic structures within each topic. our model is general and subsumes standard lda and hmm as special cases. compared with standard lda and hmm, our model can simultaneously discover both topic-specific content words and background functional words shared among topics. our model can also automatically separate content words that play different roles within a topic. using perplexity as evaluation metric, our model returns lower perplexity for unseen test documents compared with standard lda, which shows its better generalization power than lda. the acm portal is published by the association for computing machinery. copyright © 2010 acm, inc. terms of usage privacy policy code of ethics contact us useful downloads: adobe acrobat quicktime windows media player real player
analysis of subsequence time-series clustering based on moving average. subsequence time-series clustering (stsc), which consists of subsequence cutout with a sliding window and k-means clustering, had been commonly used in time-series data mining. however, a problem was pointed out that stsc always generates moderate sinusoidal patterns independently of the input. to address this problem, we theoretically explain and empirically confirm the similarity between stsc and moving average. the present analysis is consistent with, and simpler than, one of the most important analyses of stsc. we also question the pattern extraction in the time domain and discuss another solution.
finding maximal fully-correlated itemsets in large databases. finding the most interesting correlations among items is essential for problems in many commercial, medical, and scientific domains. much previous research focuses on finding correlated pairs instead of correlated itemsets in which all items are correlated with each other. when designing gift sets, store shelf arrangements, or website product categories, we are more interested in correlated itemsets than correlated pairs. we solve this problem by finding maximal fully-correlated itemsets (mfcis), in which all subsets are closely related to all other subsets. putting the items in an mfci together can promote sales within this itemset. though some exsiting methods find high-correlation itemsets, they suffer from both efficiency and effectiveness problems in large datasets. in this paper, we explore high-dimensional correlation in two ways. first, we expand the set of desirable properties for correlation measures and study the advantages and disadvantages of various measures. second, we propose an mfci framework to decouple the correlation measure from the need for efficient search. by wrapping the best measure in our mfci framework, we take advantage of likelihood ratio’s superiority in evaluating itemsets, make use of the properties of mfci to eliminate itemsets with irrelevant items, and still achieve good computational performance.
to trust or not to trust? predicting online trusts using trust antecedent framework. this paper analyzes the trustor and trustee factors that lead to inter-personal trust using a well studied trust antecedent framework in management science \cite{mayer}. to apply these factors to trust ranking problem in online rating systems, we derive features that correspond to each factor and develop different trust ranking models. the advantage of this approach is that features relevant to trust can be systematically derived so as to achieve good prediction accuracy. through a series of experiments on real data from epinions, we show that even a simple model using the derived features yields good accuracy and outperforms moletrust, a trust propagation based model. svm classifiers using these features also show improvements.
active learning with adaptive heterogeneous ensembles. one common approach to active learning is to iteratively train a single classifier by choosing data points based on its uncertainty, but it is nontrivial to design uncertainty measures unbiased by the choice of classifier. query by committee suggests that given an ensemble of diverse but accurate classifiers, the most informative data points are those that cause maximal disagreement among the predictions of the ensemble members. however the method for finding ensembles appropriate to a given data set remains an open question. in this paper, the random subspace method is combined with active learning to create multiple instances of different classifier types, and an algorithm is introduced that adapts the ratio of different classifier types in the ensemble towards better overall accuracy. here we show that the proposed algorithm outperforms c4.5 with uncertainty sampling, naive bayes with uncertainty sampling, bagging, boosting and the random subspace method with random sampling. to the best of our knowledge, our work is the first to adapt the ratio of classifiers in a heterogeneous ensemble for active learning.
cocost: a computational cost efficient classifier. computational cost of classification is as important as accuracy in on-line classification systems. the computational cost is usually dominated by the cost of computing implicit features of the raw input data. very few efforts have been made to design classifiers which perform effectively with limited computational power; instead, feature selection is usually employed as a pre-processing step to reduce the cost of running traditional classifiers. we present cocost, a novel and effective approach for building classifiers which achieve state-of-the-art classification accuracy, while keeping the expected computational cost of classification low, even without feature selection. cocost employs a wide range of novel cost-aware decision trees, each of which is tuned to specialize in classifying instances from a subset of the input space, and judiciously consults them depending on the input instance in accordance with a cost-aware meta-classifier. experimental results on a network flow detection application show that, our approach can achieve better accuracy than classifiers such as svm and random forests, while achieving 75%-90% reduction in the computational costs.
promoting total efficiency in text clustering via iterative and interactive metric learning. in this paper, we propose a framework to make the text clustering process, as a whole, efficient. in a real text clustering task, an analyst usually has some expectation on the results in mind. however, a single run of a clustering algorithm on the preprocessed data would not satisfy the expectation. then the analyst faces labor-intensive trials for improving the results that involve repetitive feature refinement and parameter tuning. we develop the iterative and interactive metric learning system (iimls) for addressing the challenge. specifically, iimls allows analysts to input feedback on a current clustering result. given the feedback, iimls optimizes metric in the feature space so that the clustering algorithm applied with the refined metric would reflect the feedback. as a byproduct, learned metric may be used for a similar dataset. illustrative examples on a real-world dataset show iimls can dramatically improve efficiency of a text clustering task. the learned “knowledge”, or the metric, is visualized for gaining insights of the optimized feature metric.
aspect guided text categorization with unobserved labels. this paper proposes a novel multiclass classification method and exhibits its advantage in the domain of text categorization with a large label space and, most importantly, when some of the labels were not observed in the training data. the key insight is the introduction of intermediate aspect variables that encode properties of the labels. aspect variables serve as a joint representation for observed and unobserved labels. this way the classification problem can be viewed as a structure learning problem with natural constraints on assignments to the aspect variables. we solve the problem as a constrained optimization problem over multiple learners and show significant improvement in classifying short sentences into a large label space of categories, including previously unobserved categories.
clustering trajectories of moving objects in an uncertain world. mining trajectory databases (td) has recently gained great interest due to the popularity of tracking devices. on the other hand, the inherent presence of uncertainty in td (e.g., due to gps errors) has not been taken yet into account during the mining process. in this paper, we study the effect of uncertainty in td clustering and introduce a three-step approach to deal with it. first, we propose an intuitionistic point vector representation of trajectories that encompasses the underlying uncertainty and introduce an effective distance metric to cope with uncertainty. second, we devise centra, a novel algorithm which tackles the problem of discovering the centroid trajectory of a group of movements. third, we propose a variant of the fuzzy c-means (fcm) clustering algorithm, which embodies centra at its update procedure. the experimental evaluation over real world td demonstrates the efficiency and effectiveness of our approach.
audio classification of bird species: a statistical manifold approach. our goal is to automatically identify which species of bird is present in an audio recording using supervised learning. devising effective algorithms for bird species classification is a preliminary step toward extracting useful ecological data from recordings collected in the field. we propose a probabilistic model for audio features within a short interval of time, then derive its bayes risk-minimizing classifier, and show that it is closely approximated by a nearest-neighbor classifier using kullback-leibler divergence to compare histograms of features. we note that feature histograms can be viewed as points on a statistical manifold, and kl divergence approximates geodesic distances defined by the fisher information metric on such manifolds. motivated by this fact, we propose the use of another approximation to the fisher information metric, namely the hellinger metric. the proposed classifiers achieve over 90% accuracy on a data set containing six species of bird, and outperform support vector machines.
multirelational topic models. in this paper we propose the multirelational topic model (mrtm) for multiple types of link modeling such as citation and coauthor links in document networks. in the citation network, the mrtm models the citation link between each pair of documents as a binary variable conditioned on their topic distributions. in the coauthor network, the mrtm models the coauthor link between each pair of authors as a binary variable conditioned on their expertise distributions. the topic discovery is collectively regularized by multiple relations in both citation and coauthor networks. this model can summarize topics from the document network, predict citation links between documents and coauthor links between authors. efficient inference and learning algorithms are derived based on gibbs sampling. experiments demonstrate that the mrtm significantly outperforms other state-of-the-art single-relational link modeling methods for large scientific document networks.