Fugu-MT 論文翻訳(概要): Active Learning of Classifiers with Label and Seed Queries

論文の概要: Active Learning of Classifiers with Label and Seed Queries

arxiv url: http://arxiv.org/abs/2209.03996v1
Date: Thu, 8 Sep 2022 18:46:23 GMT
ステータス: 処理完了
システム内更新日: 2022-09-12 12:51:50.405422
Title: Active Learning of Classifiers with Label and Seed Queries
Title（参考訳）: ラベル・シード問合せを用いた分類器のアクティブ学習
Authors: Marco Bressan, Nicol\`o Cesa-Bianchi, Silvio Lattanzi, Andrea Paudice, Maximilian Thiessen
Abstract要約: ラベルクエリのみを許可する標準的なアクティブラーニング設定では、強い凸境界を持つ分類器を$gamma$で学習するには、最悪の場合は$Omegabig(k m log frac1gammabig)$ seedクエリが必要である。 2種類のクエリを慎重に組み合わせることで、$O(m2 log n)$ラベルクエリと$Obig(m log fracmgamma)を使って、$operatornamepoly(n+m)$でバイナリ分類器を時間内に学習できることが示されている。
参考スコア（独自算出の注目度）: 18.34182076906661
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study exact active learning of binary and multiclass classifiers with margin. Given an $n$-point set $X \subset \mathbb{R}^m$, we want to learn any unknown classifier on $X$ whose classes have finite strong convex hull margin, a new notion extending the SVM margin. In the standard active learning setting, where only label queries are allowed, learning a classifier with strong convex hull margin $\gamma$ requires in the worst case $\Omega\big(1+\frac{1}{\gamma}\big)^{(m-1)/2}$ queries. On the other hand, using the more powerful seed queries (a variant of equivalence queries), the target classifier could be learned in $O(m \log n)$ queries via Littlestone's Halving algorithm; however, Halving is computationally inefficient. In this work we show that, by carefully combining the two types of queries, a binary classifier can be learned in time $\operatorname{poly}(n+m)$ using only $O(m^2 \log n)$ label queries and $O\big(m \log \frac{m}{\gamma}\big)$ seed queries; the result extends to $k$-class classifiers at the price of a $k!k^2$ multiplicative overhead. Similar results hold when the input points have bounded bit complexity, or when only one class has strong convex hull margin against the rest. We complement the upper bounds by showing that in the worst case any algorithm needs $\Omega\big(k m \log \frac{1}{\gamma}\big)$ seed and label queries to learn a $k$-class classifier with strong convex hull margin $\gamma$.
Abstract（参考訳）: 本稿では,二項分類と多項分類の正解学習について検討する。 n$-点集合 $X \subset \mathbb{R}^m$ が与えられたとき、SVMマージンを拡張する新しい概念である、クラスが有限な凸殻マージンを持つ$X$上の未知の分類子を学習したい。ラベルクエリのみを許可する標準的なアクティブラーニング設定では、強い凸包マージンを持つ分類器を学習する$\gamma$ は、最悪の場合$\omega\big(1+\frac{1}{\gamma}\big)^{(m-1)/2}$クエリを必要とする。一方、より強力なシードクエリ(同値クエリの変種)を使用することで、LittlestoneのHalvingアルゴリズムを通じて、ターゲット分類器を$O(m \log n)$クエリで学習することができるが、Halvingは計算的に非効率である。この研究では、2つのタイプのクエリを慎重に組み合わせることで、$o(m^2 \log n)$のラベルクエリと$o\big(m \log \frac{m}{\gamma}\big)$のシードクエリのみを使用して、$\operatorname{poly}(n+m)$を時間的に学習できることを示します。 k^2$乗算オーバーヘッド。同様の結果は、入力点が有界なビット複雑性を持つ場合や、他のクラスに対して強い凸包マージンを持つ場合にも成り立つ。最悪の場合、任意のアルゴリズムが$\Omega\big(k m \log \frac{1}{\gamma}\big)$のシードとラベルクエリを必要とし、強い凸包幅を持つ$k$クラス分類器を学習する。

関連論文リスト

Clustering with Non-adaptive Subset Queries [16.662507957069813]
クエリ $S の部分集合 U$, $|S|=2$ が与えられたとき、オラクルは、ポイントが同じクラスタにあり、そうでなければ、イエスを返す。ペアワイズクエリを用いた適応アルゴリズムでは、必要なクエリの数は$Theta(nk)$であることが知られている。非適応スキームは$Omega(n2)$クエリを必要とするが、これは全ての点を問合せすることで得られる自明な$O(n2)$上限と一致する。
論文参考訳（メタデータ） (2024-09-17T05:56:07Z)
Online Learning of Halfspaces with Massart Noise [47.71073318490341]
我々はMassartノイズの存在下でのオンライン学習の課題について検討する。計算効率のよいアルゴリズムで, 誤り境界が$eta T + o(T)$であることを示す。我々はMassartオンライン学習者を用いて、任意のラウンドでランダムなアクションを選択するよりも、少なくとも$(1-1/k) Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。
論文参考訳（メタデータ） (2024-05-21T17:31:10Z)
A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
本稿では,最大$tildeO(d2m3/4)$量子クエリにおいて,$G$のエッジを学習するアルゴリズムを提案する。特に、確率の高い確率で$tildeO(sqrtm)$量子クエリでサイクルとマッチングを学習するランダム化アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-02-28T21:23:40Z)
Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文参考訳（メタデータ） (2021-08-19T16:16:48Z)
Self-training Converts Weak Learners to Strong Learners in Mixture Models [86.7137362125503]
擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
論文参考訳（メタデータ） (2021-06-25T17:59:16Z)
Semi-supervised Active Regression [21.51757844385258]
本稿では,学習課題における偏りのある部分ラベル付きデータの利用について検討する。学習者は、追加のラベルクエリをほとんど行わずに、mathbbRd | X min_beta in mathbbRd | X beta - Y |2 end2 方程式でデータセット $X にアクセスすることができる。
論文参考訳（メタデータ） (2021-06-12T03:28:43Z)
Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文参考訳（メタデータ） (2021-05-17T16:40:48Z)
Active Local Learning [22.823171570933397]
クエリポイント$x$とラベルなしのトレーニングセット$S$へのアクティブアクセスを与えられた場合、H$でほぼ最適な$hの予測$h(x)$を出力します。特にラベルクエリの数は$H$の複雑さとは無関係でなければならないし、関数$h$は$x$とは無関係に明確に定義されるべきである。これはまた、すぐに距離推定のアルゴリズムを示唆している: ほぼ最適の$hを実際に学習するのに必要となる多くのラベルから$opt(H)$を推定する。
論文参考訳（メタデータ） (2020-08-31T05:39:35Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。