論文の概要: Semi-verified PAC Learning from the Crowd
- arxiv url: http://arxiv.org/abs/2106.07080v3
- Date: Thu, 18 May 2023 19:19:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-22 20:22:12.725971
- Title: Semi-verified PAC Learning from the Crowd
- Title(参考訳): 群衆からの半検証PAC学習
- Authors: Shiwei Zeng and Jie Shen
- Abstract要約: 本研究では,クラウドソース型PAC学習におけるしきい値関数の問題点について検討する。
本稿では,Charikar等の半検証モデルを用いて,PACが基礎となる仮説クラスを大量のラベルクエリで学習可能であることを示す。
- 参考スコア(独自算出の注目度): 7.594050968868919
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of crowdsourced PAC learning of threshold functions.
This is a challenging problem and only recently have query-efficient algorithms
been established under the assumption that a noticeable fraction of the workers
are perfect. In this work, we investigate a more challenging case where the
majority may behave adversarially and the rest behave as the Massart noise - a
significant generalization of the perfectness assumption. We show that under
the {semi-verified model} of Charikar et al. (2017), where we have (limited)
access to a trusted oracle who always returns correct annotations, it is
possible to PAC learn the underlying hypothesis class with a manageable amount
of label queries. Moreover, we show that the labeling cost can be drastically
mitigated via the more easily obtained comparison queries. Orthogonal to recent
developments in semi-verified or list-decodable learning that crucially rely on
data distributional assumptions, our PAC guarantee holds by exploring the
wisdom of the crowd.
- Abstract(参考訳): 閾値関数のクラウドソーシングpac学習の問題点について検討する。
これは難しい問題であり、労働者の顕著な割合が完璧であると仮定して、クエリ効率のアルゴリズムが最近確立された。
本研究では, 多数派が逆向きに行動し, 残りがマスアートノイズとして振る舞う, 完全性仮定の顕著な一般化について検討する。
また,Charikar et al. (2017) の<semi-verified model} の下では,常に正しいアノテーションを返却する信頼できる託宣者へのアクセスが制限されているため,PAC が基礎となる仮説クラスを大量のラベルクエリで学習することが可能であることを示す。
さらに,ラベリングコストは,より簡単に得られる比較クエリによって大幅に低減できることを示す。
我々のPACは、データ分散の前提に大きく依存する半検証またはリスト記述可能な学習における最近の発展に対して、群衆の知恵を探求することで保証します。
関連論文リスト
- From Chaos to Clarity: Claim Normalization to Empower Fact-Checking [57.024192702939736]
Claim Normalization(別名 ClaimNorm)は、複雑でノイズの多いソーシャルメディア投稿を、より単純で分かりやすい形式に分解することを目的としている。
本稿では,チェーン・オブ・ソートとクレーム・チェック・バシネス推定を利用した先駆的アプローチであるCACNを提案する。
実験により, CACNは様々な評価尺度において, いくつかの基準値を上回る性能を示した。
論文 参考訳(メタデータ) (2023-10-22T16:07:06Z) - Correcting Underrepresentation and Intersectional Bias for Fair
Classification [55.2480439325792]
偏見バイアスによって劣化したデータから学習する問題について考察し, 正の例を, 一定の数のセンシティブなグループに対して, 異なる未知のレートでフィルタする。
交叉群のメンバーシップが各交叉率を計算不能にするような設定であっても,少数の偏りのないデータを用いてグループワイド・ドロップアウトパラメータを効率的に推定できることが示される。
我々は,この学習と再重み付け過程をカプセル化するアルゴリズムを提案し,高い確率で真の分布に対する仮説のリスクが任意に近いことをPACスタイルの強い保証を提供する。
論文 参考訳(メタデータ) (2023-06-19T18:25:44Z) - Find a witness or shatter: the landscape of computable PAC learning [63.26015736148707]
本稿では,最近の3つのオープンな質問を解き,CPAC学習可能性の研究に寄与する。
まず,全てのCPAC学習可能なクラスが,サンプルの複雑さで適切なCPAC学習が可能なクラスに含まれることを証明した。
第二に、適切に学習できるが、計算不能に急速に増加するサンプルの複雑さに限り、決定可能な仮説のクラスが存在することを示す。
論文 参考訳(メタデータ) (2023-02-06T02:52:36Z) - PAC Verification of Statistical Algorithms [0.10878040851637999]
本研究では,PAC学習目標を満たす仮説(機械学習モデル)を対話的証明を用いて検証する,PAC検証の設定を開発する。
我々は、$mathbbR$を超える間隔の和のPAC検証のためのプロトコルを提案し、そのタスクの提案したプロトコルを改善し、より低い境界の$d$への依存と一致させる。
最終結果は,クエリの制約を満たす統計的アルゴリズムの検証のためのプロトコルである。
論文 参考訳(メタデータ) (2022-11-28T23:57:27Z) - MaxMatch: Semi-Supervised Learning with Worst-Case Consistency [149.03760479533855]
半教師付き学習(SSL)のための最悪ケース整合正則化手法を提案する。
本稿では,ラベル付きトレーニングデータとラベル付きトレーニングデータとを別々に比較した経験的損失項からなるSSLの一般化について述べる。
この境界によって動機づけられたSSLの目的は、元のラベルのないサンプルと、その複数の拡張版との最大の矛盾を最小限に抑えるものである。
論文 参考訳(メタデータ) (2022-09-26T12:04:49Z) - Analyzing Lottery Ticket Hypothesis from PAC-Bayesian Theory Perspective [25.157282476221482]
我々は、PAC-ベイズ理論がLTHと一般化行動の関係を明確に理解できることを示した。
PAC-Bayesバウンダリをスパイク・アンド・スラブ分布を用いて,入賞チケットの分析を行う。
論文 参考訳(メタデータ) (2022-05-15T15:58:27Z) - Learning Stochastic Majority Votes by Minimizing a PAC-Bayes
Generalization Bound [15.557653926558638]
分類器の有限アンサンブルに対する多数票の対について検討し、その一般化特性について検討する。
ディリクレ分布でインスタンス化し、予測されるリスクに対して閉じた形式と微分可能な表現を可能にする。
結果の多数決学習アルゴリズムは、最先端の精度と(非空きな)厳密な境界から恩恵を得る。
論文 参考訳(メタデータ) (2021-06-23T16:57:23Z) - Risk Minimization from Adaptively Collected Data: Guarantees for
Supervised and Policy Learning [57.88785630755165]
経験的リスク最小化(Empirical Risk Minimization, ERM)は、機械学習のワークホースであるが、適応的に収集されたデータを使用すると、そのモデルに依存しない保証が失敗する可能性がある。
本研究では,仮説クラス上での損失関数の平均値を最小限に抑えるため,適応的に収集したデータを用いた一般的な重み付きERMアルゴリズムについて検討する。
政策学習では、探索がゼロになるたびに既存の文献のオープンギャップを埋める率-最適後悔保証を提供する。
論文 参考訳(メタデータ) (2021-06-03T09:50:13Z) - Efficient PAC Learning from the Crowd with Pairwise Comparison [7.594050968868919]
PAC学習しきい値関数の問題を,アノテータが(騒々しい)ラベルやペア比較タグを付与できる群から検討する。
我々は、学習とアノテーションをインターリーブするラベル効率のアルゴリズムを設計し、アルゴリズムの一定のオーバーヘッドをもたらす。
論文 参考訳(メタデータ) (2020-11-02T16:37:55Z) - Probably Approximately Correct Constrained Learning [135.48447120228658]
我々は、ほぼ正しい学習フレームワーク(PAC)に基づく一般化理論を開発する。
PAC学習可能なクラスも制約のある学習者であるという意味では,学習者の導入は学習問題を難しくするものではないことを示す。
このソリューションの特性を分析し,制約付き学習が公平でロバストな分類における問題にどのように対処できるかを説明する。
論文 参考訳(メタデータ) (2020-06-09T19:59:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。