We propose a low-shot image classification method called Limo, which can train an accurate image classification model under conditions of acute data scarcity. Limo uniquely assembles existing knowledge from a set of diverse models and builds a novel mixture of experts architecture for low-shot image classification. Limo’s architecture introduces minimal number of new model parameters, such that the added parameters can be tuned even with little training data. This characteristic is especially important because, by definition, there is insufficient data in the low-shot setting to learn new model parameters. We demonstrate with extensive experimental evaluation that Limo achieves remarkable accuracy compared to state-of-the-art zero-shot and high-shot image classification approaches.

In this paper, we present a method for constructing a feature-engineered random forest by transforming the features of a given data set using a set of diverse and randomized transforms. The transformed features are then used for creating splits at each node of a random forest. In particular, we use sum-product features because of their strong expressive power. This type of on-the-fly feature engineering has significant advantages over traditional random forests because it adds to the diversity of the splits. Such a diversity further helps in variance reduction; over and above the variance reduction ability offered by traditional random forests. We show the advantages of the proposed approach over traditional random forests and other well-established baselines using extensive experimental evaluation.

Spectral clustering is one of the most popular modern clustering algorithms. It is easy to implement, can be solved efficiently, and very often outperforms other traditional clustering algorithms such as k-means. However, pectral clustering would be insufficient when dealing with most datasets which have complex statistical properties and quires the user to specify the number of clusters (called k). To address these two problems, in this paper, we propose an approach to extending spectral clustering with deep embedding and estimation of the number of clusters. Specifically, we first generate the deep embedding via learning a deep autoencoder, which transforms the raw data into the lower dimensional representations that suitable for clustering. We then provide an effective method to estimate the number of clusters by learning a softmax autoencoder from the deep embedding. We finally extend spectral clustering with the learned embedding and the estimated number. An extensive experimental study on several image and text datasets illustrates the effectiveness and efficiency of our approach.

Recent experimental studies have shown that the support vector machine and the random forest are "stand out" models that outperform most other supervised learning methods in benchmarked evaluations on real-world data sets. Studies have also established that both these models are closely related to nearest neighbor classifiers. Due to this connection, one would expect a similar performance from a nearest neighbor classifier; however, the latter lags greatly behind the support vector machine and the random forest in most evaluations. On the contrary, the nearest neighbor classifier has great theoretical potential because of its ability to model complex decision boundaries with low bias. Furthermore, it theoretically guarantees an error of no more than twice the Bayes error rate on an infinite data set. In this paper, we examine this obvious disconnect between the great theoretical promise and empirical reality of the nearest neighbor classifier. An additional point is that the random forest and support vector machine can be considered eager forms of the (lazy) nearest neighbor classifier. Inspired by the connections between nearest neighbor classifiers, support vector machines and random forest models, we propose a nearest neighbor classifier that is competitive to these models.

Singular value decomposition (SVD) has been used widely in the literature to recover the missing entries of a matrix. The basic principle in such methods is to assume that the correlated data is distributed with a low-rank structure. The knowledge of the low-rank structure is then used to predict the missing entries. SVD is based on the assumption that the data (user ratings) are distributed on a linear hyperplane. This is not always the case, and the data could often be distributed on a nonlinear hyperplane. Therefore, in this paper, we explore the methodology of kernel feature extraction to complement off-the-shelf methods for improving their accuracy. The extracted features can be used to enhance a variety of existing methods such as biased matrix factorization and SVD++. We present experimental results illustrating the effectiveness of using this approach.

Random forests are among the most successful methods used in data mining because of their extraordinary accuracy and effectiveness. However, their use is primarily limited to multidimensional data because they sample features from the original data set. In this paper, we propose a method for extending random forests to work with any arbitrary set of data objects, as long as similarities can be computed among the data objects. Furthermore, since it is understood that similarity computation between all O(n2) pairs of n objects might be expensive, our method computes only a very small fraction of the O(n2) pairwise similarities between objects to construct the forests. Our results show that the proposed similarity forest approach is very efficient and accurate on a wide variety of data sets. Therefore, this paper significantly extends the applicability of random forest methods to arbitrary data domains. Furthermore, the approach even outperforms traditional random forests on multidimensional data. We show that similarity forests are robust to the noisy similarity values that are ubiquitous in real-world applications. In many practical settings, the similarity values between objects are incompletely specified because of the difficulty in collecting such values. Similarity forests can be used in such cases with straightforward modifications.

In this paper, we introduce autoencoder ensembles for unsupervised outlier detection. One problem with neural networks is that they are sensitive to noise and often require large data sets to work robustly, while increasing data size makes them slow. As a result, there are only a few existing works in the literature on the use of neural networks in outlier detection. This paper shows that neural networks can be a very competitive technique to other existing methods. The basic idea is to randomly vary on the connectivity architecture of the autoencoder to obtain significantly better performance. Furthermore, we combine this technique with an adaptive sampling method to make our approach more efficient and effective. Experimental results comparing the proposed approach with state-of-the-art detectors are presented on several benchmark data sets showing the accuracy of our approach.

Outlier detection algorithms are often computationally intensive because of their need to score each point in the data. Even simple distance-based algorithms have quadratic complexity. High-dimensional outlier detection algorithms such as subspace methods are often even more computationally intensive because of their need to explore different subspaces of the data. In this paper, we propose an exceedingly simple subspace outlier detection algorithm, which can be implemented in a few lines of code, and whose complexity is linear in the size of the data set and the space requirement is constant. We show that this outlier detection algorithm is much faster than both conventional and high-dimensional algorithms and also provides more accurate results. The approach uses randomized hashing to score data points and has a neat subspace interpretation. Furthermore, the approach can be easily generalized to data streams. We present experimental results showing the effectiveness of the approach over other state-of-the-art methods.

Matrix factorization (MF) methods have shown great promise in collaborative filtering (CF). Conventional MF methods usually assume that the correlated data is distributed on a linear hyperplane, which is not always the case. Kernel methods are used widely in SVMs to classify linearly non-separable data, as well as in PCA to discover the non-linear embeddings of data. In this paper, we present a novel method to kernelize matrix factorization for collaborative filtering, which is equivalent to performing the low-rank matrix factorization in a possibly much higher dimensional space that is implicitly defined by the kernel function. Inspired by the success of multiple kernel learning (MKL) methods, we also explore the approach of learning multiple kernels from the rating matrix to further improve the accuracy of prediction. Since the right choice of kernel is usually unknown, our proposed multiple kernel matrix factorization method helps to select effective kernel functions from the candidates. Through extensive experiments on real-world datasets, we show that our proposed method captures the nonlinear correlations among data, which results in improved prediction accuracy compared to the state-of-art CF models.

The problem of outlier detection has been widely studied in existing literature because of its numerous applications in fraud detection, medical diagnostics, fault detection, and intrusion detection. A large category of outlier analysis algorithms have been proposed, such as proximity-based methods and local density-based methods. These methods are effective in finding outliers distributed along linear manifolds. Spectral methods, however, are particularly well suited to finding outliers when the data is distributed along manifolds of arbitrary shape. In practice, the underlying manifolds may have varying density, as a result of which a direct use of spectral methods may not be effective. In this paper, we show how to combine spectral techniques with local density-based methods in order to discover interesting outliers. We present experimental results demonstrating the effectiveness of our approach with respect to well-known competing methods.

The dramatic rise of time-series data in a variety of contexts, such as social networks, mobile sensing, data centre monitoring, etc., has fuelled interest in obtaining real-time insights from such data using distributed stream processing systems. One such extremely valuable insight is the discovery of correlations in real-time from large-scale time-series data. A key challenge in discovering correlations is that the number of time-series pairs that have to be analyzed grows quadratically in the number of time-series, giving rise to a quadratic increase in both computation cost and communication cost between the cluster nodes in a distributed environment. To tackle the challenge, we propose a framework called AEGIS. AEGIS exploits well-established statistical properties to dramatically prune the number of time-series pairs that have to be evaluated for detecting interesting correlations. Our extensive experimental evaluations on real and synthetic datasets establish the efficacy of AEGIS over baselines.

Participatory sensing has emerged as a new data collection paradigm, in which humans use their own devices (cell phone accelerometers, cameras, etc.) as sensors. This paradigm enables to collect a huge amount of data from the crowd for world-wide applications, without spending cost to buy dedicated

The next-generation mobile devices include smart watches, wristbands, wearables (e.g., Google Glass), etc. In the future such devices will constitute a large fraction of the total devices available in the market [1]. Latest studies confirm that location-based services are the most requested feature by developers with a market share of 13B in 2013 and have expected exponential growth [2]. Future location-based applications/services will use the data generated by the new mobile devices for providing enhanced user experience. This paper presents a vision of such next-generation location-based services, which we call LBS 2.0. We present the challenges and opportunities that LBS 2.0 will pose for mobile data management.

Modern positioning technologies enable collecting trajectories from moving objects across different locations over time, typically containing time-varying measurement errors of positioning systems. Unfortunately, current models on uncertain trajectories are incapable of capturing dynamically changing uncertainty in trajectory data, and lack the support of recent progress made in improving localization accuracy. In order to tackle these problems, we address three important issues centric to uncertain trajectory management. First, we propose a flexible trajectory modeling approach that takes into account model-inferred actual positions, time-varying uncertainty, and nondeterministic uncertainty ranges. Second, we develop three estimators that effectively infer evolving densities of trajectory data. Last, we present an efficient mechanism to evaluate probabilistic range queries on those evolving-density trajectories. Empirical results on two large-scale real datasets demonstrate the quality and efficiency of our approach.

Computing statistical measures for large databases of time series is a fundamental primitive for querying and mining time-series data [1]-[6]. This primitive is gaining importance with the increasing number and rapid growth of time series databases. In this paper, we introduce a framework for efficient computation of statistical measures by exploiting the concept of affine relationships. Affine relationships can be used to infer statistical measures for time series, from other related time series, instead of computing them directly; thus, reducing the overall computational cost significantly. The resulting methods exhibit at least one order of magnitude improvement over the best known methods. To the best of our knowledge, this is the first work that presents an unified approach for computing and querying several statistical measures at once. Our approach exploits affine relationships using three key components. First, the AFCLST algorithm clusters the time-series data, such that high-quality affine relationships could be easily found. Second, the SYMEX algorithm uses the clustered time series and efficiently computes the desired affine relationships. Third, the SCAPE index structure produces a many-fold improvement in the performance of processing several statistical queries by seamlessly indexing the affine relationships. Finally, we establish the effectiveness of our approaches by performing comprehensive experimental evaluation on real datasets.

Efficiently querying data collected from Large-area Community driven Sensor Networks (LCSNs) is a new and challenging problem. In our previous works, we proposed adaptive techniques for learning models (e.g., statistical, nonparametric, etc.) from such data, considering the fact that LCSN data is typically geo-temporally skewed. In this paper, we present a demonstration of EnviroMeter. EnviroMeter uses our adaptive model creation techniques for processing continuous queries on community-sensed environmental pollution data. Subsequently, it efficiently pushes current pollution updates to GPS-enabled smartphones (through its Android application) or displays it via a web-interface. We experimentally demonstrate that our model-based query processing approach is orders of magnitude efficient than processing the queries over indexed raw data.

Effectively managing the data generated by Large-area Community driven Sensor Networks (LCSNs) is a new and challenging problem. One important step for managing and querying such sensor network data is to create abstractions of the data in the form of models. These models can then be stored, retrieved, and queried as required. In our OpenSense project, we advocate an adaptive model-cover driven strategy towards effectively managing such data. Our strategy is designed considering the fundamental principles of LCSNs.

Effectively managing the data generated by community-driven mobile geo-sensor networks is a new and challenging problem. One important step for managing and querying sensor network data is to create abstractions of the data in the form of models. These models can then be stored, retrieved, and queried, as required. There has been significant amount of prior literature on using models for query processing [1]-[5]. On the contrary, however, there has been a lack of understanding on developing reliable models, considering the unique characteristics of community-driven geo-sensor networks. In an effort to correct this situation, this paper proposes various approaches for modeling the data from a community-driven mobile geo-sensor network. This data is typically collected over a large geographical area with mobile sensors having uncontrolled or semi-controlled mobility. Therefore, we propose adaptive techniques that take into account such mobility patterns and produce an accurate representation of the sensed spatiotemporal phenomenon. To substantiate our proposals, we perform extensive evaluation of our methods on two real datasets.

Although efficient processing of probabilistic databases is a well-established field, a wide range of applications are still unable to benefit from these techniques due to the lack of means for creating probabilistic databases. In fact, it is a challenging problem to associate concrete probability values with given time-series data for forming a probabilistic database, since the probability distributions used for deriving such probability values vary over time. In this paper, we propose a novel approach to create tuple-level probabilistic databases from (imprecise) time-series data. To the best of our knowledge, this is the first work that introduces a generic solution for creating probabilistic databases from arbitrary time series, which can work in online as well as offline fashion. Our approach consists of two key components. First, the dynamic density metrics that infer time-dependent probability distributions for time series, based on various mathematical models. Our main metric, called the GARCH metric, can robustly capture such evolving probability distributions regardless of the presence of erroneous values in a given time series. Second, the Ω-View builder that creates probabilistic databases from the probability distributions inferred by the dynamic density metrics. For efficient processing, we introduce the σ-cache that reuses the information derived from probability values generated at previous times. Extensive experiments over real datasets demonstrate the effectiveness of our approach.

One of the key issue in microfinance is credit risk assessment. In this paper, exploiting fuzzy symbolic clustering, we have developed a fast turn around time microcredit risk scoring system. From field studies we identified a large number of parameters for credit risk assessment; most of them were subjective and thus our preference for fuzzy symbolic approach. We have proposed two cell phone based models to execute the developed microcredit risk assessment scheme. Experimental results are presented to validate our approach