論文の概要: Geometric-Based Pruning Rules For Change Point Detection in Multiple Independent Time Series

• arxiv url: http://arxiv.org/abs/2306.09555v1
• Date: Thu, 15 Jun 2023 23:56:39 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-19 15:28:10.944328
• Title: Geometric-Based Pruning Rules For Change Point Detection in Multiple Independent Time Series
• Title（参考訳）: 複数の独立時系列における変化点検出のための幾何学的プルーニングルール
• Authors: Liudmila Pishchagina, Guillem Rigaill and Vincent Runge
• Abstract要約: 複数の独立時系列における複数の変化を検出することの問題点を考察する。 PELTアルゴリズムに符号化された不等式に基づくプルーニングルールは、線形時間複雑性をもたらす。 本稿では, 単純な幾何学的形状を用いて, 複数の独立時系列に対する機能的プルーニングの拡張を提案する。
• 参考スコア（独自算出の注目度）: 0.9023847175654603
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of detecting multiple changes in multiple independent time series. The search for the best segmentation can be expressed as a minimization problem over a given cost function. We focus on dynamic programming algorithms that solve this problem exactly. When the number of changes is proportional to data length, an inequality-based pruning rule encoded in the PELT algorithm leads to a linear time complexity. Another type of pruning, called functional pruning, gives a close-to-linear time complexity whatever the number of changes, but only for the analysis of univariate time series. We propose a few extensions of functional pruning for multiple independent time series based on the use of simple geometric shapes (balls and hyperrectangles). We focus on the Gaussian case, but some of our rules can be easily extended to the exponential family. In a simulation study we compare the computational efficiency of different geometric-based pruning rules. We show that for small dimensions (2, 3, 4) some of them ran significantly faster than inequality-based approaches in particular when the underlying number of changes is small compared to the data length.
• Abstract（参考訳）: 複数の独立時系列における複数の変化を検出する問題を考える。 最適セグメンテーションの探索は、与えられたコスト関数に対する最小化問題として表現できる。 この問題を正確に解決する動的プログラミングアルゴリズムにフォーカスしています。 変更数がデータ長に比例すると、peltアルゴリズムで符号化された不等式に基づく刈り取り規則は線形時間複雑性をもたらす。 関数的プルーニングと呼ばれる別のタイプのプルーニングは、変化の数が何であれ、不定の時系列の分析のためだけに、線形の時間複雑性を与える。 本稿では,単純な幾何学的形状(球と超矩形)を用いて,複数の独立時系列に対する機能的プルーニングの拡張を提案する。 ガウスの場合に焦点を当てるが、我々の規則のいくつかは指数族に容易に拡張できる。 シミュレーション実験では,異なる幾何学的プルーニングルールの計算効率を比較する。 小さい次元(2, 3, 4)では,データ長に比べて変化の基数が小さい場合に,不等式に基づくアプローチよりもはるかに高速に動作することが示されている。

関連論文リスト

• Learning causal graphs using variable grouping according to ancestral relationship [7.126300090990439]
  サンプルサイズが変数数に対して小さい場合には,既存手法を用いた因果グラフの推定精度が低下する。 サンプルサイズが変数の数より小さい場合、いくつかのメソッドは実現不可能である。 これらの問題を回避すべく、ある研究者は分割・対数アプローチを用いた因果構造学習アルゴリズムを提案した。
  論文  参考訳（メタデータ） (2024-03-21T04:42:04Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• Are uGLAD? Time will tell! [4.005044708572845]
  条件独立グラフ(CI)を用いた多変量時系列セグメンテーションのための新しい手法を提案する。 CIグラフは、ノード間の部分的相関を表す確率的グラフィカルモデルである。 身体活動モニタリングデータを用いて実験結果を実証した。
  論文  参考訳（メタデータ） (2023-03-21T07:46:28Z)
• Triformer: Triangular, Variable-Specific Attentions for Long Sequence Multivariate Time Series Forecasting--Full Version [50.43914511877446]
  本稿では,高い効率と精度を確保するために,三角形,可変特性に着目した注意点を提案する。 我々はTriformerが精度と効率の両方で最先端の手法より優れていることを示す。
  論文  参考訳（メタデータ） (2022-04-28T20:41:49Z)
• E-detectors: a nonparametric framework for sequential change detection [86.15115654324488]
  逐次的変化検出のための基本的かつ汎用的なフレームワークを開発する。 私たちの手順は、平均走行距離のクリーンで無症状な境界が伴います。 統計的および計算効率の両方を達成するために,これらの混合物を設計する方法を示す。
  論文  参考訳（メタデータ） (2022-03-07T17:25:02Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Isometric Multi-Shape Matching [50.86135294068138]
  形状間の対応を見つけることは、コンピュータビジョンとグラフィックスの基本的な問題である。 アイソメトリーは形状対応問題においてしばしば研究されるが、マルチマッチング環境では明確には考慮されていない。 定式化を解くのに適した最適化アルゴリズムを提案し,コンバージェンスと複雑性解析を提供する。
  論文  参考訳（メタデータ） (2020-12-04T15:58:34Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Linear time dynamic programming for the exact path of optimal models selected from a finite set [0.38073142980732994]
  本稿では,動的プログラミングアルゴリズムを用いて,ブレークポイントを線形時間で計算できることを示す。 点検出問題に対する実証的な結果から,精度と速度の向上が示された。
  論文  参考訳（メタデータ） (2020-03-05T18:16:58Z)
• Use Short Isometric Shapelets to Accelerate Binary Time Series Classification [28.469831845459183]
  時間的複雑性を低減するための2つの戦略を含む,新しいアルゴリズム,すなわち短い等尺形状変換を導入する。 これらの2つの戦略の理論的証拠は、いくつかの前提条件の下でほぼ無作為な精度を保証するために提示される。
  論文  参考訳（メタデータ） (2019-12-27T04:33:11Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。