POCKET: Pruning Random Convolution Kernels for Time Series Classification from a Feature Selection Perspective

• URL: http://arxiv.org/abs/2309.08499v4
• Date: Wed, 24 Jul 2024 19:48:04 GMT
• Title: POCKET: Pruning Random Convolution Kernels for Time Series Classification from a Feature Selection Perspective
• Authors: Shaowu Chen, Weize Sun, Lei Huang, Xiaopeng Li, Qingyuan Wang, Deepu John,
• Abstract summary: A time series classification model, POCKET, is designed to efficiently prune redundant kernels. POCKET prunes up to 60% of kernels without a significant reduction in accuracy and performs 11$times$ faster than its counterparts. Experimental results on diverse time series datasets show that POCKET prunes up to 60% of kernels without a significant reduction in accuracy and performs 11$times$ faster than its counterparts.
• Score: 8.359327841946852
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In recent years, two competitive time series classification models, namely, ROCKET and MINIROCKET, have garnered considerable attention due to their low training cost and high accuracy. However, they rely on a large number of random 1-D convolutional kernels to comprehensively capture features, which is incompatible with resource-constrained devices. Despite the development of heuristic algorithms designed to recognize and prune redundant kernels, the inherent time-consuming nature of evolutionary algorithms hinders efficient evaluation. To efficiently prune models, this paper eliminates feature groups contributing minimally to the classifier, thereby discarding the associated random kernels without direct evaluation. To this end, we incorporate both group-level ($l_{2,1}$-norm) and element-level ($l_2$-norm) regularizations to the classifier, formulating the pruning challenge as a group elastic net classification problem. An ADMM-based algorithm is initially introduced to solve the problem, but it is computationally intensive. Building on the ADMM-based algorithm, we then propose our core algorithm, POCKET, which significantly speeds up the process by dividing the task into two sequential stages. In Stage 1, POCKET utilizes dynamically varying penalties to efficiently achieve group sparsity within the classifier, removing features associated with zero weights and their corresponding kernels. In Stage 2, the remaining kernels and features are used to refit a $l_2$-regularized classifier for enhanced performance. Experimental results on diverse time series datasets show that POCKET prunes up to 60% of kernels without a significant reduction in accuracy and performs 11$\times$ faster than its counterparts. Our code is publicly available at https://github.com/ShaowuChen/POCKET.

Related papers

• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  An ideal set of kernels should: admit a linear parameterization (for tractability); dense in the set of all kernels (for accuracy) Previous algorithms for optimization of kernels were limited to classification and relied on computationally complex Semidefinite Programming (SDP) algorithms. We propose a SVD-QCQPQP algorithm which dramatically reduces the computational complexity as compared with previous SDP-based approaches.
  arXiv  Detail & Related papers  (2023-04-15T04:57:37Z)
• Lifelong Bandit Optimization: No Prior and No Regret [70.94238868711952]
  We develop LIBO, an algorithm which adapts to the environment by learning from past experience. We assume a kernelized structure where the kernel is unknown but shared across all tasks. Our algorithm can be paired with any kernelized or linear bandit algorithm and guarantees optimal performance.
  arXiv  Detail & Related papers  (2022-10-27T14:48:49Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  We propose a novel algorithm that uses a random feature approximation (RFA) of the Neural Network Gaussian Process (NNGP) kernel. Our algorithm provides at least a 100-fold speedup over KIP and can run on a single GPU. Our new method, termed an RFA Distillation (RFAD), performs competitively with KIP and other dataset condensation algorithms in accuracy over a range of large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-21T15:56:13Z)
• Efficient Approximate Kernel Based Spike Sequence Classification [56.2938724367661]
  Machine learning models, such as SVM, require a definition of distance/similarity between pairs of sequences. Exact methods yield better classification performance, but they pose high computational costs. We propose a series of ways to improve the performance of the approximate kernel in order to enhance its predictive performance.
  arXiv  Detail & Related papers  (2022-09-11T22:44:19Z)
• Multiple Kernel Clustering with Dual Noise Minimization [56.009011016367744]
  Multiple kernel clustering (MKC) aims to group data by integrating complementary information from base kernels. In this paper, we rigorously define dual noise and propose a novel parameter-free MKC algorithm by minimizing them. We observe that dual noise will pollute the block diagonal structures and incur the degeneration of clustering performance, and C-noise exhibits stronger destruction than N-noise.
  arXiv  Detail & Related papers  (2022-07-13T08:37:42Z)
• S-Rocket: Selective Random Convolution Kernels for Time Series Classification [36.9596657353794]
  Random convolution kernel transform (Rocket) is a fast, efficient, and novel approach for time series feature extraction. selection of the most important kernels and pruning the redundant and less important ones is necessary to reduce computational complexity and accelerate inference of Rocket. Population-based approach is proposed for selecting the most important kernels.
  arXiv  Detail & Related papers  (2022-03-07T15:02:12Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  adversary-resilient distributed optimization, in which. machines can independently compute gradients, and cooperate. Our algorithm is based on a new concentration technique, and its sample complexity. It is very practical: it improves upon the performance of all prior methods when no. setting machines are present.
  arXiv  Detail & Related papers  (2020-12-28T17:19:32Z)
• Kernel k-Means, By All Means: Algorithms and Strong Consistency [21.013169939337583]
  Kernel $k$ clustering is a powerful tool for unsupervised learning of non-linear data. In this paper, we generalize results leveraging a general family of means to combat sub-optimal local solutions. Our algorithm makes use of majorization-minimization (MM) to better solve this non-linear separation problem.
  arXiv  Detail & Related papers  (2020-11-12T16:07:18Z)
• 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)
• A New Algorithm for Tessellated Kernel Learning [4.264192013842097]
  An ideal set of kernels should: admit a linear parameterization (for tractability); be dense in the set of all kernels (for robustness); be universal (for accuracy) The recently proposed Tesselated Kernels (TKs) is currently the only known class which meets all three criteria. By contrast, the 2-step algorithm proposed here scales to 10,000 data points and extends to the regression problem.
  arXiv  Detail & Related papers  (2020-06-13T18:33:31Z)

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.