@article{FroeseJainNiedermeieretal., author = {Froese, Vincent and Jain, Brijnesh and Niedermeier, Rolf and Renken, Malte}, title = {Comparing temporal graphs using dynamic time warping}, series = {Social Network Analysis and Mining}, volume = {10}, journal = {Social Network Analysis and Mining}, publisher = {Springer Nature}, doi = {10.1007/s13278-020-00664-5}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:898-opus4-38493}, pages = {1 -- 16}, abstract = {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.}, language = {en} } @article{Jain, author = {Jain, Brijnesh}, title = {Warped softmax regression for time series classification}, series = {Knowledge and information systems}, volume = {63}, journal = {Knowledge and information systems}, number = {3}, publisher = {Springer Nature}, doi = {10.1007/s10115-020-01533-5}, pages = {589 -- 619}, abstract = {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.}, language = {en} } @article{YuanGeisslerShaoetal., author = {Yuan, Jing and Geissler, Christian and Shao, Weijia and Lommatzsch, Andreas and Jain, Brijnesh}, title = {When algorithm selection meets Bi-linear Learning to Rank: accuracy and inference time trade off with candidates expansion}, series = {International Journal of Data Science and Analytics}, journal = {International Journal of Data Science and Analytics}, publisher = {Springer Nature}, doi = {10.1007/s41060-020-00229-x}, pages = {17}, abstract = {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.}, language = {en} } @article{Jain, author = {Jain, Brijnesh}, title = {Sufficient conditions for the existence of a sample mean of time series under dynamic time warping}, series = {Annals of Mathematics and Artificial Intelligence}, volume = {88}, journal = {Annals of Mathematics and Artificial Intelligence}, publisher = {Springer Nature}, doi = {10.1007/s10472-019-09682-2}, pages = {313 -- 346}, abstract = {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.}, language = {en} } @inproceedings{VossJainAlbayrak, author = {Voß, Marcus and Jain, Brijnesh and Albayrak, Sahin}, title = {Subgradient Methods for Averaging Household Load Profiles under Local Permutations}, series = {2019 IEEE Milan PowerTech, 23-27 June 2019, Milan, Italy}, booktitle = {2019 IEEE Milan PowerTech, 23-27 June 2019, Milan, Italy}, publisher = {IEEE}, isbn = {978-1-5386-4723-3}, doi = {10.1109/PTC.2019.8810783}, pages = {2684 -- 2689}, abstract = {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.}, language = {en} } @article{BrillFluschnikFroeseetal., author = {Brill, Markus and Fluschnik, Till and Froese, Vincent and Jain, Brijnesh and Niedermeier, Rolf and Schultz, David}, title = {Exact mean computation in dynamic time warping spaces}, series = {Data Mining and Knowledge Discovery}, volume = {33}, journal = {Data Mining and Knowledge Discovery}, publisher = {Springer Nature}, doi = {10.1007/s10618-018-0604-8}, pages = {252 -- 291}, abstract = {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{\´e}chet function. Minimizing the Fr{\´e}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{\´e}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.}, language = {en} } @article{Jain, author = {Jain, Brijnesh}, title = {Revisiting inaccuracies of time series averaging under dynamic time warping}, series = {Pattern Recognition Letters}, volume = {125}, journal = {Pattern Recognition Letters}, number = {July}, publisher = {Elsevier}, doi = {10.1016/j.patrec.2019.05.022}, pages = {418 -- 424}, abstract = {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{\´e}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.}, language = {en} } @article{Jain, author = {Jain, Brijnesh}, title = {Making the dynamic time warping distance warping-invariant}, series = {Pattern Recognition}, volume = {94}, journal = {Pattern Recognition}, number = {October}, publisher = {Elsevier}, doi = {10.1016/j.patcog.2019.05.016}, pages = {35 -- 52}, abstract = {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.}, language = {en} } @inproceedings{MederPlumbaumRaczkowskietal., author = {Meder, Michael and Plumbaum, Till and Raczkowski, Aleksander and Jain, Brijnesh and Albayrak, Sahin}, title = {Gamification in E-Commerce : Tangible vs. Intangible Rewards}, series = {Proceedings of the 22nd International Academic Mindtrek Conference : Academic Mindtrek 2018, Tampere Finland, 10.10.2018 - 11.10.2018}, booktitle = {Proceedings of the 22nd International Academic Mindtrek Conference : Academic Mindtrek 2018, Tampere Finland, 10.10.2018 - 11.10.2018}, publisher = {ACM}, address = {New York, NY}, isbn = {9781450365895}, doi = {10.1145/3275116.3275126}, pages = {11 -- 19}, abstract = {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.}, language = {en} } @article{FroeseJainRymaretal., author = {Froese, Vincent and Jain, Brijnesh and Rymar, Maciej and Welle, Mathias}, title = {Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series}, series = {Algorithmica}, journal = {Algorithmica}, publisher = {Springer Nature}, doi = {10.1007/s00453-022-01038-3}, pages = {17}, abstract = {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.}, language = {en} } @article{JainFroeseSchultz, author = {Jain, Brijnesh and Froese, Vincent and Schultz, David}, title = {An average-compress algorithm for the sample mean problem under dynamic time warping}, series = {Journal of Global Optimization}, journal = {Journal of Global Optimization}, publisher = {Springer}, doi = {10.1007/s10898-023-01294-9}, abstract = {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.}, language = {en} } @book{SchultzJain, author = {Schultz, David and Jain, Brijnesh}, title = {Nonsmooth Analysis and Subgradient Methods for Averaging in Dynamic Time Warping Spaces}, doi = {10.48550/arXiv.1701.06393}, pages = {30}, abstract = {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.}, language = {en} } @article{JainSchultz, author = {Jain, Brijnesh and Schultz, David}, title = {Asymmetric learning vector quantization for efficient nearest neighbor classification in dynamic time warping spaces}, series = {Pattern Recognition}, volume = {76}, journal = {Pattern Recognition}, publisher = {Elsevier}, doi = {10.1016/j.patcog.2017.10.029}, pages = {349 -- 366}, abstract = {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.}, language = {en} }