論文の概要: Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy

• arxiv url: http://arxiv.org/abs/2511.08091v1
• Date: Wed, 12 Nov 2025 01:39:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-12 20:17:03.639367
• Title: Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy
• Title（参考訳）: パールの因果的階層における満足度のためのトラクタビリティへのゲートウェイ
• Authors: Robert Ganian, Marlene Gründel, Simon Wietheger,
• Abstract要約: パールズ・コーサル・ヒエラルキー(PCH)は確率的、介入的、反事実的発言を推論する中心的な枠組みである。 パラメータ化複雑性のレンズを通してこの課題を再考し、トラクタビリティへの最初のゲートウェイを特定する。
• 参考スコア（独自算出の注目度）: 16.72973567404685
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Pearl's Causal Hierarchy (PCH) is a central framework for reasoning about probabilistic, interventional, and counterfactual statements, yet the satisfiability problem for PCH formulas is computationally intractable in almost all classical settings. We revisit this challenge through the lens of parameterized complexity and identify the first gateways to tractability. Our results include fixed-parameter and XP-algorithms for satisfiability in key probabilistic and counterfactual fragments, using parameters such as primal treewidth and the number of variables, together with matching hardness results that map the limits of tractability. Technically, we depart from the dynamic programming paradigm typically employed for treewidth-based algorithms and instead exploit structural characterizations of well-formed causal models, providing a new algorithmic toolkit for causal reasoning.
• Abstract（参考訳）: Pearl's Causal Hierarchy (PCH) は確率的、介入的、反ファクト的ステートメントを推論する中心的なフレームワークであるが、PCHの公式の満足度問題は、ほとんどすべての古典的な設定で計算的に難解である。 パラメータ化複雑性のレンズを通してこの課題を再考し、トラクタビリティへの最初のゲートウェイを特定する。 本研究の結果は,主木幅や変数数などのパラメータを用いて,主要な確率的および反ファクト的フラグメントの満足度を求める固定パラメータとXPアルゴリズムと,トラクタビリティの限界をマッピングする厳密度を一致させた結果を含む。 技術的には、木幅ベースのアルゴリズムで一般的に使用される動的プログラミングパラダイムから脱却し、代わりによく形成された因果モデルの構造的特徴を活用し、因果推論のための新しいアルゴリズム的ツールキットを提供する。

関連論文リスト

• Addressing prior dependence in hierarchical Bayesian modeling for PTA data analysis I: Methodology and implementation [0.0]
  Pulsar Timing Array(PTA)データ分析で遭遇したような複雑な推論タスクは、ベイズフレームワークに依存している。 天体物理学、パルサーノイズ、ニュアンスパラメータの高次元パラメータ空間と強い相互依存性は、効率的な学習と堅牢な推論に重大な課題をもたらす。 我々はこれらの問題を階層的ベイズモデリングの枠組みにおいて、reパラメータ化戦略を導入することで解決する。
  論文  参考訳（メタデータ） (2025-11-05T17:33:44Z)
• Unlocking Symbol-Level Precoding Efficiency Through Tensor Equivariant Neural Network [84.22115118596741]
  シンボルレベルのプリコーディングにおいて,推論の複雑さの低いエンドツーエンドディープラーニング(DL)フレームワークを提案する。 提案手法は,従来の手法よりも約80倍の高速化を実現しつつ,SLPの大幅な性能向上を達成できることを示す。
  論文  参考訳（メタデータ） (2025-10-02T15:15:50Z)
• Probabilities of Causation and Root Cause Analysis with Quasi-Markovian Models [0.0]
  本稿では,アルゴリズムの単純化と,これらの確率に対する厳密な境界計算の計算複雑性を著しく低減する手法を提案する。 また、これらの因果指標を体系的に活用して因果経路全体をランク付けするルート因果解析の新しい方法論的枠組みも導入している。
  論文  参考訳（メタデータ） (2025-09-02T17:39:23Z)
• Identifying Causal Direction via Variational Bayesian Compression [6.928582707713723]
  鍵となる原理はアルゴリズムマルコフ条件であり、因果方向に応じて分解された結合分布はより簡潔な符号長をもたらすと仮定する。 従来のアプローチでは、これらの符号長を単純な関数やガウス過程(GP)に頼って容易に評価可能な複雑さで近似していた。 本稿では,ニューラルネットワークの変分ベイズ学習をコード長の解釈として活用することを提案する。
  論文  参考訳（メタデータ） (2025-05-12T12:40:15Z)
• Structural Entropy Guided Probabilistic Coding [52.01765333755793]
  構造エントロピー誘導型確率的符号化モデルSEPCを提案する。 我々は、構造エントロピー正規化損失を提案することにより、潜在変数間の関係を最適化に組み込む。 分類タスクと回帰タスクの両方を含む12の自然言語理解タスクに対する実験結果は、SEPCの優れた性能を示す。
  論文  参考訳（メタデータ） (2024-12-12T00:37:53Z)
• From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy [3.44747819522562]
  PCHのレベルによって, NPPP, PSPACE, NEXP完全満足度の問題が生じることを示す。 一方、完全言語の場合、すなわち加法、余分化、乗算が可能である場合、反事実レベルの満足度は確率的・因果的なレベルと同じであることを示す。
  論文  参考訳（メタデータ） (2024-05-12T20:25:36Z)
• Efficient Computation of Counterfactual Bounds [44.4263314637532]
  我々は,構造因果モデルのサブクラスにおけるクレダルネットのアルゴリズムを用いて,正確な反ファクト境界を計算する。 近似の精度を信頼性のある間隔で評価する。
  論文  参考訳（メタデータ） (2023-07-17T07:59:47Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  因果構造を学習することは、通常、スコアまたは独立テストを使用して構造を評価することを伴う探索問題を引き起こす。 本研究では,観測・干渉データから因果構造を予測するため,変分推論モデルを訓練する。 我々のモデルは、実質的な分布シフトの下で頑健な一般化能力を示す。
  論文  参考訳（メタデータ） (2022-05-25T17:37:08Z)
• A Fast Non-parametric Approach for Causal Structure Learning in Polytrees [0.0]
  DAG-FOCIは機能的関係や雑音を仮定せずに因果構造学習を高速に行うアルゴリズムである。 本稿では,計算生物学におけるDAG-FOCIの適用可能性を示すとともに,仮定違反に対する我々の手法の堅牢性を示す。
  論文  参考訳（メタデータ） (2021-11-29T21:26:48Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。 本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
  論文  参考訳（メタデータ） (2019-12-27T13:30:29Z)

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

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