Identification for Tree-shaped Structural Causal Models in Polynomial Time

• URL: http://arxiv.org/abs/2311.14058v2
• Date: Tue, 5 Mar 2024 14:55:23 GMT
• Title: Identification for Tree-shaped Structural Causal Models in Polynomial Time
• Authors: Aaryan Gupta and Markus Bl\"aser
• Abstract summary: Identifying causal parameters from correlations between nodes is an open problem in artificial intelligence. In this paper, we study SCMs whose directed component forms a tree. We present a randomized-time algorithm, which solves the identification problem for tree-shaped SCMs.
• Score: 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.

Related papers

• On the Complexity of Identification in Linear Structural Causal Models [3.44747819522562]
  We give a new sound and complete algorithm for generic identification which runs in space. The paper also presents evidence that identification is computationally hard in general.
  arXiv  Detail & Related papers  (2024-07-17T13:11:26Z)
• Standardizing Structural Causal Models [80.21199731817698]
  We propose internally-standardized structural causal models (iSCMs) for benchmarking algorithms. By construction, iSCMs are not $operatornameVar$-sortable, and as we show experimentally, not $operatornameR2$-sortable either for commonly-used graph families.
  arXiv  Detail & Related papers  (2024-06-17T14:52:21Z)
• iSCAN: Identifying Causal Mechanism Shifts among Nonlinear Additive Noise Models [48.33685559041322]
  This paper focuses on identifying the causal mechanism shifts in two or more related datasets over the same set of variables. Code implementing the proposed method is open-source and publicly available at https://github.com/kevinsbello/iSCAN.
  arXiv  Detail & Related papers  (2023-06-30T01:48:11Z)
• Latent Hierarchical Causal Structure Discovery with Rank Constraints [19.61598654735681]
  We consider a challenging scenario for causal structure identification, where some variables are latent and they form a hierarchical graph structure. We propose an estimation procedure that can efficiently locate latent variables, determine their cardinalities, and identify the latent hierarchical structure.
  arXiv  Detail & Related papers  (2022-10-01T03:27:54Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  Learning causal structure poses a search problem that typically involves evaluating structures using a score or independence test. We train a variational inference model to predict the causal structure from observational/interventional data. Our models exhibit robust generalization capabilities under substantial distribution shift.
  arXiv  Detail & Related papers  (2022-05-25T17:37:08Z)
• Identification in Tree-shaped Linear Structural Causal Models [4.751074059099236]
  We investigate models, whose directed component forms a tree, and show that missing cycles of bidirected edges can be used to identify the model. We show how multiple missing cycles can be combined to obtain a unique solution.
  arXiv  Detail & Related papers  (2022-03-03T16:59:49Z)
• Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
  We present the sample complexities of Recursive Grouping (RG) and Chow-Liu Recursive Grouping (CLRG) We robustify RG, CLRG, Neighbor Joining (NJ) and Spectral NJ (SNJ) by using the truncated inner product. We derive the first known instance-dependent impossibility result for structure learning of latent trees.
  arXiv  Detail & Related papers  (2021-06-02T01:37:52Z)
• Parameterized Complexity of Logic-Based Argumentation in Schaefer's Framework [1.5469452301122177]
  We study the propositional variants of the following three computational tasks studied in argumentation. ARG-Check is complete for the complexity class DP, and the other two problems are known to be complete for the second level of the hierarchy. Several cases are of very high intractability (paraNP and beyond)
  arXiv  Detail & Related papers  (2021-02-23T16:34:42Z)
• SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples [75.32013242448151]
  We consider learning Ising tree models when the observations from the nodes are corrupted by independent but non-identically distributed noise. Katiyar et al. (2020) showed that although the exact tree structure cannot be recovered, one can recover a partial tree structure. We propose Symmetrized Geometric Averaging (SGA), a more statistically robust algorithm for partial tree recovery.
  arXiv  Detail & Related papers  (2021-01-22T01:57:35Z)
• Convex Polytope Trees [57.56078843831244]
  convex polytope trees (CPT) are proposed to expand the family of decision trees by an interpretable generalization of their decision boundary. We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given.
  arXiv  Detail & Related papers  (2020-10-21T19:38:57Z)
• Robust Estimation of Tree Structured Ising Models [20.224160348675422]
  We consider the task of learning Ising models when the signs of different random variables are flipped independently with possibly unequal, unknown probabilities. We first prove that this problem is unidentifiable, however, this unidentifiability is limited to a small equivalence class of trees formed by leaf nodes exchanging positions with their neighbors.
  arXiv  Detail & Related papers  (2020-06-10T01:32:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.