論文の概要: On the Effect of Learned Clauses on Stochastic Local Search

• arxiv url: http://arxiv.org/abs/2005.04022v1
• Date: Thu, 7 May 2020 13:33:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-05 23:52:27.848604
• Title: On the Effect of Learned Clauses on Stochastic Local Search
• Title（参考訳）: 学習句が確率的局所探索に及ぼす影響について
• Authors: Jan-Hendrik Lorenz and Florian W\"orz
• Abstract要約: SATソルバでは、競合駆動型節学習(CDCL)と局所探索(SLS)が使用されている。 多数の正しいリテラルを持つ節がSLSのランタイムに有益であることを実験的に実証した。 我々は、前処理のステップとして高品質な節を追加する最も有益な戦略を導出する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: There are two competing paradigms in successful SAT solvers: Conflict-driven clause learning (CDCL) and stochastic local search (SLS). CDCL uses systematic exploration of the search space and has the ability to learn new clauses. SLS examines the neighborhood of the current complete assignment. Unlike CDCL, it lacks the ability to learn from its mistakes. This work revolves around the question whether it is beneficial for SLS to add new clauses to the original formula. We experimentally demonstrate that clauses with a large number of correct literals w. r. t. a fixed solution are beneficial to the runtime of SLS. We call such clauses high-quality clauses. Empirical evaluations show that short clauses learned by CDCL possess the high-quality attribute. We study several domains of randomly generated instances and deduce the most beneficial strategies to add high-quality clauses as a preprocessing step. The strategies are implemented in an SLS solver, and it is shown that this considerably improves the state-of-the-art on randomly generated instances. The results are statistically significant.
• Abstract（参考訳）: SATソルバには、衝突駆動節学習(CDCL)と確率局所探索(SLS)の2つの競合パラダイムがある。 CDCLは検索空間を体系的に探索し、新しい節を学習する能力を持つ。 SLSは、現在の完全な割り当ての近傍を調べます。 cdclとは異なり、失敗から学ぶ能力が欠けている。 この研究は、SLSが元の式に新しい節を追加することが有益かどうかという問題を中心に展開されている。 我々は、多数の正しいリテラルを持つ節を実験的に示す。 r. tだ 固定解はSLSのランタイムに有益である。 このような節を高品質な節と呼ぶ。 経験的評価はCDCLによって学習された短い節が高品質な属性を持っていることを示している。 ランダムに生成されたインスタンスのいくつかのドメインを調査し、前処理ステップとして高品質な節を追加する最も有益な戦略を導出する。 これらの戦略はSLSソルバに実装されており、ランダムに生成されたインスタンスの最先端性を大幅に改善することを示す。 結果は統計的に有意である。

関連論文リスト

• Bayesian scaling laws for in-context learning [72.17734205418502]
  In-context Learning(ICL)は、言語モデルをトレーニング更新なしで複雑なタスクを実行するための強力なテクニックである。 我々は、ICCがベイズ学習者を近似し、ICCのための新しいベイズスケーリング法則のファミリーを開発することを示す。
  論文  参考訳（メタデータ） (2024-10-21T21:45:22Z)
• ParaICL: Towards Robust Parallel In-Context Learning [74.38022919598443]
  大規模言語モデル(LLM)が自然言語処理の標準となっている。 インコンテキスト・ラーニング(ICL)は、いくつかの実演例の選択に依存している。 パラレルインコンテキスト学習(ParaICL)という新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-03-31T05:56:15Z)
• AutoSAT: Automatically Optimize SAT Solvers via Large Language Models [10.359005620433136]
  本稿では,既存のCDCLソルバをベースとしたモジュール型検索空間の自動最適化フレームワークであるAutoSATを提案する。 AutoSATは12データセット中9データセットでMiniSatを上回り、4データセットで最先端のハイブリッドソルバKissatを上回ります。
  論文  参考訳（メタデータ） (2024-02-16T14:04:56Z)
• Batch-ICL: Effective, Efficient, and Order-Agnostic In-Context Learning [27.729189318779603]
  Batch-ICLは、文脈内学習のための効率的、効率的、秩序に依存しない推論アルゴリズムである。 Batch-ICL は ICL の例のほとんどを一貫して上回っていることを示す。 また,メタ最適化の「エポック」を複数備えた新しいBatch-ICLを開発した。
  論文  参考訳（メタデータ） (2024-01-12T09:31:17Z)
• SCL(FOL) Can Simulate Non-Redundant Superposition Clause Learning [0.3867363075280543]
  SCL(FOL)は等式のない一階述語論理の重ね合わせにより非冗長節の導出をシミュレートできることを示す。 重畳に基づく推論は、固定縮小順序付けに対して行われる。
  論文  参考訳（メタデータ） (2023-05-22T11:12:39Z)
• Alleviating Over-smoothing for Unsupervised Sentence Representation [96.19497378628594]
  本稿では,この問題を緩和するために,SSCL(Self-Contrastive Learning)というシンプルな手法を提案する。 提案手法は非常に単純で,様々な最先端モデルに拡張して,性能向上を図ることができる。
  論文  参考訳（メタデータ） (2023-05-09T11:00:02Z)
• Towards an Understanding of Long-Tailed Runtimes of SLS Algorithms [0.0]
  GapSATソルバは、SLSソルバの性能を平均的に向上させる方法として、追加情報を学習した。 本稿では論理的に等価な問題定式化を生成する方法を提案する。 シュオニングのランダムウォークアルゴリズムのランタイムは約 Johnson SB であることを示す。
  論文  参考訳（メタデータ） (2022-10-24T12:22:25Z)
• Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
  LEC インスタンスの SAT 符号化の硬さは SAT パーティショニングでは textitw.r. と推定できることを示す。 そこで本研究では, SAT符号化の難易度を精度良く推定できるパーティショニング法を提案する。
  論文  参考訳（メタデータ） (2022-10-04T09:19:13Z)
• Too much information: CDCL solvers need to forget and perform restarts [0.0]
  競合駆動型節学習(CDCL)は命題論理の満足度問題を解くための極めて成功したパラダイムである。 この論文は、節学習がランタイムを改善するだけでなく、それを劇的に劣化させることがあることを非常に驚くべきことに示します。
  論文  参考訳（メタデータ） (2022-02-01T10:16:04Z)
• Contrastive Learning with Adversarial Examples [79.39156814887133]
  コントラスト学習(Contrastive Learning, CL)は、視覚表現の自己教師型学習(SSL)において一般的な手法である。 本稿では,コンストラクティブ・ラーニングのための新しい逆例群を紹介し,これらの例を用いてCLAEと表記されるSSLの新しい逆トレーニングアルゴリズムを定義する。
  論文  参考訳（メタデータ） (2020-10-22T20:45:10Z)
• Joint Contrastive Learning with Infinite Possibilities [114.45811348666898]
  本稿では,新しい確率論的モデリングによるコントラスト学習における最近の発展の有用性について考察する。 コントラスト学習(Joint Contrastive Learning, JCL)という,コントラスト学習の特定の形態を導出する。
  論文  参考訳（メタデータ） (2020-09-30T16:24:21Z)

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

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