論文の概要: Boolean Satisfiability via Imitation Learning

• arxiv url: http://arxiv.org/abs/2509.25411v1
• Date: Mon, 29 Sep 2025 19:09:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-01 17:09:04.283263
• Title: Boolean Satisfiability via Imitation Learning
• Title（参考訳）: 模倣学習によるブール満足度
• Authors: Zewei Zhang, Huan Liu, Yuanhao Yu, Jun Chen, Xiangyu Xu,
• Abstract要約: 我々は、競合駆動型節学習(CDCL)問題解決のための分岐ポリシーであるImitSATを提案する。 ImitSATは、専門家のKeyTraceから学んだ。
• 参考スコア（独自算出の注目度）: 21.853451002559016
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose ImitSAT, a branching policy for conflict-driven clause learning (CDCL) solvers based on imitation learning for the Boolean satisfiability problem (SAT). Unlike previous methods that predict instance-level signals to improve CDCL branching indirectly, or rely on reinforcement learning and insufficient CDCL information to enhance branching, ImitSAT learns from expert KeyTrace that collapses a full run into the sequence of surviving decisions. Replaying a KeyTrace on the same instance is nearly conflict-free, providing dense decision-level supervision and directly reducing propagations -- the dominant contributor to wall-clock time. This prefix-conditioned supervision enables ImitSAT to reproduce high-quality branches without exploration, yielding faster convergence, stable training, and seamless integration into CDCL. Extensive experiments demonstrate that ImitSAT reduces propagation counts and runtime, outperforming state-of-the-art learned approaches. We released the source code and trained model at https://github.com/zewei-Zhang/ImitSAT
• Abstract（参考訳）: ImitSATは、競合駆動型節学習(CDCL)問題解決のための分岐ポリシーであり、Boolean satisfiability problem(SAT)の模倣学習に基づくものである。 間接的にCDCL分岐を改善するためにインスタンスレベルの信号を予測したり、強化学習と不十分なCDCL情報に頼って分岐を強化する従来の方法とは異なり、ImitSATはKeyTraceの専門家から、生き残った決定の順序に完全に崩壊することを学ぶ。 同じインスタンス上でKeyTraceをリプレイすることは、ほぼコンフリクトフリーで、決定レベルの厳密な監視と、ウォールタイムにおける主要なコントリビュータである伝播の直接的削減を提供します。 このプレフィックス条件付き監視により、ImitSATは探索せずに高品質なブランチを再現することができ、より高速な収束、安定したトレーニング、CDCLへのシームレスな統合を実現している。 大規模な実験により、ImitSATは伝播回数と実行時間を減らし、最先端の学習アプローチより優れていることが示されている。 ソースコードとトレーニングされたモデルをhttps://github.com/zewei-Zhang/ImitSATでリリースしました。

関連論文リスト

• Adaptive Learning for IRS-Assisted Wireless Networks: Securing Opportunistic Communications Against Byzantine Eavesdroppers [7.256056777973974]
  ビザンチン耐性スペクトルセンシングとセキュアインテリジェント反射面(IRS)のための共同学習フレームワークを提案する。 本研究では,局所曲率の緩やかな速度で,予測更新と証明可能なサブ線形収束を提供する拡張ラグランジアン交互化アルゴリズムを開発した。 多様なネットワーク条件のシミュレーションでは、敵攻撃時の固定偽アラームレートの検出確率が高く、正直なユーザに対する総和MSEの大幅な削減、盗聴信号の強い抑制、高速収束が示される。
  論文  参考訳（メタデータ） (2025-08-11T17:28:25Z)
• Semi-supervised Semantic Segmentation with Multi-Constraint Consistency Learning [81.02648336552421]
  本稿では,エンコーダとデコーダの段階的拡張を容易にするためのマルチ制約一貫性学習手法を提案する。 自己適応型特徴マスキングとノイズ注入は、デコーダの堅牢な学習のための特徴を摂動させるために、インスタンス固有の方法で設計されている。 Pascal VOC2012およびCityscapesデータセットの実験結果から,提案したMCCLが新たな最先端性能を実現することを示す。
  論文  参考訳（メタデータ） (2025-03-23T03:21:33Z)
• AutoSAT: Automatically Optimize SAT Solvers via Large Language Models [10.359005620433136]
  本稿では,既存のCDCLソルバをベースとしたモジュール型検索空間の自動最適化フレームワークであるAutoSATを提案する。 AutoSATは12データセット中9データセットでMiniSatを上回り、4データセットで最先端のハイブリッドソルバKissatを上回ります。
  論文  参考訳（メタデータ） (2024-02-16T14:04:56Z)
• Unsupervised Continual Anomaly Detection with Contrastively-learned Prompt [80.43623986759691]
  UCADと呼ばれる新しい非教師付き連続異常検出フレームワークを提案する。 このフレームワークは、対照的に学習したプロンプトを通じて、UDAに継続的な学習能力を持たせる。 我々は総合的な実験を行い、教師なし連続異常検出とセグメンテーションのベンチマークを設定した。
  論文  参考訳（メタデータ） (2024-01-02T03:37:11Z)
• Efficient Adversarial Contrastive Learning via Robustness-Aware Coreset Selection [59.77647907277523]
  敵対的コントラスト学習(ACL)は、高価なデータアノテーションを必要としないが、敵対的攻撃に耐える堅牢な表現を出力する。 ACLは、すべてのトレーニングデータの逆の変種を生成するのに、膨大な実行時間が必要です。 本稿では,ACLの高速化を目的としたロバストネス対応コアセット選択(RCS)手法を提案する。
  論文  参考訳（メタデータ） (2023-02-08T03:20:14Z)
• A Neural Network-based SAT-Resilient Obfuscation Towards Enhanced Logic Locking [3.076761061950216]
  本稿では,ニューラルネットワークを用いた unSAT 節変換器 SATConda を提案する。 SATCondaは最小限の領域と電力オーバーヘッドを発生させ、元の機能を不必要なセキュリティで保存する。 SATCondaをISCAS85およびISCAS89ベンチマークで評価した。
  論文  参考訳（メタデータ） (2022-09-13T07:59:27Z)
• Decoupled Adversarial Contrastive Learning for Self-supervised Adversarial Robustness [69.39073806630583]
  頑健な表現学習のための対人訓練(AT)と教師なし表現学習のための自己教師型学習(SSL)は2つの活発な研究分野である。 Decoupled Adversarial Contrastive Learning (DeACL) と呼ばれる2段階のフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-07-22T06:30:44Z)
• On Continuous Local BDD-Based Search for Hybrid SAT Solving [40.252804008544985]
  CLSに必要な勾配を効率的に計算するための新しいアルゴリズムを提案する。 多くのベンチマークインスタンスに適用することにより、多用途CLSソルバであるGradSATの機能と限界について検討する。 実験結果から,GradSATは既存のSATおよびMaxSATソルバのポートフォリオに追加され,ブール適合性および最適化問題の解決に有用であることが示唆された。
  論文  参考訳（メタデータ） (2020-12-14T22:36:20Z)
• Enhancing SAT solvers with glue variable predictions [2.635832975589208]
  我々は、最先端のSATソルバであるCaDiCaLを改良し、SATCOMP 2018とSATRACE 2019のパフォーマンスを改善し、教師付き学習と強化学習によるSHA-1プレイメージアタックのデータセット上でのパフォーマンスを向上する。 我々はこれらの制限に対処し、より単純なネットワークアーキテクチャを用いて、数百万の節を含む大規模産業問題に対してCPU推論を行い、代わりにエミュレート変数を予測する訓練を行い、ラベル付きデータを簡単に生成し、強化学習タスクとして定式化することができる。
  論文  参考訳（メタデータ） (2020-07-06T07:16:49Z)

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

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