Identification for Tree-shaped Structural Causal Models in Polynomial Time
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Identification in Tree-shaped Linear Structural Causal Models
Linear structural equation models represent direct causal effects as directed edges and confounding factors as bidirected edges. An open problem is to identify the causal parameters from correlations between the nodes. W…
Efficient Identification in Linear Structural Causal Models with Auxiliary Cutsets
We develop a a new polynomial-time algorithm for identification in linear Structural Causal Models that subsumes previous non-exponential identification methods when applied to direct effects, and unifies several dispara…
SERE: Structural Example Retrieval for Enhancing LLMs in Event Causality Identification
Event Causality Identification (ECI) requires models to determine whether a given pair of events in a context exhibits a causal relationship. While Large Language Models (LLMs) have demonstrated strong performance across…
Few-Shot LearningOn the Complexity of Identification in Linear Structural Causal Models
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 c…
Efficient Identification in Linear Structural Causal Models with Instrumental Cutsets
One of the most common mistakes made when performing data analysis is attributing causal meaning to regression coefficients. Formally, a causal effect can only be computed if it is identifiable from a combination of obse…