論文の概要: Neural Approaches to SAT Solving: Design Choices and Interpretability
- arxiv url: http://arxiv.org/abs/2504.01173v1
- Date: Tue, 01 Apr 2025 20:31:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-03 19:59:19.164688
- Title: Neural Approaches to SAT Solving: Design Choices and Interpretability
- Title（参考訳）: SATソルビングへのニューラルアプローチ:設計選択と解釈可能性
- Authors: David Mojžíšek, Jan Hůla, Ziwei Li, Ziyu Zhou, Mikoláš Janota,
- Abstract要約: 本稿では,ブール充足可能性問題に適用したグラフニューラルネットワークの包括的評価を行う。
我々は、いくつかの訓練改善、特に、新しい最寄りの課題監督手法を導入する。
ニューラルネットワーク更新を繰り返す可変クラスグラフ表現の適合性について実験を行った。
- 参考スコア（独自算出の注目度）: 3.876394880838347
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this contribution, we provide a comprehensive evaluation of graph neural networks applied to Boolean satisfiability problems, accompanied by an intuitive explanation of the mechanisms enabling the model to generalize to different instances. We introduce several training improvements, particularly a novel closest assignment supervision method that dynamically adapts to the model's current state, significantly enhancing performance on problems with larger solution spaces. Our experiments demonstrate the suitability of variable-clause graph representations with recurrent neural network updates, which achieve good accuracy on SAT assignment prediction while reducing computational demands. We extend the base graph neural network into a diffusion model that facilitates incremental sampling and can be effectively combined with classical techniques like unit propagation. Through analysis of embedding space patterns and optimization trajectories, we show how these networks implicitly perform a process very similar to continuous relaxations of MaxSAT, offering an interpretable view of their reasoning process. This understanding guides our design choices and explains the ability of recurrent architectures to scale effectively at inference time beyond their training distribution, which we demonstrate with test-time scaling experiments.
- Abstract（参考訳）: 本稿では,ブール充足可能性問題に適用したグラフニューラルネットワークの包括的評価と,モデルが異なるインスタンスに一般化できるメカニズムの直感的な説明を行う。
特に,モデルの現在の状態に動的に適応し,より大きな解空間の問題に対する性能を著しく向上する,新しい最寄りの割当監督手法を導入する。
本実験では, 逐次ニューラルネットワーク更新による可変クラスグラフ表現の適合性を実証し, 演算要求を低減しつつSAT割り当て予測の精度を向上する。
ベースグラフニューラルネットワークを拡散モデルに拡張し、インクリメンタルサンプリングを容易にし、単位伝搬のような古典的手法と効果的に組み合わせることができる。
埋め込み空間パターンと最適化軌道の分析を通して、これらのネットワークがMaxSATの連続緩和と非常によく似たプロセスを実行し、それらの推論過程の解釈可能なビューを提供することを示す。
この理解は、我々の設計選択をガイドし、繰り返しアーキテクチャがトレーニングディストリビューションを超えて推論時に効果的にスケールできることを説明し、テストタイムのスケーリング実験で実証します。
関連論文リスト
- Predicting Steady-State Behavior in Complex Networks with Graph Neural Networks [0.0]
複雑なシステムでは、情報伝達は拡散または非局在化、弱局所化、強局所化と定義できる。
本研究では,線形力学系のネットワーク上での挙動を学習するために,グラフニューラルネットワークモデルの適用について検討する。
論文 参考訳（メタデータ） (2025-02-02T17:29:10Z) - Deep Learning Through A Telescoping Lens: A Simple Model Provides Empirical Insights On Grokking, Gradient Boosting & Beyond [61.18736646013446]
その驚くべき振る舞いをより深く理解するために、トレーニングされたニューラルネットワークの単純かつ正確なモデルの有用性について検討する。
3つのケーススタディで、様々な顕著な現象に関する新しい経験的洞察を導き出すためにどのように適用できるかを説明します。
論文 参考訳（メタデータ） (2024-10-31T22:54:34Z) - Improving Equivariant Model Training via Constraint Relaxation [31.507956579770088]
そこで本研究では,トレーニング中の厳密な均衡制約を緩和することにより,そのようなモデルの最適化を改善する新しい枠組みを提案する。
本研究では,様々な最先端ネットワークアーキテクチャの実験結果を提供し,このトレーニングフレームワークが一般化性能を向上した同変モデルを実現する方法を示す。
論文 参考訳（メタデータ） (2024-08-23T17:35:08Z) - The Unreasonable Effectiveness of Solving Inverse Problems with Neural Networks [24.766470360665647]
逆問題に対する解を学ぶために訓練されたニューラルネットワークは、トレーニングセット上でも古典よりも優れた解を見つけることができることを示す。
高速な推論のために新しいデータに一般化するのではなく、既知のデータに対するより良い解決策を見つけるためにも使用できる。
論文 参考訳（メタデータ） (2024-08-15T12:38:10Z) - Improving Network Interpretability via Explanation Consistency Evaluation [56.14036428778861]
本稿では、より説明可能なアクティベーションヒートマップを取得し、同時にモデル性能を向上させるフレームワークを提案する。
具体的には、モデル学習において、トレーニングサンプルを適応的に重み付けするために、新しいメトリクス、すなわち説明整合性を導入する。
そこで,本フレームワークは,これらのトレーニングサンプルに深い注意を払ってモデル学習を促進する。
論文 参考訳（メタデータ） (2024-08-08T17:20:08Z) - Neural Network-Based Score Estimation in Diffusion Models: Optimization
and Generalization [12.812942188697326]
拡散モデルは、忠実さ、柔軟性、堅牢性を改善した高品質なサンプルを生成する際に、GANと競合する強力なツールとして登場した。
これらのモデルの主要な構成要素は、スコアマッチングを通じてスコア関数を学ぶことである。
様々なタスクにおいて経験的な成功にもかかわらず、勾配に基づくアルゴリズムが証明可能な精度でスコア関数を学習できるかどうかは不明である。
論文 参考訳（メタデータ） (2024-01-28T08:13:56Z) - Towards a Better Theoretical Understanding of Independent Subnetwork Training [56.24689348875711]
独立サブネットワークトレーニング(IST)の理論的考察
ISTは、上記の問題を解決するための、最近提案され、非常に効果的である。
圧縮通信を用いた分散手法など,ISTと代替手法の基本的な違いを同定する。
論文 参考訳（メタデータ） (2023-06-28T18:14:22Z) - Data-driven emergence of convolutional structure in neural networks [83.4920717252233]
識別タスクを解くニューラルネットワークが、入力から直接畳み込み構造を学習できることを示す。
データモデルを慎重に設計することにより、このパターンの出現は、入力の非ガウス的、高次局所構造によって引き起こされることを示す。
論文 参考訳（メタデータ） (2022-02-01T17:11:13Z) - Ada-SISE: Adaptive Semantic Input Sampling for Efficient Explanation of
Convolutional Neural Networks [26.434705114982584]
畳み込みニューラルネットワークの効率的な解釈手法を提案する。
実験の結果,提案手法は実行時間を最大30%削減できることがわかった。
論文 参考訳（メタデータ） (2021-02-15T19:10:00Z) - Network Diffusions via Neural Mean-Field Dynamics [52.091487866968286]
本稿では,ネットワーク上の拡散の推論と推定のための新しい学習フレームワークを提案する。
本研究の枠組みは, ノード感染確率の正確な進化を得るために, モリ・ズワンジッヒ形式から導かれる。
我々のアプローチは、基礎となる拡散ネットワークモデルのバリエーションに対して多用途で堅牢である。
論文 参考訳（メタデータ） (2020-06-16T18:45:20Z) - Parallelization Techniques for Verifying Neural Networks [52.917845265248744]
検証問題に基づくアルゴリズムを反復的に導入し、2つの分割戦略を探索する。
また、ニューラルネットワークの検証問題を単純化するために、ニューロンアクティベーションフェーズを利用する、高度に並列化可能な前処理アルゴリズムも導入する。
論文 参考訳（メタデータ） (2020-04-17T20:21:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。