論文の概要: On the Complexity of Identification in Linear Structural Causal Models

• arxiv url: http://arxiv.org/abs/2407.12528v1
• Date: Wed, 17 Jul 2024 13:11:26 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-18 17:17:27.297438
• Title: On the Complexity of Identification in Linear Structural Causal Models
• Title（参考訳）: 線形構造因果モデルにおける同定の複雑さについて
• Authors: Julian Dörfler, Benito van der Zander, Markus Bläser, Maciej Liskiewicz,
• Abstract要約: 空間内で動作するジェネリック識別のための,新しい音響および完全アルゴリズムを提案する。 また,同定が一般に困難であることを示す。
• 参考スコア（独自算出の注目度）: 3.44747819522562
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning the unknown causal parameters of a linear structural causal model is a fundamental task in causal analysis. The task, known as the problem of identification, asks to estimate the parameters of the model from a combination of assumptions on the graphical structure of the model and observational data, represented as a non-causal covariance matrix. In this paper, we give a new sound and complete algorithm for generic identification which runs in polynomial space. By standard simulation results, this algorithm has exponential running time which vastly improves the state-of-the-art double exponential time method using a Gr\"obner basis approach. The paper also presents evidence that parameter identification is computationally hard in general. In particular, we prove, that the task asking whether, for a given feasible correlation matrix, there are exactly one or two or more parameter sets explaining the observed matrix, is hard for $\forall R$, the co-class of the existential theory of the reals. In particular, this problem is $coNP$-hard. To our best knowledge, this is the first hardness result for some notion of identifiability.
• Abstract（参考訳）: 線形構造因果モデルの未知因果パラメータを学習することは因果解析の基本的な課題である。 同定問題として知られるこのタスクは、モデルのグラフィカルな構造に関する仮定と、非因果共分散行列として表される観測データの組み合わせからモデルのパラメータを推定する。 本稿では,多項式空間で動作する一般化同定のための,新しい音響および完全アルゴリズムを提案する。 標準的なシミュレーション結果から,このアルゴリズムは,Gr\"オブナーベースアプローチを用いて,最先端の2次指数時間法を大幅に改善する指数実行時間を持つ。 また,パラメータ同定が一般に困難であることを示す。 特に、与えられた実現可能な相関行列に対して、観測された行列を説明するパラメータセットが1つ以上存在するかどうかを問うタスクは、実数の存在論的理論の共クラスである$\forall R$に対して難しいことを証明している。 特に、この問題は$coNP$-hardである。 私たちの知る限りでは、これは識別可能性の概念に対する最初の難しさの結果です。

関連論文リスト

• Parameter identification in linear non-Gaussian causal models under general confounding [8.273471398838533]
  このようなモデルが潜伏変数を含む場合の線形係数の同定について検討する。 我々の主な成果は、直接的な因果効果の一般的な識別可能性を決定するのに必要かつ十分であるグラフィカルな基準である。 同定結果に基づいて推定を報告し、フィードバックループを持つモデルへの一般化を探索し、因果グラフの識別可能性に関する新たな結果を提供する。
  論文  参考訳（メタデータ） (2024-05-31T14:39:14Z)
• Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models [2.0738462952016232]
  関数因果モデルに基づく手法は、ユニークなグラフを識別することができるが、次元性の呪いや強いパラメトリックな仮定を課すことに苦しむ。 本研究では,局所的な因果構造を利用した観測データにおけるグローバル因果発見のための新しいハイブリッド手法を提案する。 我々は, 合成データに対する実証的な検証を行い, 正確性および最悪の場合の時間複雑度を理論的に保証する。
  論文  参考訳（メタデータ） (2024-05-23T12:28:16Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Score-based Causal Representation Learning: Linear and General Transformations [31.786444957887472]
  本稿は、識別可能性と達成可能性の両方に対処する。 スコアに基づくアルゴリズムのクラスを設計し、識別性と達成性の両方を保証する。 結果は構造化された合成データと画像データの実験によって実証的に検証される。
  論文  参考訳（メタデータ） (2024-02-01T18:40:03Z)
• Identification for Tree-shaped Structural Causal Models in Polynomial Time [1.5151556900495786]
  ノード間の相関から因果パラメータを同定することは、人工知能におけるオープンな問題である。 本稿では,木を配向成分とするSCMについて検討する。 本稿では,木形SCMの同定問題を解くランダム時間アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-11-23T15:26:29Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  因果構造を学習することは、通常、スコアまたは独立テストを使用して構造を評価することを伴う探索問題を引き起こす。 本研究では,観測・干渉データから因果構造を予測するため,変分推論モデルを訓練する。 我々のモデルは、実質的な分布シフトの下で頑健な一般化能力を示す。
  論文  参考訳（メタデータ） (2022-05-25T17:37:08Z)
• Probabilistic Simplex Component Analysis [66.30587591100566]
  PRISMは、データ循環記述のシンプルさの頂点をデータから識別する確率論的シンプルコンポーネント分析手法である。 この問題には多様な応用があり、最も注目すべきはリモートセンシングにおけるハイパースペクトルアンミックスと機械学習における非負行列分解である。
  論文  参考訳（メタデータ） (2021-03-18T05:39:00Z)
• Disentangling Observed Causal Effects from Latent Confounders using Method of Moments [67.27068846108047]
  我々は、軽度の仮定の下で、識別性と学習可能性に関する保証を提供する。 我々は,線形制約付き結合テンソル分解に基づく効率的なアルゴリズムを開発し,スケーラブルで保証可能な解を得る。
  論文  参考訳（メタデータ） (2021-01-17T07:48:45Z)
• Causal Expectation-Maximisation [70.45873402967297]
  ポリツリーグラフを特徴とするモデルにおいても因果推論はNPハードであることを示す。 我々は因果EMアルゴリズムを導入し、分類的表現変数のデータから潜伏変数の不確かさを再構築する。 我々は、反事実境界が構造方程式の知識なしにしばしば計算できるというトレンドのアイデアには、目立たずの制限があるように思える。
  論文  参考訳（メタデータ） (2020-11-04T10:25:13Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  半パラメトリック指数族分布におけるパラメータの統計的推定問題として、両部グラフを考察し、その表現学習問題を定式化する。 提案手法は, 地中真理付近で強い凸性を示すため, 勾配降下法が線形収束率を達成できることを示す。 我々の推定器は指数族内の任意のモデル誤特定に対して頑健であり、広範な実験で検証されている。
  論文  参考訳（メタデータ） (2020-03-02T16:40:36Z)

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

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