論文の概要: 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の単発サブセット選択について検討する。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Fair Submodular Cover [18.37610521373708]
フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。
まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。
次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
論文 参考訳（メタデータ） (2024-07-05T18:37:09Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Max-Min Diversification with Fairness Constraints: Exact and
Approximation Algorithms [17.57585822765145]
本稿では,小データセットに適した正確なアルゴリズムと,大データセットにスケールする任意の$varepsilon in (0, 1)$に対して$frac1-varepsilon integer 5$-approximationアルゴリズムを提案する。
実世界のデータセットに対する実験は、提案アルゴリズムが既存のデータセットよりも優れていることを示す。
論文 参考訳（メタデータ） (2023-01-05T13:02:35Z) - 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) - Minimax Optimal Algorithms with Fixed-$k$-Nearest Neighbors [13.231906521852718]
大規模なデータセットを小さなグループに分割する分散学習シナリオを考察する。
分類,回帰,密度推定のための固定k$-NN情報を集約する最適ルールを提案する。
十分多数のグループに固定された$k$の分散アルゴリズムは、乗算対数係数までの最小誤差率を得ることを示す。
論文 参考訳（メタデータ） (2022-02-05T01:59:09Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。
我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文 参考訳（メタデータ） (2021-04-06T20:25:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。