論文の概要: 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のメイントラックからベンチマークのパフォーマンス向上が示された。
関連論文リスト
- Resolving Knowledge Conflicts in Large Language Models [48.92369530853202]
大規模言語モデル(LLM)はしばしば知識の衝突に遭遇する。
知識衝突が発生した場合のLLMのデシラタとは何か,既存のLLMがそれを満たすのかを問う。
KNOWLEDGE CONFLICTは文脈知識の衝突をシミュレートするための評価フレームワークである。
論文 参考訳(メタデータ) (2023-10-02T06:57:45Z) - Rehearsal: Simulating Conflict to Teach Conflict Resolution [54.32934135393982]
リハーサル(Rehearsal)は、ユーザーがシミュレート可能なインターロケータで競合をリハーサルできるシステムである。
ユーザはRehearsalを使って、事前に定義されたさまざまなコンフリクトシナリオの処理を実践できる。
リハーサルはIRPを使って紛争解決理論に基づく発話を生成する。
論文 参考訳(メタデータ) (2023-09-21T17:59:20Z) - SCREWS: A Modular Framework for Reasoning with Revisions [58.698199183147935]
我々は、リビジョンを伴う推論のためのモジュラーフレームワークであるSCREWSを紹介する。
我々は、SCREWSが、共通のフレームワークの下で、いくつかの以前のアプローチを統合することを示す。
我々は,多種多様な推論タスクに基づいて,最先端のLCMを用いてフレームワークの評価を行った。
論文 参考訳(メタデータ) (2023-09-20T15:59:54Z) - What is a decision problem? [0.0]
私たちのモチベーションは、意思決定分析と運用研究が、メソッドのクラスを中心に(規律として)構造化されているという事実に関連しています。
この目的のために、クライアントから提供された(または提供された)プリミティブに基づいて、既存のメソッドとは独立して、新しいフレームワークを導入します。
論文 参考訳(メタデータ) (2023-01-07T01:03:08Z) - Understanding Interpersonal Conflict Types and their Impact on
Perception Classification [7.907976678407914]
我々は、新しいアノテーションスキームを使用し、コンフリクトアスペクトアノテーションとコンフリクトアスペクトアノテーションの新しいデータセットをリリースする。
次に、ある状況において、ある個人の行動が正しいものであると認識するかどうかを予測する分類器を構築します。
我々の発見は、紛争や社会規範を理解する上で重要な意味を持つ。
論文 参考訳(メタデータ) (2022-08-18T10:39:35Z) - Causal Fairness Analysis [68.12191782657437]
意思決定設定における公平性の問題を理解し、モデル化し、潜在的に解決するためのフレームワークを導入します。
我々のアプローチの主な洞察は、観測データに存在する格差の定量化と、基礎となる、しばしば観測されていない、因果的なメカニズムの収集を結びつけることである。
本研究は,文献中の異なる基準間の関係を整理し,説明するための最初の体系的試みであるフェアネスマップにおいて,本研究の成果を左右するものである。
論文 参考訳(メタデータ) (2022-07-23T01:06:34Z) - 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) - Entangled and correlated photon mixed strategy for social decision
making [0.0]
エンタングル型および相関型光子型戦略の最適混合は、報酬環境の力学に依存することを示す。
本研究は、光子の量子的側面と古典的側面を混合的に利用して意思決定を行う方法である。
論文 参考訳(メタデータ) (2020-10-25T10:57:50Z) - Resolving Head-On Conflicts for Multi-Agent Path Finding with
Conflict-Based Search [0.0]
競合ベースの検索(CBS)は、マルチエージェントパス探索問題を解決するための一般的なフレームワークである。
本稿では,新たな手法,すなわち,このような矛盾を見出すヘッドオン技術を紹介する。
実験の結果,ヘッドオン技術は最先端のMAPFソルバCBSHを改善した。
論文 参考訳(メタデータ) (2020-07-07T15:52:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。