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

• arxiv url: http://arxiv.org/abs/2405.05190v1
• Date: Wed, 8 May 2024 16:26:49 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-09 13:55:22.269603
• Title: Is Transductive Learning Equivalent to PAC Learning?
• Title（参考訳）: トランスダクティブ学習はPAC学習に等価か?
• Authors: Shaddin Dughmi, Yusuf Kalayci, Grayson York,
• Abstract要約: 本研究では,トランスダクティブ学習とPAC学習は,実現可能な環境において擬似的損失を伴う教師あり学習と本質的に等価であることを示す。 その結果,トランスダクティブ学習とPAC学習は,実現可能な環境において擬似的損失を伴う教師あり学習と本質的に同等であることが示唆された。
• 参考スコア（独自算出の注目度）: 0.9012198585960443
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Most work in the area of learning theory has focused on designing effective Probably Approximately Correct (PAC) learners. Recently, other models of learning such as transductive error have seen more scrutiny. We move toward showing that these problems are equivalent by reducing agnostic learning with a PAC guarantee to agnostic learning with a transductive guarantee by adding a small number of samples to the dataset. We first rederive the result of Aden-Ali et al. arXiv:2304.09167 reducing PAC learning to transductive learning in the realizable setting using simpler techniques and at more generality as background for our main positive result. Our agnostic transductive to PAC conversion technique extends the aforementioned argument to the agnostic case, showing that an agnostic transductive learner can be efficiently converted to an agnostic PAC learner. Finally, we characterize the performance of the agnostic one inclusion graph algorithm of Asilis et al. arXiv:2309.13692 for binary classification, and show that plugging it into our reduction leads to an agnostic PAC learner that is essentially optimal. Our results imply that transductive and PAC learning are essentially equivalent for supervised learning with pseudometric losses in the realizable setting, and for binary classification in the agnostic setting. We conjecture this is true more generally for the agnostic setting.
• Abstract（参考訳）: 学習理論の領域におけるほとんどの研究は、効果的な確率的略正(PAC)学習者の設計に焦点を当てている。 近年,帰納的誤りなどの他の学習モデルはより精査されている。 我々は,これらの問題に対して,データセットに少数のサンプルを追加することで,PAC保証付き無知学習とトランスダクティブ保証付き無知学習を減らし,同値であることを示そうとしている。 Aden-Ali et al arXiv:2304.09167によるPAC学習を、より単純な手法で実現可能な実現性学習に還元する。 PAC変換技術は、上記の主張を無知のケースに拡張し、無知のトランスダクティブ学習者が効率よく無知のPAC学習者に変換可能であることを示す。 最後に、バイナリ分類のためのAsilis et al arXiv:2309.13692の非依存型1包含グラフアルゴリズムの性能を特徴付け、これを還元することにより、本質的に最適なPAC学習者となることを示す。 その結果,トランスダクティブ学習と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)

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

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