論文の概要: Certifiable Boolean Reasoning Is Universal

• arxiv url: http://arxiv.org/abs/2602.05120v1
• Date: Wed, 04 Feb 2026 23:09:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-06 18:49:08.661581
• Title: Certifiable Boolean Reasoning Is Universal
• Title（参考訳）: 証明されたブール推論は普遍的である
• Authors: Wenhao Li, Anastasis Kratsios, Hrad Ghoukasian, Dennis Zvigelsky,
• Abstract要約: ディープラーニングモデルは常に任意の$f:0,1Bto0,1$タスクを通じて推論可能であることを示す。 任意のブール$f:0,1Bto0,1$に対して、サンプリングされた回路が任意に高い確率で$f$を計算するパラメータ構成が存在する。
• 参考スコア（独自算出の注目度）: 17.33786517296165
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The proliferation of agentic systems has thrust the reasoning capabilities of AI into the forefront of contemporary machine learning. While it is known that there \emph{exist} neural networks which can reason through any Boolean task $f:\{0,1\}^B\to\{0,1\}$, in the sense that they emulate Boolean circuits with fan-in $2$ and fan-out $1$ gates, trained models have been repeatedly demonstrated to fall short of these theoretical ideals. This raises the question: \textit{Can one exhibit a deep learning model which \textbf{certifiably} always reasons and can \textbf{universally} reason through any Boolean task?} Moreover, such a model should ideally require few parameters to solve simple Boolean tasks. We answer this question affirmatively by exhibiting a deep learning architecture which parameterizes distributions over Boolean circuits with the guarantee that, for every parameter configuration, a sample is almost surely a valid Boolean circuit (and hence admits an intrinsic circuit-level certificate). We then prove a universality theorem: for any Boolean $f:\{0,1\}^B\to\{0,1\}$, there exists a parameter configuration under which the sampled circuit computes $f$ with arbitrarily high probability. When $f$ is an $\mathcal{O}(\log B)$-junta, the required number of parameters scales linearly with the input dimension $B$. Empirically, on a controlled truth-table completion benchmark aligned with our setting, the proposed architecture trains reliably and achieves high exact-match accuracy while preserving the predicted structure: every internal unit is Boolean-valued on $\{0,1\}^B$. Matched MLP baselines reach comparable accuracy, but only about $10\%$ of hidden units admit a Boolean representation; i.e.\ are two-valued over the Boolean cube.
• Abstract（参考訳）: エージェントシステムの拡散は、AIの推論能力を現代の機械学習の最前線に押し上げた。 Boolean タスク $f:\{0,1\}^B\to\{0,1\}$ を推論できる 'emph{exist} ニューラルネットワークが存在することは知られているが、ファンインの 2 ドルとファンアウトの 1 ドルのゲートでブール回路をエミュレートするという意味では、これらの理論的な理想を満たさないことが繰り返し実証されている。 これは疑問を提起する: \textit{Can one shows a deep learning model that \textbf{certifiably} always reasons and \textbf{universally} reason through any Boolean task? さらに、そのようなモデルは単純なBooleanタスクを解決するために、理想的にはパラメータをほとんど必要とすべきです。 本稿では,各パラメータ構成に対して,サンプルがほぼ確実に有効なブール回路であることを保証して,ブール回路上の分布をパラメータ化する深層学習アーキテクチャを提示することによって,この問題を肯定的に解決する。 任意のブール$f:\{0,1\}^B\to\{0,1\}$に対して、サンプリングされた回路が任意の高い確率で$f$を計算するパラメータ構成が存在する。 f$が$\mathcal{O}(\log B)$-juntaであるとき、要求されるパラメータの数は入力次元$B$と線形にスケールする。 経験的に、我々の設定に合致した制御真理テーブル補完ベンチマークにおいて、提案したアーキテクチャは、予測された構造を保ちながら、確実に訓練し、高い精度の精度を達成する:すべての内部ユニットは、$\{0,1\}^B$でブール値となる。 マッチングされたMLPベースラインは同等の精度に達するが、隠されたユニットの約10\%はブール表現を許容する。

関連論文リスト

• Optimal Anytime-Valid Tests for Composite Nulls [12.048034578791954]
  合成ヌルに対する最適レベル-$$パワーワンテストの設計問題を考察する。 まず、有限アルファベットのケース($|mathcalX| = m infty$)を考えると、インフニバーサル$e$-プロセスに基づくテストが最適であることを示す。
  論文  参考訳（メタデータ） (2025-12-23T04:14:56Z)
• Bias-Class Discrimination of Universal QRAM Boolean Memories [0.0]
  コヒーレントでアドレス可能なクエリを使って$f$のバイアスクラスについて推測できるものは何か? 重み付きバイアスクラスの場合、アドレスレジスタ上で誘導される単一クエリアンサンブル状態は、単一コピーのヘルストロム等価測定と成功確率に対して閉形式の式を生成する2固有空間構造を持つことを示す。 これはDeutsch-Jozsaの完全識別のケースを超えて、Bernstein-Vaziraniのような正確な識別設定を補完する。
  論文  参考訳（メタデータ） (2025-12-19T12:14:18Z)
• ProofWala: Multilingual Proof Data Synthesis and Theorem-Proving [53.67926215943612]
  $rm P Small ROOFW Small ALA$は、ニューラル定理プローサと2つの確立された対話的証明アシスタント(ITP)間の相互作用を可能にする 私たちは、$rm P Small ROOFWsmall ALA$生成のCoqとLeanのデータの組み合わせでトレーニングされたモデルが、標準のprov-at-k$メトリック上で、Lean-onlyとCoq-onlyのモデルを上回っていることを示します。
  論文  参考訳（メタデータ） (2025-02-07T05:35:46Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Approximation Rates and VC-Dimension Bounds for (P)ReLU MLP Mixture of Experts [17.022107735675046]
  Mixture-of-Experts(MoEs)は、従来のディープラーニングモデルを越えてスケールアップすることができる。 MoMLPモデル全体のVC次元が$tildeO(LmaxnL,JW)$であるので、MoMLPが一般化可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-05T19:11:57Z)
• On Symmetric Pseudo-Boolean Functions: Factorization, Kernels and Applications [0.0]
  任意の対称擬ブール函数が、同値に級数や分解として表せることを証明する。 これらの結果を用いて、スピングラスエネルギー関数、量子情報、テンソルネットワークの文献に現れる対称擬ブール関数を解析する。
  論文  参考訳（メタデータ） (2022-09-29T18:00:07Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• On the Optimal Memorization Power of ReLU Neural Networks [53.15475693468925]
  フィードフォワードReLUニューラルネットワークは、軽度の分離可能性仮定を満たす任意のN$ポイントを記憶することができることを示す。 このような大きなビットの複雑性を持つことは、サブ線形数のパラメータを記憶するのに必要であり、十分であることを示す。
  論文  参考訳（メタデータ） (2021-10-07T05:25:23Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)

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

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