論文の概要: Parameterized Complexity of Logic-Based Argumentation in Schaefer's Framework

• arxiv url: http://arxiv.org/abs/2102.11782v1
• Date: Tue, 23 Feb 2021 16:34:42 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-25 04:33:07.939717
• Title: Parameterized Complexity of Logic-Based Argumentation in Schaefer's Framework
• Title（参考訳）: シェーファーの枠組みにおける論理に基づく論証のパラメータ化複雑性
• Authors: Yasir Mahmood, Arne Meier, Johannes Schmidt
• Abstract要約: 以下の3つの計算タスクの命題的変種を議論の中で検討する。 ARG-Checkは複雑性クラスDPに対して完全であり、他の2つの問題は階層の2番目のレベルで完全であることが知られている。 いくつかの症例は非常に難治性が高い(paranp以降)
• 参考スコア（独自算出の注目度）: 1.5469452301122177
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Logic-based argumentation is a well-established formalism modelling nonmonotonic reasoning. It has been playing a major role in AI for decades, now. Informally, a set of formulas is the support for a given claim if it is consistent, subset-minimal, and implies the claim. In such a case, the pair of the support and the claim together is called an argument. In this paper, we study the propositional variants of the following three computational tasks studied in argumentation: ARG (exists a support for a given claim with respect to a given set of formulas), ARG-Check (is a given set a support for a given claim), and ARG-Rel (similarly as ARG plus requiring an additionally given formula to be contained in the support). ARG-Check is complete for the complexity class DP, and the other two problems are known to be complete for the second level of the polynomial hierarchy (Parson et al., J. Log. Comput., 2003) and, accordingly, are highly intractable. Analyzing the reason for this intractability, we perform a two-dimensional classification: first, we consider all possible propositional fragments of the problem within Schaefer's framework (STOC 1978), and then study different parameterizations for each of the fragment. We identify a list of reasonable structural parameters (size of the claim, support, knowledge-base) that are connected to the aforementioned decision problems. Eventually, we thoroughly draw a fine border of parameterized intractability for each of the problems showing where the problems are fixed-parameter tractable and when this exactly stops. Surprisingly, several cases are of very high intractability (paraNP and beyond).
• Abstract（参考訳）: 論理に基づく議論は、非単調推論をモデル化する定評のある形式主義である。 aiには何十年も前から大きな役割を果たしてきた。 形式的に、式の一式は、それが一貫した部分集合最小であり、主張を暗示するならば、与えられたクレームの支持である。 このような場合、サポートとクレームのペアを一緒に引数と呼びます。 本稿では,議論の中で研究されている3つの計算タスクの命題的変種について検討する。arg(ある論理式に対して与えられたクレームに対するサポートが存在する)、arg-check(与えられたクレームに対するサポートを与えられた集合である)、arg-rel(argとそれに含まれる追加の公式を必要とする)である。 ARG-Check は複雑性クラス DP に対して完全であり、その他の2つの問題は多項式階層の第2レベル (Parson et al., J. Log) に対して完全であることが知られている。 Comput., 2003)、そしてそれ故に、非常に難解である。 第一に、シェイファーの枠組み(STOC 1978)内の問題の可能性のあるすべての命題フラグメントを検討し、各フラグメントの異なるパラメータ化を研究する。 上記の決定問題に関連する合理的な構造パラメータ(クレーム,サポート,ナレッジベースのサイズ)のリストを同定する。 最終的に、固定パラメータがどこにあるか、いつそれが止まるのかを示す各問題に対して、パラメータ化の難しさの細かい境界を徹底的に描き出す。 驚くべきことに、いくつかのケースは非常に難易度が高い(paraNP以降)。

関連論文リスト

• MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
  大規模言語モデル(LLM)は、高い精度で算術語問題を解くことができるが、訓練された言語よりも複雑な問題にどのように一般化するかは、ほとんど分かっていない。 本研究では、任意に複雑な算術証明問題に対する LLM の評価フレームワーク、MathGAP を提案する。
  論文  参考訳（メタデータ） (2024-10-17T12:48:14Z)
• Rejection in Abstract Argumentation: Harder Than Acceptance? [18.299322342860513]
  我々は、否定条件(RC)と呼ばれる拡張から引数を推論するための柔軟な条件を考える。 還元AFは非常に表現力が高く、階層の上位層に自然の問題を引き起こす。
  論文  参考訳（メタデータ） (2024-08-20T09:37:04Z)
• Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach [0.0]
  完全拡張である引数の集合の確率を計算する複雑なタスクのアルゴリズムを開発する。 実験的評価は我々のアプローチの可能性を示唆している。
  論文  参考訳（メタデータ） (2024-07-06T12:08:38Z)
• Counterfactual and Semifactual Explanations in Abstract Argumentation: Formal Foundations, Complexity and Computation [19.799266797193344]
  議論ベースのシステムは、意思決定プロセスをサポートしながら説明責任を欠くことが多い。 対実的・半実的な説明は解釈可能性のテクニックである。 本稿では,制約の弱いArgumentation Frameworkにおいて,逆ファクトおよび半ファクトのクエリを符号化可能であることを示す。
  論文  参考訳（メタデータ） (2024-05-07T07:27:27Z)
• Identification for Tree-shaped Structural Causal Models in Polynomial Time [1.5151556900495786]
  ノード間の相関から因果パラメータを同定することは、人工知能におけるオープンな問題である。 本稿では,木を配向成分とするSCMについて検討する。 本稿では,木形SCMの同定問題を解くランダム時間アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-11-23T15:26:29Z)
• Neuro-Symbolic Integration Brings Causal and Reliable Reasoning Proofs [95.07757789781213]
  LLMの複雑な推論には2行のアプローチが採用されている。 1行の作業は様々な推論構造を持つLLMを誘導し、構造出力は自然に中間推論ステップと見なすことができる。 他方の行では、LCMのない宣言的解法を用いて推論処理を行い、推論精度は向上するが、解法のブラックボックスの性質により解釈性に欠ける。 具体的には,Prologインタプリタが生成した中間検索ログにアクセスし,人間可読推論に解釈可能であることを示す。
  論文  参考訳（メタデータ） (2023-11-16T11:26:21Z)
• A Unifying Framework for Learning Argumentation Semantics [50.69905074548764]
  Inductive Logic Programmingアプローチを用いて、抽象的および構造化された議論フレームワークのアクセシビリティセマンティクスを解釈可能な方法で学習する新しいフレームワークを提案する。 提案手法は既存の議論解法よりも優れており,フォーマルな議論や人間と機械の対話の領域において,新たな研究の方向性が開けることになる。
  論文  参考訳（メタデータ） (2023-10-18T20:18:05Z)
• Query Structure Modeling for Inductive Logical Reasoning Over Knowledge Graphs [67.043747188954]
  KGに対する帰納的論理的推論のための構造モデル付きテキスト符号化フレームワークを提案する。 線形化されたクエリ構造とエンティティを、事前訓練された言語モデルを使ってエンコードして、回答を見つける。 2つの帰納的論理推論データセットと3つの帰納的推論データセットについて実験を行った。
  論文  参考訳（メタデータ） (2023-05-23T01:25:29Z)
• Analytical Solutions for the Inverse Problem within Gradual Semantics [3.957174470017176]
  本稿では,段階的意味論における逆問題の解法として解析的アプローチを用いる方法を示す。 現在の最先端とは違って、そのようなアプローチは素早く解を見つけることができ、そのことが保証される。
  論文  参考訳（メタデータ） (2022-03-02T15:55:10Z)
• Variational Causal Networks: Approximate Bayesian Inference over Causal Structures [132.74509389517203]
  離散DAG空間上の自己回帰分布をモデル化したパラメトリック変分族を導入する。 実験では,提案した変分後部が真の後部を良好に近似できることを示した。
  論文  参考訳（メタデータ） (2021-06-14T17:52:49Z)
• From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
  本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。 8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
  論文  参考訳（メタデータ） (2020-06-05T10:56:52Z)

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

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