論文の概要: On Irrelevant Literals in Pseudo-Boolean Constraint Learning
- arxiv url: http://arxiv.org/abs/2012.04424v1
- Date: Tue, 8 Dec 2020 13:52:09 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-16 21:27:30.288496
- Title: On Irrelevant Literals in Pseudo-Boolean Constraint Learning
- Title（参考訳）: Pseudo-Boolean Constraint Learningにおける無関係リテラルについて
- Authors: Danel Le Berre, Pierre Marquis, Stefan Mengel, Romain Wallon
- Abstract要約: 関連するリテラルが、本来よりも弱い制約を推論する可能性があることを示す。
これは、切断平面に基づくpbソルバの現在の実装は、無関係リテラルの発生を防止するために再検討されるべきであることを示唆している。
- 参考スコア（独自算出の注目度）: 21.506382989223784
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Learning pseudo-Boolean (PB) constraints in PB solvers exploiting cutting
planes based inference is not as well understood as clause learning in
conflict-driven clause learning solvers. In this paper, we show that PB
constraints derived using cutting planes may contain \emph{irrelevant
literals}, i.e., literals whose assigned values (whatever they are) never
change the truth value of the constraint. Such literals may lead to infer
constraints that are weaker than they should be, impacting the size of the
proof built by the solver, and thus also affecting its performance. This
suggests that current implementations of PB solvers based on cutting planes
should be reconsidered to prevent the generation of irrelevant literals.
Indeed, detecting and removing irrelevant literals is too expensive in practice
to be considered as an option (the associated problem is NP-hard.
- Abstract（参考訳）: PBソルバにおける擬似ブール(PB)制約の学習は、競合駆動型節学習ソルバにおける節学習ほど理解されていない。
本稿では,切断平面を用いて導出されるpb制約が,制約の真理値を決して変更しないリテラルである \emph{irrelevant literals} を含む可能性があることを示す。
このようなリテラルは、本来よりも弱い制約を推測し、ソルバによって構築された証明のサイズに影響し、その結果その性能に影響する可能性がある。
これは、切断平面に基づくpbソルバの現在の実装は、無関係リテラルの発生を防止するために再検討されるべきであることを示唆している。
実際、無関係リテラルの検出と削除は、実際にはオプションとして考えるには高すぎる(関連する問題はNPハードである)。
関連論文リスト
- Learning General Continuous Constraint from Demonstrations via Positive-Unlabeled Learning [8.361428709513476]
本稿では,実証から連続的,任意の,あるいは非線形な制約を推測する,正の未ラベル(PU)学習手法を提案する。
提案手法の有効性を2つのMujoco環境で検証した。
論文 参考訳（メタデータ） (2024-07-23T14:00:18Z) - On the Correspondence of Non-flat Assumption-based Argumentation and Logic Programming with Negation as Failure in the Head [20.981256612743145]
非平坦なABAとLPの対応性を示す。
次に、この結果を、もともと双極性ABAと呼ばれる非平坦なABAの断片に対して定義された、いわゆる集合安定ABA意味論に拡張する。
本稿では,LP の集合安定セマンティクスを頭の中の失敗として定義し,集合安定な ABA セマンティクスとの対応を示す。
論文 参考訳（メタデータ） (2024-05-15T15:10:03Z) - ConstraintChecker: A Plugin for Large Language Models to Reason on
Commonsense Knowledge Bases [53.29427395419317]
コモンセンス知識ベース(CSKB)に対する推論は,新しいコモンセンス知識を取得する方法として検討されてきた。
我々は**ConstraintChecker*を提案します。
論文 参考訳（メタデータ） (2024-01-25T08:03:38Z) - Using Integer Constraint Solving in Reuse Based Requirements Engineering [0.0]
製品ライン(PL)は、再利用ベースの構成に対する効果的なアプローチを証明した。
現在、製品は制約満足度問題と見なせることが広く認識されている。
制約プログラミングをPLの制約を指定するための第一選択候補として考えるのは当然である。
本稿では,PL制約の指定に整数制約プログラミングを用いることについて,さらに検討する。
論文 参考訳（メタデータ） (2023-09-28T09:20:07Z) - Interpretability at Scale: Identifying Causal Mechanisms in Alpaca [62.65877150123775]
本研究では、Boundless DASを用いて、命令に従う間、大規模言語モデルにおける解釈可能な因果構造を効率的に探索する。
私たちの発見は、成長し、最も広くデプロイされている言語モデルの内部構造を忠実に理解するための第一歩です。
論文 参考訳（メタデータ） (2023-05-15T17:15:40Z) - APOLLO: A Simple Approach for Adaptive Pretraining of Language Models
for Logical Reasoning [73.3035118224719]
本稿では,論理的推論能力を改善した適応事前学習型言語モデルAPOLLOを提案する。
APOLLOはReClorで比較可能であり、LogiQAでベースラインを上回ります。
論文 参考訳（メタデータ） (2022-12-19T07:40:02Z) - Online Selective Classification with Limited Feedback [82.68009460301585]
オンライン学習モデルにおいて、予測者がインスタンスの分類を控える可能性のある選択的分類について検討する。
私たちが考慮している設定の健全な2つの側面は、データが不可避である可能性があるため、データは不可避である可能性があるということです。
smash$tildeO(T1-mu)$ over abstention against Adaptive adversaries. smash$tildeO(T1-mu)$ incurring smash$tildeO(T1-mu)$ over abstention。
論文 参考訳（メタデータ） (2021-10-27T08:00:53Z) - Sufficient reasons for classifier decisions in the presence of
constraints [9.525900373779395]
最近の研究では、二項分類器による決定を推論する理論が明らかにされている。
我々は制約を考慮したより一般的な理論を提案する。
私たちは、この単純なアイデアが(時にはもっと)簡潔な理由をもたらすことを証明します。
論文 参考訳（メタデータ） (2021-05-12T23:36:12Z) - Please Mind the Root: Decoding Arborescences for Dependency Parsing [67.71280539312536]
我々はUniversal Dependency Treebankから多くの言語における最先端の出力を分析する。
最悪の制約違反率は24%です。
論文 参考訳（メタデータ） (2020-10-06T08:31:14Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z) - On Weakening Strategies for PB Solvers [19.78156213005998]
現在の擬ブール解法は、競合解析中に新しい制約を推測するために切断平面証明システムの異なる変種を実装している。
これらの変種の一つは一般化分解であり、強い制約を推測することができるが、それが生成する係数の増大に悩まされる。
別の変種は弱化と除算を使い、実際はより効率的だがより弱い制約を推測する。
論文 参考訳（メタデータ） (2020-05-09T15:40:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。