Source-linked AI summary
DirectLiNGAM: A direct method for learning a linear non-Gaussian structural equation model
Shohei Shimizu, Takanori Inazumi, Yasuhiro Sogawa, Aapo Hyvarinen, Yoshinobu Kawahara, Takashi Washio, Patrik O. Hoyer, Kenneth Bollen
TL;DR
Existing covariance-based approaches often cannot identify the full causal structure, while ICA-based LiNGAM estimation relies on iterative search that may fail to converge. The paper proposes DirectLiNGAM, which estimates causal order through successive removal of independent components without algorithmic parameters. Under strict model assumptions, it converges to the right solution in a fixed number of steps and often shows better statistical performance than ICA-based estimation, although its computational cost can be higher.
Problem
Conventional linear acyclic models often cannot identify causal ordering and connection strengths from covariance structure without prior network knowledge, while ICA-based estimation may not converge reliably.
Method
DirectLiNGAM estimates causal ordering by successively removing independent components, then estimates connection strengths using conventional methods.
Results
DirectLiNGAM is guaranteed to converge to the right solution in a fixed number of steps under strict model assumptions and often provides better statistical performance than ICA-based estimation.
Takeaways & Limitations
The method provides a direct, parameter-free procedure for estimating LiNGAM structure, with promising results in simulations and real-world physics and sociology applications.
Takeaways & Limitations
DirectLiNGAM can have higher computational cost than ICA-LiNGAM, especially when the low-rank approximation is inefficient and M is large.
Abstract
from arXiv · showhide
Structural equation models and Bayesian networks have been widely used to analyze causal relations between continuous variables. In such frameworks, linear acyclic models are typically used to model the data-generating process of variables. Recently, it was shown that use of non-Gaussianity identifies the full structure of a linear acyclic model, i.e., a causal ordering of variables and their connection strengths, without using any prior knowledge on the network structure, which is not the case with conventional methods. However, existing estimation methods are based on iterative search algorithms and may not converge to a correct solution in a finite number of steps. In this paper, we propose a new direct method to estimate a causal ordering and connection strengths based on non-Gaussianity. In contrast to the previous methods, our algorithm requires no algorithmic parameters and is guaranteed to converge to the right solution within a small fixed number of steps if the data strictly follows the model.
1 Introduction
Causal discovery without controlled experiments is difficult because conventional covariance-based linear acyclic models often cannot identify the full structure. The paper introduces DirectLiNGAM, a direct non-Gaussian method that avoids iterative search and has fixed-step convergence under strict model assumptions.
- Controlled experiments are often ethically impossible or too expensive, motivating causal inference from observational data.
- Conventional linear acyclic models typically use covariance structure and often cannot identify causal ordering and connection strengths without prior network knowledge.
- LiNGAM uses non-Gaussianity to identify the full causal structure without pre-specifying a causal order.
- ICA-LiNGAM methods depend on iterative search and algorithmic parameters, creating risks of local optima or nonconvergence.These parameters include initial guesses, convergence criteria, and, for gradient methods, step sizes.
- DirectLiNGAM successively removes independent components to estimate causal order in a number of steps equal to the number of variables.It needs no initial guess or similar algorithmic parameters and is guaranteed to converge under strict model assumptions with infinite sample size.
- After causal ordering is identified, connection strengths can be estimated using conventional covariance-based methods such as least squares and maximum likelihood.
2 Background
LiNGAM models continuous variables with linear, acyclic relationships and independent non-Gaussian external influences, enabling identification of causal structure from observed data. Its ICA-based estimation resolves matrix indeterminacies but has parameter-selection, convergence, and scale-sensitivity issues.
- 2.1 A linear non-Gaussian acyclic model: LiNGAM: LiNGAM represents each variable as a linear function of earlier variables and an independent, non-Gaussian external influence.Acyclicity permits the adjacency matrix to be permuted into strictly lower-triangular form.
- 2.1 A linear non-Gaussian acyclic model: LiNGAM: An exogenous observed variable has no incoming directed edge from another observed variable and therefore equals its external influence in LiNGAM.At least one such variable exists under acyclicity and the no-latent-confounders assumption.
- 2.2 Identifiability of the model: ICA identifies the mixing matrix up to permutation, scaling, and sign, while LiNGAM constraints recover these indeterminacies and yield the connection-strength matrix B.The diagonal normalization of W=I−B resolves scaling and signs, after which B is computed as I−W.
- 2.3 ICA-LiNGAM algorithm: The ICA-LiNGAM procedure estimates A, normalizes the rows of the inverse matrix, computes B, and searches for a permutation close to strictly lower triangular.For higher-dimensional data, it sets the smallest absolute-valued elements to zero before testing permutability.
- 2.4 Potential problems of ICA-LiNGAM: ICA-based LiNGAM can fail to converge finitely when initialization or gradient step sizes are unsuitable, and its permutation procedures are not scale-invariant.Variable scales can change or misidentify the ordering, even though scales are irrelevant to the causal ordering.
3 A direct method: DirectLiNGAM
DirectLiNGAM identifies exogenous variables through non-Gaussian independence tests, removes their effects, and recursively preserves the causal ordering in residual data. The resulting procedure avoids iterative parameter search, while its computational cost can exceed ICA-LiNGAM when low-rank approximation is inefficient.
- Effect removal and recursion: The method removes an identified exogenous variable’s effects by least-squares regression, then applies the same identification logic to the residual vector.The residual vector satisfies a new LiNGAM with non-Gaussian, mutually independent error terms.
- Exogenous-variable identification: An exogenous variable is identified exactly when it is independent of every residual from regressing the other variables on it.For non-exogenous variables, at least one residual remains dependent because they share a non-Gaussian external influence.
- Effect removal and recursion: The residual variables retain the same causal ordering as the original observed variables after removing an exogenous variable’s effects.Deleting the corresponding row and column preserves the lower-triangular structure of the mixing matrix.
- Independence measurement: Kernel-based mutual information is used because least-squares residuals are uncorrelated with predictors but are not necessarily independent.The implementation estimates mutual information nonparametrically from Gram matrices and low-rank approximations.
- DirectLiNGAM algorithm: DirectLiNGAM estimates the causal ordering and connection strengths without initial guesses or comparable algorithmic parameters.Its ordering procedure repeatedly identifies exogenous variables and removes their effects rather than searching iteratively in parameter space.
- Computational complexity: DirectLiNGAM has known complexity and fixed-step convergence, but its computational cost can exceed ICA-LiNGAM when the low-rank rank M is large.The dominant ordering step has complexity O(np^3M^2+p^4M^3), while typical ICA algorithms lack guaranteed runtime and convergence.
4 Simulations
Simulations compared DirectLiNGAM and ICA-LiNGAM on sparse and dense networks across variable counts, sample sizes, and non-Gaussian distributions. DirectLiNGAM produced more accurate estimates, while prior knowledge generally improved accuracy and computational time, especially for dense networks.
- Simulation design: Five datasets were generated for each combination of p=10, 20, 50, 100 variables and n=500, 1000, 2000 samples in sparse networks.Additional datasets were generated for dense networks under the same combinations of p and n.
- Simulation design: The simulations used sparse and dense directed acyclic networks, randomly assigned connection strengths, and 18 non-Gaussian external-influence distributions.Observed variables followed the LiNGAM and were randomly permuted before estimation.
- Estimation accuracy: DirectLiNGAM achieved better Frobenius-norm distances than ICA-LiNGAM for all tested conditions.The experiments reported median distances over five replications.
- Computational cost: DirectLiNGAM required more computation than ICA-LiNGAM as sample size increased, with the kernel-based independence measure as a main bottleneck.The reported actual elapsed times were approximately one-quarter of the CPU times because the CPU had four cores.
- Estimation accuracy: Scatterplots showed DirectLiNGAM estimates grouped more closely around the true-value diagonal than ICA-LiNGAM estimates for sparse and dense networks.The comparison covered different variable counts, sample sizes, adjacency matrices, and 18 external-influence distributions.
- Prior knowledge: Using prior knowledge produced more accurate estimates and lower computational times in most cases, particularly for dense networks.Prior knowledge narrowed the search space by identifying directed paths or reducing the number of causal orders and connection strengths to estimate.
5 Applications to real-world data
DirectLiNGAM was applied to physics and sociology datasets, producing causal orderings and networks that generally aligned with domain knowledge and outperformed conventional comparisons in identifying directions. Its results also exposed assumption violations and differences from ICA-LiNGAM.
- Physical data: DirectLiNGAM and ICA-LiNGAM estimated identical causal orderings for the double-pendulum data.Their estimated connection strengths nevertheless differed substantially.
- Physical data: DirectLiNGAM recovered effects of θ1 and θ2 on angular speeds ω1 and ω2, consistent with domain knowledge.The estimated effect of θ1 on θ2 was negligible, with coefficient of determination 0.01.
- Physical data: ICA-LiNGAM found no significant directed edges in the double-pendulum data because its estimates varied across bootstrap samples.DirectLiNGAM identified significant total effects from θ1 and θ2 to several variables, whereas ICA-LiNGAM found only θ2 on ω2.
- Physical data: PC and GES recovered only parts of the physical-data structure and missed several directions identified by DirectLiNGAM.PC found θ1→ω1 but not θ2→ω2; GES found θ1→θ2 but not the angular-speed effects.
- Sociology data: In sociology data, nearly all DirectLiNGAM edges were reasonable under domain knowledge, with one mistaken direction between son’s education and father’s education.ICA-LiNGAM made an additional mistake, inferring that number of siblings was determined by son’s education.
- Sociology data: The sociology results suggest that some LiNGAM assumptions may be violated despite the large sample size.The authors specifically connect the incorrect education-direction estimate with possible model-assumption violations.
- Sociology data: PC and GES left many sociology edge directions unidentified and incorrectly oriented the relation between father’s occupation and son’s occupation.Both methods correctly oriented the relation between father’s occupation and father’s education.
6 Conclusion
The paper concludes that DirectLiNGAM provides fixed-step convergence and known computational complexity under strict model adherence, with promising simulation and real-world results. It identifies statistical-assumption testing and computational efficiency as future work.
- Conclusion: DirectLiNGAM is guaranteed to converge to the right solution in a fixed number of steps when data strictly follows LiNGAM.The method also has known computational complexity, unlike most ICA methods.
- Conclusion: Simulations suggested that DirectLiNGAM often achieved better statistical performance than a state-of-the-art ICA-based method.The conclusion reports promising results in physics and sociology applications.
- Conclusion: Future work includes assessing tests for violations of model assumptions and improving practical computational efficiency.The proposed directions include independence testing and implementation improvements.
A Adaptive Lasso
Adaptive Lasso is presented as a regularization method for selecting variables under the LiNGAM data-generating process, assuming the causal ordering of potential parents is known.
- A Adaptive Lasso: Adaptive Lasso is a variable-selection regularization technique that assumes the same data-generating process as LiNGAM.It penalizes connection strengths using an L1 penalty.
- A Adaptive Lasso: Unlike LiNGAM, Adaptive Lasso assumes that potential parent variables earlier in the causal order are already known.LiNGAM estimates this variable set instead.
- A Adaptive Lasso: Adaptive Lasso selects tuning parameters by five-fold cross-validation and obtains initial coefficient estimates by ordinary least squares regression.The cited work shows asymptotic selection of the nonzero parent-variable set.