論文の概要: Active Learning of General Halfspaces: Label Queries vs Membership Queries

• arxiv url: http://arxiv.org/abs/2501.00508v1
• Date: Tue, 31 Dec 2024 15:40:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-05 17:13:09.741096
• Title: Active Learning of General Halfspaces: Label Queries vs Membership Queries
• Title（参考訳）: 一般のハーフスペースのアクティブラーニング:ラベルクエリ対メンバシップクエリ
• Authors: Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma,
• Abstract要約: アクティブな学習者は、$tildeOmega(d/(log(m)epsilon)$というラベルの複雑さを必要とする。 クエリ複雑性が$tildeO(min1/p, 1/epsilon + dcdot polylog (1/epsilon))$$O(opt)+epsilon$のエラー保証を実現する。
• 参考スコア（独自算出の注目度）: 35.41111301965335
• License:
• Abstract: We study the problem of learning general (i.e., not necessarily homogeneous) halfspaces under the Gaussian distribution on $R^d$ in the presence of some form of query access. In the classical pool-based active learning model, where the algorithm is allowed to make adaptive label queries to previously sampled points, we establish a strong information-theoretic lower bound ruling out non-trivial improvements over the passive setting. Specifically, we show that any active learner requires label complexity of $\tilde{\Omega}(d/(\log(m)\epsilon))$, where $m$ is the number of unlabeled examples. Specifically, to beat the passive label complexity of $\tilde{O} (d/\epsilon)$, an active learner requires a pool of $2^{poly(d)}$ unlabeled samples. On the positive side, we show that this lower bound can be circumvented with membership query access, even in the agnostic model. Specifically, we give a computationally efficient learner with query complexity of $\tilde{O}(\min\{1/p, 1/\epsilon\} + d\cdot polylog(1/\epsilon))$ achieving error guarantee of $O(opt)+\epsilon$. Here $p \in [0, 1/2]$ is the bias and $opt$ is the 0-1 loss of the optimal halfspace. As a corollary, we obtain a strong separation between the active and membership query models. Taken together, our results characterize the complexity of learning general halfspaces under Gaussian marginals in these models.
• Abstract（参考訳）: ガウス分布の下での一般(つまり、必ずしも同質ではない)半空間の学習問題を、ある種のクエリアクセスの存在下では$R^d$で研究する。 従来のプールベースアクティブラーニングモデルでは、アルゴリズムは以前にサンプリングした点に対して適応ラベルクエリを作成できるため、受動的設定に対する非自明な改善を除外する強力な情報理論の下界を確立できる。 具体的には、どんなアクティブ学習者でも$\tilde{\Omega}(d/(\log(m)\epsilon))$というラベルの複雑さを必要とすることを示す。 具体的には、$\tilde{O} (d/\epsilon)$のパッシブなラベル複雑性に打ち勝つために、アクティブな学習者は、ラベルなしのサンプルに2$^{poly(d)}$のプールを必要とする。 肯定的な側面から、この下限は、アグノスティックモデルであっても、メンバシップクエリアクセスによって回避可能であることを示す。 具体的には、クエリ複雑性が$\tilde{O}(\min\{1/p, 1/\epsilon\} + d\cdot polylog(1/\epsilon))$$O(opt)+\epsilon$のエラー保証を実現する。 ここで$p \in [0, 1/2]$はバイアス、$opt$は最適半空間の0-1損失である。 コーナリーとして、アクティブなクエリモデルとメンバーシップクエリモデルの間には、強い分離が得られます。 まとめると、これらのモデルにおけるガウス境界の下での一般半空間の学習の複雑さを特徴付ける。

関連論文リスト

• Robust Learning of Multi-index Models via Iterative Subspace Approximation [36.138661719725626]
  ガウス分布下でラベルノイズを伴うマルチインデックスモデル(MIM)の学習課題について検討する。 一定の正則性特性を満たす有限範囲の良好なMIMに着目する。 ランダムな分類ノイズが存在する場合、我々のアルゴリズムの複雑さは1/epsilon$と不可知的にスケールする。
  論文  参考訳（メタデータ） (2025-02-13T17:37:42Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Semi-supervised Active Regression [21.51757844385258]
  本稿では,学習課題における偏りのある部分ラベル付きデータの利用について検討する。 学習者は、追加のラベルクエリをほとんど行わずに、mathbbRd | X min_beta in mathbbRd | X beta - Y |2 end2 方程式でデータセット $X にアクセスすることができる。
  論文  参考訳（メタデータ） (2021-06-12T03:28:43Z)
• On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise [4.8728183994912415]
  対比雑音を伴う$mathbbRd$の同質半空間のオンラインアクティブ学習について研究する。 私たちの主な貢献は、時間内で動作するパーセプトロンライクなアクティブラーニングアルゴリズムです。 アルゴリズムは、ほぼ最適ラベルの複雑さで基礎となるハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-12-19T22:04:10Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• Active Local Learning [22.823171570933397]
  クエリポイント$x$とラベルなしのトレーニングセット$S$へのアクティブアクセスを与えられた場合、H$でほぼ最適な$hの予測$h(x)$を出力します。 特にラベルクエリの数は$H$の複雑さとは無関係でなければならないし、関数$h$は$x$とは無関係に明確に定義されるべきである。 これはまた、すぐに距離推定のアルゴリズムを示唆している: ほぼ最適の$hを実際に学習するのに必要となる多くのラベルから$opt(H)$を推定する。
  論文  参考訳（メタデータ） (2020-08-31T05:39:35Z)
• 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)

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

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