論文の概要: Learning DNF through Generalized Fourier Representations

• arxiv url: http://arxiv.org/abs/2506.01075v1
• Date: Sun, 01 Jun 2025 16:24:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-05 01:42:09.251285
• Title: Learning DNF through Generalized Fourier Representations
• Title（参考訳）: 一般化フーリエ表現によるDNFの学習
• Authors: Mohsen Heidari, Roni Khardon,
• Abstract要約: 学習理論では, 統一型および製品分布下でのDNF(Disjunctive Normal Form)の学習性は, このような表現を通じて確立されている。 本稿では,フーリエ表現を用いた学習分野への5つの主要な貢献について述べる。 最後の貢献は、差分有界木BN分布を学習するためのアルゴリズムを開発することである。
• 参考スコア（独自算出の注目度）: 12.354076490479516
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Fourier representation for the uniform distribution over the Boolean cube has found numerous applications in algorithms and complexity analysis. Notably, in learning theory, learnability of Disjunctive Normal Form (DNF) under uniform as well as product distributions has been established through such representations. This paper makes five main contributions. First, it introduces a generalized Fourier expansion that can be used with any distribution $D$ through the representation of the distribution as a Bayesian network (BN). Second, it shows that the main algorithmic tools for learning with the Fourier representation, that use membership queries to approximate functions by recovering their heavy Fourier coefficients, can be used with slight modifications with the generalized expansion. These results hold for any distribution. Third, it analyzes the $L_1$ spectral norm of conjunctions under the new expansion, showing that it is bounded for a class of distributions which can be represented by difference bounded tree BN, where a parent node in the BN representation can change the conditional expectation of a child node by at most $\alpha<0.5$. Lower bounds are presented to show that such constraints are necessary. The fourth contribution uses these results to show the learnability of DNF with membership queries under difference bounded tree BN. The final contribution is to develop an algorithm for learning difference-bounded tree BN distributions, thus extending the DNF learnability result to cases where the distribution is not known in advance.
• Abstract（参考訳）: ブール立方体上の均一分布に対するフーリエ表現は、アルゴリズムや複雑性解析に多くの応用を見出した。 特に、学習理論において、一様および積分布の下でのDNF(Disjunctive Normal Form)の学習性は、そのような表現を通して確立されている。 本論文の主な貢献は5つある。 まず、一般化されたフーリエ展開を導入し、分布をベイズネットワーク(BN)として表現することで任意の分布で$D$で使用できる。 第2に、フーリエ表現を用いて学習するための主要なアルゴリズムツールが、その重いフーリエ係数を復元することで、会員クエリを使って関数を近似し、一般化された拡張でわずかに修正できることが示される。 これらの結果はどんな分布にも当てはまる。 第3に、新たな拡張の下で結合の$L_1$スペクトルノルムを分析し、BN表現の親ノードが子ノードの条件予測を少なくとも$\alpha<0.5$で変更できるような差分有界木BNで表現できる分布のクラスに有界であることを示す。 下限はそのような制約が必要であることを示すために示される。 第4のコントリビューションは、これらの結果を用いて、差分木BNの下での会員クエリによるDNFの学習可能性を示す。 最後の貢献は、差分有界木BN分布を学習するためのアルゴリズムを開発することである。

関連論文リスト

• SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groups [14.925722398371498]
  本稿では,S_n$以上の複雑な分布を学習するタスクを単純化する離散拡散モデルを提案する。 有限群上のランダムウォークの理論に基づいて拡散長を選択するための経験的ガイドラインを提供する。 本モデルでは,4桁画像のソート,ジグソーパズル,旅行セールスマン問題などの課題に対して,最先端ないし同等のパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2024-10-03T19:37:40Z)
• The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs [59.03660013787925]
  ヘテロフィリー・スノーフレーク仮説を導入し、ヘテロ親和性グラフの研究をガイドし、促進するための効果的なソリューションを提供する。 観察の結果,我々のフレームワークは多種多様なタスクのための多目的演算子として機能することがわかった。 さまざまなGNNフレームワークに統合することができ、パフォーマンスを詳細に向上し、最適なネットワーク深さを選択するための説明可能なアプローチを提供する。
  論文  参考訳（メタデータ） (2024-06-18T12:16:00Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。 我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。 また、異なるアンサンブルを区別する新しい問題も分析できます。
  論文  参考訳（メタデータ） (2024-04-29T14:33:24Z)
• Entropy and the Kullback-Leibler Divergence for Bayesian Networks: Computational Complexity and Efficient Implementation [0.0]
  我々は、最も一般的な分布仮定の下で、シャノンのエントロピーと BN に対するクルバック・リーバーの発散を計算する方法を示す。 ガウス BN に対して、KL の計算複雑性を立方体から二次体に還元できることが示されている。
  論文  参考訳（メタデータ） (2023-11-29T15:51:04Z)
• Factorized Fourier Neural Operators [77.47313102926017]
  Factorized Fourier Neural Operator (F-FNO) は偏微分方程式をシミュレートする学習法である。 我々は,数値解法よりも桁違いに高速に動作しながら,誤差率2%を維持していることを示す。
  論文  参考訳（メタデータ） (2021-11-27T03:34:13Z)
• On some theoretical limitations of Generative Adversarial Networks [77.34726150561087]
  GANが任意の確率分布を生成できるという一般的な仮定である。 GANが重み付き分布を生成できないことを示すExtreme Value Theoryに基づく新しい結果を提供する。
  論文  参考訳（メタデータ） (2021-10-21T06:10:38Z)
• Distributional Reinforcement Learning with Unconstrained Monotonic Neural Networks [7.907645828535088]
  本稿では,ランダムリターン分布の異なる表現を学習するための方法論を提案する。 制約のない単調深Q-network (UMDQN) と呼ばれる新しい分布RLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-06T20:03:50Z)

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

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