論文の概要: Proper Learnability and the Role of Unlabeled Data

• arxiv url: http://arxiv.org/abs/2502.10359v1
• Date: Fri, 14 Feb 2025 18:41:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-17 14:47:42.143340
• Title: Proper Learnability and the Role of Unlabeled Data
• Title（参考訳）: 学習性の向上とラベルなしデータの役割
• Authors: Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng,
• Abstract要約: 適切な学習可能性が論理的に決定不可能な問題、すなわちZFC公理に依存しない問題が存在することを示す。 そこで本研究では,PACモデルにおいて,適切な学習可能性の特性を損なう不確実性に関するすべての結果を示す。
• 参考スコア（独自算出の注目度）: 10.168670899305232
• License:
• Abstract: Proper learning refers to the setting in which learners must emit predictors in the underlying hypothesis class $H$, and often leads to learners with simple algorithmic forms (e.g. empirical risk minimization (ERM), structural risk minimization (SRM)). The limitation of proper learning, however, is that there exist problems which can only be learned improperly, e.g. in multiclass classification. Thus, we ask: Under what assumptions on the hypothesis class or the information provided to the learner is a problem properly learnable? We first demonstrate that when the unlabeled data distribution is given, there always exists an optimal proper learner governed by distributional regularization, a randomized generalization of regularization. We refer to this setting as the distribution-fixed PAC model, and continue to evaluate the learner on its worst-case performance over all distributions. Our result holds for all metric loss functions and any finite learning problem (with no dependence on its size). Further, we demonstrate that sample complexities in the distribution-fixed PAC model can shrink by only a logarithmic factor from the classic PAC model, strongly refuting the role of unlabeled data in PAC learning (from a worst-case perspective). We complement this with impossibility results which obstruct any characterization of proper learnability in the realizable PAC model. First, we observe that there are problems whose proper learnability is logically undecidable, i.e., independent of the ZFC axioms. We then show that proper learnability is not a monotone property of the underlying hypothesis class, and that it is not a local property (in a precise sense). Our impossibility results all hold even for the fundamental setting of multiclass classification, and go through a reduction of EMX learning (Ben-David et al., 2019) to proper classification which may be of independent interest.
• Abstract（参考訳）: 適切な学習は、学習者が基礎となる仮説クラス$H$で予測器を出力しなければならない設定を指し、しばしば単純なアルゴリズム形式(例えば、経験的リスク最小化(ERM)、構造的リスク最小化(SRM))を持つ学習者につながる。 しかし、適切な学習の限界は、マルチクラス分類において、不適切にしか学べない問題が存在することである。 仮説クラスや学習者に提供された情報はどのような仮定で適切に学習可能か? まず、ラベルのないデータ分布が与えられると、正規化のランダム化一般化である分布正規化に支配される最適な適切な学習者が常に存在することを実証する。 我々は,この設定を分散固定型PACモデルと呼び,全ての分布に対して最悪の性能を示す学習者の評価を継続する。 この結果は、すべての計量損失関数と有限学習問題に対して成り立つ(サイズに依存しない)。 さらに、分散固定PACモデルにおけるサンプル複雑度は、古典的なPACモデルからの対数係数のみによって減少し、PAC学習におけるラベルなしデータの役割を(最悪の場合の観点から)強く否定することを示した。 PACモデルにおいて、適切な学習可能性の特性を阻害する不合理な結果でこれを補完する。 まず、適切な学習可能性が論理的に決定不可能な問題、すなわちZFC公理に依存しない問題が存在することを観察する。 次に、適切な学習性は、基礎となる仮説クラスの単調な性質ではなく、(正確には)局所的な性質ではないことを示す。 EMX学習(Ben-David et al , 2019)から独立した関心を持つ可能性のある適切な分類へと還元されていく。

関連論文リスト

• Probably Approximately Precision and Recall Learning [62.912015491907994]
  精度とリコールは機械学習の基本的な指標である。 一方的なフィードバック – トレーニング中にのみ肯定的な例が観察される – は,多くの実践的な問題に固有のものだ。 PAC学習フレームワークでは,各仮説をグラフで表現し,エッジは肯定的な相互作用を示す。
  論文  参考訳（メタデータ） (2024-11-20T04:21:07Z)
• On Characterizing and Mitigating Imbalances in Multi-Instance Partial Label Learning [57.18649648182171]
  我々は、MI-PLLの文脈において、これまで研究されていない問題に対処するためのコントリビューションを行っている。 最小限の仮定をしながら、クラス固有のMI-PLLのリスク境界を導出する。 我々の理論は、$sigma$が学習の不均衡に大きな影響を及ぼすというユニークな現象を明らかにしている。
  論文  参考訳（メタデータ） (2024-07-13T20:56:34Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。 データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-16T04:32:22Z)
• 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)
• Differentially-Private Bayes Consistency [70.92545332158217]
  差分プライバシー(DP)を満たすベイズ一貫した学習ルールを構築する。 ほぼ最適なサンプル複雑性を持つ半教師付き環境で,任意のVCクラスをプライベートに学習できることを実証する。
  論文  参考訳（メタデータ） (2022-12-08T11:57:30Z)
• Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
  非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。 本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
  論文  参考訳（メタデータ） (2022-10-26T03:19:24Z)
• Semi-verified PAC Learning from the Crowd [7.594050968868919]
  本研究では,クラウドソース型PAC学習におけるしきい値関数の問題点について検討する。 本稿では,Charikar等の半検証モデルを用いて,PACが基礎となる仮説クラスを大量のラベルクエリで学習可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-13T20:05:16Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  経験的リスク最小化(Empirical Risk Minimization, ERM)は、機械学習のワークホースであるが、適応的に収集されたデータを使用すると、そのモデルに依存しない保証が失敗する可能性がある。 本研究では,仮説クラス上での損失関数の平均値を最小限に抑えるため,適応的に収集したデータを用いた一般的な重み付きERMアルゴリズムについて検討する。 政策学習では、探索がゼロになるたびに既存の文献のオープンギャップを埋める率-最適後悔保証を提供する。
  論文  参考訳（メタデータ） (2021-06-03T09:50:13Z)
• A Theory of Universal Learning [26.51949485387526]
  普遍的な学習の確率は3つしかないことを示す。 任意の概念クラスの学習曲線は指数的あるいは任意に遅い速度で減衰することを示す。
  論文  参考訳（メタデータ） (2020-11-09T15:10:32Z)
• Probably Approximately Correct Constrained Learning [135.48447120228658]
  我々は、ほぼ正しい学習フレームワーク(PAC)に基づく一般化理論を開発する。 PAC学習可能なクラスも制約のある学習者であるという意味では,学習者の導入は学習問題を難しくするものではないことを示す。 このソリューションの特性を分析し,制約付き学習が公平でロバストな分類における問題にどのように対処できるかを説明する。
  論文  参考訳（メタデータ） (2020-06-09T19:59:29Z)

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

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