論文の概要: Efficient Prototype Selection via Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2210.01860v1
- Date: Tue, 4 Oct 2022 19:03:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-06 12:42:45.095832
- Title: Efficient Prototype Selection via Multi-Armed Bandits
- Title(参考訳): マルチアーマッドバンドによる効率的なプロトタイプ選択
- Authors: Arghya Roy Chaudhuri, Pratik Jawanpuria, and Bamdev Mishra
- Abstract要約: 与えられたデータセットの典型的な例は、基礎となるデータ分布に関する解釈可能な洞察を提供する。
主要な課題は大規模な設定であり、ほぼすべての可能なペアに対して、データポイントのペア間の類似性比較を行う必要がある。
- 参考スコア(独自算出の注目度): 16.822770693792823
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we propose a multi-armed bandit based framework for identifying
a compact set of informative data instances (i.e., the prototypes) that best
represents a given target set. Prototypical examples of a given dataset offer
interpretable insights into the underlying data distribution and assist in
example-based reasoning, thereby influencing every sphere of human decision
making. A key challenge is the large-scale setting, in which similarity
comparison between pairs of data points needs to be done for almost all
possible pairs. We propose to overcome this limitation by employing stochastic
greedy search on the space of prototypical examples and multi-armed bandit
approach for reducing the number of similarity comparisons. We analyze the
total number of similarity comparisons needed by approach and provide an upper
bound independent of the size of the target set.
- Abstract(参考訳): 本稿では,与えられた対象集合を最もよく表わす,情報型データインスタンス(すなわちプロトタイプ)のコンパクトセットを識別するための,多腕バンディットベースのフレームワークを提案する。
与えられたデータセットの原型的な例は、基礎となるデータ分布に関する解釈可能な洞察を提供し、例ベースの推論を支援する。
重要な課題は、ほぼすべての可能なペアに対して、データポイントのペア間の類似性比較を行う必要がある、大規模設定である。
本稿では, 確率的欲求探索を原型例の空間に応用し, 類似度比較の回数を減らすためのマルチアームバンディットアプローチを提案する。
アプローチに必要な類似度比較の総数を分析し,対象集合のサイズに依存しない上限を提供する。
関連論文リスト
- 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) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳(メタデータ) (2023-12-13T11:08:25Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24:15Z) - Piecewise-Stationary Multi-Objective Multi-Armed Bandit with Application
to Joint Communications and Sensing [7.0997346625024]
本稿では,この問題を解決するために,変化検出を用いた汎用上信頼境界(UCB)に基づくアルゴリズムを提案する。
また,統合通信・センシングシステムにおけるエネルギー効率のよい波形設計問題を玩具の例として定式化する。
論文 参考訳(メタデータ) (2023-02-10T14:10:14Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-31T19:14:30Z) - 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) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳(メタデータ) (2020-06-15T21:55:34Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳(メタデータ) (2020-05-26T17:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。