論文の概要: GIST: Greedy Independent Set Thresholding for Diverse Data Summarization
- arxiv url: http://arxiv.org/abs/2405.18754v1
- Date: Wed, 29 May 2024 04:39:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-30 18:48:25.183482
- 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 various data summarization(textsfMDDS$)と呼ばれる新しいサブセット選択タスクを提案する。
目的は、各点のトータルユーティリティと、選択された任意の点間の最小距離をキャプチャする多様性項を組み合わせた目的を最大化することである。
この作業は、$textttGIST$アルゴリズムを示し、$textsfMDDS$の$frac23$-approximation保証を達成する。
- 参考スコア（独自算出の注目度）: 21.69260104523751
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose a novel subset selection task called min-distance diverse data summarization ($\textsf{MDDS}$), 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 is to maximize an objective that combines the total utility of the points and a diversity term that captures the minimum distance between any pair of selected points, subject to the constraint $|S| \le k$. For example, the points may correspond to training examples in a data sampling problem, e.g., learned embeddings of images extracted from a deep neural network. This work presents the $\texttt{GIST}$ algorithm, which achieves a $\frac{2}{3}$-approximation guarantee for $\textsf{MDDS}$ by approximating a series of maximum independent set problems with a bicriteria greedy algorithm. We also prove a complementary $(\frac{2}{3}+\varepsilon)$-hardness of approximation, for any $\varepsilon > 0$. Finally, we provide an empirical study that demonstrates $\texttt{GIST}$ outperforms existing methods for $\textsf{MDDS}$ on synthetic data, and also for a real-world image classification experiment the studies single-shot subset selection for ImageNet.
- Abstract（参考訳）: 本稿では,機械学習,例えばデータサンプリング,特徴選択など,多種多様な応用が可能な,min-distance various data summarization(\textsf{MDDS}$)と呼ばれる新しいサブセット選択タスクを提案する。
計量空間における点の集合が与えられたとき、ゴールは、点の全体の効用と、任意の選択された点間の最小距離を、制約$|S| \le k$の条件で捉える多様性項を組み合わせた目的を最大化することである。
例えば、このポイントは、深層ニューラルネットワークから抽出された画像の学習された埋め込みなど、データサンプリング問題におけるトレーニング例に対応できる。
この研究は$\texttt{GIST}$アルゴリズムを示し、bicriteria greedyアルゴリズムで一連の最大独立集合問題を近似することで$\frac{2}{3}$-approximation guarantee for $\textsf{MDDS}$を達成する。
また、任意の$\varepsilon > 0$に対して、相補的な$(\frac{2}{3}+\varepsilon)$-近似の硬度も証明する。
最後に,$\texttt{GIST}$が合成データに対して$\textsf{MDDS}$の既存の手法よりも優れており,実世界の画像分類実験では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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。