論文の概要: Finite Sample Complexity Analysis of Binary Segmentation

• arxiv url: http://arxiv.org/abs/2410.08654v1
• Date: Fri, 11 Oct 2024 09:26:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-30 22:45:00.737258
• Title: Finite Sample Complexity Analysis of Binary Segmentation
• Title（参考訳）: バイナリセグメンテーションの有限サンプル複雑度解析
• Authors: Toby Dylan Hocking,
• Abstract要約: 与えられた有限$N$,$K$,および最小セグメント長パラメータに対する二分分割の時間と空間の複雑さを解析するための新しい手法について述べる。 実データについて実証的な分析を行い、二分法は実際は最適速度に近いことが多いことを示唆する。
• 参考スコア（独自算出の注目度）: 2.474754293747645
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Binary segmentation is the classic greedy algorithm which recursively splits a sequential data set by optimizing some loss or likelihood function. Binary segmentation is widely used for changepoint detection in data sets measured over space or time, and as a sub-routine for decision tree learning. In theory it should be extremely fast for $N$ data and $K$ splits, $O(N K)$ in the worst case, and $O(N \log K)$ in the best case. In this paper we describe new methods for analyzing the time and space complexity of binary segmentation for a given finite $N$, $K$, and minimum segment length parameter. First, we describe algorithms that can be used to compute the best and worst case number of splits the algorithm must consider. Second, we describe synthetic data that achieve the best and worst case and which can be used to test for correct implementation of the algorithm. Finally, we provide an empirical analysis of real data which suggests that binary segmentation is often close to optimal speed in practice.
• Abstract（参考訳）: バイナリセグメンテーション(英: Binary segmentation)は、損失や可能性関数を最適化することで、逐次データセットを再帰的に分割する古典的なグリードアルゴリズムである。 バイナリセグメンテーションは、空間や時間で測定されたデータセットの変化点検出や、決定木学習のサブルーチンとして広く使用されている。 理論的には、$N$データと$K$分割、最悪の場合は$O(N K)$、最良の場合は$O(N \log K)$に対して非常に高速であるべきである。 本稿では,与えられた有限$N$,$K$,最小セグメント長パラメータに対する二分分割の時間と空間の複雑さを解析するための新しい手法について述べる。 まず,アルゴリズムが考慮すべき分割数の最大かつ最悪のケース数を計算できるアルゴリズムについて述べる。 第2に,最善かつ最悪のケースを達成し,アルゴリズムの正しい実装をテストするために使用できる合成データについて述べる。 最後に、実データについて実証的な分析を行い、二分分割が実際に最適な速度に近づいたことを示唆する。

関連論文リスト

• Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
  本稿では,条件付き選好ネットワーク(CP-nets)上での選好を集約する近似アルゴリズムの設計と解析について述べる。 その焦点は、一般に最適な解が指数関数的な大きさであることが知られている、いわゆる「エンフスワップ」よりも、優先的な選好を集約することである。
  論文  参考訳（メタデータ） (2023-12-14T17:31:38Z)
• Fully-Dynamic Decision Trees [3.0058005235097114]
  ラベル付き例の挿入と削除の任意のシーケンス上で決定木を維持するための,最初の完全動的アルゴリズムを開発した。 実数値機能の場合、このアルゴリズムは挿入/削除毎に$Obig(fracd log3 nepsilon2big)$.amortized run timeを持つ。 同様の保証を持つアルゴリズムは、amortized run time $Omega(d)$と space $tildeOmega (n d)$を使用する。
  論文  参考訳（メタデータ） (2022-12-01T18:58:19Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Systematically improving existing k-means initialization algorithms at nearly no cost, by pairwise-nearest-neighbor smoothing [1.2570180539670577]
  PNN-smoothingと呼ばれる$k$-meansクラスタリングアルゴリズムを初期化するメタメソッドを提案する。 与えられたデータセットを$J$のランダムなサブセットに分割し、各データセットを個別にクラスタリングし、結果のクラスタリングをペアワイズ・アネレス・ニーバーメソッドとマージする。
  論文  参考訳（メタデータ） (2022-02-08T15:56:30Z)
• Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
  条件勾配法(CGM)は現代の機械学習で広く使われている。 ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。 本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
  論文  参考訳（メタデータ） (2021-11-30T05:40:14Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• A new heuristic algorithm for fast k-segmentation [0.0]
  文献には$k$-segmentationの厳密で近似的な方法が存在する。 本稿では,既存の手法を改善するために,新しいアルゴリズムを提案する。 計算コストのごく一部で正確な手法と競合するアキュラシーを提供することを実証的に見出した。
  論文  参考訳（メタデータ） (2020-09-02T04:50:17Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
  混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。 数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。 さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
  論文  参考訳（メタデータ） (2020-01-17T18:47:02Z)

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

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