論文の概要: Hardness of Learning Boolean Functions from Label Proportions

• arxiv url: http://arxiv.org/abs/2403.19401v1
• Date: Thu, 28 Mar 2024 13:24:18 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-29 16:14:04.146934
• Title: Hardness of Learning Boolean Functions from Label Proportions
• Title（参考訳）: ラベル分布からブール関数を学習する難しさ
• Authors: Venkatesan Guruswami, Rishi Saket,
• Abstract要約: 近年,ラベル比率(LLP)から学習するフレームワークは,機械学習において重要性を増している。 本研究では,LLP学習ブール関数の抽出性に着目した。 最大2ドルでOR関数と整合なサイズのバッグの集合が与えられた場合、常に多くの節の CNF を見つけることはNP-hard であることが示される。 またパリティの学習可能性について研究し、$(q/2q-1 + o(1))$-fraction以上を満たすのがNPハードであることを示す。
• 参考スコア（独自算出の注目度）: 33.02999921743856
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In recent years the framework of learning from label proportions (LLP) has been gaining importance in machine learning. In this setting, the training examples are aggregated into subsets or bags and only the average label per bag is available for learning an example-level predictor. This generalizes traditional PAC learning which is the special case of unit-sized bags. The computational learning aspects of LLP were studied in recent works (Saket, NeurIPS'21; Saket, NeurIPS'22) which showed algorithms and hardness for learning halfspaces in the LLP setting. In this work we focus on the intractability of LLP learning Boolean functions. Our first result shows that given a collection of bags of size at most $2$ which are consistent with an OR function, it is NP-hard to find a CNF of constantly many clauses which satisfies any constant-fraction of the bags. This is in contrast with the work of (Saket, NeurIPS'21) which gave a $(2/5)$-approximation for learning ORs using a halfspace. Thus, our result provides a separation between constant clause CNFs and halfspaces as hypotheses for LLP learning ORs. Next, we prove the hardness of satisfying more than $1/2 + o(1)$ fraction of such bags using a $t$-DNF (i.e. DNF where each term has $\leq t$ literals) for any constant $t$. In usual PAC learning such a hardness was known (Khot-Saket, FOCS'08) only for learning noisy ORs. We also study the learnability of parities and show that it is NP-hard to satisfy more than $(q/2^{q-1} + o(1))$-fraction of $q$-sized bags which are consistent with a parity using a parity, while a random parity based algorithm achieves a $(1/2^{q-2})$-approximation.
• Abstract（参考訳）: 近年,ラベル比率(LLP)から学習するフレームワークは,機械学習において重要性を増している。 この設定では、トレーニング例はサブセットまたはバッグに集約され、サンプルレベルの予測子を学ぶために、バッグごとの平均ラベルのみが利用可能である。 これは、単位サイズのバッグの特殊なケースである従来のPAC学習を一般化する。 LLPの計算学習の側面は、最近の研究(Saket, NeurIPS'21; Saket, NeurIPS'22)で研究され、LLP設定におけるハーフスペースの学習のためのアルゴリズムと硬さを示した。 本研究では,LLP学習ブール関数の抽出性に着目した。 最初の結果は、少なくとも2ドルでOR関数と整合性を持つバッグの集合が与えられた場合、常に多くの節のCNFを見つけることがNPハードであることを示している。 これは(Saket, NeurIPS'21)の作業とは対照的に、ハーフスペースを使ってORを学習するための(2/5)$-approximationを与えました。 そこで本研究では,LLP学習ORの仮説として,定数節CNFとハーフスペースを分離した。 次に、任意の定数$t$に対して$t$-DNF(つまり、各項が$\leq t$リテラルを持つDNF)を用いて、そのようなバッグの1/2 + o(1)$分以上を満たすことの難しさを証明する。 通常のPAC学習では、ノイズORを学習するためにのみ、そのような難易度(Khot-Saket, FOCS'08)が知られていた。 またパリティの学習可能性について検討し、$(q/2^{q-1} + o(1))$-fraction of $q$-sized bag that are consistent with a parity using a parity, while a random parity based algorithm achieve a $(1/2^{q-2})$-approximation。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Tight Time-Space Lower Bounds for Constant-Pass Learning [1.7387739961208148]
  サンプルストリームを$q$で通過するパリティ学習アルゴリズムに対して,メモリサンプルの少ないバウンダリを厳密に証明する。 このような学習者には、メモリサイズが$Omega(n2)$か、少なくとも$Omega(n)$サンプルが必要である。 これまでの研究と同様に、この結果は、ほぼ直交的な概念を多く含んだ学習問題にまで及んでいる。
  論文  参考訳（メタデータ） (2023-10-12T06:36:31Z)
• Distributional PAC-Learning from Nisan's Natural Proofs [0.0]
  Lambda-circuitsを学習するために、$Lambdaの回路境界の自然な証明は効率的なアルゴリズムを暗示する。 我々は、この意味を$Lambda notsupseteq AC0[p]$、ランダムな例のみを用いて任意の例分布を学習する学習アルゴリズムに一般化できるかどうか検討する。
  論文  参考訳（メタデータ） (2023-10-05T16:13:29Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• The Sample Complexity of Multi-Distribution Learning for VC Classes [25.73730126599202]
  マルチディストリビューション学習は、PAC学習を複数のデータ分布を持つ設定に一般化したものである。 PAC学習クラスでは, 既知の上層境界と下層境界との間に大きなギャップが残っている。 本稿では,この問題の最近の進展と,統計学習におけるゲームダイナミクスの利用の基礎となるいくつかのハードルについて論じる。
  論文  参考訳（メタデータ） (2023-07-22T18:02:53Z)
• Agnostic Multi-Group Active Learning [24.97598179536084]
  能動的学習の観点から,この問題の変種を考察し,学習者がコレクションの各分布からどの例をラベル付けするかを判断する権限を付与する。 我々の主な課題は、不一致に基づくアクティブラーニングのような標準的なアクティブラーニング技術が、マルチグループラーニングの目的に直接適用されないことである。 既存のアルゴリズムを改良し、多群学習の非依存的な定式化のための一貫した能動的学習アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-06-02T21:24:13Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
  論文  参考訳（メタデータ） (2020-06-25T19:59:24Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。 正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
  論文  参考訳（メタデータ） (2020-06-22T17:53:54Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

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

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