論文の概要: GIST: Greedy Independent Set Thresholding for Diverse Data Summarization
- arxiv url: http://arxiv.org/abs/2405.18754v2
- Date: Mon, 10 Feb 2025 21:17:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-12 14:03:21.944616
- Title: GIST: Greedy Independent Set Thresholding for Diverse Data Summarization
- Title（参考訳）: GIST: 異種データ要約のためのGreedy Independent Set Thresholding
- Authors: Matthew Fahrbach, Srikumar Ramalingam, Morteza Zadimoghaddam, Sara Ahmadian, Gui Citovsky, Giulia DeSalvo,
- Abstract要約: 単調部分モジュラーユーティリティを用いたmin-distance diversificationと呼ばれる新しいサブセット選択問題を導入する(textsfMDMS$)。
計量空間内の点の集合が与えられたとき、$textsfMDMS$ の目標は、任意の選択された点間の単調部分モジュラー効用項と最小距離の多様性項を組み合わせた目的関数を最大化することである。
- 参考スコア（独自算出の注目度）: 21.69260104523751
- License:
- Abstract: We introduce a novel subset selection problem called min-distance diversification with monotone submodular utility ($\textsf{MDMS}$), which has a wide variety of applications in machine learning, e.g., data sampling and feature selection. Given a set of points in a metric space, the goal of $\textsf{MDMS}$ is to maximize an objective function combining a monotone submodular utility term and a min-distance diversity term between any pair of selected points, subject to a cardinality constraint. We propose the $\texttt{GIST}$ algorithm, which achieves a $\frac{1}{2}$-approximation guarantee for $\textsf{MDMS}$ by approximating a series of maximum independent set problems with a bicriteria greedy algorithm. We also prove that it is NP-hard to approximate to within a factor of $0.5584$. Finally, we demonstrate that $\texttt{GIST}$ outperforms existing benchmarks for on a real-world image classification task that studies single-shot subset selection for ImageNet.
- Abstract（参考訳）: 本稿では,モノトン部分モジュラーユーティリティを用いたmin-distance diversification(min-distance diversification)と呼ばれる新しいサブセット選択問題を導入する。
計量空間内の点の集合が与えられたとき、$\textsf{MDMS}$の目標は、濃度制約を受ける任意の選択された点間の単調部分モジュラー効用項と最小距離の多様性項を組み合わせた目的関数を最大化することである。
ビクリテリアグレディアルゴリズムを用いて一連の最大独立集合問題を近似することにより、$\frac{1}{2}$-approximation guarantee for $\textsf{MDMS}$を実現する。
また、NP-ハードが0.5584$の係数で近似できることも証明する。
最後に、$\texttt{GIST}$は、ImageNetの単発サブセット選択を研究する実世界の画像分類タスクにおいて、既存のベンチマークよりも優れていることを示す。
関連論文リスト
- Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
条件分布は機械学習の中心的な問題です
ペアデータとペアデータの両方を統合する新しい学習パラダイムを提案する。
我々のアプローチはまた、興味深いことに逆エントロピー最適輸送(OT)と結びついている。
論文 参考訳（メタデータ） (2024-10-03T16:12:59Z) - Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error [25.777423855881878]
我々は、$Oleft(Hepsilonright)$-optimal Policyを得ることができることを示す新しい除去アルゴリズムを示す。
我々は上界を$widetildeOmegaleft(Hepsilonright)$-optimality lower boundで補い、この問題の完全な図面を与える。
論文 参考訳（メタデータ） (2024-07-18T15:58:04Z) - Collaborative non-parametric two-sample testing [55.98760097296213]
目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。
グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。
提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
論文 参考訳（メタデータ） (2024-02-08T14:43:56Z) - Variance Alignment Score: A Simple But Tough-to-Beat Data Selection
Method for Multimodal Contrastive Learning [17.40655778450583]
本稿では、Sigma_texttest, Sigma_irangle$という形式を持つVariance Alignment Score(VAS)という原則付き計量を提案する。
VASとCLIPのスコアを合わせると、ノイズの多いデータセットDataCompの38評価セットに1.3%、高品質なデータセットCC12MのVTABに2.5%の差でベースラインを上回ります。
論文 参考訳（メタデータ） (2024-02-03T06:29:04Z) - Weighted Sparse Partial Least Squares for Joint Sample and Feature
Selection [7.219077740523681]
本稿では, 共同サンプルと特徴選択のために, $ell_infty/ell_0$-norm制約付きスパースPSS(ell_infty/ell_$-wsPLS)法を提案する。
我々は,各マルチビューwsPLSモデルに対して効率的な反復アルゴリズムを開発し,その収束性を示す。
論文 参考訳（メタデータ） (2023-08-13T10:09:25Z) - Sharper Bounds for $\ell_p$ Sensitivity Sampling [56.45770306797584]
まず, $ell_p$ 部分空間埋め込みを $p に対して高感度サンプリングする。
また、ルートレバレッジスコアサンプリングアルゴリズムは1leq p2$に対して約$d$を達成し、レバレッジスコアと感度サンプリングの組み合わせにより、約$d2/pmathfrak S2-4/p$を2pinftyで改善することを示した。
論文 参考訳（メタデータ） (2023-06-01T14:27:28Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Streaming Algorithms for Diversity Maximization with Fairness
Constraints [4.53279507109072]
ストリーミングアルゴリズムは、1回のパスで$X$をシーケンシャルに処理し、フェアネス制約を保証しながら最大emph順序で返却サブセットを処理すべきである。
多様性は一般にNPハードであるため、データストリームの公平な多様性のための2つのアルゴリズムを提案する。
実験の結果,両アルゴリズムは最先端のアルゴリズムに匹敵する品質の解を提供することがわかった。
論文 参考訳（メタデータ） (2022-07-30T11:47:31Z) - Projection-Free Algorithm for Stochastic Bi-level Optimization [17.759493152879013]
本研究は、目的関数が他の最適化問題に依存する二段階最適化問題を解く最初のプロジェクションフリーアルゴリズムを示す。
提案されている$textbfStochastic $textbfF$rank-$textbfW$olfe ($textbfSCFW$)は、凸目的に対して$mathcalO(epsilon-2)$のサンプル複雑性を実現するために示されている。
論文 参考訳（メタデータ） (2021-10-22T11:49:15Z) - Sampling from a $k$-DPP without looking at all items [58.30573872035083]
カーネル関数とサブセットサイズ$k$が与えられた場合、我々のゴールは、サブセットによって誘導されるカーネル行列の行列式に比例する確率を持つ$n$アイテムから$k$をサンプリングすることである(つまり$k$-DPP)。
既存の$k$-DPPサンプリングアルゴリズムは、すべての$n$アイテムを複数回パスする高価な前処理ステップを必要とするため、大規模なデータセットでは利用できない。
そこで我々は, 十分大きなデータの均一なサンプルを適応的に構築し, より小さな$k$のアイテムを効率よく生成するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2020-06-30T16:40:44Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。