論文の概要: GPU-accelerated Faster Mean Shift with euclidean distance metrics
- arxiv url: http://arxiv.org/abs/2112.13891v1
- Date: Mon, 27 Dec 2021 20:18:24 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-30 14:48:56.532020
- Title: GPU-accelerated Faster Mean Shift with euclidean distance metrics
- Title（参考訳）: ユークリッド距離測定によるGPU加速平均シフト
- Authors: Le You, Han Jiang, Jinyong Hu, Chorng Chang, Lingxi Chen, Xintong Cui,
Mengyang Zhao
- Abstract要約: 平均シフトアルゴリズムはクラスタリング問題の解法として広く用いられている。
従来の研究では,GPUを高速化する高速平均シフトアルゴリズムが提案されている。
本研究では,ユークリッド距離測定値を扱うために,従来のアルゴリズムを拡張し改良する。
- 参考スコア（独自算出の注目度）: 1.3507758562554621
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Handling clustering problems are important in data statistics, pattern
recognition and image processing. The mean-shift algorithm, a common
unsupervised algorithms, is widely used to solve clustering problems. However,
the mean-shift algorithm is restricted by its huge computational resource cost.
In previous research[10], we proposed a novel GPU-accelerated Faster Mean-shift
algorithm, which greatly speed up the cosine-embedding clustering problem. In
this study, we extend and improve the previous algorithm to handle Euclidean
distance metrics. Different from conventional GPU-based mean-shift algorithms,
our algorithm adopts novel Seed Selection & Early Stopping approaches, which
greatly increase computing speed and reduce GPU memory consumption. In the
simulation testing, when processing a 200K points clustering problem, our
algorithm achieved around 3 times speedup compared to the state-of-the-art
GPU-based mean-shift algorithms with optimized GPU memory consumption.
Moreover, in this study, we implemented a plug-and-play model for faster
mean-shift algorithm, which can be easily deployed. (Plug-and-play model is
available: https://github.com/masqm/Faster-Mean-Shift-Euc)
- Abstract（参考訳）: クラスタリング問題は、データ統計、パターン認識、画像処理において重要である。
一般的な教師なしアルゴリズムである平均シフトアルゴリズムは、クラスタリング問題を解決するために広く使われている。
しかし、平均シフトアルゴリズムはその膨大な計算資源コストによって制限される。
前研究[10]では,コサイン埋め込みクラスタリング問題を大幅に高速化するGPUアクセラレーション高速平均シフトアルゴリズムを提案した。
本研究では,ユークリッド距離測定値を扱うために,従来のアルゴリズムを拡張し改良する。
従来のGPUベースの平均シフトアルゴリズムとは違って,提案アルゴリズムはSeed Selection & Early Stoppingアプローチを採用し,計算速度を大幅に向上させ,GPUメモリ使用量を削減する。
シミュレーションテストでは,200k点のクラスタリング問題を処理する場合,gpuメモリ消費を最適化したgpuベース平均シフトアルゴリズムと比較して,約3倍の高速化を達成した。
さらに,本研究では,より高速な平均シフトアルゴリズムのためのプラグ・アンド・プレイモデルを実装した。
(プラグアンドプレイモデルはhttps://github.com/masqm/faster-mean-shift-euc)
関連論文リスト
- Implementation and Analysis of GPU Algorithms for Vecchia Approximation [0.8057006406834466]
Vecchia Approximationは計算複雑性を減らすために広く使われており、恥ずかしい並列アルゴリズムで計算することができる。
Vecchia Approximationのためにマルチコアソフトウェアが開発されたが、グラフィックス処理ユニット(GPU)上で動作するように設計されたソフトウェアは不足している。
我々の新しい手法は他の2つより優れており、GpGpU Rパッケージに表示されます。
論文 参考訳（メタデータ） (2024-07-03T01:24:44Z) - Fast, Scalable, Warm-Start Semidefinite Programming with Spectral
Bundling and Sketching [53.91395791840179]
我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。
USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
論文 参考訳（メタデータ） (2023-12-19T02:27:22Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer
Vision [6.574107319036238]
Hochbaum pseudoflowアルゴリズムは最速のシリアルアルゴリズムであり、Boykov-Kolmogorovアルゴリズムは最もメモリ効率が高い。
既存の min-cut/max-flow アルゴリズムは、大きな問題ではシリアルアルゴリズムを著しく上回るが、中小問題ではオーバーヘッドが増大する。
論文 参考訳（メタデータ） (2022-02-01T14:06:27Z) - RAMA: A Rapid Multicut Algorithm on GPU [23.281726932718232]
本稿では,マルチカット問題(マグニチュード相関クラスタリング)に対する高並列原始双対アルゴリズムを提案する。
我々のアルゴリズムは、最適距離を推定する原始解と双対下界を生成する。
最大$mathcalO(108)$変数を数秒で、小さな原始双対ギャップで、非常に大規模なベンチマーク問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-04T10:33:59Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Faster Mean-shift: GPU-accelerated clustering for cosine embedding-based
cell segmentation and tracking [12.60841328582138]
本稿では,埋め込み型セルセグメンテーションとトラッキングの計算ボトルネックに対処する,高速平均シフトアルゴリズムを提案する。
提案したFaster Mean-shiftアルゴリズムは、最先端の埋め込みベースのセルインスタンスのセグメンテーションとトラッキングアルゴリズムと比較して7～10倍の高速化を実現した。
我々の高速平均シフトアルゴリズムは、メモリ消費を最適化した他のGPUベンチマークと比較して計算速度も高い。
論文 参考訳（メタデータ） (2020-07-28T14:52:51Z) - Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。
最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。
ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
論文 参考訳（メタデータ） (2020-06-18T08:16:25Z) - Heterogeneous CPU+GPU Stochastic Gradient Descent Algorithms [1.3249453757295084]
ヘテロジニアスCPU+GPUアーキテクチャの深層学習のためのトレーニングアルゴリズムについて検討する。
私たちの2倍の目標 -- 収束率と資源利用を同時に最大化する -- は、この問題を難しくします。
これらのアルゴリズムの実装は,複数の実データセットよりも高速な収束と資源利用の両立を実現していることを示す。
論文 参考訳（メタデータ） (2020-04-19T05:21:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。