論文の概要: On the Complexity of Learning from Label Proportions
- arxiv url: http://arxiv.org/abs/2004.03515v1
- Date: Tue, 7 Apr 2020 16:15:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-15 23:02:50.449682
- Title: On the Complexity of Learning from Label Proportions
- Title(参考訳): ラベル分布からの学習の複雑さについて
- Authors: Benjamin Fish, Lev Reyzin
- Abstract要約: ラベル付学習データを用いてラベル比率で学習する問題について検討する。
この学習モデルは、投票者による政治選挙における候補者の投票数を予測することを含む、幅広い設定に適用できる。
意外なことに、有限VCクラスでは、LPPが効率的に学習できることは、PACで効率的に学習できることの厳密なサブセットであることを示している。
- 参考スコア(独自算出の注目度): 4.111899441919163
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the problem of learning with label proportions, which we call LLP
learning, the training data is unlabeled, and only the proportions of examples
receiving each label are given. The goal is to learn a hypothesis that predicts
the proportions of labels on the distribution underlying the sample. This model
of learning is applicable to a wide variety of settings, including predicting
the number of votes for candidates in political elections from polls.
In this paper, we formally define this class and resolve foundational
questions regarding the computational complexity of LLP and characterize its
relationship to PAC learning. Among our results, we show, perhaps surprisingly,
that for finite VC classes what can be efficiently LLP learned is a strict
subset of what can be leaned efficiently in PAC, under standard complexity
assumptions. We also show that there exist classes of functions whose
learnability in LLP is independent of ZFC, the standard set theoretic axioms.
This implies that LLP learning cannot be easily characterized (like PAC by VC
dimension).
- Abstract(参考訳): LLP学習と呼ばれるラベル比の学習では、トレーニングデータにラベルが付けられておらず、各ラベルを受信するサンプルの割合のみが与えられる。
目的は、サンプルの基礎となる分布上のラベルの割合を予測する仮説を学習することである。
この学習モデルは、投票者による政治選挙における候補者の投票数を予測することを含む、幅広い設定に適用できる。
本稿では,このクラスを正式に定義し,LPPの計算複雑性に関する基礎的な疑問を解決し,PAC学習との関係を特徴づける。
私たちの結果のうち、おそらく驚くべきことに、llpが効率的に学習できる有限のvcクラスは、標準的な複雑性仮定の下で、pacで効率的に傾けるものの厳密なサブセットである。
また、LLPにおける学習可能性が標準集合理論公理であるZFCに依存しない関数のクラスが存在することを示す。
これはLPP学習を(VC次元によるPACのような)容易に特徴付けることができないことを意味する。
関連論文リスト
- Partial Label Learning with a Partner [55.74236846238119]
部分ラベル学習(PLL)では、各インスタンスは候補ラベルのセットに関連付けられ、そのうち1つだけが接地真実である。
提案手法は, 未ラベルサンプルの同定と修正を支援するため, 新たなパートナーを導入し, 相互監督のパラダイムを提案する。
論文 参考訳(メタデータ) (2023-12-18T09:09:52Z) - Robust Representation Learning for Unreliable Partial Label Learning [86.909511808373]
部分ラベル学習(Partial Label Learning, PLL)は、弱い教師付き学習の一種で、各トレーニングインスタンスに候補ラベルのセットが割り当てられる。
これはUn Reliable partial Label Learning (UPLL) と呼ばれ、部分ラベルの本質的な信頼性の欠如とあいまいさにより、さらなる複雑さをもたらす。
本研究では,信頼できない部分ラベルに対するモデル強化を支援するために,信頼性に欠けるコントラスト学習を活用するUnreliability-Robust Representation Learning framework(URRL)を提案する。
論文 参考訳(メタデータ) (2023-08-31T13:37:28Z) - Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
実現可能性の仮定を必要としない,単純かつ効率的なブースティングアルゴリズムを提案する。
本稿では,リスト学習者の向上に関する新たな結果と,マルチクラスPAC学習の特徴付けのための新しい証明を提案する。
論文 参考訳(メタデータ) (2023-07-02T19:26:58Z) - Pseudo Labels Regularization for Imbalanced Partial-Label Learning [11.93067260471484]
部分ラベル学習と長期学習の課題は、まともな境界分布と擬似ラベルの描画を一致させることである。
本手法は,ヘッドクラスの擬似ラベルを罰することにより,標準化されたベンチマークの下で最先端の手法を実装している。
論文 参考訳(メタデータ) (2023-03-06T15:21:55Z) - Learning with Partial Labels from Semi-supervised Perspective [28.735185883881172]
部分ラベル学習(Partial Label、PL)とは、部分ラベル付きデータから学習するタスクである。
セミスーパーバイザード・パースペクティブ(PLSP)を用いた部分ラベル学習という新しいPL学習手法を提案する。
PLSPは、特に高いあいまいさレベルにおいて、既存のPLベースライン法よりも著しく優れている。
論文 参考訳(メタデータ) (2022-11-24T15:12:16Z) - Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。
本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
論文 参考訳(メタデータ) (2022-10-26T03:19:24Z) - Learning from Label Proportions by Learning with Label Noise [30.7933303912474]
ラベル比例(LLP)からの学習は、データポイントをバッグに分類する弱い教師付き分類問題である。
ラベル雑音による学習の低減に基づくLLPに対する理論的基礎的なアプローチを提案する。
このアプローチは、複数のデータセットやアーキテクチャにわたるディープラーニングシナリオにおける経験的パフォーマンスの向上を実証する。
論文 参考訳(メタデータ) (2022-03-04T18:52:21Z) - Learning with Proper Partial Labels [87.65718705642819]
部分ラベル学習は、不正確なラベルを持つ弱い教師付き学習の一種である。
この適切な部分ラベル学習フレームワークには,従来の部分ラベル学習設定が数多く含まれていることを示す。
次に、分類リスクの統一的非バイアス推定器を導出する。
論文 参考訳(メタデータ) (2021-12-23T01:37:03Z) - Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
部分ラベル学習(Partial-label Learning, PLL)は、典型的な弱教師付き学習問題であり、各トレーニングインスタンスには、真のラベルである候補ラベルのセットが設けられている。
既存のほとんどの手法は、特定の方法で解決しなければならない制約付き最適化として精巧に設計されており、計算複雑性をビッグデータにスケールアップするボトルネックにしている。
本稿では,モデルと最適化アルゴリズムの柔軟性を備えた分類器の新しいフレームワークを提案する。
論文 参考訳(メタデータ) (2020-02-19T08:35:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。