提出更轻量的时序分类方法,速度更快且精度几乎不变。
MomentQuant: an even more minimalist interval method with linear time complexity for time series classification
- 用切比雪夫展开近似分位数,避免排序提升效率
- 算法时间复杂度降至线性,推理速度显著提升
- 适合频繁推理的实时应用场景
时序数据在众多实际应用中普遍存在,时序分类旨在为新出现的未见时序分配标签。尽管已有多种算法,但预测性能与计算成本之间的权衡始终是核心问题。Quant是一种基于区间的算法,通过递归固定二分区间提取分位数,兼具高准确率和高速度。本文提出两项改进:一是对原始Quant进行更优实现;二是引入基于Cornish-Fisher展开的近似分位数替代精确分位数,无需排序,从而降低计算复杂度。新算法称为MomentQuant。实验表明,我们的Quant实现比原版更快,而MomentQuant进一步加速,仅以微小精度损失为代价。该改进在真实场景中尤为关键,因推理次数远超训练。
原文摘要 · Abstract (English)
Time series data is very common in many real-world applications and in numerous domains, with increasing interest for automated information extraction using machine learning. One of these subfields is time series classification, which consists in assigning a label to each new, unseen time series. Many algorithms have been developed over the past decades, with the trade-off between predictive performance and computational cost being consistently discussed. Quant, an interval-based algorithm extracting quantiles from recursive, fixed, dyadic intervals, was shown to achieve high accuracy, while being very fast. We propose two changes to make this algorithm even faster. The first one is a better optimized implementation of the exact same algorithm. The second one is to derive approximate quantiles, using the Cornish-Fisher expansion, instead of exact quantiles. This change removes the necessity to sort the time series, leading to a smaller computational complexity. We call this novel algorithm MomentQuant. We provide evidence that our implementation of Quant is faster than the original one, and that MomentQuant is even faster than our implementation of Quant, at the cost of a tiny decrease in predictive performance. These improvements are especially relevant for real-life applications, where inference is performed much more often than training.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。