論文の概要: Efficiently Explaining CSPs with Unsatisfiable Subset Optimization (extended algorithms and examples)

• arxiv url: http://arxiv.org/abs/2303.11712v3
• Date: Tue, 28 Nov 2023 13:07:47 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-30 16:41:47.134861
• Title: Efficiently Explaining CSPs with Unsatisfiable Subset Optimization (extended algorithms and examples)
• Title（参考訳）: 不満足な部分最適化によるcspの効率的な説明(拡張アルゴリズムと例)
• Authors: Emilio Gamba, Bart Bogaerts, Tias Guns
• Abstract要約: 我々は,制約満足度問題の解法を段階的に説明する手法を最近提案した。 ここでは、コスト関数を用いて単純さを定量化する単純な推論ステップの列を説明する。
• 参考スコア（独自算出の注目度）: 14.163888405810635
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We build on a recently proposed method for stepwise explaining solutions of Constraint Satisfaction Problems (CSP) in a human-understandable way. An explanation here is a sequence of simple inference steps where simplicity is quantified using a cost function. The algorithms for explanation generation rely on extracting Minimal Unsatisfiable Subsets (MUS) of a derived unsatisfiable formula, exploiting a one-to-one correspondence between so-called non-redundant explanations and MUSs. However, MUS extraction algorithms do not provide any guarantee of subset minimality or optimality with respect to a given cost function. Therefore, we build on these formal foundations and tackle the main points of improvement, namely how to generate explanations efficiently that are provably optimal (with respect to the given cost metric). For that, we developed (1) a hitting set-based algorithm for finding the optimal constrained unsatisfiable subsets; (2) a method for re-using relevant information over multiple algorithm calls; and (3) methods exploiting domain-specific information to speed up the explanation sequence generation. We experimentally validated our algorithms on a large number of CSP problems. We found that our algorithms outperform the MUS approach in terms of explanation quality and computational time (on average up to 56 % faster than a standard MUS approach).
• Abstract（参考訳）: 我々は,制約満足度問題 (CSP) の解を,人間に理解可能な方法で段階的に説明する手法を最近提案した。 ここでは、コスト関数を用いて単純さを定量化する単純な推論ステップの列を説明する。 説明生成アルゴリズムは、派生した不満足な式から最小不満足な部分集合(MUS)を抽出し、いわゆる非冗長な説明とMUSを1対1で対応させる。 しかし、mus抽出アルゴリズムは、与えられたコスト関数に対する部分的最小性や最適性の保証を提供しない。 したがって、これらの形式的基礎の上に構築し、改善の主なポイント、すなわち(与えられたコストメトリックに関して)確実に最適な説明を効率的に生成する方法に取り組む。 そこで本研究では,(1)最適制約を満たさない部分集合を探索するヒット集合型アルゴリズム,(2)複数のアルゴリズム呼び出しで関連する情報を再利用する手法,(3)説明シーケンス生成を高速化するためにドメイン固有情報を利用する手法を開発した。 我々は多数のcsp問題に対してアルゴリズムを実験的に検証した。 我々のアルゴリズムは、説明品質と計算時間(標準のMUSアプローチよりも平均56%高速)において、MUSアプローチよりも優れていることがわかった。

関連論文リスト

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• OptABC: an Optimal Hyperparameter Tuning Approach for Machine Learning Algorithms [1.6114012813668934]
  OptABCは、ABCアルゴリズムがほぼ最適解へのより高速な収束を支援するために提案されている。 OptABCは、人工蜂コロニーアルゴリズム、K-Meansクラスタリング、greedyアルゴリズム、および反対ベースの学習戦略を統合している。 実験結果から,OptABCの有効性が文献の既存手法と比較された。
  論文  参考訳（メタデータ） (2021-12-15T22:33:39Z)
• Efficiently Explaining CSPs with Unsatisfiable Subset Optimization [17.498283247757445]
  我々は,制約満足度問題の解法を説明する手法を最近提案した。 ここでの説明は、単純な推論ステップのシーケンスであり、推論ステップの単純さは、使用される制約の数や種類、事実によって測定される。 2つの新しい問題、すなわち、確実に最適である説明を生成する方法と、それらを効率的に生成する方法に取り組みます。
  論文  参考訳（メタデータ） (2021-05-25T08:57:43Z)
• Learning Linear Temporal Properties from Noisy Data: A MaxSAT Approach [22.46055650237819]
  雑音の存在下でも簡潔な公式を推測するための2つのアルゴリズムを考案する。 我々の第一のアルゴリズムは、推論問題を満足できる問題に還元することで最小の式を推論する。 第2の学習アルゴリズムは、決定木学習アルゴリズムに基づく公式上の決定木を導出する第1のアルゴリズムに依存している。
  論文  参考訳（メタデータ） (2021-04-30T16:06:03Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。 この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。 我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
  論文  参考訳（メタデータ） (2020-06-21T15:32:21Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

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

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