論文の概要: e-means: outperforming k-means (in one-tenth the epochs)
- arxiv url: http://arxiv.org/abs/2611.09501v1
- Date: Fri, 06 Nov 2026 14:22:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-10 12:00:36.667713
- Title: e-means: outperforming k-means (in one-tenth the epochs)
- Title(参考訳): e-means (複数形 e-means)
- Abstract要約: ミニバッチ更新を伴うk平均の指数的移動平均最適化手法を提案する。
また、崩壊率とバッチサイズが最終的なパフォーマンスに与える影響について、スケーリング法則を定めています。
結果として得られたクラスタリングアルゴリズムは e-means と呼ばれ、ロイズk-means よりもはるかに高速で、損失の減少に収束する。
- 参考スコア(独自算出の注目度): 22.735518961851856
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Lloyd's k-means algorithm is a long-running standard for clustering, with applications in data analysis, retrieval, quantization and data curation. In this paper, we introduce an exponential moving average optimization procedure for k-means with mini-batch updates, powered by modern deep learning machinery and new insights. We also establish scaling laws on how decay rate and batch size impact final performance. This gives us a formulaic rule to fix them for multiple problem sizes and embedding datasets, without the need for any hyperparameter sweep. The resulting clustering algorithm, coined e-means, is much faster than Lloyd k-means and converges to lower losses, frequently even beating k-means++. On a wide array of embeddings datasets, it beats the loss of Lloyd k-means at 25 epochs in 1.4 to 2.6 epochs, which translates to 10-45x GPU wall-clock speedups compared to state-of-the-art k-means implementations. As an example, e-means partitions DINO10B, a dataset of 10 billion DINO embeddings, into 16 million clusters in only 2.5 epochs, reaching a loss below Lloyd's at 25 epochs.
- Abstract(参考訳): ロイドのk平均アルゴリズムはクラスタリングの長い標準であり、データ解析、検索、量子化、データキュレーションに応用されている。
本稿では,近代的な深層学習機構と新たな洞察を応用した,ミニバッチ更新によるk平均の指数的移動平均最適化手法を提案する。
また、崩壊率とバッチサイズが最終的なパフォーマンスに与える影響について、スケーリング法則を定めています。
これにより、ハイパーパラメータスイープを必要とせずに、複数の問題サイズの修正とデータセットの埋め込みを公式ルールで行います。
結果として生成されるクラスタリングアルゴリズムは e-means と呼ばれ、ロイズk-means よりもはるかに高速で、損失を減らし、k-means++ を圧倒することもある。
幅広い埋め込みデータセットにおいて、Lloyd k-meansが1.4から2.6 epochsで25 epochsで失われ、最先端のk-means実装と比較して10-45倍のGPUウォールクロックスピードアップになる。
例えば、e-meansは100億のDINO埋め込みのデータセットであるDINO10Bを、わずか2.5エポックで1600万のクラスタに分割し、ロイドの25エポックでの損失に達した。
関連論文リスト
- Communication-Avoiding Linear Algebraic Kernel K-Means on GPUs [1.0017970035130424]
我々は大規模なKernel K-meansクラスタリングのための分散メモリ並列アルゴリズムスイートを提案する。
我々の手法は、ケルネル K-平均の計算コストが最も高い成分を通信効率の良い分散線形代数プリミティブにマッピングする。
我々の1.5Dアルゴリズムは、常に最高性能を達成し、K-meansは従来よりも1~2桁大きなデータにスケールできる。
論文 参考訳(メタデータ) (2026-01-23T19:25:10Z) - K*-Means: A Parameter-free Clustering Algorithm [55.20132267309382]
k*-meansは、kや他のパラメータをセットする必要がない新しいクラスタリングアルゴリズムである。
最小記述長の原理を用いて、クラスタの分割とマージによって最適なクラスタ数k*を自動的に決定する。
k*-平均が収束することが保証されることを証明し、kが未知のシナリオにおいて既存のメソッドよりも著しく優れていることを実験的に証明する。
論文 参考訳(メタデータ) (2025-05-17T08:41:07Z) - On Simplifying Large-Scale Spatial Vectors: Fast, Memory-Efficient, and Cost-Predictable k-means [7.192072206801592]
k平均アルゴリズムは、高速な解析と学習をサポートするために、2Dジオロケーションや3Dポイントクラウドのような大規模な空間ベクトルを単純化することができる。
既存のk平均アルゴリズムは、メモリやCPU使用時間などの重要な計算資源で高い性能を達成する。
本稿では,Dsk-meansと呼ばれる高速で,メモリ効率が高く,コスト予測可能なk-meansを提案する。
論文 参考訳(メタデータ) (2024-12-03T08:16:59Z) - FT K-means: A High-Performance K-means on GPU with Fault Tolerance [10.100958054600438]
FT K-meansは,オンラインフォールトトレランスを備えたK-meansの高性能実装である。
まず、NVIDIAのcuMLライブラリと比較して、競争性能を達成するためのステップワイズ最適化戦略を提案する。
我々は、異なるデータ型をサポートし、異なる入力形式に適応するテンプレートベースのコード生成フレームワークにより、FT K平均をさらに改善する。
論文 参考訳(メタデータ) (2024-08-02T17:01:36Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳(メタデータ) (2023-05-12T03:01:41Z) - Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。
我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。
RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
論文 参考訳(メタデータ) (2022-10-21T15:56:13Z) - Reducing Variance in Temporal-Difference Value Estimation via Ensemble
of Deep Networks [109.59988683444986]
MeanQは単純なアンサンブル法であり、ターゲット値をアンサンブル平均として推定する。
本稿では,Atari Learning Environmentベンチマークを用いた実験において,MeanQが顕著なサンプル効率を示すことを示す。
論文 参考訳(メタデータ) (2022-09-16T01:47:36Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳(メタデータ) (2022-04-20T07:14:21Z) - K-Splits: Improved K-Means Clustering Algorithm to Automatically Detect
the Number of Clusters [0.12313056815753944]
本稿では,k-meansに基づく改良された階層型アルゴリズムであるk-splitsを紹介する。
提案手法の主な利点は,精度と速度である。
論文 参考訳(メタデータ) (2021-10-09T23:02:57Z) - Ball k-means [53.89505717006118]
Ball k-meansアルゴリズムは、ポイントセントロイド距離計算の削減に集中して、クラスタを記述するためにボールを使用する。
高速、余分なパラメータなし、単純設計のボールk平均アルゴリズムは、素早いk平均アルゴリズムを全面的に置き換える。
論文 参考訳(メタデータ) (2020-05-02T10:39:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。