論文の概要: On Distributed Larger-Than-Memory Subset Selection With Pairwise Submodular Functions

• arxiv url: http://arxiv.org/abs/2402.16442v2
• Date: Wed, 12 Mar 2025 13:02:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-13 21:17:52.291013
• Title: On Distributed Larger-Than-Memory Subset Selection With Pairwise Submodular Functions
• Title（参考訳）: ペアワイズ部分モジュラ関数を用いた分散大規模タンメモリサブセット選択について
• Authors: Maximilian Böther, Abraham Sebastian, Pranjal Awasthi, Ana Klimovic, Srikumar Ramalingam,
• Abstract要約: 証明可能な近似保証付き分散バウンディングアルゴリズムを提案する。 CIFAR-100 と ImageNet の高品質なサブセットは,集中型手法と比較して,品質が損なわれるか,あるいは損なわれない。
• 参考スコア（独自算出の注目度）: 31.334053253182795
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Modern datasets span billions of samples, making training on all available data infeasible. Selecting a high quality subset helps in reducing training costs and enhancing model quality. Submodularity, a discrete analogue of convexity, is commonly used for solving such subset selection problems. However, existing algorithms for optimizing submodular functions are sequential, and the prior distributed methods require at least one central machine to fit the target subset in DRAM. At billion datapoint scale, even the subset may not fit a single machine, and the sequential algorithms are prohibitively slow. In this paper, we relax the requirement of having a central machine for the target subset by proposing a novel distributed bounding algorithm with provable approximation guarantees. The algorithm iteratively bounds the minimum and maximum utility values to select high quality points and discard the unimportant ones. When bounding does not find the complete subset, we use a multi-round, partition-based distributed greedy algorithm to identify the remaining subset. We discuss how to implement these algorithms in a distributed data processing framework and empirically analyze different configurations. We find high quality subsets on CIFAR-100 and ImageNet with marginal or no loss in quality compared to centralized methods, and scale to a dataset with 13 billion points.
• Abstract（参考訳）: 現代のデータセットは数十億のサンプルにまたがっており、利用可能なすべてのデータをトレーニングすることは不可能である。 高品質なサブセットの選択は、トレーニングコストの削減とモデル品質の向上に役立つ。 凸性の離散的な類似である部分モジュラリティは、そのような部分集合選択問題を解くために一般的に用いられる。 しかしながら、サブモジュール関数を最適化するための既存のアルゴリズムは逐次的であり、以前の分散手法ではDRAMのターゲットサブセットに適合するために少なくとも1つの中央マシンを必要とする。 数十億のデータポイントスケールでは、サブセットでさえ単一のマシンに収まらない可能性があり、シーケンシャルアルゴリズムは違法に遅い。 本稿では,証明可能な近似保証付き分散バウンディングアルゴリズムを提案することにより,対象サブセットの中央マシンを持つ必要を緩和する。 アルゴリズムは最小限と最大限のユーティリティ値を反復的にバインドして高品質のポイントを選択し、重要でないものを捨てる。 バウンディングが完全なサブセットを見つけられなかった場合、残りのサブセットを特定するために、複数ラウンドのパーティションベースの分散グリードアルゴリズムを使用する。 分散データ処理フレームワークでこれらのアルゴリズムをどのように実装するかを議論し、異なる構成を経験的に分析する。 CIFAR-100 と ImageNet の高品質なサブセットは,集中型手法に比べて品質が損なわれ,13億点のデータセットにスケールする。

関連論文リスト

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• Multi-objective Binary Coordinate Search for Feature Selection [0.24578723416255746]
  大規模特徴選択問題の解法として,二元多目的座標探索(MOCS)アルゴリズムを提案する。 その結果,実世界の5つの大規模データセットにおいて,NSGA-IIよりも提案手法が優れていることが示唆された。
  論文  参考訳（メタデータ） (2024-02-20T00:50:26Z)
• A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
  サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。 我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-12-17T04:41:07Z)
• Achieving Long-term Fairness in Submodular Maximization through Randomization [16.33001220320682]
  人種や性別などのセンシティブな属性を含む可能性のあるデータアイテムを扱う場合、公平性を意識したアルゴリズムを実装することが重要です。 群フェアネス制約を満たしながら単調部分モジュラ函数を最大化する問題について検討する。
  論文  参考訳（メタデータ） (2023-04-10T16:39:19Z)
• Towards Automated Imbalanced Learning with Deep Hierarchical Reinforcement Learning [57.163525407022966]
  不均衡学習はデータマイニングにおいて基本的な課題であり、各クラスにトレーニングサンプルの不均等な比率が存在する。 オーバーサンプリングは、少数民族のための合成サンプルを生成することによって、不均衡な学習に取り組む効果的な手法である。 我々は,異なるレベルの意思決定を共同で最適化できる自動オーバーサンプリングアルゴリズムであるAutoSMOTEを提案する。
  論文  参考訳（メタデータ） (2022-08-26T04:28:01Z)
• Parallel Instance Filtering for Malware Detection [0.0]
  この研究は、Parallel Instance Filtering (PIF)と呼ばれる新しい並列インスタンス選択アルゴリズムを提案する。 このアルゴリズムの主な考え方は、データセット全体をカバーしているインスタンスの重複しないサブセットにデータセットを分割し、各サブセットにフィルタリングプロセスを適用することである。 我々はPIFアルゴリズムと、50,000の悪意あるサンプルからなる大規模なデータセット上で、最先端のインスタンス選択アルゴリズムを比較した。
  論文  参考訳（メタデータ） (2022-06-28T11:14:20Z)
• Multi-granularity Relabeled Under-sampling Algorithm for Imbalanced Data [15.030895782548576]
  不均衡な分類問題は、データマイニングと機械学習において重要かつ困難な問題の1つであることが判明した。 Tomek-Linkサンプリングアルゴリズムは、データ上のクラスオーバーラップを効果的に低減し、識別が難しい多数インスタンスを除去し、アルゴリズムの分類精度を向上させる。 しかし、Tomek-Linksアンダーサンプリングアルゴリズムは、世界中に最も近い隣り合う境界インスタンスのみを考慮し、潜在的に局所的な重複するインスタンスを無視している。 本稿では,データセットの局所的情報を完全に考慮した多粒度アンダーサンプリングアルゴリズム(MGRU)を提案する。
  論文  参考訳（メタデータ） (2022-01-11T14:07:55Z)
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
  半教師付きMSSCのための分岐結合アルゴリズムを提案する。 背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。 提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
  論文  参考訳（メタデータ） (2021-11-30T17:08:53Z)
• Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization [28.862321453597918]
  非滑らかな有限サム最小化は機械学習の基本的な問題である。 本稿では,確率的リシャフリングを用いた分散近位勾配アルゴリズムを開発し,その問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-11-06T07:29:55Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Determinantal consensus clustering [77.34726150561087]
  本稿では,クラスタリングアルゴリズムのランダム再起動における決定点プロセス (DPP) の利用を提案する。 DPPは部分集合内の中心点の多様性を好んでいる。 DPPとは対照的に、この手法は多様性の確保と、すべてのデータフェースについて良好なカバレッジを得るために失敗することを示す。
  論文  参考訳（メタデータ） (2021-02-07T23:48:24Z)
• Fast Greedy Subset Selection from Large Candidate Solution Sets in Evolutionary Multi-objective Optimization [11.110675371854988]
  本稿では,超体積,IGD,IGD+インジケータのグリーディ部分選択の効率について論じる。 我々の考えは、超体積インジケータで知られている部分モジュラー特性を用いて、それらの効率を改善することである。
  論文  参考訳（メタデータ） (2021-02-01T16:14:15Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。 通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。 分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。 分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
  論文  参考訳（メタデータ） (2020-10-02T10:41:59Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)

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

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