提出线性复杂度的近似核得分函数，加速因果发现
Fast Causal Discovery by Approximate Kernel-based Generalized Score Functions with Linear Computational Complexity
- 用低秩技术与规则优化复合矩阵运算，实现线性时间空间复杂度
- 在大规模数据上计算速度提升显著，准确率接近现有最优方法
- 适合处理多样数据类型的大规模因果推断任务
基于得分的因果发现方法通过评估候选图并选择得分最高的图来识别因果关系。其中一类流行的得分函数是基于核的广义得分函数，因其无需假设因果机制和数据分布，在实践中表现良好。然而，这类方法存在严重的时空计算挑战，时间复杂度为$/mathcal{O}(n^3)$，空间复杂度为$/mathcal{O}(n^2)$，其中$n$为样本量。本文提出一种近似核基广义得分函数，通过低秩技术与设计的一组规则处理复杂的复合矩阵运算，实现$/mathcal{O}(n)$的时间和空间复杂度，并开发了针对不同数据类型的采样算法以高效处理多样化数据。在合成与真实数据上的广泛实验表明，相比现有最先进方法，本方法不仅能显著降低计算成本，还能在大规模数据上保持相近的准确率。
原文摘要 · Abstract (English)
Score-based causal discovery methods can effectively identify causal relationships by evaluating candidate graphs and selecting the one with the highest score. One popular class of scores is kernel-based generalized score functions, which can adapt to a wide range of scenarios and work well in practice because they circumvent assumptions about causal mechanisms and data distributions. Despite these advantages, kernel-based generalized score functions pose serious computational challenges in time and space, with a time complexity of $\mathcal{O}(n^3)$ and a memory complexity of $\mathcal{O}(n^2)$, where $n$ is the sample size. In this paper, we propose an approximate kernel-based generalized score function with $\mathcal{O}(n)$ time and space complexities by using low-rank technique and designing a set of rules to handle the complex composite matrix operations required to calculate the score, as well as developing sampling algorithms for different data types to benefit the handling of diverse data types efficiently. Our extensive causal discovery experiments on both synthetic and real-world data demonstrate that compared to the state-of-the-art method, our method can not only significantly reduce computational costs, but also achieve comparable accuracy, especially for large datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。