論文の概要: Learning with Positive and Imperfect Unlabeled Data

• arxiv url: http://arxiv.org/abs/2504.10428v1
• Date: Mon, 14 Apr 2025 17:19:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-15 16:53:40.917355
• Title: Learning with Positive and Imperfect Unlabeled Data
• Title（参考訳）: 有意かつ不完全なラベル付きデータによる学習
• Authors: Jane H. Lee, Anay Mehrotra, Manolis Zampetakis,
• Abstract要約: 本研究では,ラベルのないデータ分布がシフトした場合に,正および未ラベルのデータからバイナリ分類器を学習する問題について検討する。 PIU学習における本研究の主な成果は,PIU学習におけるサンプルの複雑さの特徴と,誤分類誤差を実現するための計算的かつ標本効率のよいアルゴリズムである。
• 参考スコア（独自算出の注目度）: 7.04316974339151
• License:
• Abstract: We study the problem of learning binary classifiers from positive and unlabeled data when the unlabeled data distribution is shifted, which we call Positive and Imperfect Unlabeled (PIU) Learning. In the absence of covariate shifts, i.e., with perfect unlabeled data, Denis (1998) reduced this problem to learning under Massart noise; however, that reduction fails under even slight shifts. Our main results on PIU learning are the characterizations of the sample complexity of PIU learning and a computationally and sample-efficient algorithm achieving a misclassification error $\varepsilon$. We further show that our results lead to new algorithms for several related problems. 1. Learning from smooth distributions: We give algorithms that learn interesting concept classes from only positive samples under smooth feature distributions, bypassing known existing impossibility results and contributing to recent advances in smoothened learning (Haghtalab et al, J.ACM'24) (Chandrasekaran et al., COLT'24). 2. Learning with a list of unlabeled distributions: We design new algorithms that apply to a broad class of concept classes under the assumption that we are given a list of unlabeled distributions, one of which--unknown to the learner--is $O(1)$-close to the true feature distribution. 3. Estimation in the presence of unknown truncation: We give the first polynomial sample and time algorithm for estimating the parameters of an exponential family distribution from samples truncated to an unknown set approximable by polynomials in $L_1$-norm. This improves the algorithm by Lee et al. (FOCS'24) that requires approximation in $L_2$-norm. 4. Detecting truncation: We present new algorithms for detecting whether given samples have been truncated (or not) for a broad class of non-product distributions, including non-product distributions, improving the algorithm by De et al. (STOC'24).
• Abstract（参考訳）: 本研究では,未ラベルデータ分布がシフトした際の正・未ラベルデータからバイナリ分類器を学習する問題について検討し,正・不完全未ラベル学習(PIU)と呼ぶ。 完全ラベルのないデータである共変量シフトがないため、デニス(1998年)はこの問題をマスアートノイズの下での学習に還元したが、その減少はわずかにシフトしても失敗する。 PIU学習における主な成果は、PIU学習のサンプル複雑さの特徴と、誤分類誤差を$\varepsilon$とする計算的かつサンプル効率のよいアルゴリズムである。 さらに,本研究の結果から,いくつかの問題に対する新しいアルゴリズムが得られたことを示す。 1. 円滑な分布からの学習: 滑らかな特徴分布下での正のサンプルのみから興味深い概念クラスを学習し, 既知の不合理性を回避し, 近年のスムーズな学習の進歩に寄与するアルゴリズム(Haghtalab et al, J.ACM'24) (Chandrasekaran et al , COLT'24) を提供する。 2) 未ラベル分布のリストを用いた学習: 未ラベル分布のリストが与えられるという前提のもと, 幅広い概念クラスに適用可能な新しいアルゴリズムを設計する。 3. 未知の乱数が存在する場合の推定: L_1$-norm の多項式で近似可能な未知の集合にトランケートされた標本から指数族分布のパラメータを推定するための最初の多項式サンプルと時間アルゴリズムを与える。 これは、$L_2$-normの近似を必要とするLee et al (FOCS'24)によるアルゴリズムを改善する。 4. トランケーションの検出: 非生産物分布を含む幅広い種類の非生産物分布に対して、与えられたサンプルが切り取られているか(あるいは検出されていないか)を検知し、De et al (STOC'24) によるアルゴリズムを改良するアルゴリズムを提案する。

関連論文リスト

• Tolerant Algorithms for Learning with Arbitrary Covariate Shift [18.37181965815327]
  学習者は,ある分布からラベル付き集合を学習するが,異なる,潜在的に逆向きに生成されたテスト分布で評価する。 我々は,PQ学習 (Goldwasser, A. Kalai, Y. Kalai, Montasser NeurIPS 2020) とTDS学習 (Klivans, Stavropoulos, Vasilyan COLT 2024) の2つのフレームワークに注目した。
  論文  参考訳（メタデータ） (2024-06-04T19:50:05Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。 データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-16T04:32:22Z)
• Testable Learning with Distribution Shift [9.036777309376697]
  分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。 テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。 ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
  論文  参考訳（メタデータ） (2023-11-25T23:57:45Z)
• PAC Learning Linear Thresholds from Label Proportions [13.58949814915442]
  ラベルパーセンテージ(LLP)からの学習は教師付き学習の一般化である。 ラベル比のランダムバッグへのアクセスを与えられた場合, LTF を用いて LTF を効率よく学習できることを示す。 学習アルゴリズムの実験的評価と,[Saket'21, Saket'22] とランダム LTF との比較を含む。
  論文  参考訳（メタデータ） (2023-10-16T05:59:34Z)
• Adaptive Negative Evidential Deep Learning for Open-set Semi-supervised Learning [69.81438976273866]
  オープンセット半教師付き学習(Open-set SSL)は、ラベル付きデータ(inliers)で観測されない新しいカテゴリ(outliers)を含むラベル付きデータとテストデータを含む、より実践的なシナリオである。 本研究では,様々な不確かさを定量化するための外乱検出器として顕在的深層学習(EDL)を導入し,自己学習と推論のための異なる不確実性指標を設計する。 Inlierとoutlierの両方を含むラベルなしデータセットに適合するように、新しい適応的負の最適化戦略を提案する。
  論文  参考訳（メタデータ） (2023-03-21T09:07:15Z)
• A Log-linear Gradient Descent Algorithm for Unbalanced Binary Classification using the All Pairs Squared Hinge Loss [0.0]
  本稿では,2乗損失と2乗損失の関数表現を新たに提案し,線形時間あるいは対数線形時間で勾配を計算するアルゴリズムを提案する。 我々の新しいアルゴリズムは、以前のアルゴリズムよりも不均衡なデータセットのAUC値が高く、以前よりも大きなバッチサイズを利用できる。
  論文  参考訳（メタデータ） (2023-02-21T23:35:00Z)
• Dist-PU: Positive-Unlabeled Learning from a Label Distribution Perspective [89.5370481649529]
  本稿では,PU学習のためのラベル分布視点を提案する。 そこで本研究では,予測型と基底型のラベル分布間のラベル分布の整合性を追求する。 提案手法の有効性を3つのベンチマークデータセットで検証した。
  論文  参考訳（メタデータ） (2022-12-06T07:38:29Z)
• Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
  我々は、$rho$が少なくとも0.8$である場合に、エラー指数を少なくとも40%向上させるアルゴリズムを設計し、分析する。 我々の分析は、グラフの一部により多くのデータを割り当てるために、微小だが検出可能なサンプルの統計的変動を巧みに活用することに基づいている。
  論文  参考訳（メタデータ） (2021-10-27T10:45:21Z)
• Minimax Active Learning [61.729667575374606]
  アクティブラーニングは、人間のアノテーションによってラベル付けされる最も代表的なサンプルをクエリすることによって、ラベル効率の高いアルゴリズムを開発することを目指している。 現在のアクティブラーニング技術は、最も不確実なサンプルを選択するためにモデルの不確実性に頼るか、クラスタリングを使うか、最も多様なラベルのないサンプルを選択するために再構築する。 我々は,不確実性と多様性を両立させる半教師付きミニマックスエントロピーに基づく能動学習アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-12-18T19:03:40Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

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

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