論文の概要: Identification for Tree-shaped Structural Causal Models in Polynomial Time

• arxiv url: http://arxiv.org/abs/2311.14058v2
• Date: Tue, 5 Mar 2024 14:55:23 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-07 01:40:44.887862
• Title: Identification for Tree-shaped Structural Causal Models in Polynomial Time
• Title（参考訳）: 多項式時間における木型構造因果モデルの同定
• Authors: Aaryan Gupta and Markus Bl\"aser
• Abstract要約: ノード間の相関から因果パラメータを同定することは、人工知能におけるオープンな問題である。 本稿では,木を配向成分とするSCMについて検討する。 本稿では,木形SCMの同定問題を解くランダム時間アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 1.5151556900495786
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Linear structural causal models (SCMs) are used to express and analyse the relationships between random variables. Direct causal effects are represented as directed edges and confounding factors as bidirected edges. Identifying the causal parameters from correlations between the nodes is an open problem in artificial intelligence. In this paper, we study SCMs whose directed component forms a tree. Van der Zander et al. (AISTATS'22, PLMR 151, pp. 6770--6792, 2022) give a PSPACE-algorithm for the identification problem in this case, which is a significant improvement over the general Gr\"obner basis approach, which has doubly-exponential time complexity in the number of structural parameters. In this work, we present a randomized polynomial-time algorithm, which solves the identification problem for tree-shaped SCMs. For every structural parameter, our algorithms decides whether it is generically identifiable, generically 2-identifiable, or generically unidentifiable. (No other cases can occur.) In the first two cases, it provides one or two fractional affine square root terms of polynomials (FASTPs) for the corresponding parameter, respectively.
• Abstract（参考訳）: 線形構造因果モデル(SCM)は、確率変数間の関係を表現・解析するために用いられる。 直接因果効果は有向エッジとして表現され、結合因子は両向エッジとして表現される。 ノード間の相関から因果パラメータを同定することは、人工知能におけるオープンな問題である。 本稿では,木を配向成分とするSCMについて検討する。 Van der Zander et al. (AISTATS'22, PLMR 151, pp. 6770--6792, 2022) は、この場合の同定問題に対する PSPACE-algorithm を与える。 本研究では,木形SCMの同定問題を解くランダム化多項式時間アルゴリズムを提案する。 すべての構造パラメータに対して、アルゴリズムは、汎用的に識別可能か、ジェネリックで2-識別可能か、ジェネリックで識別不能かを決定する。 (他にはあり得ない。) 最初の2つのケースでは、対応するパラメータに対して多項式の1つまたは2つの分数アフィン平方根項(FASTP)を提供する。

関連論文リスト

• On the Complexity of Identification in Linear Structural Causal Models [3.44747819522562]
  空間内で動作するジェネリック識別のための,新しい音響および完全アルゴリズムを提案する。 また,同定が一般に困難であることを示す。
  論文  参考訳（メタデータ） (2024-07-17T13:11:26Z)
• Standardizing Structural Causal Models [80.21199731817698]
  ベンチマークアルゴリズムのための内部標準構造因果モデル(iSCM)を提案する。 構成上、iSCMは$operatornameVar$-sortableではなく、実験的に示すように、$operatornameR2$-sortableではない。
  論文  参考訳（メタデータ） (2024-06-17T14:52:21Z)
• iSCAN: Identifying Causal Mechanism Shifts among Nonlinear Additive Noise Models [48.33685559041322]
  本稿では,同一変数集合上の2つ以上の関連するデータセットにおける因果メカニズムシフトの同定に焦点をあてる。 提案手法を実装したコードはオープンソースであり、https://github.com/kevinsbello/iSCAN.comで公開されている。
  論文  参考訳（メタデータ） (2023-06-30T01:48:11Z)
• Latent Hierarchical Causal Structure Discovery with Rank Constraints [19.61598654735681]
  我々は、いくつかの変数が潜伏し、階層的なグラフ構造を形成する因果構造同定のための挑戦的なシナリオを考える。 本稿では,潜伏変数を効率よく検出し,その濃度を判定し,潜伏階層構造を同定する推定手法を提案する。
  論文  参考訳（メタデータ） (2022-10-01T03:27:54Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  因果構造を学習することは、通常、スコアまたは独立テストを使用して構造を評価することを伴う探索問題を引き起こす。 本研究では,観測・干渉データから因果構造を予測するため,変分推論モデルを訓練する。 我々のモデルは、実質的な分布シフトの下で頑健な一般化能力を示す。
  論文  参考訳（メタデータ） (2022-05-25T17:37:08Z)
• Identification in Tree-shaped Linear Structural Causal Models [4.751074059099236]
  そこで本研究では,有向成分が木を形成するモデルについて検討し,二方向エッジの欠落サイクルがモデル同定に有効であることを示す。 複数の欠落したサイクルが組み合わさってユニークな解が得られることを示す。
  論文  参考訳（メタデータ） (2022-03-03T16:59:49Z)
• Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
  Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。 RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。 我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
  論文  参考訳（メタデータ） (2021-06-02T01:37:52Z)
• Parameterized Complexity of Logic-Based Argumentation in Schaefer's Framework [1.5469452301122177]
  以下の3つの計算タスクの命題的変種を議論の中で検討する。 ARG-Checkは複雑性クラスDPに対して完全であり、他の2つの問題は階層の2番目のレベルで完全であることが知られている。 いくつかの症例は非常に難治性が高い(paranp以降)
  論文  参考訳（メタデータ） (2021-02-23T16:34:42Z)
• SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples [75.32013242448151]
  ノードからの観測が独立しているが非識別的に分散ノイズによって破損した場合、Ising Treeモデルの学習を検討する。 Katiyarら。 (2020) は, 正確な木構造は復元できないが, 部分木構造を復元できることを示した。 統計的に堅牢な部分木回復アルゴリズムであるSymmetrized Geometric Averaging(SGA)を提案する。
  論文  参考訳（メタデータ） (2021-01-22T01:57:35Z)
• Convex Polytope Trees [57.56078843831244]
  コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。 木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
  論文  参考訳（メタデータ） (2020-10-21T19:38:57Z)
• Robust Estimation of Tree Structured Ising Models [20.224160348675422]
  我々は、異なる確率変数の符号が、おそらく不等で未知の確率で独立に反転するときに、イジングモデルを学習するタスクを考える。 しかし, この不同一性は, 葉ノードが近傍と位置を交換して形成する小さな同値類に限られる。
  論文  参考訳（メタデータ） (2020-06-10T01:32:45Z)

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

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