Causal Discovery: Learning Causal Graphs from Data

Module: Machine Learning | Difficulty: Advanced

Causal Graph

Directed acyclic graph representing causal relationships.

PC Algorithm

1. Start with complete undirected graph
2. Remove edges based on conditional independence tests
3. Orient edges using v-structures and Meek rules

Score-Based (GES)

FCI Algorithm

Handles latent variables and selection bias.

Identifiability

import numpy as np
from scipy.stats import pearsonr

def conditional_independence_test(x, y, z, alpha=0.05):
    if len(z) == 0:
        corr, pval = pearsonr(x, y)
        return pval > alpha
    # Partial correlation
    from sklearn.linear_model import LinearRegression
    reg_x = LinearRegression().fit(z, x)
    reg_y = LinearRegression().fit(z, y)
    res_x = x - reg_x.predict(z)
    res_y = y - reg_y.predict(z)
    corr, pval = pearsonr(res_x, res_y)
    return pval > alpha

def pc_algorithm(data, alpha=0.05):
    n_vars = data.shape[1]
    adj_matrix = np.ones((n_vars, n_vars), dtype=bool)
    np.fill_diagonal(adj_matrix, False)
    for depth in range(n_vars):
        for i in range(n_vars):
            for j in range(n_vars):
                if not adj_matrix[i,j]: continue
                neighbors = np.where(adj_matrix[i] & (np.arange(n_vars) != i))[0]
                for subset in itertools.combinations(neighbors, depth):
                    z = data[:, list(subset)]
                    if conditional_independence_test(data[:,i], data[:,j], z, alpha):
                        adj_matrix[i,j] = adj_matrix[j,i] = False
    return adj_matrix

Research Insight: Causal discovery from observational data is possible under strong assumptions (faithfulness, causal sufficiency). The PC algorithm's complexity is exponential in the number of variables, making it impractical for high-dimensional data.