論文の概要: Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach

• arxiv url: http://arxiv.org/abs/2407.05058v1
• Date: Sat, 6 Jul 2024 12:08:38 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-09 21:18:15.699693
• Title: Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach
• Title（参考訳）: コンステレーションアプローチによる確率的議論へのアルゴリズム的アプローチの適応
• Authors: Andrei Popescu, Johannes P. Wallner,
• Abstract要約: 完全拡張である引数の集合の確率を計算する複雑なタスクのアルゴリズムを開発する。 実験的評価は我々のアプローチの可能性を示唆している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reasoning with defeasible and conflicting knowledge in an argumentative form is a key research field in computational argumentation. Reasoning under various forms of uncertainty is both a key feature and a challenging barrier for automated argumentative reasoning. It was shown that argumentative reasoning using probabilities faces in general high computational complexity, in particular for the so-called constellation approach. In this paper, we develop an algorithmic approach to overcome this obstacle. We refine existing complexity results and show that two main reasoning tasks, that of computing the probability of a given set being an extension and an argument being acceptable, diverge in their complexity: the former is #P-complete and the latter is #-dot-NP-complete when considering their underlying counting problems. We present an algorithm for the complex task of computing the probability of a set of arguments being a complete extension by using dynamic programming operating on tree-decompositions. An experimental evaluation shows promise of our approach.
• Abstract（参考訳）: 議論的形式における非現実的で矛盾する知識との推論は、計算的議論において重要な研究分野である。 様々な形の不確実性の下での推論は、自動議論的推論の鍵となる特徴と難しい障壁である。 確率を用いた議論的推論は一般に高い計算複雑性に直面しており、特にいわゆるコンステレーションアプローチではそうである。 本稿では,この障害を克服するためのアルゴリズム的アプローチを開発する。 我々は、既存の複雑性結果を洗練し、与えられた集合が拡張である確率を計算し、引数が許容されるという2つの主要な推論タスクが複雑さを分散させることを示す: 前者は#P完全であり、後者は根底にある数え上げ問題を考えると#-dot-NP完全である。 本稿では,木分割操作の動的プログラミングを用いて,一組の引数が完全拡張である確率を計算した複雑なタスクのアルゴリズムを提案する。 実験的評価は我々のアプローチの可能性を示唆している。

関連論文リスト

• The Computational Complexity of Circuit Discovery for Inner Interpretability [0.30723404270319693]
  我々は古典的およびパラメータ化された計算複雑性理論を用いて回路発見を研究する。 私たちの発見は、難しい複雑さの風景を明らかにします。 このフレームワークは、解釈可能性クエリの範囲と限界を理解するのに役立ちます。
  論文  参考訳（メタデータ） (2024-10-10T15:22:48Z)
• Predicting Probabilities of Error to Combine Quantization and Early Exiting: QuEE [68.6018458996143]
  本稿では,量子化と早期出口動的ネットワークを組み合わせたより一般的な動的ネットワークQuEEを提案する。 我々のアルゴリズムは、ソフトアーリーエグジットや入力依存圧縮の一形態と見なすことができる。 提案手法の重要な要素は、さらなる計算によって実現可能な潜在的な精度向上の正確な予測である。
  論文  参考訳（メタデータ） (2024-06-20T15:25:13Z)
• Counterfactual and Semifactual Explanations in Abstract Argumentation: Formal Foundations, Complexity and Computation [19.799266797193344]
  議論ベースのシステムは、意思決定プロセスをサポートしながら説明責任を欠くことが多い。 対実的・半実的な説明は解釈可能性のテクニックである。 本稿では,制約の弱いArgumentation Frameworkにおいて,逆ファクトおよび半ファクトのクエリを符号化可能であることを示す。
  論文  参考訳（メタデータ） (2024-05-07T07:27:27Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  本稿では,コードと推論能力の相関性を測定するために,複雑性に富んだ推論スコア(CIRS)を提案する。 具体的には、抽象構文木を用いて構造情報をエンコードし、論理的複雑性を計算する。 コードはhttps://github.com/zjunlp/EasyInstructのEasyInstructフレームワークに統合される。
  論文  参考訳（メタデータ） (2023-08-29T17:22:39Z)
• From Probabilistic Programming to Complexity-based Programming [0.5874142059884521]
  本稿では,CompLogという新しい計算フレームワークの主な特徴と実装について述べる。 ProbLogのような確率的プログラミングシステムにインスパイアされたCompLogは、Simplicity Theoryによって提案された推論メカニズムに基づいている。 提案システムでは,ある状況の予期せぬ事柄を,元投稿や元被写体で計算することができる。
  論文  参考訳（メタデータ） (2023-07-28T10:11:01Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• The Hardness of Reasoning about Probabilities and Causality [5.190207094732672]
  本研究では,定量的確率論的推論と因果的影響に対するdo-calculus推論を表現可能な言語について検討する。 この研究の主な貢献は、満足度問題の正確な計算複雑性を確立することである。 我々は、よく研究されたクラス $exists$R の簡潔な変種と見なすことができる Succ$exists$R という新しい自然複雑性クラスを導入する。
  論文  参考訳（メタデータ） (2023-05-16T15:01:22Z)
• Exceeding Computational Complexity Trial-and-Error Dynamic Action and Intelligence [0.0]
  計算複雑性 (Computational complexity) は、計算の難易度を規定する計算機科学のコア理論である。 本稿では,概念を明確にし,不特定型コンピューティング,特化型コンピューティング,コンピュータエージェント,動的検索などの定義を提案する。 また,このフレームワーク,すなわちトライアル・アンド・エラー+動的検索を提案し,議論する。
  論文  参考訳（メタデータ） (2022-12-22T21:23:27Z)
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
  分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。 この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
  論文  参考訳（メタデータ） (2020-07-30T04:18:51Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)
• From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
  本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。 8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
  論文  参考訳（メタデータ） (2020-06-05T10:56:52Z)

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

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