論文の概要: Testing Noise Assumptions of Learning Algorithms

• arxiv url: http://arxiv.org/abs/2501.09189v1
• Date: Wed, 15 Jan 2025 22:33:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-17 15:09:09.712995
• Title: Testing Noise Assumptions of Learning Algorithms
• Title（参考訳）: 学習アルゴリズムの騒音推定試験
• Authors: Surbhi Goel, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan,
• Abstract要約: 我々は計算学習理論に根本的な疑問を呈する。 トレーニングセットが与えられたノイズモデルの仮定を満たすかどうかを効率的にテストできるだろうか? トレーニングデータ上で様々なノイズ仮定をテストするための,最初の効率的なアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 20.28174893000374
• License:
• Abstract: We pose a fundamental question in computational learning theory: can we efficiently test whether a training set satisfies the assumptions of a given noise model? This question has remained unaddressed despite decades of research on learning in the presence of noise. In this work, we show that this task is tractable and present the first efficient algorithm to test various noise assumptions on the training data. To model this question, we extend the recently proposed testable learning framework of Rubinfeld and Vasilyan (2023) and require a learner to run an associated test that satisfies the following two conditions: (1) whenever the test accepts, the learner outputs a classifier along with a certificate of optimality, and (2) the test must pass for any dataset drawn according to a specified modeling assumption on both the marginal distribution and the noise model. We then consider the problem of learning halfspaces over Gaussian marginals with Massart noise (where each label can be flipped with probability less than $1/2$ depending on the input features), and give a fully-polynomial time testable learning algorithm. We also show a separation between the classical setting of learning in the presence of structured noise and testable learning. In fact, for the simple case of random classification noise (where each label is flipped with fixed probability $\eta = 1/2$), we show that testable learning requires super-polynomial time while classical learning is trivial.
• Abstract（参考訳）: トレーニングセットが与えられたノイズモデルの仮定を満たすかどうかを効率的にテストできるのか? この問題は、ノイズの存在下での学習に関する何十年にもわたっての研究にもかかわらず、未解決のままである。 本研究では,この課題が抽出可能であることを示し,トレーニングデータ上で様々なノイズ仮定をテストするための,最初の効率的なアルゴリズムを提案する。 この問題をモデル化するために、最近提案されたRubinfeld and Vasilyan (2023) の検証可能な学習フレームワークを拡張し、学習者が次の2つの条件を満たすテストを実行する必要がある。 次に、マスアートノイズを伴うガウスの辺辺空間(各ラベルは入力特徴に応じて1/2ドル未満の確率で反転できる)を学習し、完全多項式時間テスト可能な学習アルゴリズムを提案する。 また、構造化雑音の存在下での古典的な学習設定とテスト可能な学習との分離を示す。 実際、ランダムな分類ノイズ(各ラベルが固定確率$\eta = 1/2$で反転する)の単純な場合、テスト可能な学習は超多項式時間を必要とし、古典的な学習は自明であることを示す。

関連論文リスト

• ROG$_{PL}$: Robust Open-Set Graph Learning via Region-Based Prototype Learning [52.60434474638983]
  本稿では,複雑な雑音グラフデータに対する堅牢なオープンセット学習を実現するために,ROG$_PL$という統一フレームワークを提案する。 このフレームワークは2つのモジュール、すなわちラベルの伝搬による認知と、リージョンによるオープンセットのプロトタイプ学習で構成されている。 我々の知る限り、ROG$_PL$は複雑なノイズを持つグラフデータに対して、最初の堅牢なオープンセットノード分類法である。
  論文  参考訳（メタデータ） (2024-02-28T17:25:06Z)
• Testable Learning with Distribution Shift [9.036777309376697]
  分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。 テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。 ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
  論文  参考訳（メタデータ） (2023-11-25T23:57:45Z)
• Noisy Pair Corrector for Dense Retrieval [59.312376423104055]
  ノイズペアコレクタ(NPC)と呼ばれる新しい手法を提案する。 NPCは検出モジュールと修正モジュールから構成される。 我々は,テキスト検索ベンチマークのNatural QuestionとTriviaQA,コード検索ベンチマークのStaQCとSO-DSで実験を行った。
  論文  参考訳（メタデータ） (2023-11-07T08:27:14Z)
• Efficient Testable Learning of Halfspaces with Adversarial Label Noise [44.32410859776227]
  最近導入されたテスト可能な学習モデルでは、データがテスタを通過すると、データに対する堅牢な学習者の出力を信頼するように、テスタ-ラーナーを作成する必要がある。 テストラナーは、時間$poly(d/eps)$を実行し、ミス分類エラー$O(opt)+eps$でハーフスペースを出力します。
  論文  参考訳（メタデータ） (2023-03-09T18:38:46Z)
• An Efficient Tester-Learner for Halfspaces [13.13131953359806]
  本稿では、Rubinfeld と Vasilyan が最近定義したテスト可能な学習モデルにおいて、ハーフスペースを学習するための最初の効率的なアルゴリズムを提案する(2023)。 このモデルでは、学習者は、トレーニングセットがテストに合格するたびに、その出力仮説の精度がほぼ最適であると認定する。
  論文  参考訳（メタデータ） (2023-02-28T18:51:55Z)
• A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity [15.746613321517282]
  我々は、モーメントマッチングやメートル法非依存のツールを用いて、テスト可能な学習アルゴリズムを開発するための強力な新しいアプローチを提案する。 意外なことに、テスト可能な学習における情報理論の複雑さは、概念クラスのRademacher複雑さによって強く特徴づけられている。
  論文  参考訳（メタデータ） (2022-11-23T21:29:51Z)
• The Optimal Noise in Noise-Contrastive Learning Is Not What You Think [80.07065346699005]
  この仮定から逸脱すると、実際により良い統計的推定結果が得られることが示される。 特に、最適な雑音分布は、データと異なり、また、別の家族からさえも異なる。
  論文  参考訳（メタデータ） (2022-03-02T13:59:20Z)
• Smoothed Embeddings for Certified Few-Shot Learning [63.68667303948808]
  我々はランダムな平滑化を数ショットの学習モデルに拡張し、入力を正規化された埋め込みにマッピングする。 この結果は、異なるデータセットの実験によって確認される。
  論文  参考訳（メタデータ） (2022-02-02T18:19:04Z)
• Robust Learning under Strong Noise via SQs [5.9256596453465225]
  各SQ学習可能なクラスは、幅広いノイズモデルに対して、OPT + $epsilon Misilon誤分類誤差を持つ効率的な学習アルゴリズムを許容することを示す。 この設定は、既知の雑音確率を持つRCNの下で広く研究されている問題分類を大幅に一般化する。
  論文  参考訳（メタデータ） (2020-10-18T21:02:26Z)
• 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)

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

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