論文の概要: Is Transductive Learning Equivalent to PAC Learning?

• arxiv url: http://arxiv.org/abs/2405.05190v2
• Date: Tue, 29 Oct 2024 22:07:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-31 14:23:43.843641
• Title: Is Transductive Learning Equivalent to PAC Learning?
• Title（参考訳）: トランスダクティブ学習はPAC学習に等価か?
• Authors: Shaddin Dughmi, Yusuf Kalayci, Grayson York,
• Abstract要約: PACモデルとトランスダクティブモデルは、本質的には非依存のバイナリ分類に等価であることを示す。 我々は,2番目の結果が2進分類を超えて拡張可能かどうかという興味深い疑問を残して,トランスダクティブモデルとPACモデルがより広範に等価であることを示す。
• 参考スコア（独自算出の注目度）: 0.9012198585960443
• License:
• Abstract: Much of learning theory is concerned with the design and analysis of probably approximately correct (PAC) learners. The closely related transductive model of learning has recently seen more scrutiny, with its learners often used as precursors to PAC learners. Our goal in this work is to understand and quantify the exact relationship between these two models. First, we observe that modest extensions of existing results show the models to be essentially equivalent for realizable learning for most natural loss functions, up to low order terms in the error and sample complexity. The situation for agnostic learning appears less straightforward, with sample complexities potentially separated by a $\frac{1}{\epsilon}$ factor. This is therefore where our main contributions lie. Our results are two-fold: 1. For agnostic learning with bounded losses (including, for example, multiclass classification), we show that PAC learning reduces to transductive learning at the cost of low-order terms in the error and sample complexity via an adaptation of the reduction of arXiv:2304.09167 to the agnostic setting. 2. For agnostic binary classification, we show the converse: transductive learning is essentially no more difficult than PAC learning. Together with our first result this implies that the PAC and transductive models are essentially equivalent for agnostic binary classification. This is our most technical result, and involves two steps: A symmetrization argument on the agnostic one-inclusion graph (OIG) of arXiv:2309.13692 to derive the worst-case agnostic transductive instance, and expressing the error of the agnostic OIG algorithm for this instance in terms of the empirical Rademacher complexity of the class. We leave as an intriguing open question whether our second result can be extended beyond binary classification to show the transductive and PAC models equivalent more broadly.
• Abstract（参考訳）: 学習理論の多くは、おそらくほぼ正しい(PAC)学習者の設計と分析に関係している。 近縁な学習モデルであるトランスダクティブ・モデルは最近より精査され、その学習者はPAC学習者の前駆体としてしばしば使用される。 この研究の目標は、これらの2つのモデル間の正確な関係を理解し、定量化することです。 まず、既存の結果の控えめな拡張は、ほとんどの自然損失関数に対して、誤差とサンプルの複雑さの低次項まで、モデルが本質的には実現可能な学習に等価であることを示す。 不可知学習の状況は、より単純で、サンプルの複雑さは$\frac{1}{\epsilon}$ factorによって分離される可能性がある。 ですから、これが私たちの主な貢献の場所なのです。 1) 有界な学習(例えば,多クラス分類を含む)においては,PAC学習は,arXiv:2304.09167の減少を適応させることにより,誤差とサンプルの複雑さの低次項を犠牲にして,トランスダクティブ学習に還元されることを示す。 2) 不可知二分分類では, トランスダクティブ・ラーニングはPAC学習ほど難しくない。 最初の結果と合わせて、PACとトランスダクティブモデルが本質的に非依存のバイナリ分類に等価であることを示している。 arXiv:2309.13692のAgnostic One-inclusion graph (OIG) に関する対称性の議論は、最悪の場合のAgnostic Transductiveインスタンスを導出するものであり、この場合のAgnostic OIGアルゴリズムの誤差を、経験的なRademacher複雑性の観点から表現するものである。 我々は,2番目の結果が2進分類を超えて拡張可能かどうかという興味深い疑問を残して,トランスダクティブモデルとPACモデルをより広範囲に示す。

関連論文リスト

• Error Exponent in Agnostic PAC Learning [4.772817128620037]
  おそらく略正解(PAC)は、学習問題やアルゴリズムの分析に広く用いられている。 本稿では,情報理論における誤り指数を用いたPAC学習について考察する。 いくつかの仮定では、幅広い問題に対する分散依存誤差指数の改善が見られ、学習におけるPAC誤差確率の指数的挙動が確立される。
  論文  参考訳（メタデータ） (2024-05-01T18:08:03Z)
• Transductive Learning Is Compact [10.168670899305232]
  一般の損失関数を用いた教師あり学習において, 広範に保持されるコンパクト性結果を示す。 不適切な計量損失を伴う実現可能な学習のために、サンプルの複雑さの正確なコンパクトさは失敗する可能性があることを示す。 我々は、無知の場合においてより大きなギャップが可能であると推測する。
  論文  参考訳（メタデータ） (2024-02-15T23:10:45Z)
• On Learning Latent Models with Multi-Instance Weak Supervision [57.18649648182171]
  本稿では,複数の入力インスタンスに関連付けられた遷移関数$sigma$ラベルによって,教師信号が生成される弱い教師付き学習シナリオについて考察する。 我々の問題は、潜在的な構造学習やニューロシンボリックな統合など、さまざまな分野で満たされている。
  論文  参考訳（メタデータ） (2023-06-23T22:05:08Z)
• Learnability, Sample Complexity, and Hypothesis Class Complexity for Regression Models [10.66048003460524]
  この研究はPACの基礎に触発され、既存の回帰学習問題に動機付けられている。 提案手法はEpsilon-Confidence Aough Correct (epsilon CoAC)で示され、Kullback Leibler divergence(相対エントロピー)を利用する。 これにより、学習者は異なる複雑性順序の仮説クラスを比較でき、それらの中から最小のエプシロンを最適に選択できる。
  論文  参考訳（メタデータ） (2023-03-28T15:59:12Z)
• Agnostic PAC Learning of k-juntas Using L2-Polynomial Regression [9.732863739456036]
  計算複雑性の低いフーリエ展開に基づく新しいPAC学習アルゴリズムを提案する。 我々は,PAC学習を0-1の損失と最小2乗推定問題とを結びつけることで,その結果を実証する。 MMSE誤差から0-1損失の優雅な上限を導出し、MMSEの符号がMMSEを含む任意の概念クラスに対するPAC学習者であることを示す。
  論文  参考訳（メタデータ） (2023-03-08T19:54:07Z)
• Instance-Dependent Label-Noise Learning with Manifold-Regularized Transition Matrix Estimation [172.81824511381984]
  遷移行列 T(x) は、インスタンス依存ノイズ(IDN)の下では特定できない 我々は、T(x) の幾何学について、「より近い2つのインスタンスは、それに対応する遷移行列がより類似している」という仮定を提案する。 本手法は,難解なIDNの下でのラベルノイズ学習において,最先端の手法よりも優れている。
  論文  参考訳（メタデータ） (2022-06-06T04:12:01Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  因果構造を学習することは、通常、スコアまたは独立テストを使用して構造を評価することを伴う探索問題を引き起こす。 本研究では,観測・干渉データから因果構造を予測するため,変分推論モデルを訓練する。 我々のモデルは、実質的な分布シフトの下で頑健な一般化能力を示す。
  論文  参考訳（メタデータ） (2022-05-25T17:37:08Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals [47.81107898315438]
  そこで我々は,二元性LPを用いて,多種多様な問題に対するサンプルのハードファミリーを見つける手法を開発した。 L1$-regression は本質的には最適であり、概念クラスを学習する際の計算困難さは、クラスから任意の関数を近似するのに要する次数と密接に関連していることが示される。
  論文  参考訳（メタデータ） (2021-02-08T18:06:32Z)
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
  分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。 この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
  論文  参考訳（メタデータ） (2020-07-30T04:18:51Z)

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

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