論文の概要: Counting Answer Sets of Disjunctive Answer Set Programs

• arxiv url: http://arxiv.org/abs/2507.11655v1
• Date: Tue, 15 Jul 2025 18:41:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-17 19:00:11.112543
• Title: Counting Answer Sets of Disjunctive Answer Set Programs
• Title（参考訳）: 解答集合の解答集合の数え方
• Authors: Mohimenul Kabir, Supratik Chakraborty, Kuldeep S Meel,
• Abstract要約: 本稿では,解法論理プログラムの解集合をカウントする新しいフレームワークSharpASP-SRを提案する。 SharpASP-SRは, 応答数が大きいインスタンスにおいて, 既存のカウンタを著しく上回っていることを示す。
• 参考スコア（独自算出の注目度）: 28.739355096774155
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Answer Set Programming (ASP) provides a powerful declarative paradigm for knowledge representation and reasoning. Recently, counting answer sets has emerged as an important computational problem with applications in probabilistic reasoning, network reliability analysis, and other domains. This has motivated significant research into designing efficient ASP counters. While substantial progress has been made for normal logic programs, the development of practical counters for disjunctive logic programs remains challenging. We present SharpASP-SR, a novel framework for counting answer sets of disjunctive logic programs based on subtractive reduction to projected propositional model counting. Our approach introduces an alternative characterization of answer sets that enables efficient reduction while ensuring that intermediate representations remain of polynomial size. This allows SharpASP-SR to leverage recent advances in projected model counting technology. Through extensive experimental evaluation on diverse benchmarks, we demonstrate that SharpASP-SR significantly outperforms existing counters on instances with large answer set counts. Building on these results, we develop a hybrid counting approach that combines enumeration techniques with SharpASP-SR to achieve state-of-the-art performance across the full spectrum of disjunctive programs.
• Abstract（参考訳）: Answer Set Programming (ASP)は知識表現と推論のための強力な宣言的パラダイムを提供する。 近年,確率論的推論,ネットワーク信頼性解析,その他の分野への応用において,解集合の数え上げが重要な計算問題として浮上している。 これは、効率的なASPカウンタの設計に関する重要な研究を動機付けている。 通常の論理プログラムにはかなりの進歩があったが、解法論理プログラムの実用的なカウンタの開発はいまだに困難である。 本稿では,予測命題モデルカウントに対する減算に基づく解法論理プログラムの解集合をカウントする新しいフレームワークSharpASP-SRを提案する。 提案手法では, 中間表現が多項式サイズのままであることを保証するとともに, 効率の低下を可能にする解集合の代替的特徴付けを導入する。 これによりSharpASP-SRは、予測されたモデルカウント技術の最近の進歩を活用することができる。 シャープASP-SRは,多様なベンチマークの広範な実験的評価を通じて,解集合数が大きいインスタンスにおいて,既存のカウンタを著しく上回っていることを示す。 これらの結果に基づいて,列挙手法をSharpASP-SRと組み合わせたハイブリッドカウント手法を開発し,全領域にわたって最先端の性能を実現する。

関連論文リスト

• PixelThink: Towards Efficient Chain-of-Pixel Reasoning [70.32510083790069]
  PixelThinkは、外部から推定されるタスクの難しさと内部で測定されたモデルの不確実性を統合する、シンプルで効果的なスキームである。 シーンの複雑さと予測信頼度に応じて推論の長さを圧縮することを学ぶ。 実験により,提案手法は推論効率と全体セグメンテーション性能の両方を改善した。
  論文  参考訳（メタデータ） (2025-05-29T17:55:49Z)
• TACO: Think-Answer Consistency for Optimized Long-Chain Reasoning and Efficient Data Learning via Reinforcement Learning in LVLMs [50.820065021136024]
  DeepSeek R1には、大規模言語モデル(LLM)のためのかなり高度な複雑な推論がある。 最近の手法は、R1の推論能力をマルチモーダルな設定で再現しようと試みている。 視覚推論のための新しい強化学習アルゴリズムTACOを提案する。
  論文  参考訳（メタデータ） (2025-05-27T06:30:48Z)
• Inference-Time Computations for LLM Reasoning and Planning: A Benchmark and Insights [49.42133807824413]
  本稿では,大規模言語モデル(LLM)の複雑な課題解決における推論と計画能力について検討する。 近年の推論時間技術の発展は,LLM推論を追加訓練なしで向上させる可能性を示している。 OpenAIのo1モデルは、マルチステップ推論と検証の新たな使用を通じて、有望なパフォーマンスを示している。
  論文  参考訳（メタデータ） (2025-02-18T04:11:29Z)
• PEA: Enhancing LLM Performance on Computational-Reasoning Tasks [21.13926189404758]
  本研究では、計算推論問題と呼ばれる重要な推論タスクのクラスを記述し、解決するための形式的なアプローチを紹介する。 このフレームワークはこれらの問題を述語と列挙の構成要素に分解し、LLMを使って特定の述語、列挙、集約ルールに基づいてプログラムを合成する。 実験的な評価により、PEAはベンチマーク計算問題における基礎となるモデルの性能を大幅に向上し、平均精度が約50%向上し、効率が向上することがわかった。
  論文  参考訳（メタデータ） (2025-02-16T00:27:05Z)
• Answer Set Counting and its Applications [0.8158530638728501]
  提案式にコンパクトエンコーディングを利用する,正確なASPカウンタである sharpASP を開発した。 さらに我々は,ガウス・ジョーダン除去をASPソルバに組み込んだハッシュベースのカウンタであるApproxASPという,近似的なASPカウンタを提案した。
  論文  参考訳（メタデータ） (2025-02-13T11:52:55Z)
• BRiTE: Bootstrapping Reinforced Thinking Process to Enhance Language Model Reasoning [78.63421517563056]
  大規模言語モデル(LLM)は複雑な推論タスクにおいて顕著な機能を示した。 本稿では,新しいグラフィカルモデルを用いてLLM推論を定式化する統一確率的フレームワークを提案する。 本稿では,Bootstrapping Reinforced Thinking Process (BRiTE)アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2025-01-31T02:39:07Z)
• Enhancing Multi-Step Reasoning Abilities of Language Models through Direct Q-Function Optimization [49.362750475706235]
  強化学習(Reinforcement Learning, RL)は、大規模言語モデルを人間の好みと整合させ、複雑なタスクを遂行する能力を向上させる上で重要な役割を担っている。 反応生成過程をマルコフ決定プロセス(MDP)として定式化し,ソフトアクター・クリティック(SAC)フレームワークを用いて,言語モデルによって直接パラメータ化されたQ関数を最適化する,直接Q関数最適化(DQO)を提案する。 GSM8KとMATHという2つの数学問題解決データセットの実験結果から、DQOは従来の手法よりも優れており、言語モデルを整合させるための有望なオフライン強化学習手法として確立されている。
  論文  参考訳（メタデータ） (2024-10-11T23:29:20Z)
• Think Beyond Size: Adaptive Prompting for More Effective Reasoning [0.0]
  本稿では,動的かつ反復的なフレームワークであるAdaptive Promptingを紹介する。 その結果、Adaptive Promptingは、算術的推論(GSM8K、MultiArithm)、論理的推論、コモンセンスタスクなど、様々な推論ベンチマークのパフォーマンスを著しく向上させることを示した。 提案手法は,計算効率を維持しつつ,GPT-4などの大規模モデルと競合する性能を実現する。
  論文  参考訳（メタデータ） (2024-10-10T17:14:36Z)
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach [57.788675205519986]
  我々は任意の解法によって生成されるPOMDP実行から高品質なトレースを学習する。 我々は、データと時間効率のIndu Logic Programming(ILP)を利用して、解釈可能な信念に基づくポリシー仕様を生成する。 ASP(Answer Set Programming)で表現された学習は、ニューラルネットワークよりも優れた性能を示し、より少ない計算時間で最適な手作りタスクに類似していることを示す。
  論文  参考訳（メタデータ） (2024-02-29T15:36:01Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Extended High Utility Pattern Mining: An Answer Set Programming Based Framework and Applications [0.0]
  ASPのようなルールベースの言語は、パターンユーティリティを評価するためのユーザが提供する基準を指定するのに適しているようだ。 本稿では,従来の文献では考慮されていない実用基準の新たなクラスを実現するためのフレームワークを提案する。 新型コロナウイルス患者のICU入院を予測するための革新的な方法の定義のために,ビルディングブロックとして活用する。
  論文  参考訳（メタデータ） (2023-03-23T11:42:57Z)
• NAPG: Non-Autoregressive Program Generation for Hybrid Tabular-Textual Question Answering [52.10214317661547]
  現在の数値推論法はプログラムシーケンスを自己回帰的にデコードする。 プログラム生成の精度は、デコードステップがエラー伝搬によって展開されるにつれて急激に低下する。 本稿では,非自己回帰型プログラム生成フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-11-07T11:25:21Z)
• Harnessing Incremental Answer Set Solving for Reasoning in Assumption-Based Argumentation [1.5469452301122177]
  仮定に基づく議論(ABA)は、中心的な構造化された議論形式である。 近年のASPの進歩により、ABAのNPハード推論タスクを効率的に解けるようになった。
  論文  参考訳（メタデータ） (2021-08-09T17:34:05Z)

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

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