Learning Sparse Causal Models is not NP-hard
원문 초록
This paper shows that causal model discovery is not an NP-hard problem, in the sense that for sparse graphs bounded by node degree k the sound and complete causal model can be obtained in worst case order N^{2(k+2)} independence tests, even when latent variables and selection bias may be present. We present a modification of the well-known FCI algorithm that implements the method for an independence oracle, and suggest improvements for sample/real-world data versions. It does not contradict any known hardness results, and does not solve an NP-hard problem: it just proves that sparse causal discovery is perhaps more complicated, but not as hard as learning minimal Bayesian networks.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
When Selection Meets Intervention: Additional Complexities in Causal Discovery
인과 기전 변화에서 구조적 바이어스 식별
Identifying Structural Biases from Causal Mechanism Shifts
인과 발견 방법들은 일반적으로 모든 데이터가 독립 동일 분포(i.i.d.)를 따른다고 가정하며, 시스템에 영향을 미치는 측정되지 않은 변수가 없다고 가정합니다. 실제로는 이러한 가정들이 종종 위반되어 부정확한 추론으로 이어집니다. 본 논문에서는 인과 기전 변화로부터 숨겨진 교란(confounding)과 선택 바이어스를 식별하는 방법을 연구합니다. 특히, 구조적 바이어스는 의존적인 기전 변화를 초래함을 보여줍니다. 즉, 서로 다른 환경의 데이터가 주어졌을 때 어떤 변수에 대해 기전이 변화하는지 고려함으로써, 어떤 변수가 편향되지 않았는지, 숨겨진 교란의 영향을 받는지, 아니면 선택 바이어스를 겪고 있는지 파악할 수 있습니다. 우리는 이를 상호 정보량에 기반한 경험적으로 테스트 가능한 기준으로 공식화하고, 어떤 조건 하에서 구조적 바이어스를 식별하는지 보여줍니다. 어떤 노드가 어떤 종류의 바이어스의 영향을 받는지 파악하기 위해 StruBI 알고리즘을 소개합니다. 합성 데이터와 실제 데이터에 대한 실험 결과, StruBI가 실제 환경에서도 잘 작동함을 보여주며, 영향을 받은 변수 집합과 바이어스 유형을 정확하게 복원하고 최신 성능(state-of-the-art)을 큰 폭으로 능가합니다.
잠재 변수를 가진 인과 구조의 관측적 부분 순서
The observational partial order of causal structures with latent variables
동일한 가시 변수(visible variable) 집합을 갖는 두 인과 구조에 대해, 첫 번째 구조로 실현 가능한 가시 변수 상의 분포 집합이 두 번째 구조로 실현 가능한 가시 변수 상의 분포 집합을 포함하면, 첫 번째 구조가 두 번째 구조를 관측적으로 지배(observationally dominate)한다고 한다. 이러한 지배 관계를 알면 관측 데이터가 주어졌을 때 이들 구조 중 어느 것이 적합한지 판별하는 데 유용하다. 본 연구에서는 잠재 변수(latent variable)를 가진 인과 구조의 동치류(equivalence class)들이 관측적 지배 관계에 대해 이루는 부분 순서를 결정하는 문제를 다룬다. 가시 변수가 세 개인 경우에는 지배 순서를 완전하게 규명하였고, 가시 변수가 네 개인 경우에는 부분적으로 규명하였다. 또한 우리의 기법은 어떤 관측적 동치류가 벨 부등식(Bell inequalities) 및 도구 부등식(instrumental inequalities)과 유사한 비자명한(nontrivial) 부등식 제약으로 실현 가능한 분포 집합이 특징지어지는지를 식별하는 데에도 도움이 된다. 가시 변수의 수가 늘어날수록 비자명한 부등식 제약을 만족하는 동치류가 어디에나 존재하게 된다는 증거를 발견하였다. (이러한 동치류는 양자적으로 실현 가능한 분포와 고전적으로 실현 가능한 분포 사이에 차이가 있을 수 있는 경우이므로, 이는 양자-고전 간극(quantum-classical gap)이 존재할 가능성 또한 어디에나 있음을 시사한다.) 나아가, 조건부 독립 제약에만 의존하는 제약 기반 인과 발견(causal discovery) 알고리즘은, 이를 넘어서는 알고리즘(즉, 중첩 마르코프(nested Markov) 제약과 부등식 제약도 함께 활용하는 알고리즘)에 비해 관측적 동치류를 구별하는 능력이 상당히 약하다는 증거도 발견하였다.
전문가 지식을 활용한 완전한 인과 설명을 향하여
Towards Complete Causal Explanation with Expert Knowledge
우리는 최대 조상 그래프(MAG)의 마르코프 동치류를 특정 엣지 마크를 포함하는 MAG로만 제한하는 문제를 연구하며, 이를 전문가 지식 또는 방향 지식이라 부른다. 이러한 마르코프 동치류의 제한은 제한된 필수 조상 그래프(restricted essential ancestral graph)로 유일하게 표현될 수 있다. 우리의 기여는 여러 측면에 걸쳐 있다. 첫째, Ali et al. (2009)의 추측을 포함하여 전체 마르코프 동치류에 대한 특정 성질들을 증명한다. 둘째, 필수 조상 그래프에 방향 지식을 추가하기 위한 새로운 건전한 그래프 방향화 규칙들을 제시한다. 또한 Zhang (2008b)의 일부 방향화 규칙은 방향 지식으로 마르코프 동치류를 제한하는 데 필요하지 않음을 보인다. 셋째, 이 방향 지식을 포함하는 알고리즘을 제공하고, 특정 조건 하에서 알고리즘의 출력이 제한된 필수 조상 그래프임을 보인다. 마지막으로, 명시된 조건 외의 경우에 대해 그래프가 제한된 필수 그래프인지 확인하는 알고리즘을 제공하고 그 실행 시간을 논의한다. 이 연구는 잠재적 교란(latent confounding)을 허용하는 환경으로 Meek (1995)를 일반화한 것으로 볼 수 있다.
LLM-Generated Feedback Supports Learning If Learners Choose to Use It
Paths to Causality: Finding Informative Subgraphs Within Knowledge Graphs for Knowledge-Based Causal Discovery
토론
이 논문과 연결된 포럼 글이 아직 없습니다.