論文の概要: How to Query An Oracle? Efficient Strategies to Label Data
- arxiv url: http://arxiv.org/abs/2110.02341v1
- Date: Tue, 5 Oct 2021 20:15:35 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-07 14:06:01.236081
- Title: How to Query An Oracle? Efficient Strategies to Label Data
- Title（参考訳）: oracleに問い合わせる方法は?
データラベルの効率的な戦略
- Authors: Farshad Lahouti, Victoria Kostina, Babak Hassibi
- Abstract要約: 機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。
本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。
さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
- 参考スコア（独自算出の注目度）: 59.89900843097016
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the basic problem of querying an expert oracle for labeling a
dataset in machine learning. This is typically an expensive and time consuming
process and therefore, we seek ways to do so efficiently. The conventional
approach involves comparing each sample with (the representative of) each class
to find a match. In a setting with $N$ equally likely classes, this involves
$N/2$ pairwise comparisons (queries per sample) on average. We consider a
$k$-ary query scheme with $k\ge 2$ samples in a query that identifies
(dis)similar items in the set while effectively exploiting the associated
transitive relations. We present a randomized batch algorithm that operates on
a round-by-round basis to label the samples and achieves a query rate of
$O(\frac{N}{k^2})$. In addition, we present an adaptive greedy query scheme,
which achieves an average rate of $\approx 0.2N$ queries per sample with
triplet queries. For the proposed algorithms, we investigate the query rate
performance analytically and with simulations. Empirical studies suggest that
each triplet query takes an expert at most 50\% more time compared with a
pairwise query, indicating the effectiveness of the proposed $k$-ary query
schemes. We generalize the analyses to nonuniform class distributions when
possible.
- Abstract（参考訳）: 我々は、機械学習でデータセットをラベル付けするためにエキスパートオラクルに問い合わせる基本的な問題を考える。
これは一般的に高価で時間のかかるプロセスであり、効率的な方法を模索しています。
従来のアプローチでは、各サンプルと各クラス(代表)を比較してマッチを見つける。
等しく可能なクラスが$N$の場合、これは平均で$N/2$ペアワイズ比較(サンプルあたりのクエリ)を行う。
k$-aryのクエリスキームと$k\ge 2$のサンプルをセット内の類似のアイテムを識別し、関連する推移的関係を効果的に活用するクエリで検討する。
サンプルをラベル付けするためにラウンドバイラウンドで動作し,クエリレートが$o(\frac{n}{k^2})$となるランダム化バッチアルゴリズムを提案する。
さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたりの平均値は$\approx 0.2N$である。
提案アルゴリズムでは,クエリレートの性能を解析的に,シミュレーションにより検討する。
実証的研究により、各三重項クエリは、ペアクエリと比較して、少なくとも50倍の時間でエキスパートを必要とすることが示唆され、提案された$k$-aryクエリスキームの有効性が示されている。
可能な場合、解析を非一様クラス分布に一般化する。
関連論文リスト
- Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity [16.331196225467707]
強化学習におけるサンプル効率と適応性の関係を理論的に検討する。
私たちは、バッチ毎にフィードバックが処理され、クエリが更新されるように、クエリをK$のバッチで送信できる学習フレームワークを採用しています。
論文 参考訳（メタデータ） (2023-10-02T20:14:01Z) - JoinGym: An Efficient Query Optimization Environment for Reinforcement
Learning [58.71541261221863]
結合順序選択(JOS)は、クエリの実行コストを最小化するために結合操作を順序付けする問題である。
木質強化学習(RL)のためのクエリ最適化環境JoinGymを提案する。
JoinGymは内部で、事前計算されたデータセットから中間結果の濃度を調べることで、クエリプランのコストをシミュレートする。
論文 参考訳（メタデータ） (2023-07-21T17:00:06Z) - Fast Interactive Search with a Scale-Free Comparison Oracle [17.38671584773247]
比較ベースの検索アルゴリズムにより、ユーザはフォームのクエリに応答してデータベース内のターゲットアイテム$t$を見つけることができる。
そのような類似性三重項に対して$(i,j;t)$に対して$gamma$-CKLと呼ばれるスケールフリー確率オラクルモデルを提案する。
我々は,バックトラッキング戦略により,$gamma$-CKL のオラクルの下で,指数関数的に収束率の高い探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-06-02T09:33:19Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳（メタデータ） (2022-11-28T08:40:12Z) - Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with
a Faulty Oracle [7.449644976563424]
本稿では,クラスタリングを不良オラクルで研究するためのエレガントな理論的モデルを提案する。
一般の場合の$k$クラスタに対して、クエリ最適で時間効率のアルゴリズムを得られるかどうかというオープンな疑問として残された。
情報理論の回復が可能であれば,全ての定数$k$に対して,ほぼ最適なクエリ複雑性(最大$O(log2 n)$)を持つ時間効率アルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-06-18T22:20:12Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - A Provably Efficient Sample Collection Strategy for Reinforcement
Learning [123.69175280309226]
オンライン強化学習(RL)における課題の1つは、エージェントがその振る舞いを最適化するために、環境の探索とサンプルの活用をトレードオフする必要があることである。
1) 生成モデル(環境のスパースシミュレータなど)にアクセス可能な状態のサンプル数を規定する「対象別」アルゴリズム,2) 所定のサンプルをできるだけ早く生成する「対象別」サンプル収集。
論文 参考訳（メタデータ） (2020-07-13T15:17:35Z) - Query complexity of heavy hitter estimation [6.373263986460191]
我々は、サブセット $mathcalSgamma_mathcalP$ を、基礎となる分布 $mathcalP$ をサポートする要素の特定の問題を考える。
それぞれのクエリはインデックス$i$であり、オラクルは値を$X_i$と$(b)$はペア$(i,j)$である。
それぞれの問合せモデルに対して、各ラウンドでどの問合せを全体に依存するかを決定するシーケンシャルな推定アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-05-29T07:15:46Z) - Query-Efficient Correlation Clustering [13.085439249887713]
相関クラスタリングはクラスタリングの最も自然な定式化であることは間違いない。
相関クラスタリングの主な欠点は、入力として$Theta(n2)$ペアの類似性を必要とすることである。
我々は,最大3cdot OPT + O(fracn3Q)$の相違点が期待される解が得られる相関クラスタリングアルゴリズムを考案した。
論文 参考訳（メタデータ） (2020-02-26T15:18:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。