論文の概要: The Causal Description Gap: Information-Theoretic Separations Across Pearl's Hierarchy

• arxiv url: http://arxiv.org/abs/2605.02177v1
• Date: Mon, 04 May 2026 03:13:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-05 20:33:50.120391
• Title: The Causal Description Gap: Information-Theoretic Separations Across Pearl's Hierarchy
• Title（参考訳）: Causal Description Gap: パール階層全体にわたる情報理論的分離
• Authors: Seyed Morteza Emadi,
• Abstract要約: パールの因果的階層は、観察的、介入的、および反ファクト的クエリが質的に異なることを示している。 我々は、クエリのクラスに対してSCMによって引き起こされる答えのオラクルのKolmogorov複雑性であるクエリクラス記述長によってこれを形式化する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Pearl's causal hierarchy shows that observational, interventional, and counterfactual queries are qualitatively distinct. We ask a quantitative version of this question: how many additional bits are needed to specify higher-rung causal answers once lower-rung answers are known? We formalize this via query-class description length, the Kolmogorov complexity of the answer oracle induced by an SCM for a class of queries. Our main construction gives binary acyclic SCMs whose observational distribution has constant description length, while the single-variable interventional answer oracle has description length $Θ(n^2)$. A degree-sensitive upper bound shows that finite-gate-schema SCMs of indegree $d$ have observational-interventional gap at most $O(nd \log(en/d) + n \log n)$, making the quadratic construction order-optimal in the dense regime and a rooted-tree construction order-optimal for bounded indegree. The quadratic separation persists under $\varepsilon$-accurate total-variation descriptions for every fixed $\varepsilon < 1/4$. At the next rung, the full hard-do interventional oracle can still leave a $Θ(n)$ counterfactual description gap. A general ambiguity-to-bits theorem and Shannon analogue show that these gaps equal the logarithm of residual higher-rung ambiguity up to lower-order terms.
• Abstract（参考訳）: パールの因果的階層は、観察的、介入的、および反ファクト的クエリが質的に異なることを示している。 我々は、この質問の定量的バージョンを尋ねる:下肺の答えが分かっていれば、高肺の因果関係の答えを特定するために、追加のビットがいくつ必要か? 我々は、クエリのクラスに対してSCMによって引き起こされる答えのオラクルのKolmogorov複雑性であるクエリクラス記述長によってこれを形式化する。 我々の主構成は、観測分布が一定記述長を持つ二元非巡回SCMを与え、一方、単一変数の介入応答オラクルは記述長が$(n^2)$である。 次数感受性の上界は、indegree $d$ の有限ゲート-スキーマ SCM が、最大$O(nd \log(en/d) + n \log n)$ の観測的インターベンショナルギャップを持つことを示している。 二次分離は$\varepsilon$-accurate total-variation descriptions for every fixed $\varepsilon < 1/4$ で継続する。 次の行程では、完全なハード・ド・インターベンショナル・オラクルは、いまだに$(n)$の反実的記述ギャップを残すことができる。 一般的なあいまいさ-ビット間の定理とシャノン類似定理は、これらのギャップが、下位項までの残余な高言語あいまいさの対数と等しいことを示している。

関連論文リスト

• Coherent Rollout Oracles for Finite-Horizon Sequential Decision Problems [0.0]
  逐次決定問題に対するコヒーレント量子ロールアウトには、ユニタリシミュレータが必要である。 枝依存の有効作用では、この写像は、絡み合った$N-bitマスク上のコヒーレントなランク選択である。 このプリミティブの最初の可逆・可逆的複雑性解析を行う。
  論文  参考訳（メタデータ） (2026-04-28T00:46:37Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Leave-One-Out Prediction for General Hypothesis Classes [9.855978207725549]
  本稿では,EMM周辺における経験的リスクレベルセットに基づく一般的な集約手法であるMLSA(Median of Level-Set Aggregation)を紹介する。 LOO_S(hath) ;le; C cdot frac1n min_hin H L_S(h) ;+; fracComp(S,
  論文  参考訳（メタデータ） (2026-03-02T16:27:44Z)
• On the Gradient Complexity of Private Optimization with Private Oracles [51.044364532408345]
  我々は,リプシッツ損失の個人的経験的/人口的リスクの1次オラクルクエリーの観点から,ランニング時間について検討した。 予測ランニングタイム$(minfracsqrtd2, fracdlog(1/))$は、$dgeq 1/2$のときの次元の問題に対して$$$過剰なリスクを達成するために必要であることを示す。
  論文  参考訳（メタデータ） (2025-11-17T23:58:11Z)
• The Mutual Information In The Vicinity of Capacity-Achieving Input Distributions [6.675805308519987]
  距離が$Pi_mathcalA$までの相互情報の最も遅い減少の正確な特徴は、$Pi_mathcalA$の小さな地区で決定される。 古典量子チャネルの結果は、二次境界に対して分離出力ヒルベルト空間仮定と、正確な特徴づけのために有限次元出力ヒルベルト空間仮定の下で確立される。
  論文  参考訳（メタデータ） (2023-04-27T14:27:08Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Leveraged Matrix Completion with Noise [84.20092979053119]
  未知の$ntimes n$ matrix of rank $r$ from just $mathcalO(nrlog2 (n))$ entry. 我々の証明は、ゴルフスキームに基づく十分な最適条件を記述する新しいアプローチによって支持されている。
  論文  参考訳（メタデータ） (2020-11-11T16:25:45Z)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。 我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。 一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
  論文  参考訳（メタデータ） (2020-06-07T14:47:07Z)

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

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