論文の概要: A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability

• arxiv url: http://arxiv.org/abs/2202.05420v1
• Date: Fri, 11 Feb 2022 03:01:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-14 14:20:27.816003
• Title: A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability
• Title（参考訳）: 半教師付き逆回転PAC学習性の評価
• Authors: Idan Attias and Steve Hanneke and Yishay Mansour
• Abstract要約: 本研究では,PACモデルにおける逆回転予測器の半教師付き学習の問題について検討する。 半教師付き学習におけるサンプルの複雑さには、ラベル付きサンプルの数とラベルなしサンプルの数という2つのパラメータがある。
• 参考スコア（独自算出の注目度）: 50.570683146531564
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of semi-supervised learning of an adversarially-robust predictor in the PAC model, where the learner has access to both labeled and unlabeled examples. The sample complexity in semi-supervised learning has two parameters, the number of labeled examples and the number of unlabeled examples. We consider the complexity measures, $VC_U \leq dim_U \leq VC$ and $VC^*$, where $VC$ is the standard $VC$-dimension, $VC^*$ is its dual, and the other two measures appeared in Montasser et al. (2019). The best sample bound known for robust supervised PAC learning is $O(VC \cdot VC^*)$, and we will compare our sample bounds to $\Lambda$ which is the minimal number of labeled examples required by any robust supervised PAC learning algorithm. Our main results are the following: (1) in the realizable setting it is sufficient to have $O(VC_U)$ labeled examples and $O(\Lambda)$ unlabeled examples. (2) In the agnostic setting, let $\eta$ be the minimal agnostic error. The sample complexity depends on the resulting error rate. If we allow an error of $2\eta+\epsilon$, it is still sufficient to have $O(VC_U)$ labeled examples and $O(\Lambda)$ unlabeled examples. If we insist on having an error $\eta+\epsilon$ then $\Omega(dim_U)$ labeled examples are necessary, as in the supervised case. The above results show that there is a significant benefit in semi-supervised robust learning, as there are hypothesis classes with $VC_U=0$ and $dim_U$ arbitrary large. In supervised learning, having access only to labeled examples requires at least $\Lambda \geq dim_U$ labeled examples. Semi-supervised require only $O(1)$ labeled examples and $O(\Lambda)$ unlabeled examples. A byproduct of our result is that if we assume that the distribution is robustly realizable by a hypothesis class, then with respect to the 0-1 loss we can learn with only $O(VC_U)$ labeled examples, even if the $VC$ is infinite.
• Abstract（参考訳）: 学習者がラベル付きとラベル付きの両方の例にアクセスできるpacモデルにおける,逆ロバスト予測器の半教師付き学習の問題点について検討する。 半教師付き学習におけるサンプル複雑性は、ラベル付きサンプル数とラベルなしサンプル数という2つのパラメータを持つ。 例えば、$VC_U \leq dim_U \leq VC$と$VC^*$、$VC$は標準の$VC$-dimension、$VC^*$はその双対、その他の2つの尺度はMontasser et al. (2019)である。 堅牢なPAC学習で知られている最良のサンプルは$O(VC \cdot VC^*)$であり、我々のサンプル境界を、堅牢なPAC学習アルゴリズムに必要なラベル付きサンプルの最小数である$\Lambda$と比較する。 1) 実現可能な設定では、$O(VC_U)$ラベル付き例と$O(\Lambda)$ラベルなし例を持つことで十分です。 2) agnostic 設定では、$\eta$ を最小の agnostic エラーとする。 サンプルの複雑さは、結果のエラー率に依存する。 2\eta+\epsilon$のエラーを許せば、ラベル付き例は$O(VC_U)$、ラベルなし例は$O(\Lambda)$で十分である。 もし$\eta+\epsilon$のエラーを主張するなら、教師付きの場合のように$\omega(dim_u)$ラベル付き例が必要である。 上記の結果は、半教師付きロバスト学習には、$vc_u=0$ と $dim_u$ を持つ仮説クラスがあるため、大きな利点があることを示している。 教師付き学習では、ラベル付き例のみにアクセスするには、少なくとも$\Lambda \geq dim_U$ラベル付き例が必要である。 半教師はラベル付き例は$O(1)$とラベルなし例は$O(\Lambda)$である。 結果の副産物は、分布が仮説クラスによって堅牢に実現可能であると仮定すると、0-1の損失に対して$O(VC_U)$ラベル付き例だけで学習できるということである。

関連論文リスト

• Transductive Learning Is Compact [10.168670899305232]
  一般の損失関数を用いた教師あり学習において, 広範に保持されるコンパクト性結果を示す。 不適切な計量損失を伴う実現可能な学習のために、サンプルの複雑さの正確なコンパクトさは失敗する可能性があることを示す。 我々は、無知の場合においてより大きなギャップが可能であると推測する。
  論文  参考訳（メタデータ） (2024-02-15T23:10:45Z)
• Virtual Category Learning: A Semi-Supervised Learning Method for Dense Prediction with Extremely Limited Labels [63.16824565919966]
  本稿では,ラベルの修正を伴わずに,混乱したサンプルを積極的に使用することを提案する。 仮想カテゴリー(VC)は、モデルの最適化に安全に貢献できるように、各混乱したサンプルに割り当てられる。 私たちの興味深い発見は、密集した視覚タスクにおけるVC学習の利用に注目しています。
  論文  参考訳（メタデータ） (2023-12-02T16:23:52Z)
• MaxMatch: Semi-Supervised Learning with Worst-Case Consistency [149.03760479533855]
  半教師付き学習(SSL)のための最悪ケース整合正則化手法を提案する。 本稿では,ラベル付きトレーニングデータとラベル付きトレーニングデータとを別々に比較した経験的損失項からなるSSLの一般化について述べる。 この境界によって動機づけられたSSLの目的は、元のラベルのないサンプルと、その複数の拡張版との最大の矛盾を最小限に抑えるものである。
  論文  参考訳（メタデータ） (2022-09-26T12:04:49Z)
• Complementing Semi-Supervised Learning with Uncertainty Quantification [6.612035830987296]
  そこで本研究では,アレータ性およびてんかん性不確実性定量化に依存する,教師なし不確実性認識の新たな目的を提案する。 CIFAR-100やMini-ImageNetのような複雑なデータセットでは,結果が最先端の成果よりも優れています。
  論文  参考訳（メタデータ） (2022-07-22T00:15:02Z)
• An analysis of over-sampling labeled data in semi-supervised learning with FixMatch [66.34968300128631]
  ほとんどの半教師付き学習手法は、ミニバッチを訓練する際にラベルをオーバーサンプルする。 本稿では,この実践が学習と方法を改善するかどうかを考察する。 ラベル付けの有無に関わらず、トレーニングデータから各ミニバッチを均一にサンプリングする別の設定と比較する。
  論文  参考訳（メタデータ） (2022-01-03T12:22:26Z)
• Unsupervised Learning of Debiased Representations with Pseudo-Attributes [85.5691102676175]
  教師なし方式で,単純かつ効果的な脱バイアス手法を提案する。 特徴埋め込み空間上でクラスタリングを行い、クラスタリング結果を利用して疑似属性を識別する。 次に,非偏り表現を学習するために,クラスタベースの新しい重み付け手法を用いる。
  論文  参考訳（メタデータ） (2021-08-06T05:20:46Z)
• Semi-verified PAC Learning from the Crowd [7.594050968868919]
  本研究では,クラウドソース型PAC学習におけるしきい値関数の問題点について検討する。 本稿では,Charikar等の半検証モデルを用いて,PACが基礎となる仮説クラスを大量のラベルクエリで学習可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-13T20:05:16Z)
• Robust learning under clean-label attack [26.323812778809913]
  クリーンラベルデータ汚染攻撃におけるロバスト学習の問題点について検討する。 学習目標は、最適なPAC学習よりも難しい攻撃可能な速度を最小限にすることです。
  論文  参考訳（メタデータ） (2021-03-01T00:21:15Z)
• Multi-Complementary and Unlabeled Learning for Arbitrary Losses and Models [6.177038245239757]
  本稿では,新しい多言語学習フレームワークを提案する。 まず、複数の相補ラベルを持つサンプルから、分類リスクの偏りのない推定を行う。 次に,未ラベルのサンプルをリスク定式化に組み込むことにより,予測器をさらに改良する。
  論文  参考訳（メタデータ） (2020-01-13T13:52:54Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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