論文の概要: On Improving the Backjump Level in PB Solvers

• arxiv url: http://arxiv.org/abs/2107.13085v1
• Date: Tue, 27 Jul 2021 21:23:03 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-29 14:02:59.974258
• Title: On Improving the Backjump Level in PB Solvers
• Title（参考訳）: PBソルバーのバックジャンプレベル改善について
• Authors: Romain Wallon
• Abstract要約: PB制約が存在する場合,SATソルバにおいて最も高いバックジャンプを行う保証がないことを示す。 コンフリクト分析で同定されたバックジャンプレベルを改善するために,様々なアプローチを導入,評価する。 実験の結果, PBソルバでは準最適バックジャンプがよく見られるが, その影響は明らかでない。
• 参考スコア（独自算出の注目度）: 2.741266294612776
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Current PB solvers implement many techniques inspired by the CDCL architecture of modern SAT solvers, so as to benefit from its practical efficiency. However, they also need to deal with the fact that many of the properties leveraged by this architecture are no longer true when considering PB constraints. In this paper, we focus on one of these properties, namely the optimality of the so-called first unique implication point (1-UIP). While it is well known that learning the first assertive clause produced during conflict analysis ensures to perform the highest possible backjump in a SAT solver, we show that there is no such guarantee in the presence of PB constraints. We also introduce and evaluate different approaches designed to improve the backjump level identified during conflict analysis by allowing to continue the analysis after reaching the 1-UIP. Our experiments show that sub-optimal backjumps are fairly common in PB solvers, even though their impact on the solver is not clear.
• Abstract（参考訳）: 現在のPBソルバは、現在のSATソルバのCDCLアーキテクチャにインスパイアされた多くの技術を実装し、その実用的効率の恩恵を受ける。 しかし、PB制約を考慮すると、このアーキテクチャによって活用されるプロパティの多くがもはや真実ではないという事実にも対処する必要がある。 本稿では、これらの特性の1つ、すなわち、いわゆる第一一意含意点(1-UIP)の最適性に焦点を当てる。 コンフリクト解析で生成した最初の断定節を学習することでSATソルバの最大バックジャンプの実行が保証されることはよく知られているが,PB制約の存在下ではそのような保証は存在しない。 また,1-UIPに到達した後に解析を継続させることにより,紛争解析において同定されたバックジャンプレベルを改善するために設計された異なるアプローチを導入・評価する。 実験の結果, PBソルバでは準最適バックジャンプがよく見られるが, その影響は明らかでない。

関連論文リスト

• Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives [16.101435842520473]
  本稿では,POMDPにおける最大到達可能性確率問題(indefinite-horizon)と呼ばれる問題について検討する。 割引問題に対するポイントベース手法の成功に触発され,MRPPへの拡張について検討した。 本稿では,これらの手法の強みを有効活用し,信念空間を効率的に探索するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-05T02:33:50Z)
• Theoretically Achieving Continuous Representation of Oriented Bounding Boxes [64.15627958879053]
  本論文は,オブジェクト指向境界ボックス表現における不連続性を完全に解決しようとする試みである。 本研究では,既存の検出器に容易に統合可能なCOBB(Continuous OBB)という新しい表現法を提案する。 OOD評価のためのオープンソースのディープラーニングフレームワークJittorの検出ツールボックスJDetをベースとした,モジュール化されたベンチマークを開発した。
  論文  参考訳（メタデータ） (2024-02-29T09:27:40Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean Optimization [10.513103815142731]
  PBO(Pseudo-Boolean Optimization)の解法における局所探索アルゴリズムの改良法について検討する。 我々のアルゴリズムであるDeciLS-PBOは最先端のアルゴリズムと比較して有望な性能を持つ。
  論文  参考訳（メタデータ） (2023-01-28T17:03:56Z)
• Optimizing Two-way Partial AUC with an End-to-end Framework [154.47590401735323]
  ROC曲線のエリア(AUC)は、機械学習にとって重要な指標である。 最近の研究は、TPAUCが既存のPartial AUCメトリクスと本質的に矛盾していることを示している。 本論文では,この新指標を最適化するための最初の試行について述べる。
  論文  参考訳（メタデータ） (2022-06-23T12:21:30Z)
• On Dedicated CDCL Strategies for PB Solvers [6.716102421801302]
  PB制約の特異性を考慮し,CDCL戦略を適応させるさまざまな方法を提案し,評価する。 我々の実験は、これらの専用戦略が、時としてこれらの解法の性能を改善できることを示している。
  論文  参考訳（メタデータ） (2021-09-02T15:22:27Z)
• Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
  トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。 性能は不特定な事前条件で優雅に低下することを示す。
  論文  参考訳（メタデータ） (2021-07-03T23:17:26Z)
• Equilibrium Learning in Combinatorial Auctions: Computing Approximate Bayesian Nash Equilibria via Pseudogradient Dynamics [0.0]
  汎用的でスケーラブルなマルチエージェント平衡学習法を提案する。 様々なオークションでBNEを近似する高速で頑健な収束を観察する。
  論文  参考訳（メタデータ） (2021-01-28T11:53:32Z)
• Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation [70.41056265629815]
  最適化アルゴリズムを開発する際、エッジウェイトなどのパラメータが入力として正確に知られていることが一般的である。 本稿では、最近、限られたフィードバックを伴う純粋探索問題に対する手法について概説する。
  論文  参考訳（メタデータ） (2020-12-31T12:40:52Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  我々は、最小二乗値スタイルのアルゴリズムで一般的に使用される、より標準的なベルマン誤差の概念の下での反復が、ほぼ最適値関数の学習において強力なPAC保証を提供することを示す。 そこで本稿では,任意の(線形な)報酬関数に対して,最適に近いポリシーを学習するためにどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2020-08-18T04:34:21Z)

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

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