論文の概要: A new heuristic algorithm for fast k-segmentation
- arxiv url: http://arxiv.org/abs/2009.05148v1
- Date: Wed, 2 Sep 2020 04:50:17 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-22 18:26:17.760467
- Title: A new heuristic algorithm for fast k-segmentation
- Title（参考訳）: 高速kセグメンテーションのための新しいヒューリスティックアルゴリズム
- Authors: Sabarish Vadarevu and Vijay Karamcheti
- Abstract要約: 文献には$k$-segmentationの厳密で近似的な方法が存在する。
本稿では,既存の手法を改善するために,新しいアルゴリズムを提案する。
計算コストのごく一部で正確な手法と競合するアキュラシーを提供することを実証的に見出した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The $k$-segmentation of a video stream is used to partition it into $k$
piecewise-linear segments, so that each linear segment has a meaningful
interpretation. Such segmentation may be used to summarize large videos using a
small set of images, to identify anomalies within segments and change points
between segments, and to select critical subsets for training machine learning
models. Exact and approximate segmentation methods for $k$-segmentation exist
in the literature. Each of these algorithms occupies a different spot in the
trade-off between computational complexity and accuracy. A novel heuristic
algorithm is proposed in this paper to improve upon existing methods. It is
empirically found to provide accuracies competitive with exact methods at a
fraction of the computational expense.
The new algorithm is inspired by Lloyd's algorithm for K-Means and Lloyd-Max
algorithm for scalar quantization, and is called the LM algorithm for
convenience. It works by iteratively minimizing a cost function from any given
initialisation; the commonly used $L_2$ cost is chosen in this paper. While the
greedy minimization makes the algorithm sensitive to initialisation, the
ability to converge from any initial guess to a local optimum allows the
algorithm to be integrated into other existing algorithms. Three variants of
the algorithm are tested over a large number of synthetic datasets, one being a
standalone LM implementation, and two others that combine with existing
algorithms. One of the latter two -- LM-enhanced-Bottom-Up segmentation -- is
found to have the best accuracy and the lowest computational complexity among
all algorithms. This variant of LM can provide $k$-segmentations over data sets
with up to a million image frames within several seconds.
- Abstract（参考訳）: ビデオストリームの$k$-セグメンテーションは、各線形セグメントが意味のある解釈を持つように、$k$の区分線形セグメントに分割するために使用される。
このようなセグメンテーションは、小さなイメージセットを使用して大きなビデオを要約し、セグメント内の異常を識別し、セグメント間の変化点を識別し、機械学習モデルをトレーニングするための重要なサブセットを選択するために使用することができる。
文献には$k$-segmentationの厳密で近似的なセグメンテーション法が存在する。
これらのアルゴリズムはそれぞれ、計算複雑性と精度のトレードオフにおいて異なる位置を占めている。
本稿では,既存の手法を改善するため,新しいヒューリスティックアルゴリズムを提案する。
計算コストのごく一部で正確な手法と競合するアキュラシーを提供することを実証的に見出した。
新しいアルゴリズムは、K平均のロイドアルゴリズムとスカラー量子化のためのロイドマックスアルゴリズムにインスパイアされ、利便性のためにLMアルゴリズムと呼ばれる。
この手法は,任意の初期化からコスト関数を反復的に最小化することで機能する。
欲望の最小化はアルゴリズムを初期化に敏感にするが、任意の初期推測から局所最適に収束する能力により、アルゴリズムを他の既存のアルゴリズムに統合することができる。
アルゴリズムの3つの変種は、多数の合成データセット上でテストされ、1つはスタンドアロンのlm実装、2つは既存のアルゴリズムと組み合わせられる。
LM強化ボットアップセグメンテーション(LM-enhanced-Bottom-Up segmentation)と呼ばれる後者の2つのうちの1つは、全てのアルゴリズムの中で最高の精度と最小の計算複雑性を持つ。
このlmの変種は、数秒で最大100万のイメージフレームを持つデータセットに対して、k$-segmentationを提供することができる。
関連論文リスト
- GreedyML: A Parallel Algorithm for Maximizing Submodular Functions [2.9998889086656586]
分散メモリマルチプロセッサ上での単調部分モジュラ関数の最大化のための並列近似アルゴリズムについて述べる。
我々の研究は、データ要約、機械学習、グラフスカラー化といった分野における実践的な応用のために、大規模データセットのサブモジュラー最適化問題を解決する必要性によって動機付けられている。
論文 参考訳（メタデータ） (2024-03-15T14:19:09Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic
Composite Optimization [10.762749887051546]
本稿では,Proxcal$DASA-GTとProxcal$DASA-Aの2時間スケールアルゴリズムを提案する。
以前の作業とは異なり、我々のアルゴリズムは、大きなバッチサイズ、より複雑な単位演算、より強い仮定を必要とせずに、同等の複雑さを達成する。
論文 参考訳（メタデータ） (2023-02-20T05:16:18Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Practical, Provably-Correct Interactive Learning in the Realizable
Setting: The Power of True Believers [12.09273192079783]
我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。
我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-11-09T02:33:36Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and
Hierarchical Spatial Clustering [6.4805900740861]
HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。
我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。
48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
論文 参考訳（メタデータ） (2021-04-02T16:05:00Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - A Systematic Characterization of Sampling Algorithms for Open-ended
Language Generation [71.31905141672529]
本稿では,自己回帰型言語モデルに広く採用されている祖先サンプリングアルゴリズムについて検討する。
エントロピー低減, 秩序保存, 斜面保全の3つの重要な特性を同定した。
これらの特性を満たすサンプリングアルゴリズムのセットが,既存のサンプリングアルゴリズムと同等に動作することがわかった。
論文 参考訳（メタデータ） (2020-09-15T17:28:42Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。