Reinforcement Learning for Causal Discovery without Acyclicity Constraints

📄 arXiv: 2408.13448v4 📥 PDF

作者: Bao Duong, Hung Le, Biwei Huang, Thin Nguyen

分类: cs.LG, stat.ME, stat.ML

发布日期: 2024-08-24 (更新: 2025-05-30)

备注: Accepted at TMLR 04/2025

期刊: Transactions on Machine Learning Research (2025)

💡 一句话要点

ALIAS：一种无环约束的强化学习因果发现方法

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 因果发现 强化学习 有向无环图 策略梯度 无环约束

📋 核心要点

  1. 现有基于评分的因果发现方法在学习有向无环图（DAG）时，面临着复杂的无环约束，限制了对DAG空间的有效探索。
  2. ALIAS的核心思想是利用强化学习，并提出一种新颖的DAG参数化方法，将连续空间直接映射到DAG空间，从而避免显式无环约束。
  3. 实验结果表明，ALIAS在合成和真实数据集上，相比现有方法，在因果发现任务中表现出更强的性能。

📝 摘要（中文）

本文提出了一种名为ALIAS（reinforced dAg Learning wIthout Acyclicity conStraints）的全新因果发现方法，该方法利用强化学习机制。与传统基于评分的方法相比，ALIAS无需显式地强制执行无环约束，从而避免了在庞大的DAG空间中进行低效的探索。ALIAS通过一种新颖的DAG参数化方法，将连续空间直接映射到所有DAG的空间，实现了仅需一步即可生成DAG的高效策略，其复杂度为最优的二次复杂度。这种方法使得ALIAS能够利用策略梯度方法和已建立的评分函数，更有效地搜索空间。在合成和真实数据集上进行的实验结果表明，与最先进的因果发现方法相比，ALIAS在日益困难的实验条件下表现出强大的性能。

🔬 方法详解

问题定义：论文旨在解决从观测数据中学习有向无环图（DAG）的因果发现问题。现有基于评分的方法，例如使用局部启发式搜索，在搜索DAG空间时，需要显式地强制执行无环约束，这导致搜索效率低下，尤其是在DAG空间非常庞大时。因此，如何高效地探索DAG空间，同时避免复杂的无环约束，是该论文要解决的核心问题。

核心思路：ALIAS的核心思路是利用强化学习，学习一个策略，该策略能够直接从连续空间生成DAG，而无需显式地检查或强制执行无环约束。这种方法通过一种新颖的DAG参数化方法实现，该方法将连续空间直接映射到所有DAG的空间。

技术框架：ALIAS的整体框架包括以下几个主要部分：1) 状态表示：将观测数据编码为强化学习的状态；2) 策略网络：使用神经网络学习一个策略，该策略能够根据当前状态生成DAG的参数；3) DAG参数化：使用一种新颖的参数化方法，将策略网络输出的参数转换为DAG；4) 奖励函数：使用已建立的评分函数（例如，贝叶斯信息准则BIC）作为奖励函数，鼓励策略生成更符合数据的DAG；5) 策略优化：使用策略梯度方法优化策略网络，使其能够生成更好的DAG。

关键创新：ALIAS最重要的技术创新点在于其DAG参数化方法，该方法能够将连续空间直接映射到所有DAG的空间，而无需显式地强制执行无环约束。这与现有方法形成了本质区别，现有方法通常需要使用复杂的算法来保证生成的图是无环的。

关键设计：ALIAS的关键设计包括：1) DAG参数化方法的具体形式（论文中未明确给出，属于未知细节）；2) 策略网络的结构（例如，神经网络的层数、激活函数等）；3) 奖励函数的选择（例如，BIC、MDL等）；4) 策略梯度方法的选择（例如，REINFORCE、PPO等）；5) 训练过程中的超参数设置（例如，学习率、batch size等）。这些设计细节会影响ALIAS的性能，需要在实验中进行调整和优化。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，ALIAS在合成数据集和真实数据集上均优于现有的因果发现方法。具体来说，在某些数据集上，ALIAS能够显著提高因果发现的准确率，并且能够处理更大规模的数据集。这些结果表明，ALIAS是一种有竞争力的因果发现方法，具有很强的实际应用潜力。

🎯 应用场景

该研究成果可应用于多个领域，例如基因调控网络推断、社交网络分析、经济模型构建等。通过更准确地发现变量之间的因果关系，可以帮助人们更好地理解复杂系统，并做出更明智的决策。未来，该方法可以进一步扩展到处理更大规模的数据集和更复杂的因果结构，从而在更多实际应用中发挥作用。

📄 摘要（原文）

Recently, reinforcement learning (RL) has proved a promising alternative for conventional local heuristics in score-based approaches to learning directed acyclic causal graphs (DAGs) from observational data. However, the intricate acyclicity constraint still challenges the efficient exploration of the vast space of DAGs in existing methods. In this study, we introduce ALIAS (reinforced dAg Learning wIthout Acyclicity conStraints), a novel approach to causal discovery powered by the RL machinery. Our method features an efficient policy for generating DAGs in just a single step with an optimal quadratic complexity, fueled by a novel parametrization of DAGs that directly translates a continuous space to the space of all DAGs, bypassing the need for explicitly enforcing acyclicity constraints. This approach enables us to navigate the search space more effectively by utilizing policy gradient methods and established scoring functions. In addition, we provide compelling empirical evidence for the strong performance of ALIAS in comparison with state-of-the-arts in causal discovery over increasingly difficult experiment conditions on both synthetic and real datasets.