論文の概要: MomentQuant: an even more minimalist interval method with linear time complexity for time series classification
- arxiv url: http://arxiv.org/abs/2609.05136v1
- Date: Fri, 04 Sep 2026 13:37:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-07 18:15:24.056377
- Title: MomentQuant: an even more minimalist interval method with linear time complexity for time series classification
- Title（参考訳）: MomentQuant: 時系列分類のための線形時間複雑性を持つさらにミニマリスト区間法
- Abstract要約: 時系列データは、多くの現実世界のアプリケーションや多くの領域で非常に一般的である。
時系列分類は、新しい、目に見えない各時系列にラベルを割り当てることによって構成される。
過去数十年にわたって多くのアルゴリズムが開発され、予測性能と計算コストのトレードオフが一貫して議論されている。
- 参考スコア（独自算出の注目度）: 0.4145742235679815
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: 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.
- Abstract（参考訳）: 時系列データは、多くの現実世界のアプリケーションや多くの領域で非常に一般的であり、機械学習を用いた自動情報抽出への関心が高まっている。
これらのサブフィールドの1つは時系列分類であり、新しい、目に見えない各時系列にラベルを割り当てることで構成されている。
過去数十年にわたって多くのアルゴリズムが開発され、予測性能と計算コストのトレードオフが一貫して議論されている。
再帰的、固定的、二進的間隔から量子を抽出する間隔ベースのアルゴリズムであるQuantは、非常に高速でありながら高い精度を達成できることを示した。
このアルゴリズムをより高速にするための2つの変更を提案する。
1つ目は、全く同じアルゴリズムのより優れた最適化実装である。
2つ目は、正確な量子化ではなく、コーンウォール・フィッシャー展開を用いて近似量子化を導出することである。
この変更は時系列をソートする必要をなくし、計算の複雑さを小さくする。
このアルゴリズムを MomentQuant と呼ぶ。
我々は,Quantの実装が元の実装よりも高速であること,MomentQuantが予測性能をわずかに低下させることで,Quantの実装よりも高速であることを示す。
これらの改善は、トレーニングよりも推論が頻繁に実行される現実のアプリケーションに特に関係している。
関連論文リスト
- Federated stochastic bilevel optimization with fully first-order gradients [57.1147486991903]
フェデレーション行列の2レベル最適化は、機械学習に広く応用されているため、近年積極的に研究されている。
既存のフェデレートされた双レベル最適化アルゴリズムは、二階ヘッセン行列とヤコビ行列の計算を必要とする。
本稿では,一階オーラクルのみに依存する新しいフェデレーション収束分散誘導二段降下アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-09-14T21:12:59Z) - Randomized and quantum approximate matrix multiplication [0.718791111462057]
長い行の文献ではランダム化アルゴリズムを考慮し、より速い時間で近似解を返す。
まず、Cohen-Lewis (99) によるランダムウォークに基づく古典的アルゴリズムの洗練された解析を行い、Sarl'os (06) と Drineas-Kannan-Mahoney (06) によるスケッチに基づく。
次に、他のすべての手法よりも高速な1つの古典的アルゴリズムを生成するコーエン=ルイスの改良を提案する。
論文 参考訳（メタデータ） (2025-10-09T17:44:03Z) - Efficient Quantum Approximate $k$NN Algorithm via Granular-Ball Computing [4.294483824607684]
リアルタイム複雑性は、$k$-Nearest Neighbors($k$NN)が直面する最大の課題の1つ
我々は、Granular-BallベースのQuantum $k$NN(GB-Q$k$NN)と呼ばれる革新的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-05-29T04:16:29Z) - A system identification approach to clustering vector autoregressive time series [50.66782357329375]
基礎となる力学に基づく時系列のクラスタ化は、複雑なシステムモデリングを支援するために研究者を惹きつけている。
現在の時系列クラスタリング手法のほとんどは、スカラー時系列のみを処理し、ホワイトノイズとして扱うか、高品質な特徴構築のためにドメイン知識に依存している。
システム識別アプローチは、機能/測定構造に頼るのではなく、基礎となる自己回帰力学を明示的に考慮することで、ベクトル時系列クラスタリングを処理できる。
論文 参考訳（メタデータ） (2025-05-20T14:31:44Z) - Replicable Learning of Large-Margin Halfspaces [46.91303295440005]
我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。
Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
論文 参考訳（メタデータ） (2024-02-21T15:06:51Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits [3.5707423185282665]
永続ベッチ数を計算するための改良された量子アルゴリズムを提案する。
量子アルゴリズムが実用的なタスクの指数的高速化を達成できるかどうかを論じる。
論文 参考訳（メタデータ） (2022-09-26T17:56:11Z) - OMPQ: Orthogonal Mixed Precision Quantization [72.63889596498004]
混合精度量子化は、ハードウェアの多重ビット幅演算を利用して、ネットワーク量子化の全ポテンシャルを解き放つ。
本稿では、整数プログラミングの損失と高い相関関係にあるネットワーク性の概念であるプロキシメトリックを最適化することを提案する。
このアプローチは、量子化精度にほとんど妥協することなく、検索時間と必要なデータ量を桁違いに削減する。
論文 参考訳（メタデータ） (2021-09-16T10:59:33Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - Quantum-Inspired Classical Algorithm for Principal Component Regression [1.9105479266011323]
本研究では,データ点数に対して時間的多元対数で動作する主成分回帰のアルゴリズムを開発する。
この指数的なスピードアップは、より大きなデータセットにおける潜在的な応用を可能にする。
論文 参考訳（メタデータ） (2020-10-16T20:50:48Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Quantum Ensemble for Classification [2.064612766965483]
機械学習のパフォーマンスを改善する強力な方法は、複数のモデルの予測を組み合わせたアンサンブルを構築することである。
量子重ね合わせ,絡み合い,干渉を利用して分類モデルのアンサンブルを構築する新しい量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-07-02T11:26:54Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。