School of Computer Science, Guangdong University of Technology, Guangzhou, China.
School of Computer Science, Guangdong University of Technology, Guangzhou, China; School of Mathematics and Big Data, Foshan University, Foshan, China.
Neural Netw. 2020 Apr;124:130-145. doi: 10.1016/j.neunet.2019.12.020. Epub 2020 Jan 7.
In recent years, Linear Non-Gaussian Acyclic Model (LiNGAM) has been widely used for the discovery of causal network. However, solutions based on LiNGAM usually yield high computational complexity as well as unsatisfied accuracy when the data is high-dimensional or the sample size is too small. Such complexity or accuracy problems here are often originated from their prior selection of root nodes when estimating a causal ordering. Thus, a causal discovery algorithm termed as GPL algorithm (the LiNGAM algorithm of Giving Priority to Leaf-nodes) under a mild assumption is proposed in this paper. It assigns priority to leaf nodes other than root nodes. Since leaf nodes do not affect others in a structure, we can directly estimate a causal ordering in a bottom-up way without performing additional operations like data updating process. Corresponding proofs for both feasibility and superiority are offered based on the properties of leaf nodes. Aside from theoretical analyses, practical experiments are conducted on both synthetic and real-world data, which confirm that GPL algorithm outperforms the other two state-of-the-art algorithms in computational complexity and accuracy, especially when dealing with high-dimensional data (up to 200) or small sample size (down to 100 for the dimension of 70).
近年来，线性非高斯无环模型（LiNGAM）已被广泛应用于因果网络的发现。然而，基于 LiNGAM 的解决方案通常在数据维度较高或样本量较小时会产生较高的计算复杂度和较差的准确性。这种复杂度或准确性问题通常源于在估计因果顺序时对根节点的预先选择。因此，本文提出了一种因果发现算法，称为 GPL 算法（优先考虑叶节点的 LiNGAM 算法），该算法在一个温和的假设下进行。它优先考虑叶节点而不是根节点。由于叶节点在结构中不会影响其他节点，因此我们可以直接自底向上估计因果顺序，而无需执行数据更新等额外操作。基于叶节点的性质，提供了相应的可行性和优越性的证明。除了理论分析外，还在合成数据和真实世界数据上进行了实际实验，结果表明 GPL 算法在计算复杂度和准确性方面优于其他两种最先进的算法，尤其是在处理高维数据（高达 200）或小样本量（维度为 70 时低至 100）时。
