Use Short Isometric Shapelets to Accelerate Binary Time Series Classification

• URL: http://arxiv.org/abs/1912.11982v2
• Date: Sun, 20 Dec 2020 09:44:08 GMT
• Title: Use Short Isometric Shapelets to Accelerate Binary Time Series Classification
• Authors: Weibo Shu, Yaqiang Yao, Shengfei Lyu, Jinlong Li, and Huanhuan Chen
• Abstract summary: We introduce a novel algorithm, i.e. short isometric shapelet transform, which contains two strategies to reduce the time complexity. The theoretical evidences of these two strategies are presented to guarantee a near-lossless accuracy under some preconditions.
• Score: 28.469831845459183
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the research area of time series classification, the ensemble shapelet transform algorithm is one of state-of-the-art algorithms for classification. However, its high time complexity is an issue to hinder its application since its base classifier shapelet transform includes a high time complexity of a distance calculation and shapelet selection. Therefore, in this paper we introduce a novel algorithm, i.e. short isometric shapelet transform, which contains two strategies to reduce the time complexity. The first strategy of SIST fixes the length of shapelet based on a simplified distance calculation, which largely reduces the number of shapelet candidates as well as speeds up the distance calculation in the ensemble shapelet transform algorithm. The second strategy is to train a single linear classifier in the feature space instead of an ensemble classifier. The theoretical evidences of these two strategies are presented to guarantee a near-lossless accuracy under some preconditions while reducing the time complexity. Furthermore, empirical experiments demonstrate the superior performance of the proposed algorithm.

Related papers

• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two principled algorithms for the test-time compute of large language models. We prove theoretically that the failure probability of one algorithm decays to zero exponentially as its test-time compute grows.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Approximating Metric Magnitude of Point Sets [4.522729058300309]
  Metric magnitude is a measure of the "size" of point clouds with many desirable geometric properties. It has been adapted to various mathematical contexts and recent work suggests that it can enhance machine learning and optimization algorithms. In this paper, we study the magnitude problem, and show efficient ways of approximating it. We show that it can be cast as a convex optimization problem, but not as a submodular optimization. The paper describes two new algorithms - an iterative approximation algorithm that converges fast and is accurate, and a subset selection method that makes the computation even faster.
  arXiv  Detail & Related papers  (2024-09-06T17:15:28Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Diffeomorphic Transformations for Time Series Analysis: An Efficient Approach to Nonlinear Warping [0.0]
  The proliferation and ubiquity of temporal data across many disciplines has sparked interest for similarity, classification and clustering methods. Traditional distance measures such as the Euclidean are not well-suited due to the time-dependent nature of the data. This thesis proposes novel elastic alignment methods that use parametric & diffeomorphic warping transformations.
  arXiv  Detail & Related papers  (2023-09-25T10:51:47Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Smooth Deformation Field-based Mismatch Removal in Real-time [10.181846237133167]
  Non-rigid deformation makes it difficult to remove mismatches because no parametric transformation can be found. We propose an algorithm based on the re-weighting and 1-point RANSAC strategy (R1P-RNSC) We show that the combination of the two algorithms has the best accuracy compared to other state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-07-16T18:20:25Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  We investigate how large should a training set be to ensure that a parameter's average metrics performance over the training set is close to its expected, future performance. We show that if this approximation holds under the L-infinity norm, we can provide strong sample complexity bounds. We empirically evaluate our bounds in the context of integer programming, one of the most powerful tools in computer science.
  arXiv  Detail & Related papers  (2020-06-21T15:32:21Z)
• Solution Path Algorithm for Twin Multi-class Support Vector Machine [6.97711662470035]
  The paper is devoted to the fast regularization parameter tuning algorithm for the twin multi-class support vector machine. A new sample dataset division method is adopted and the Lagrangian multipliers are proved to be piecewise linear. The proposed method can achieve good classification performance with reducing the computational cost of grid search method from exponential level to the constant level.
  arXiv  Detail & Related papers  (2020-05-30T14:05:46Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.