TY - JOUR A1 - Froese, Vincent A1 - Jain, Brijnesh A1 - Niedermeier, Rolf A1 - Renken, Malte T1 - Comparing temporal graphs using dynamic time warping JF - Social Network Analysis and Mining N2 - Within many real-world networks, the links between pairs of nodes change over time. Thus, there has been a recent boom in studying temporal graphs. Recognizing patterns in temporal graphs requires a proximity measure to compare different temporal graphs. To this end, we propose to study dynamic time warping on temporal graphs. We define the dynamic tem- poral graph warping (dtgw) distance to determine the dissimilarity of two temporal graphs. Our novel measure is flexible and can be applied in various application domains. We show that computing the dtgw-distance is a challenging (in general) NP-hard optimization problem and identify some polynomial-time solvable special cases. Moreover, we develop a quadratic programming formulation and an efficient heuristic. In experiments on real-world data, we show that the heuristic performs very well and that our dtgw-distance performs favorably in de-anonymizing networks compared to other approaches. Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:898-opus4-38493 VL - 10 SP - 1 EP - 16 PB - Springer Nature ER - TY - JOUR A1 - Jain, Brijnesh T1 - Warped softmax regression for time series classification JF - Knowledge and information systems N2 - Linear models are a mainstay in statistical pattern recognition but do not play a role in time series classification, because they fail to account for temporal variations. To overcome this limitation, we combine linear models with dynamic time warping (dtw). We analyze the resulting warped-linear models theoretically and empirically. The three main theoretical results are (i) the Representation Theorem, (ii) the Matrix Complexity Lemma, and (iii) local Lipschitz continuity of the warped softmax function. The Representation Theorem roughly states that warped-linear models correspond to polytope classifiers in Euclidean spaces. This key result is useful because it simplifies analysis of warped-linear models. For example, it provides a geometric interpretation, points to the label dependency problem, and justifies application of warped-linear models not only on temporal but also on multivariate data. The Representation Theorem together with the Matrix Complexity Lemma reveals that warped-linear models implement a weight trick by weight selection and massive weight sharing. Local Lipschitz continuity of warped softmax functions admits a principled training of warped-linear models by stochastic subgradient methods. Empirical results show that replacing the inner product of linear models with a dtw-score substantially improves its predictive performance. The theoretical and empirical contributions of this article provide a simple and efficient first-trial alternative to nearest-neighbor methods and open up new perspectives for more sophisticated classifiers such as warped deep learning. KW - Dynamic time warping KW - Linear classifier KW - Softmax regression KW - Time series Y1 - 2021 U6 - https://doi.org/10.1007/s10115-020-01533-5 VL - 63 IS - 3 SP - 589 EP - 619 PB - Springer Nature ER - TY - JOUR A1 - Yuan, Jing A1 - Geissler, Christian A1 - Shao, Weijia A1 - Lommatzsch, Andreas A1 - Jain, Brijnesh T1 - When algorithm selection meets Bi-linear Learning to Rank: accuracy and inference time trade off with candidates expansion JF - International Journal of Data Science and Analytics N2 - Algorithm selection (AS) tasks are dedicated to find the optimal algorithm for an unseen problem instance. With the knowledge of problem instances’ meta-features and algorithms’ landmark performances, Machine Learning (ML) approaches are applied to solve AS problems. However, the standard training process of benchmark ML approaches in AS either needs to train the models specifically for every algorithm or relies on the sparse one-hot encoding as the algorithms’ representation. To escape these intermediate steps and form the mapping function directly, we borrow the learning to rank framework from Recommender System (RS) and embed the bi-linear factorization to model the algorithms’ performances in AS. This Bi-linear Learning to Rank (BLR) has proven to work with competence in some AS scenarios and thus is also proposed as a benchmark approach. Thinking from the evaluation perspective in the modern AS challenges, precisely predicting the performance is usually the measuring goal. Though approaches’ inference time also needs to be counted for the running time cost calculation, it’s always overlooked in the evaluation process. The multi-objective evaluation metric Adjusted Ratio of Root Ratios (A3R) is therefore advocated in this paper to balance the trade-off between the accuracy and inference time in AS. Concerning A3R, BLR outperforms other benchmarks when expanding the candidates range to TOP3. The better effect of this candidates expansion results from the cumulative optimum performance during the AS process. We take the further step in the experimentation to represent the advantage of such TOPK expansion, and illustrate that such expansion can be considered as the supplement for the convention of TOP1 selection during the evaluation process. Y1 - 2020 U6 - https://doi.org/10.1007/s41060-020-00229-x PB - Springer Nature ER - TY - JOUR A1 - Jain, Brijnesh T1 - Sufficient conditions for the existence of a sample mean of time series under dynamic time warping JF - Annals of Mathematics and Artificial Intelligence N2 - Time series averaging is an important subroutine for several time series data mining tasks. The most successful approaches formulate the problem of time series averaging as an optimization problem based on the dynamic time warping (DTW) distance. The existence of an optimal solution, called sample mean, is an open problem for more than four decades. Its existence is a necessary prerequisite to formulate exact algorithms, to derive complexity results, and to study statistical consistency. In this article, we propose sufficient conditions for the existence of a sample mean. A key result for deriving the proposed sufficient conditions is the Reduction Theorem that provides an upper bound for the minimum length of a sample mean. Y1 - 2020 U6 - https://doi.org/10.1007/s10472-019-09682-2 VL - 88 SP - 313 EP - 346 PB - Springer Nature ER - TY - CHAP A1 - Voß, Marcus A1 - Jain, Brijnesh A1 - Albayrak, Sahin T1 - Subgradient Methods for Averaging Household Load Profiles under Local Permutations T2 - 2019 IEEE Milan PowerTech, 23-27 June 2019, Milan, Italy N2 - The sample mean is one of the most fundamental concepts in statistics with far-reaching implications for data mining and pattern recognition. Household load profiles are compared to the aggregated levels more intermittent and a specific error measure based on local permutations has been proposed to cope with this when comparing profiles. We formally describe a distance based on this error, the local permutation invariant (LPI) distance, and introduce the sample mean problem in the LPI space. An existing exact solution has exponential complexity and is only tractable for very few profiles. We propose three subgradient-based approximation algorithms and compare them empirically on 100 households of the CER dataset. We find that stochastic subgradient descent can approximate the mean best, while the majorize-minimize mean is a good compromise for applications as no hyperparameter-tuning is needed. We show how the algorithms can be used in forecasting and clustering to achieve more appropriate results than by using the arithmetic mean. KW - Distance measurement KW - Load modeling KW - Approximation methods Y1 - 2019 SN - 978-1-5386-4723-3 U6 - https://doi.org/10.1109/PTC.2019.8810783 SP - 2684 EP - 2689 PB - IEEE ER - TY - JOUR A1 - Brill, Markus A1 - Fluschnik, Till A1 - Froese, Vincent A1 - Jain, Brijnesh A1 - Niedermeier, Rolf A1 - Schultz, David T1 - Exact mean computation in dynamic time warping spaces JF - Data Mining and Knowledge Discovery N2 - Averaging time series under dynamic time warping is an important tool for improving nearest-neighbor classifiers and formulating centroid-based clustering. The most promising approach poses time series averaging as the problem of minimizing a Fréchet function. Minimizing the Fréchet function is NP-hard and so far solved by several heuristics and inexact strategies. Our contributions are as follows: we first discuss some inaccuracies in the literature on exact mean computation in dynamic time warping spaces. Then we propose an exponential-time dynamic program for computing a global minimum of the Fréchet function. The proposed algorithm is useful for benchmarking and evaluating known heuristics. In addition, we present an exact polynomial-time algorithm for the special case of binary time series. Based on the proposed exponential-time dynamic program, we empirically study properties like uniqueness and length of a mean, which are of interest for devising better heuristics. Experimental evaluations indicate substantial deficits of state-of-the-art heuristics in terms of their output quality. Y1 - 2019 U6 - https://doi.org/10.1007/s10618-018-0604-8 VL - 33 SP - 252 EP - 291 PB - Springer Nature ER - TY - JOUR A1 - Jain, Brijnesh T1 - Revisiting inaccuracies of time series averaging under dynamic time warping JF - Pattern Recognition Letters N2 - This article revisits an analysis on (in)accuracies of time series averaging under dynamic time warping (dtw) conducted by Niennattrakul and Ratanamahatana [16]. They proposed a correctness-criterion for dtw-averages and postulated that dtw-averages can drift out of the cluster of time series to be averaged. They claimed that dtw-averages are inaccurate if they violate the correctness-criterion or suffer from the drift-out phenomenon. Furthermore, they conjectured that such inaccuracies are caused by the lack of triangle inequality. In this article, we show that a rectified version of the correctness-criterion is unsatisfiable and that the concept of drift-out is geometrically and operationally inconclusive. Satisfying the triangle inequality is insufficient to achieve correctness and unnecessary to overcome the drift-out phenomenon. We place the concept of drift-out on a principled basis and show that Fréchet means never drift out. The adjusted drift-out is a way to test to which extent an approximated dtw-average is coherent. Empirical results show that approximations obtained by the state-of-the-art averaging methods are incoherent in over a third of all cases. KW - k-means KW - Time series averaging KW - Dynamic time warping KW - Time series Y1 - 2019 U6 - https://doi.org/10.1016/j.patrec.2019.05.022 VL - 125 IS - July SP - 418 EP - 424 PB - Elsevier ER - TY - JOUR A1 - Jain, Brijnesh T1 - Making the dynamic time warping distance warping-invariant JF - Pattern Recognition N2 - The literature postulates that the dynamic time warping (dtw) distance can cope with temporal variations but stores and processes time series in a form as if the dtw-distance cannot cope with such variations. To address this inconsistency, we first show that the dtw-distance is not warping-invariant—despite its name and contrary to its characterization in some publications. The lack of warping-invariance contributes to the inconsistency mentioned above and to a strange behavior. To eliminate these peculiarities, we convert the dtw-distance to a warping-invariant semi-metric, called time-warp-invariant (twi) distance. Empirical results suggest that the error rates of the twi and dtw nearest-neighbor classifier are practically equivalent in a Bayesian sense. However, the twi-distance requires less storage and computation time than the dtw-distance for a broad range of problems. These results challenge the current practice of applying the dtw-distance in nearest-neighbor classification and suggest the proposed twi-distance as a more efficient and consistent option. KW - Nearest-neighbor rule KW - Dynamic time warping KW - Time series KW - Semi-metric Y1 - 2019 U6 - https://doi.org/10.1016/j.patcog.2019.05.016 VL - 94 IS - October SP - 35 EP - 52 PB - Elsevier ER - TY - CHAP A1 - Meder, Michael A1 - Plumbaum, Till A1 - Raczkowski, Aleksander A1 - Jain, Brijnesh A1 - Albayrak, Sahin T1 - Gamification in E-Commerce : Tangible vs. Intangible Rewards T2 - Proceedings of the 22nd International Academic Mindtrek Conference : Academic Mindtrek 2018, Tampere Finland, 10.10.2018 - 11.10.2018 N2 - Increasing user participation or changing behavior are key goals when applying gamification. Existing studies in domains such as education, health, and enterprise show that gamification can have a positive impact on meeting these goals. However, there is still a lack of detailed insights into how certain game design elements affect user behavior and motivation. To gain further insight, this paper presents a user study in the field with 20, 000 participants of a mobile e-commerce application over a one-month time period to analyze the impact of gamification in the e-commerce domain and to compare the effectiveness of tangible versus intangible rewards. Results show that gamification has a positive impact in the e-commerce domain. The study also reveals that tangible rewards increase the user activity substantially more than intangible rewards. We further show how tangible rewards affect certain user types and provide a first discussion on the lastingness of these rewards. Y1 - 2018 SN - 9781450365895 U6 - https://doi.org/10.1145/3275116.3275126 SP - 11 EP - 19 PB - ACM CY - New York, NY ER - TY - JOUR A1 - Froese, Vincent A1 - Jain, Brijnesh A1 - Rymar, Maciej A1 - Welle, Mathias T1 - Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series JF - Algorithmica N2 - Dynamic Time Warping (DTW) is a well-known similarity measure for time series. The standard dynamic programming approach to compute the DTW distance of two length-n time series, however, requires O(n2) time, which is often too slow for real-world applications. Therefore, many heuristics have been proposed to speed up the DTW computation. These are often based on lower bounding techniques, approximating the DTW distance, or considering special input data such as binary or piecewise constant time series. In this paper, we present a first exact algorithm to compute the DTW distance of two run-length encoded time series whose running time only depends on the encoding lengths of the inputs. The worst-case running time is cubic in the encoding length. In experiments we show that our algorithm is indeed fast for time series with short encoding lengths. Y1 - 2022 U6 - https://doi.org/10.1007/s00453-022-01038-3 PB - Springer Nature ER - TY - JOUR A1 - Jain, Brijnesh A1 - Froese, Vincent A1 - Schultz, David T1 - An average-compress algorithm for the sample mean problem under dynamic time warping JF - Journal of Global Optimization N2 - Computing a sample mean of time series under dynamic time warping is NP-hard. Consequently, there is an ongoing research effort to devise efficient heuristics. The majority of heuristics have been developed for the constrained sample mean problem that assumes a solution of predefined length. In contrast, research on the unconstrained sample mean problem is underdeveloped. In this article, we propose a generic average-compress (AC) algorithm to address the unconstrained problem. The algorithm alternates between averaging (A-step) and compression (C-step). The A-step takes an initial guess as input and returns an approximation of a sample mean. Then the C-step reduces the length of the approximate solution. The compressed approximation serves as initial guess of the A-step in the next iteration. The purpose of the C-step is to direct the algorithm to more promising solutions of shorter length. The proposed algorithm is generic in the sense that any averaging and any compression method can be used. Experimental results show that the AC algorithm substantially outperforms current state-of-the-art algorithms for time series averaging. KW - Time series averaging KW - Fréchet function KW - Heuristic KW - Nonconvex optimization Y1 - 2023 U6 - https://doi.org/10.1007/s10898-023-01294-9 PB - Springer ER - TY - BOOK A1 - Schultz, David A1 - Jain, Brijnesh T1 - Nonsmooth Analysis and Subgradient Methods for Averaging in Dynamic Time Warping Spaces N2 - Time series averaging in dynamic time warping (DTW) spaces has been successfully applied to improve pattern recognition systems. This article proposes and analyzes subgradient methods for the problem of finding a sample mean in DTW spaces. The class of subgradient methods generalizes existing sample mean algorithms such as DTW Barycenter Averaging (DBA). We show that DBA is a majorize-minimize algorithm that converges to necessary conditions of optimality after finitely many iterations. Empirical results show that for increasing sample sizes the proposed stochastic subgradient (SSG) algorithm is more stable and finds better solutions in shorter time than the DBA algorithm on average. Therefore, SSG is useful in online settings and for non-small sample sizes. The theoretical and empirical results open new paths for devising sample mean algorithms: nonsmooth optimization methods and modified variants of pairwise averaging methods. Y1 - 2017 U6 - https://doi.org/10.48550/arXiv.1701.06393 ER - TY - JOUR A1 - Jain, Brijnesh A1 - Schultz, David T1 - Asymmetric learning vector quantization for efficient nearest neighbor classification in dynamic time warping spaces JF - Pattern Recognition N2 - The nearest neighbor method together with the dynamic time warping (DTW) distance is one of the most popular approaches in time series classification. This method suffers from high storage and computation requirements for large training sets. As a solution to both drawbacks, this article extends learning vector quantization (LVQ) from Euclidean spaces to DTW spaces. The proposed generic LVQ scheme uses asymmetric weighted averaging as update rule. We theoretically justify the asymmetric LVQ scheme via subgradient techniques and by the margin-growth principle. In addition, we show that the decision boundary of two prototypes from different classes is piecewise quadratic. Empirical results exhibited superior performance of asymmetric generalized LVQ (GLVQ) over other state-of-the-art prototype generation methods for nearest neighbor classification. Y1 - 2018 U6 - https://doi.org/10.1016/j.patcog.2017.10.029 VL - 76 SP - 349 EP - 366 PB - Elsevier ER -