論文の概要: IASCAR: Incremental Answer Set Counting by Anytime Refinement

• arxiv url: http://arxiv.org/abs/2311.07233v1
• Date: Mon, 13 Nov 2023 10:53:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-14 14:51:44.623264
• Title: IASCAR: Incremental Answer Set Counting by Anytime Refinement
• Title（参考訳）: IASCAR: インクリメンタルAnswer Set Counting by Anytime Refinement
• Authors: Johannes K. Fichte, Sarah Alice Gaggl, Markus Hecher, Dominik Rusovac
• Abstract要約: 本稿では,CNFの知識コンパイルを前提として,サポート対象モデルを符号化する手法を提案する。 予備的な実証分析では,有望な結果を示す。
• 参考スコア（独自算出の注目度）: 18.761758874408557
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Answer set programming (ASP) is a popular declarative programming paradigm with various applications. Programs can easily have many answer sets that cannot be enumerated in practice, but counting still allows quantifying solution spaces. If one counts under assumptions on literals, one obtains a tool to comprehend parts of the solution space, so-called answer set navigation. However, navigating through parts of the solution space requires counting many times, which is expensive in theory. Knowledge compilation compiles instances into representations on which counting works in polynomial time. However, these techniques exist only for CNF formulas, and compiling ASP programs into CNF formulas can introduce an exponential overhead. This paper introduces a technique to iteratively count answer sets under assumptions on knowledge compilations of CNFs that encode supported models. Our anytime technique uses the inclusion-exclusion principle to improve bounds by over- and undercounting systematically. In a preliminary empirical analysis, we demonstrate promising results. After compiling the input (offline phase), our approach quickly (re)counts.
• Abstract（参考訳）: Answer set programming (ASP)は、様々なアプリケーションで一般的な宣言型プログラミングパラダイムである。 プログラムは、実際に列挙できない多くの解集合を持つことは容易であるが、数えることによって解空間の定量化が可能である。 リテラルの仮定の下で数えると、解空間の一部を理解するツール(いわゆる解集合ナビゲーション)が得られる。 しかし、解空間の一部をナビゲートするには何度も数える必要があり、理論的には高価である。 知識コンパイルはインスタンスを多項式時間で計算する表現にコンパイルする。 しかし、これらの手法はCNF式にのみ存在し、ASPプログラムをCNF式にコンパイルすると指数的オーバーヘッドが生じる。 本稿では,CNFの知識コンパイルを前提として,サポート対象モデルを符号化する手法を提案する。 当社のanytimeテクニックでは,包含排他原則を使用して,オーバーカウントとオーバーカウントによる境界の改善を体系的に行います。 予備的な実証分析では,有望な結果を示した。 入力(オフラインフェーズ)をコンパイルすると、我々のアプローチはすぐに(再)カウントされます。

関連論文リスト

• Recursive Visual Programming [53.76415744371285]
  本稿では、生成ルーチンを単純化し、より効率的な問題解決を提供し、より複雑なデータ構造を管理するRecursive Visual Programming (RVP)を提案する。 本稿では,VSR,COVR,GQA,NextQAなどのベンチマークにおいて,RVPの有効性を示す。
  論文  参考訳（メタデータ） (2023-12-04T17:27:24Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• Answering Ambiguous Questions via Iterative Prompting [84.3426020642704]
  オープンドメインの質問応答では、質問のあいまいさのため、複数の妥当な回答が存在する可能性がある。 ひとつのアプローチは、すべての有効な回答を直接予測することですが、これは、妥当性と多様性のバランスに苦労する可能性があります。 本稿では,あいまいな疑問に答える既存手法の欠陥に対処するため,AmbigPromptを提案する。
  論文  参考訳（メタデータ） (2023-07-08T04:32:17Z)
• Towards end-to-end ASP computation [8.804696601388706]
  本稿では,与えられた制約を満たす線形代数的安定モデルと解集合プログラミング(ASP)のエンドツーエンドアプローチを提案する。 我々は、行列化された正規論理プログラムから構築されたコスト関数の数値最小化として、Lin-Zhaoの定理 citeLin04 をベクトル空間内で直接制約とともに実装する。 3色およびハミルトンサイクル問題を含むプログラミング例を用いて、我々のアプローチを実証的に検証する。
  論文  参考訳（メタデータ） (2023-06-12T02:00:22Z)
• Top-Down Knowledge Compilation for Counting Modulo Theories [11.086759883832505]
  入力式が決定論的分解可能な否定正規形(d-DNNF)である場合、仮説モデルカウントは効率的に解ける。 トップダウン知識コンパイルは#SAT問題を解決する最先端技術である。 我々は,DPLL(T)探索の痕跡に基づくトップダウンコンパイラを提唱する。
  論文  参考訳（メタデータ） (2023-06-07T15:46:28Z)
• Evaluating and Improving Tool-Augmented Computation-Intensive Math Reasoning [75.74103236299477]
  CoT(Chain-of- Thought prompting)とツール拡張は、大きな言語モデルを改善するための効果的なプラクティスとして検証されている。 ツールインターフェース,すなわち textbfDELI を用いた推論ステップを考慮に入れた新しい手法を提案する。 CARPと他の6つのデータセットの実験結果から、提案されたDELIは、主に競合ベースラインを上回っていることが示された。
  論文  参考訳（メタデータ） (2023-06-04T17:02:59Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  本稿では,ニューラルネットワーク演算子から知識グラフの埋め込みを分解する,複雑な問合せ応答のためのフレームワークを提案する。 クエリグラフの上に、局所的な原子式上のワンホップ推論とグローバル論理的推論を結びつける論理メッセージパッシングニューラルネットワーク(LMPNN)を提案する。 我々のアプローチは、最先端のニューラルCQAモデルをもたらす。
  論文  参考訳（メタデータ） (2023-01-21T02:34:06Z)
• Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks [108.4568236569645]
  CoT(Chain-of-thinkts prompting)は、これらのタスクに対する最先端の手法である。 本稿では、言語モデルを用いて推論過程をプログラムとして表現する「思考プログラム(PoT)」を提案する。 PoTは、評価されたすべてのデータセットに対して、CoTに対する平均的なパフォーマンス向上を約12%示すことができる。
  論文  参考訳（メタデータ） (2022-11-22T21:06:00Z)
• Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs [22.39203220587435]
  本稿では,このような量的推論問題に対処するために必要な基礎的数え上げ問題を効率的に解くことのできる,新しいシステムを提案する。 本システムでは,木幅をグラフベースで表し,ELPプログラムの抽象表現(グラフ)を反復的に探索し,精算する。 私たちのアプローチは、最近導入された既存のシステムと競合しています。
  論文  参考訳（メタデータ） (2021-08-06T09:46:34Z)
• grASP: A Graph Based ASP-Solver and Justification System [5.098678276629787]
  本稿では,目標の結合をノードとして明示的に表現する,新たな依存グラフに基づく解集合探索手法を提案する。 私たちの表現は因果関係を保ち、答えセットの各リテラルをエレガントに見つけるために正当化します。
  論文  参考訳（メタデータ） (2021-04-02T18:16:20Z)
• ASP(AC): Answer Set Programming with Algebraic Constraints [20.559497209595822]
  本稿では、半順序値と重み付け式評価を比較する制約を含むような、代数制約付き解集合プログラミング(ASP(AC))を紹介する。 この研究は論理プログラミングの理論と実践の受け入れを検討中である。
  論文  参考訳（メタデータ） (2020-08-10T10:20:49Z)

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

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