We propose ordering-based approaches for learning the maximal ancestral graph (MAG) of a structural equation model (SEM) up to its Markov equivalence class (MEC) in the presence of unobserved variables. Existing ordering-based methods in the literature recover a graph through learning a causal order (c-order). We advocate for a novel order called removable order (r-order) as they are advantageous over c-orders for structure learning. This is because r-orders are the minimizers of an appropriately defined optimization problem that could be either solved exactly (using a reinforcement learning approach) or approximately (using a hill-climbing search). Moreover, the r-orders (unlike c-orders) are invariant among all the graphs in a MEC and include c-orders as a subset. Given that set of r-orders is often significantly larger than the set of c-orders, it is easier for the optimization problem to find an r-order instead of a c-order. We evaluate the performance and the scalability of our proposed approaches on both real-world and randomly generated networks.
翻译:我们建议采用基于命令的方法,在未观测到变量的情况下,学习直至其Markov等值类的结构等同模型的最大祖传图(MAG),在未观测到的变量面前学习。文献中现有的基于命令的方法通过学习因果顺序(c-order)恢复了一张图。我们主张采用名为可移动顺序(r-order)的新秩序,因为它们比结构学习的c-order更有利。这是因为r-ords是适当界定的优化问题的最小化因素,这一问题可以完全(使用强化学习方法)解决,或者大约(使用山坡搜索)解决。此外,r-ords(类似于c-orders)在MEC的所有图表中都是不易变的,并将c-ords作为一个子。鉴于这套r-ords往往大大大于c-ords,优化问题更容易找到r-ords而不是c-ords。我们评估了在现实世界和随机生成的网络上的拟议方法的性能和可扩展性。