論文の概要: Understanding Boolean Function Learnability on Deep Neural Networks: PAC Learning Meets Neurosymbolic Models

• arxiv url: http://arxiv.org/abs/2009.05908v4
• Date: Tue, 16 Sep 2025 01:18:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-17 17:50:52.485499
• Title: Understanding Boolean Function Learnability on Deep Neural Networks: PAC Learning Meets Neurosymbolic Models
• Title（参考訳）: 深層ニューラルネットワークにおけるブール関数学習の理解:PAC学習とニューロシンボリックモデル
• Authors: Marcio Nicolau, Anderson R. Tavares, Zhiwei Zhang, Pedro Avelar, João M. Flach, Luis C. Lamb, Moshe Y. Vardi,
• Abstract要約: モデルサンプリングベンチマーク、最適化問題、および制約度の異なるランダム3CNFに関する公式を解析する。 i) ニューラルネットワークは、純粋なルールベースのシステムや純粋なシンボリックアプローチよりも一般化します。
• 参考スコア（独自算出の注目度）: 14.29299960914962
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Computational learning theory states that many classes of boolean formulas are learnable in polynomial time. This paper addresses the understudied subject of how, in practice, such formulas can be learned by deep neural networks. Specifically, we analyze boolean formulas associated with model-sampling benchmarks, combinatorial optimization problems, and random 3-CNFs with varying degrees of constrainedness. Our experiments indicate that: (i) neural learning generalizes better than pure rule-based systems and pure symbolic approach; (ii) relatively small and shallow neural networks are very good approximators of formulas associated with combinatorial optimization problems; (iii) smaller formulas seem harder to learn, possibly due to the fewer positive (satisfying) examples available; and (iv) interestingly, underconstrained 3-CNF formulas are more challenging to learn than overconstrained ones. Such findings pave the way for a better understanding, construction, and use of interpretable neurosymbolic AI methods.
• Abstract（参考訳）: 計算学習理論 (Computational learning theory) は、ブール式の多くのクラスが多項式時間で学習可能であることを述べる。 本稿では, ニューラルネットワークを用いて, 実際にそのような公式を学習する方法について, 未研究の課題に対処する。 具体的には,モデルサンプリングベンチマーク,組合せ最適化問題,および制約度の異なるランダム3CNFに関するブール式を解析する。 私たちの実験は、こう示しています。 (i)ニューラルラーニングは、純粋規則に基づくシステムや純粋記号的アプローチよりも一般化する。 (II) 比較的小さく浅いニューラルネットワークは、組合せ最適化問題に関連する公式の非常によい近似器である。 (iii) より小さい式は学習が難しいように思われるが、おそらく、利用可能な正の(満足の)例が少なくなるためである。 興味深いことに、3-CNF式は過剰に制約された式よりも学習が難しい。 このような発見は、解釈可能なニューロシンボリックAI手法をよりよく理解し、構築し、使用するための道を開く。

関連論文リスト

• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。 本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
  論文  参考訳（メタデータ） (2024-07-18T22:05:21Z)
• Memorization With Neural Nets: Going Beyond the Worst Case [5.03863830033243]
  実際には、ディープニューラルネットワークはトレーニングデータを簡単に補間できることが多い。 本稿では、3層ニューラルネットワークを時間内に補間する単純なランダム化アルゴリズムを提案する。 サンプル数に依存しない保証を得るため、最悪の記憶能力限界を超えて移動します。
  論文  参考訳（メタデータ） (2023-09-30T10:06:05Z)
• The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks [59.26515696183751]
  ニューラルネットワークにおけるアルゴリズム発見は、時としてより複雑であることを示す。 単純な学習問題でさえ、驚くほど多様なソリューションを許容できることが示されています。
  論文  参考訳（メタデータ） (2023-06-30T17:59:13Z)
• Efficient, probabilistic analysis of combinatorial neural codes [0.0]
  ニューラルネットワークは、個々のニューロンの活動の組み合わせの形で入力を符号化する。 これらのニューラルネットワークは、その高次元性としばしば大量のデータのため、計算上の課題を示す。 従来の手法を小さな例に適用し,実験によって生成された大きなニューラルコードに適用する。
  論文  参考訳（メタデータ） (2022-10-19T11:58:26Z)
• Benchmarking Compositionality with Formal Languages [64.09083307778951]
  我々は,NLPにおける大規模ニューラルモデルが,データから学習しながら,原始概念をより大規模な新しい組み合わせに組み込むことができるかどうかを検討する。 多くのトランスデューサをランダムにサンプリングすることにより、ニューラルネットワークによる合成関係の学習性に寄与する特性を探索する。 モデルは完全に関係を学習するか全く学習しないかが分かる。鍵となるのはトランジッションカバレッジであり、トランジッション毎に400の例でソフトな学習可能性制限を設定する。
  論文  参考訳（メタデータ） (2022-08-17T10:03:18Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。 我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
  論文  参考訳（メタデータ） (2021-07-31T10:25:26Z)
• Gone Fishing: Neural Active Learning with Fisher Embeddings [55.08537975896764]
  ディープニューラルネットワークと互換性のあるアクティブな学習アルゴリズムの必要性が高まっている。 本稿では,ニューラルネットワークのための抽出可能かつ高性能な能動学習アルゴリズムBAITを紹介する。
  論文  参考訳（メタデータ） (2021-06-17T17:26:31Z)
• Proof of the Theory-to-Practice Gap in Deep Learning via Sampling Complexity bounds for Neural Network Approximation Spaces [5.863264019032882]
  関数の近似化や積分に基づく(決定的あるいはランダム化)アルゴリズムの計算複雑性について検討する。 この分野における最も重要な問題の1つは、理論的に証明可能なニューラルネットワーク近似率を実現できるかどうかという問題である。
  論文  参考訳（メタデータ） (2021-04-06T18:55:20Z)
• PAC-learning gains of Turing machines over circuits and neural networks [1.4502611532302039]
  私達は最低記述の長さの原則を持って来ることができるサンプル効率の潜在的な利益を研究します。 我々はチューリングマシンを用いて普遍的なモデルと回路を表現する。 回路の複雑さと密接性における古典的オープン問題との密接な関係を浮き彫りにする。
  論文  参考訳（メタデータ） (2021-03-23T17:03:10Z)
• ODEN: A Framework to Solve Ordinary Differential Equations using Artificial Neural Networks [0.0]
  我々は、ニューラルネットワークの性能を評価するために、正確な解の知識を必要としない特定の損失関数を証明した。 ニューラルネットワークは、トレーニング領域内での継続的ソリューションの近似に熟練していることが示されている。 ユーザフレンドリで適応可能なオープンソースコード(ODE$mathcalN$)がGitHubで提供されている。
  論文  参考訳（メタデータ） (2020-05-28T15:34:10Z)
• Belief Propagation Reloaded: Learning BP-Layers for Labeling Problems [83.98774574197613]
  最も単純な推論手法の1つとして、切り詰められた最大積のBelief伝播を取り上げ、それをディープラーニングモデルの適切なコンポーネントにするために必要となるものを加えます。 このBP-Layerは畳み込みニューラルネットワーク(CNN)の最終ブロックまたは中間ブロックとして使用できる このモデルは様々な密集予測問題に適用可能であり、パラメータ効率が高く、ステレオ、光フロー、セマンティックセグメンテーションにおける堅牢な解を提供する。
  論文  参考訳（メタデータ） (2020-03-13T13:11:35Z)

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

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