Strings and Streams

Maintaining an accurate trained model on an infinite data stream is challenging due to concept drifts that render a learned model inaccurate.Updating the model periodically can be expensive, and so traditional approaches for computationally limited devices involve a variation of online or incremental learning, which tend to be less robust.The advent of heterogeneous architectures and Internet-connected devices gives rise to a new opportunity.A weak processor can call upon a stronger processor or a cloud server to perform a complete batch training pass once a concept drift is detected - trading power or network bandwidth for increased accuracy.We capitalize on this opportunity in two steps.We first develop a computationally efficient bound for changes in any linear model with convex, differentiable loss.We then propose a sliding window-based algorithm that uses a small number of batch model computations to maintain an accurate model of the data stream. It uses the bound to continuously evaluate the difference between the parameters of the existing model and a hypothetical optimal model, triggering computation only as needed.Empirical evaluation on real and synthetic datasets shows that our proposed algorithm adapts well to concept drifts and provides a better tradeoff between the number of model computations and model accuracy than classic concept drift detectors.When predicting changes in electricity prices, for example, we achieve 6

Change point detection plays a fundamental role in many real-world applications,where the goal is to analyze and monitor the behaviour of a data stream.In this paper, we study change detection in binary streams. To this end, weuse a likelihood ratio between two models as a measure for indicatingchange. The first model is a single bernoulli variable while the second modeldivides the stored data in two segments, and models each segment with itsown bernoulli variable. Finding the optimal split can be done in O(n) time,where n is the number of entries since the last change point.This is too expensive for large n. To combat this we propose an approximationscheme that yields (1 - ϵ) approximation in O(ϵ^-1^2 n) time.The speed-up consists of several steps: First we reduce the number of possiblecandidates by adopting a known result from segmentation problems. We then showthat for fixed bernoulli parameters we can find the optimal change point inlogarithmic time. Finally, we show how to construct a candidate listof size O(ϵ^-1 n) for model parameters.We demonstrate empirically the approximation quality and the running time ofour algorithm, showing that we can gain a significant speed-up with a minimalaverage loss in optimality.

String data are often disseminated to support applications such as location-based service provision or DNA sequence analysis. This dissemination, however, may expose sensitive patterns that model confidential knowledge (e.g., trips to mental health clinics from a string representing a user's location history). In this paper, we consider the problem of sanitizing a string by concealing the occurrences of sensitive patterns, while maintaining data utility. First, we propose a time-optimal algorithm, TFS-ALGO, to construct the shortest string preserving the order of appearance and the frequency of all non-sensitive patterns. Such a string allows accurately performing tasks based on the sequential nature and pattern frequencies of the string. Second, we propose a time-optimal algorithm, PFS-ALGO, which preserves a partial order of appearance of non-sensitive patterns but produces a much shorter string that can be analyzed more efficiently. The strings produced by either of these algorithms may reveal the location of sensitive patterns. In response, we propose a heuristic, MCSR-ALGO, which replaces letters in these strings with carefully selected letters, so that sensitive patterns are not reinstated and occurrences of spurious patterns are prevented. We implemented our sanitization approach that applies TFS-ALGO, PFS-ALGO and then MCSR-ALGO and experimentally show that it is effective and efficient.

Both complex and evolving nature of time series structure make forecasting among one of the most important and challenging tasks in time series analysis. Typical methods for forecasting are designed to model time-evolving dependencies between data observations. However, it is generally accepted that none of them is universally valid for every application. Therefore, methods for learning heterogeneous ensembles by combining a diverse set of forecasts together appear as a promising solution to tackle this task. Hitherto, in classical ML literature, ensemble techniques such as stacking, cascading and voting are mostly restricted to operate in a static manner. To deal with changes in the relative performance of models as well as changes in the data distribution, we propose a drift-aware meta-learning approach for adaptively selecting and combining forecasting models. Our assumption is that different forecasting models have different areas of expertise and a varying relative performance. Our method ensures dynamic selection of initial ensemble base models candidates through a performance drift detection mechanism. Since diversity is a fundamental component in ensemble methods, we propose a second stage selection with clustering that is computed after each drift detection. Predictions of final selected models are combined into a single prediction. An exhaustive empirical testing of the method was performed, evaluating both generalization error and scalability of the approach using time series from several real world domains. Empirical results show the competitiveness of the method in comparison to state-of-the-art approaches for combining forecasters.