論文の概要: Solution Enumeration by Optimality in Answer Set Programming
- arxiv url: http://arxiv.org/abs/2108.03474v1
- Date: Sat, 7 Aug 2021 15:50:23 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-10 15:10:03.771225
- Title: Solution Enumeration by Optimality in Answer Set Programming
- Title(参考訳): 解集合プログラミングにおける最適性による解列挙
- Authors: Jukka Pajunen, Tomi Janhunen
- Abstract要約: この研究は最適解の素列挙を超えて、最適性による解列挙の計算タスクに対処する(SEO)。
既存の解解法は、既に全ての(最適)解集合の列挙をサポートしている。
上述した解集合列挙のタスクに対する最初の一般アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 6.122161391301866
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Given a combinatorial search problem, it may be highly useful to enumerate
its (all) solutions besides just finding one solution, or showing that none
exists. The same can be stated about optimal solutions if an objective function
is provided. This work goes beyond the bare enumeration of optimal solutions
and addresses the computational task of solution enumeration by optimality
(SEO). This task is studied in the context of Answer Set Programming (ASP)
where (optimal) solutions of a problem are captured with the answer sets of a
logic program encoding the problem. Existing answer-set solvers already support
the enumeration of all (optimal) answer sets. However, in this work, we
generalize the enumeration of optimal answer sets beyond strictly optimal ones,
giving rise to the idea of answer set enumeration in the order of optimality
(ASEO). This approach is applicable up to the best k answer sets or in an
unlimited setting, which amounts to a process of sorting answer sets based on
the objective function. As the main contribution of this work, we present the
first general algorithms for the aforementioned tasks of answer set
enumeration. Moreover, we illustrate the potential use cases of ASEO. First, we
study how efficiently access to the next-best solutions can be achieved in a
number of optimization problems that have been formalized and solved in ASP.
Second, we show that ASEO provides us with an effective sampling technique for
Bayesian networks.
- Abstract(参考訳): 組合せ探索問題を考えると、一つの解を見つけるだけでなく(すべて)その解を列挙したり、存在しないことを示すのに非常に有用である。
目的関数が与えられた場合、最適解についても同様に述べることができる。
この仕事は最適解の素数列挙を超越しており、最適性による解の列挙(seo)の計算タスクに対処する。
このタスクは Answer Set Programming (ASP) の文脈で研究され、問題の(最適)解は問題を符号化する論理プログラムの解集合でキャプチャされる。
既存の解解法は、既に全ての(最適)解集合の列挙をサポートしている。
しかし,本研究では,最適解集合の列挙を厳密な最適解集合を超えて一般化し,最適解集合の列挙を最適性(ASEO)の順に導く。
このアプローチは、最高の k 個の解集合または無限の設定に適用できるが、これは目的関数に基づいて解集合をソートする過程に相当する。
本研究の主な貢献として,上記の解集合列挙のタスクに対して,最初の一般アルゴリズムを提案する。
さらに,ASEOの潜在的なユースケースについて述べる。
まず、asp.netで形式化され解決された多くの最適化問題において、次善のソリューションにいかに効率的にアクセスできるかについて検討する。
次に,ASEOがベイジアンネットワークに有効なサンプリング手法を提供することを示す。
関連論文リスト
- Analyzing and Enhancing the Backward-Pass Convergence of Unrolled
Optimization [50.38518771642365]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。
本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。
Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
論文 参考訳(メタデータ) (2023-12-28T23:15:18Z) - RIGA: A Regret-Based Interactive Genetic Algorithm [14.388696798649658]
そこで本研究では,多目的最適化問題を優先的精度で解くための対話型遺伝的アルゴリズムを提案する。
我々のアルゴリズムはRIGAと呼ばれ、集約関数がパラメータ内で線形であることから、任意の多目的最適化問題に適用できる。
いくつかのパフォーマンス指標(計算時間、最適性とクエリ数のギャップ)に対して、RIGAは最先端のアルゴリズムよりも優れた結果を得る。
論文 参考訳(メタデータ) (2023-11-10T13:56:15Z) - Logic-Based Benders Decomposition in Answer Set Programming for Chronic
Outpatients Scheduling [2.370481325034443]
Answer Set Programming (ASP)では、ユーザーは宣言的に問題を定義でき、効率的な解法でそれを解決できる。
他の研究領域では、論理ベースのベンダー分解(LBBD)が有効であることが証明された。
本稿では, 医療分野の応用を事例として, LBBD を ASP に適用する。
論文 参考訳(メタデータ) (2023-05-19T19:34:47Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳(メタデータ) (2022-01-28T05:53:28Z) - A Mutual Information Maximization Approach for the Spurious Solution
Problem in Weakly Supervised Question Answering [60.768146126094955]
弱々しい教師付き質問応答は通常、最終的な答えのみを監督信号として持つ。
偶然に正解を導出する刺激的な解が多数存在するかもしれないが、そのような解の訓練はモデルの性能を損なう可能性がある。
本稿では,質問応答対と予測解間の相互情報の最大化により,このような意味的相関を明示的に活用することを提案する。
論文 参考訳(メタデータ) (2021-06-14T05:47:41Z) - Efficiently Explaining CSPs with Unsatisfiable Subset Optimization [17.498283247757445]
我々は,制約満足度問題の解法を説明する手法を最近提案した。
ここでの説明は、単純な推論ステップのシーケンスであり、推論ステップの単純さは、使用される制約の数や種類、事実によって測定される。
2つの新しい問題、すなわち、確実に最適である説明を生成する方法と、それらを効率的に生成する方法に取り組みます。
論文 参考訳(メタデータ) (2021-05-25T08:57:43Z) - 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) - Batch Bayesian Optimization on Permutations using Acquisition Weighted
Kernels [86.11176756341114]
決定点プロセスに基づく新しい効率的なバッチ取得方法であるLAWを紹介します。
本研究では,理論特性の知見を得るための後悔分析法を提案する。
二次代入などの置換を含むいくつかの標準問題に対する手法を評価する。
論文 参考訳(メタデータ) (2021-02-26T10:15:57Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。
最小クラスタ回復誤差率のアルゴリズムを考案する。
適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文 参考訳(メタデータ) (2019-10-14T09:18:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。