論文の概要: A Deep Dive into Conflict Generating Decisions
- arxiv url: http://arxiv.org/abs/2105.04595v1
- Date: Mon, 10 May 2021 18:17:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-13 08:25:46.936448
- Title: A Deep Dive into Conflict Generating Decisions
- Title（参考訳）: 紛争を引き起こした決定を深く掘り下げる
- Authors: Md Solimul Chowdhury, Martin M\"uller, Jia You
- Abstract要約: 私たちは、Satisfiability(SAT)問題を解決するためにConflict Driven Clause Learningを使用します。
そこで我々は,CDCLがコンフリクトから節を学習することを示した。
我々は、mc決定の学習節から一部の変数の選択優先度を下げる新しい決定戦略として、共通推論変数還元(CRVR)を開発した。
- 参考スコア（独自算出の注目度）: 3.222802562733787
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Boolean Satisfiability (SAT) is a well-known NP-complete problem. Despite
this theoretical hardness, SAT solvers based on Conflict Driven Clause Learning
(CDCL) can solve large SAT instances from many important domains. CDCL learns
clauses from conflicts, a technique that allows a solver to prune its search
space. The selection heuristics in CDCL prioritize variables that are involved
in recent conflicts. While only a fraction of decisions generate any conflicts,
many generate multiple conflicts.
In this paper, we study conflict-generating decisions in CDCL in detail. We
investigate the impact of single conflict (sc) decisions, which generate only
one conflict, and multi-conflict (mc) decisions which generate two or more. We
empirically characterize these two types of decisions based on the quality of
the learned clauses produced by each type of decision. We also show an
important connection between consecutive clauses learned within the same mc
decision, where one learned clause triggers the learning of the next one
forming a chain of clauses. This leads to the consideration of similarity
between conflicts, for which we formulate the notion of conflictsproximity as a
similarity measure. We show that conflicts in mc decisions are more closely
related than consecutive conflicts generated from sc decisions. Finally, we
develop Common Reason Variable Reduction (CRVR) as a new decision strategy that
reduces the selection priority of some variables from the learned clauses of mc
decisions. Our empirical evaluation of CRVR implemented in three leading
solvers demonstrates performance gains in benchmarks from the main track of SAT
Competition-2020.
- Abstract（参考訳）: ブール満足度(SAT)はよく知られたNP完全問題である。
このような理論的難しさにもかかわらず、CDCL(Conflict Driven Clause Learning)に基づくSATソルバは、多くの重要なドメインから大きなSATインスタンスを解くことができる。
cdclはコンフリクト(コンフリクト)から節を学習する。
CDCLにおける選択ヒューリスティックは、近年の紛争に関わる変数を優先している。
決定のごく一部が矛盾を発生させるが、多くは複数の衝突を発生させる。
本稿では,cdclにおける紛争発生決定を詳細に検討する。
単一紛争(single conflict,sc)決定は1つの紛争のみを発生させ,複数紛争(multi-conflict,mc)決定は2つ以上の紛争を発生させる。
我々は,これらの2種類の意思決定を,各タイプの意思決定によって生成された学習節の品質に基づいて実証的に特徴付ける。
また,同一のmc決定で学習される連続した節間の重要な関係を示し,学習された節が次の節の連鎖を形成する学習をトリガーすることを示す。
これは紛争間の類似性を考慮し、類似度尺度として対立確率の概念を定式化する。
mc決定における衝突は、sc決定から生じる連続的な衝突よりも密接に関連していることを示す。
最後に,いくつかの変数の選択優先度をmc決定の学習節から減少させる新しい決定戦略として,共通理由変数削減(crvr)を開発した。
3つのリーディングソルバに実装したcrvrの実証評価により,satコンペティション-2020のメイントラックからベンチマークのパフォーマンス向上が示された。
関連論文リスト
- ECon: On the Detection and Resolution of Evidence Conflicts [56.89209046429291]
大規模言語モデル(LLM)の台頭は意思決定システムにおける情報の質に大きな影響を与えている。
本研究では,実世界の誤情報シナリオをシミュレートするために,多様で検証された証拠衝突を生成する手法を提案する。
論文 参考訳（メタデータ） (2024-10-05T07:41:17Z) - AdaCAD: Adaptively Decoding to Balance Conflicts between Contextual and Parametric Knowledge [57.66282463340297]
知識の衝突は、大きな言語モデル(LLM)の文脈における情報と、そのパラメータに格納された知識との相違から生じる。
コンフリクトの度合いに基づいて動的に調整の重みを推定する,AdaCADと呼ばれる細粒度なインスタンスレベルのアプローチを提案する。
論文 参考訳（メタデータ） (2024-09-11T16:35:18Z) - ConflictBank: A Benchmark for Evaluating the Influence of Knowledge Conflicts in LLM [36.332500824079844]
大規模言語モデル (LLM) は、多くの分野にわたって顕著な進歩を遂げてきたが、知識紛争の重大な問題は研究されることはめったにない。
我々は3つの側面から知識衝突を評価するために開発された最初の総合ベンチマークであるConflictBankを紹介する。
本研究は, 誤情報, 時間的相違, 意味的相違から生じる対立を慎重に分析し, 4つのモデルファミリーと12個のLLMインスタンスに分類した。
論文 参考訳（メタデータ） (2024-08-22T02:33:13Z) - Differentiating Choices via Commonality for Multiple-Choice Question Answering [54.04315943420376]
複数選択の質問応答は、正しい答えを選択するための貴重な手がかりを提供することができる。
既存のモデルでは、それぞれの選択を別々にランク付けし、他の選択によって提供されるコンテキストを見渡すことが多い。
本稿では,DCQAと呼ばれる共通性を識別・排除することで,選択を識別する新しいモデルを提案する。
論文 参考訳（メタデータ） (2024-08-21T12:05:21Z) - Configurable Mirror Descent: Towards a Unification of Decision Making [36.42770584314967]
特定の意思決定問題に対処する様々な方法が提案されている。
特定のカテゴリーでの成功にもかかわらず、これらの手法は通常独立して進化し、他のカテゴリに一般化することができない。
本研究は,3つの主要なコントリビューションでこの問題に対処するための予備的試みを示す。
論文 参考訳（メタデータ） (2024-05-20T03:10:22Z) - Selecting the Most Conflicting Pair of Candidates [6.838139628413773]
我々は、最も対立する候補者、すなわち最も対立の大きい候補者を見つける観点から、委員会選挙を調査する。
この目的を達成するための基本的な公理を提案することで、著名なマルチウィンナー投票規則が満たされていないことを示す。
その後のより深い分析は、その動作方法に光を当てている。
論文 参考訳（メタデータ） (2024-05-09T16:00:20Z) - SCREWS: A Modular Framework for Reasoning with Revisions [58.698199183147935]
我々は、リビジョンを伴う推論のためのモジュラーフレームワークであるSCREWSを紹介する。
我々は、SCREWSが、共通のフレームワークの下で、いくつかの以前のアプローチを統合することを示す。
我々は,多種多様な推論タスクに基づいて,最先端のLCMを用いてフレームワークの評価を行った。
論文 参考訳（メタデータ） (2023-09-20T15:59:54Z) - On the Complexity of Adversarial Decision Making [101.14158787665252]
決定推定係数は, 相手の意思決定に対する後悔度を低く抑えるのに必要であり, 十分であることを示す。
我々は、決定推定係数を他のよく知られた複雑性尺度の変種に結びつける新しい構造結果を提供する。
論文 参考訳（メタデータ） (2022-06-27T06:20:37Z) - Modularity in Reinforcement Learning via Algorithmic Independence in
Credit Assignment [79.5678820246642]
提案手法は, 事前決定の順序に対して, スパース変化のみを必要とする伝達問題に対して, 政策段階の手法よりも, より標本効率が高いことを示す。
我々は最近提案された社会的意思決定の枠組みをマルコフ決定プロセスよりもよりきめ細かい形式主義として一般化する。
論文 参考訳（メタデータ） (2021-06-28T21:29:13Z) - Learning to Resolve Conflicts for Multi-Agent Path Finding with
Conflict-Based Search [35.71926950656326]
Conflict-Based Search (CBS) はパス探索のための最先端のアルゴリズムである。
我々は,oracle の意思決定を観察するコンフリクト選択のための機械学習フレームワークを提案する。
提案手法は,現在のcbsソルバよりも,成功率,検索ツリーサイズ,ランタイムを大幅に向上させる。
論文 参考訳（メタデータ） (2020-12-10T22:44:35Z) - Resolving Head-On Conflicts for Multi-Agent Path Finding with
Conflict-Based Search [0.0]
競合ベースの検索(CBS)は、マルチエージェントパス探索問題を解決するための一般的なフレームワークである。
本稿では,新たな手法,すなわち,このような矛盾を見出すヘッドオン技術を紹介する。
実験の結果,ヘッドオン技術は最先端のMAPFソルバCBSHを改善した。
論文 参考訳（メタデータ） (2020-07-07T15:52:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。