CAM: Causal additive models, high-dimensional order search and penalized regression

Peter Bühlmann; Jonas Peters; Jan Ernest

Source-linked AI summary

CAM: Causal additive models, high-dimensional order search and penalized regression

Peter Bühlmann, Jonas Peters, Jan Ernest

arXiv:1310.1533v2Oct 6, 2013stat.MEcs.LGstat.ML

TL;DR

The paper studies estimation and structure learning for potentially high-dimensional additive structural equation models, where causal structure learning faces computational and identifiability challenges. It separates order search from edge selection, using nonregularized or restricted maximum likelihood for the former and sparse regression for the latter. The resulting estimators have low- and high-dimensional consistency guarantees, support misspecified error distributions, and are implemented in an algorithm evaluated on simulated and real data.

Problem
Causal structure learning is challenged by identifiability issues and a model space growing super-exponentially with the number of variables, while existing additive-model approaches may be limited in dimension or computational feasibility.
Method
The method estimates variable order with nonregularized or restricted maximum likelihood, then performs feature selection and additive-function estimation using sparse regression.
Results
The paper establishes consistency in low- and high-dimensional settings, allows misspecified error distributions, and develops an efficient algorithm whose performance is illustrated on simulated and real data.
Takeaways & Limitations
Decoupling order estimation from regularized feature selection substantially simplifies structure search and estimation for identifiable causal additive models.

Abstract

from arXiv · show

We develop estimation for potentially high-dimensional additive structural equation models. A key component of our approach is to decouple order search among the variables from feature or edge selection in a directed acyclic graph encoding the causal structure. We show that the former can be done with nonregularized (restricted) maximum likelihood estimation while the latter can be efficiently addressed using sparse regression techniques. Thus, we substantially simplify the problem of structure search and estimation for an important class of causal models. We establish consistency of the (restricted) maximum likelihood estimator for low- and high-dimensional scenarios, and we also allow for misspecification of the error distribution. Furthermore, we develop an efficient computational algorithm which can deal with many variables, and the new method's accuracy and performance is illustrated on simulated and real data.

1. Introduction.

The paper addresses causal structure learning in additive structural equation models by separating variable-order estimation from feature selection. It combines maximum likelihood for order search with sparse regression for edge selection, targeting identifiable low- and high-dimensional settings.

Problem: Causal structure learning is difficult because model spaces grow super-exponentially with the number of variables, creating computational and statistical challenges.The paper also notes identifiability issues when prior structural information is absent.
Model: The model class consists of additive structural equation models whose identifiable structure extends linear Gaussian models through nonlinear additive functions.The setup assumes observed variables and an acyclic causal DAG, while hidden variables and cycles are discussed as extensions.
Method: The method decouples order search from feature selection: nonregularized or restricted maximum likelihood estimates the order, while sparse regression selects edges and estimates additive functions.In high-dimensional settings, preliminary neighborhood selection restricts the order search before sparse additive regression.
Theory and scope: The approach develops consistency results for low- and high-dimensional restricted maximum likelihood and accommodates misspecified error distributions.The paper presents this as an extension beyond approaches limited to small dimensions or fixed error specifications.
Computation and evaluation: The authors provide an efficient algorithm for many variables and illustrate its accuracy and performance on simulated and real data.The computational procedure uses IncEdge for order estimation and Prune for feature selection.

2. Additive structural equation models.

The paper studies additive structural equation models whose nonlinear functions can identify the causal DAG under suitable conditions, while linear-Gaussian models generally identify only a Markov equivalence class. It uses identifiable orderings to support likelihood-based estimation and intervention-distribution estimation.

Model formulation: Additive SEMs represent each variable through parent-specific smooth functions and an error term, with directed edges corresponding to nonzero additive functions.The model is a structured alternative to fully multivariate functions, whose estimation can suffer from the curse of dimensionality.
Identifiability: When all additive functions are nonlinear and sufficiently smooth, the DAG and its active set are identifiable from the observational distribution.A different DAG with nonconstant, three-times-differentiable functions generates a different distribution under the stated conditions.
Order estimation: Under suitable assumptions, the estimated ordering belongs to the set of true orderings with probability tending to one.The resulting complete super-DAG contains the true DAG and can support consistent estimation of intervention distributions without recovering the exact true DAG.
Identifiability: For linear Gaussian SEMs, arbitrary orderings admit lower-triangular representations, so only the Markov equivalence class is generally identifiable under faithfulness.Orderings consistent with a DAG in that equivalence class yield representations with the fewest nonzero coefficients.
Intervention estimation: Sparse regression or model selection can reduce the complete ordering-induced super-DAG to a smaller super-DAG, improving the statistical efficiency of estimated intervention distributions.The screening property holds under conditions such as compatibility and sufficiently large nonzero-function norms.
Intervention estimation: Estimated causal effects and intervention distributions remain consistently estimable from the estimated full super-DAG, although a smaller included super-DAG typically provides more efficient estimates.The paper assumes interventions leave the other structural equations unchanged and that there are no hidden variables.

3. Restricted maximum likelihood estimation: Computational and statistical benefits.

The method restricts permutation search using preliminary neighborhood selection, separating computationally difficult order estimation from sparse feature selection. Restricted maximum likelihood is both more tractable and statistically important when the number of variables exceeds the sample size.

Benefits: Restricting permutations makes maximum likelihood computation more tractable and is statistically crucial in high-dimensional settings where p > n.The restricted estimator is substantially easier to compute when the selected neighborhoods are small, as expected under sparse true neighborhoods.
Procedure: Under stated conditions, neighborhood selection produces sets containing the structural-equation parents, so restricting candidate regressors preserves the relevant variables.The containment property is written as ˆAj ⊇ pa(j).
Procedure: Restricted maximum likelihood searches only over permutations compatible with preliminary neighborhood-selection sets rather than over all permutations.Neighborhood selection uses additive regression of each variable against all others, with Group Lasso as a natural feature-selection method.
Computation: Permutation equivalence classes can further reduce the restricted likelihood search to one representative per class.The equivalence relation is formulated through the restricted DAG induced by each permutation.

4. Consistency in correct and misspecified models.

The paper establishes consistency for estimating variable order in additive structural equation models, including settings with misspecified error distributions and biased function estimation. High-dimensional consistency is obtained with restricted maximum likelihood under preliminary screening and additional assumptions.

Correctly specified models: Consistency holds for variable ordering under the stated additive structural equation model assumptions, without requiring feature or edge selection.The result establishes that a correct order can be found directly through likelihood-based estimation.
Near nonidentifiability: If ξp approaches zero in near-nonidentifiable models, consistency still holds when ξp ≫ n^-1/2.The condition addresses settings such as near linearity in Gaussian structural equation models.
Near nonidentifiability: Error variances approaching zero can create identifiability problems by making ξp close to zero.This provides a concrete failure boundary for the identifiability condition used in the consistency results.
Uniform convergence: Uniform convergence requires uniform bounds on tail and moment quantities, error variances, function approximation, and the identifiability quantity ξp.These conditions define the distribution class over which uniform convergence is obtained.
Misspecified models: Order estimation remains consistent with independent non-Gaussian errors and truncated function expansions using few basis functions.Theorem 2 explicitly covers potentially non-Gaussian errors and biased function estimation from limited basis expansions.
High-dimensional models: In high-dimensional settings with p ≫ n, restricted maximum likelihood is consistent under screening, sparsity, and related assumptions.The high-dimensional procedure first estimates supersets of parent sets before applying restricted likelihood estimation.

5. Computation and implementation.

The implementation separates order estimation from feature selection through IncEdge and Prune, with preliminary neighborhood selection supporting high-dimensional problems. Its modular steps use greedy likelihood gains, additive model fitting, and variable-selection methods.

Preliminary neighborhood selection: Preliminary neighborhood selection fits additive models against all other variables and retains variables repeatedly selected during boosting.The implementation keeps up to ten variables selected most often, requiring at least three selections in 100 boosting iterations.
IncEdge: IncEdge greedily adds the edge producing the largest gain in log-likelihood at each iteration.The procedure begins with an empty DAG and updates the candidate structure iteratively.
IncEdge: A score matrix records each edge’s reduction in negative log-likelihood, and only the affected node column needs recomputation after an edge is added.The score decomposes over nodes, while cycle avoidance removes further inadmissible edges.
High-dimensional implementation: With preliminary neighborhood selection, IncEdge considers only candidate parent relationships, making the algorithm feasible for up to a few thousand nodes.The initial sparsification reduces the score matrix before greedy order estimation.
Prune: Prune applies variable-selection techniques to remove nonrelevant edges from the DAG estimated by IncEdge.The implementation uses additive-model significance testing and declares covariates significant at p-values no greater than 0.001.
Prune: Pruning can substantially reduce structural Hamming distance while preserving correct estimated interventional distributions when the initial DAG is a super DAG of the true DAG.The paper also notes that alternative hypothesis-testing and penalized additive-model methods can replace the implementation used here.

6. Numerical results.

The numerical results evaluate the effectiveness of individual algorithmic steps and compare the complete procedure with state-of-the-art methods. They also examine noninjective functions, the linear Gaussian case, and robustness to model misspecification.

Evaluation: The experiments assess the effectiveness of each step in the proposed algorithm.
Evaluation: The complete procedure is compared with other state-of-the-art methods.
Additional analyses: Additional experiments investigate noninjective functions, the linear Gaussian case, and robustness to model misspecification.

6.1. Simulated data.

Simulations evaluate CAM’s accuracy, scalability, robustness to misspecification, and behavior on linear-Gaussian data. CAM generally outperforms competitors in identifiable nonlinear settings and remains competitive under several deviations from its assumptions.

Algorithmic steps: PNS substantially reduces computation time, while pruning reduces SHD but leaves SID almost unchanged.PNS is required when p > n to avoid degeneration of the score function.
Comparison to existing methods: 477±19 SHD is achieved by CAM at p = 1000 and n = 200, compared with 1214±37 for PC and 1330±40 for CPC.Only PC, CPC, and CAM scale to this high-dimensional setting.
Injective functions: CAM remains better than RESIT, LiNGAM, PC, CPC, and GES when injective sigmoid-type functions make edge directions harder to identify.Performance decreases relative to Gaussian-process functions, which are generally noninjective.
Linear Gaussian SEMs: CAM’s performance is comparable to competing methods in linear Gaussian SEMs after both estimated and true DAGs are expanded to CPDAGs.CAM is disadvantaged by using nonlinear rather than linear regression in this setting.
Misspecified models: The simulations include deviations from Gaussian noise and additivity, with γ = 1 denoting Gaussian noise and ω = 1 denoting the fully additive model.These experiments assess empirical performance under misspecified error distributions and functions.
Misspecified models: In sparse DAGs, CAM yields comparatively small SID under nonadditive functions, while performance worsens for nonsparse truths but remains slightly better than PC.PC’s average lower SID bounds are roughly 520 for both ω = 1 and ω = 0.

6.2. Real data.

CAM is applied to 39 genes from two Arabidopsis isoprenoid pathways and estimates a directed acyclic structure. Stability-selected edges connect genes within pathways and agree with their known overall directions.

Scoring: CAM’s twenty best-scoring edges provide the primary directed-edge ranking, and MCT →CMK is ranked 22nd rather than appearing among them.The scores should not be interpreted as p-values because the graph was estimated from data.
Stability selection: Stability selection identifies edges connecting genes within one of the two pathways, with directions agreeing with the pathways’ overall direction.Under suitable assumptions, the procedure yields an expected number of false positives below two.

7. Conclusions and extensions.

The paper concludes that CAM separates order search from edge selection, supporting scalable estimation for identifiable additive structural equation models. It establishes consistency in low- and high-dimensional settings, reports empirical accuracy, and identifies boundaries involving nonidentifiability, hidden variables, and cycles.

Conclusions: CAM decouples order search from feature or edge selection, using nonregularized maximum likelihood for the former and regularized regression for the latter.The approach is proposed for additive structural equation models with Gaussian errors and identifiable causal structure.
Conclusions: Consistency is established for restricted and unrestricted maximum likelihood estimators in low- and high-dimensional scenarios, with empirical evaluation on simulated and real data.The method also allows misspecification of the error distribution and uses an efficient computational algorithm.
Extensions: The estimation principle extends to other structural equation models when the underlying DAG is identifiable from the observational distribution.Examples include nonlinearly transformed additive models and Gaussian SEMs with equal error variances.
Limitations: When the DAG is nonidentifiable from the distribution, the methodology requires adaptation and regularized maximum likelihood may be needed for sparse solutions.Under faithfulness, the relevant orders correspond to the Markov equivalence class of the underlying DAG.
Extensions: Extending sparse permutation search to models with hidden variables or directed cycles remains an open direction, and CAMs are not closed under marginalization.The latter means marginalizing variables need not preserve the CAM class.