論文の概要: ProtoBandit: Efficient Prototype Selection via Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2210.01860v4
- Date: Wed, 23 Aug 2023 15:22:04 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-24 18:58:27.056162
- Title: ProtoBandit: Efficient Prototype Selection via Multi-Armed Bandits
- Title（参考訳）: ProtoBandit:マルチアーマッドバンドによる効率的なプロトタイプ選択
- Authors: Arghya Roy Chaudhuri, Pratik Jawanpuria, and Bamdev Mishra
- Abstract要約: ProtoBanditは、ソースデータセットから情報的データインスタンスのコンパクトなセットを特定するための、マルチアームのBanditベースのフレームワークである。
提案アルゴリズムは,数桁の類似性計算コール数(100～1000倍)を削減し,最先端手法と同等の解を求める。
- 参考スコア（独自算出の注目度）: 9.333087475006003
- 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) from a
source dataset $S$ that best represents a given target set $T$. 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. Current state-of-the-art prototype
selection approaches require $O(|S||T|)$ similarity comparisons between source
and target data points, which becomes prohibitively expensive for large-scale
settings. We propose to mitigate this limitation by employing stochastic greedy
search in the space of prototypical examples and multi-armed bandits for
reducing the number of similarity comparisons. Our randomized algorithm,
ProtoBandit, identifies a set of $k$ prototypes incurring $O(k^3|S|)$
similarity comparisons, which is independent of the size of the target set. An
interesting outcome of our analysis is for the $k$-medoids clustering problem
$T = S$ setting) in which we show that our algorithm ProtoBandit approximates
the BUILD step solution of the partitioning around medoids (PAM) method in
$O(k^3|S|)$ complexity. Empirically, we observe that ProtoBandit reduces the
number of similarity computation calls by several orders of magnitudes
($100-1000$ times) while obtaining solutions similar in quality to those from
state-of-the-art approaches.
- Abstract（参考訳）: そこで本研究では,ターゲットセット$t$を最もよく表現するソースデータセット$s$から,情報型データインスタンス(すなわちプロトタイプ)のコンパクトセットを識別するマルチアームのbanditベースのフレームワークを提案する。
与えられたデータセットの原型的な例は、基礎となるデータ分布に対する解釈可能な洞察を提供し、例ベースの推論を支援する。
現在のプロトタイプ選択アプローチでは、ソースとターゲットのデータポイントの類似度比較が$o(|s|||t|)である。
類似度比較の回数を減らすために,確率的欲求探索を原型例と多腕包帯の空間に導入することにより,この制限を軽減することを提案する。
我々のランダム化アルゴリズムであるProtoBanditは、ターゲット集合のサイズに依存しない$O(k^3|S|)$類似性比較を生じる$k$のプロトタイプの集合を同定する。
我々の分析の興味深い結果は、$k$-medoidsクラスタリング問題 $T = S$ set に対して、我々のアルゴリズム ProtoBandit が、$O(k^3|S|)$ complexity におけるメドイド(PAM) メソッドの分割の BUILD ステップ解を近似することを示したことである。
実証的に、protobanditは、最先端のアプローチから同等の品質のソリューションを得る一方で、数桁のマグニチュード(100～1000ドル)の類似度計算呼び出しの数を減少させる。
関連論文リスト
- Lightweight Protocols for Distributed Private Quantile Estimation [12.586899971090277]
我々は、各ユーザが1つのデータポイントを1つのドメインに[B]$で保持するときに、1つの量子を推定する2つの強調適応アルゴリズムを考察する。
適応的な設定では、$varepsilon$-LDPアルゴリズムを用い、$O(fraclog Bvarepsilon2alpha2)$ユーザしか必要としないエラー$alpha$内の量子化を推定できる。
論文 参考訳（メタデータ） (2025-02-05T08:39:02Z) - Representative Arm Identification: A fixed confidence approach to identify cluster representatives [7.459521930846415]
マルチアームバンディット(MAB)フレームワークにおける代表腕識別問題について検討する。
RAI問題は、最高の腕や、上位の$K$から$M$を識別するなど、いくつかのよく研究されたMAB問題としてカバーされている。
本稿では,信頼区間の概念に基づく2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-08-26T11:47:52Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。