論文の概要: Too much information: CDCL solvers need to forget and perform restarts

• arxiv url: http://arxiv.org/abs/2202.01030v1
• Date: Tue, 1 Feb 2022 10:16:04 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-04 03:54:12.547646
• Title: Too much information: CDCL solvers need to forget and perform restarts
• Title（参考訳）: 情報過剰:CDCLソルバは忘れ、再起動する必要がある
• Authors: Tom Kr\"uger and Jan-Hendrik Lorenz and Florian W\"orz
• Abstract要約: 競合駆動型節学習(CDCL)は命題論理の満足度問題を解くための極めて成功したパラダイムである。 この論文は、節学習がランタイムを改善するだけでなく、それを劇的に劣化させることがあることを非常に驚くべきことに示します。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Conflict-driven clause learning (CDCL) is a remarkably successful paradigm for solving the satisfiability problem of propositional logic. Instead of a simple depth-first backtracking approach, this kind of solver learns the reason behind occurring conflicts in the form of additional clauses. However, despite the enormous success of CDCL solvers, there is still only a shallow understanding of what influences the performance of these solvers in what way. This paper will demonstrate, quite surprisingly, that clause learning (without being able to get rid of some clauses) can not only improve the runtime but can oftentimes deteriorate it dramatically. By conducting extensive empirical analysis, we find that the runtime distributions of CDCL solvers are multimodal. This multimodality can be seen as a reason for the deterioration phenomenon described above. Simultaneously, it also gives an indication of why clause learning in combination with clause deletion and restarts is virtually the de facto standard of SAT solving in spite of this phenomenon. As a final contribution, we will show that Weibull mixture distributions can accurately describe the multimodal distributions. Thus, adding new clauses to a base instance has an inherent effect of making runtimes long-tailed. This insight provides a theoretical explanation as to why the techniques of restarts and clause deletion are useful in CDCL solvers.
• Abstract（参考訳）: 競合駆動型節学習(CDCL)は命題論理の満足度問題を解くための極めて成功したパラダイムである。 単純な深さ優先のバックトラックアプローチの代わりに、この種の解法は、追加の節の形で競合が発生する理由を学ぶ。 しかし、CDCLソルバの圧倒的な成功にもかかわらず、これらのソルバの性能にどのような影響を及ぼすかは、まだ理解されていない。 この論文は、節の学習(いくつかの節を削除せずに)がランタイムを改善できるだけでなく、しばしばそれを劇的に悪化させることを示した。 広範な経験的分析を行うことにより,CDCLソルバのランタイム分布が多モードであることが判明した。 この多モード性は、前述の劣化現象の理由と見なすことができる。 同時に、この現象にもかかわらずSAT解決の事実上のデファクトスタンダードである条項削除と再起動の組み合わせによる節学習の理由を示す。 最後に,ワイブル混合分布がマルチモーダル分布を正確に記述できることを示す。 したがって、ベースインスタンスに新しい節を追加することは、ランタイムを長期化する本質的に効果がある。 この洞察は、リスタートや節削除のテクニックがcdclソルバで有用である理由に関する理論的説明を提供する。

関連論文リスト

• ICL-TSVD: Bridging Theory and Practice in Continual Learning with Pre-trained Models [103.45785408116146]
  連続学習(CL)は、連続的に提示される複数のタスクを解決できるモデルを訓練することを目的としている。 最近のCLアプローチは、ダウンストリームタスクをうまく一般化する大規模な事前学習モデルを活用することで、強力なパフォーマンスを実現している。 しかし、これらの手法には理論的保証がなく、予期せぬ失敗をしがちである。 私たちは、経験的に強いアプローチを原則化されたフレームワークに統合することで、このギャップを埋めます。
  論文  参考訳（メタデータ） (2024-10-01T12:58:37Z)
• Larger Language Models Don't Care How You Think: Why Chain-of-Thought Prompting Fails in Subjective Tasks [25.562937159039038]
  In-Context Learning (ICL) in Large Language Models (LLM) が自然言語処理の主流の手法として登場した。 ICLはタスク先行の検索に大きく依存しており、タスクを実行するための"学習"は少なくなっている。 驚くべきことに、CoT(Chain-of-Thought)は、大きな言語モデルではICLと同じ後方崩壊に悩まされている。
  論文  参考訳（メタデータ） (2024-09-10T03:06:17Z)
• Many-Shot In-Context Learning [58.395589302800566]
  大規模言語モデル (LLMs) は、文脈内学習 (ICL) において優れている 我々は、多種多様な生成的および識別的タスクにおける顕著なパフォーマンス向上を観察する。 少数ショット学習とは異なり、多ショット学習は事前学習されたバイアスをオーバーライドするのに効果的である。
  論文  参考訳（メタデータ） (2024-04-17T02:49:26Z)
• RecDCL: Dual Contrastive Learning for Recommendation [65.6236784430981]
  本稿では、RecDCLという2つのコントラスト学習推薦フレームワークを提案する。 RecDCLでは、FCLの目的は、ユーザとイテムの正のペアに対する冗長なソリューションを排除することである。 BCLの目的は、表現の堅牢性を高めるために出力ベクトルにコントラスト埋め込みを生成するために利用される。
  論文  参考訳（メタデータ） (2024-01-28T11:51:09Z)
• Better patching using LLM prompting, via Self-Consistency [5.892272127970584]
  自己整合性(Self-Consistency, S-C)は、問題の説明を生成する上で、エキサイティングで極めて優れたテクニックである。 本稿では,修正作業のコミットログを説明として,S-C手法のプログラム修復への応用について述べる。 我々は,MODITデータセット上で,プログラムの修正を促そうとする従来のアプローチを破って,最先端の成果を得た。
  論文  参考訳（メタデータ） (2023-05-31T18:28:46Z)
• SCL(FOL) Can Simulate Non-Redundant Superposition Clause Learning [0.3867363075280543]
  SCL(FOL)は等式のない一階述語論理の重ね合わせにより非冗長節の導出をシミュレートできることを示す。 重畳に基づく推論は、固定縮小順序付けに対して行われる。
  論文  参考訳（メタデータ） (2023-05-22T11:12:39Z)
• Joint Contrastive Learning with Infinite Possibilities [114.45811348666898]
  本稿では,新しい確率論的モデリングによるコントラスト学習における最近の発展の有用性について考察する。 コントラスト学習(Joint Contrastive Learning, JCL)という,コントラスト学習の特定の形態を導出する。
  論文  参考訳（メタデータ） (2020-09-30T16:24:21Z)
• From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
  本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。 8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
  論文  参考訳（メタデータ） (2020-06-05T10:56:52Z)
• On the Effect of Learned Clauses on Stochastic Local Search [0.0]
  SATソルバでは、競合駆動型節学習(CDCL)と局所探索(SLS)が使用されている。 多数の正しいリテラルを持つ節がSLSのランタイムに有益であることを実験的に実証した。 我々は、前処理のステップとして高品質な節を追加する最も有益な戦略を導出する。
  論文  参考訳（メタデータ） (2020-05-07T13:33:16Z)
• Learning with Multiple Complementary Labels [94.8064553345801]
  補ラベル(CL)は、単に例の不正なクラスを示すが、CLで学習すると、多クラス分類器が生成される。 そこで本研究では,MCLを各例に示すための新しい問題設定と,MCLを学習するための2つの方法を提案する。
  論文  参考訳（メタデータ） (2019-12-30T13:50:51Z)

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

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