Reliable and Efficient Anytime Skeleton Learning

Authors

  • Rui Ding Microsoft Research
  • Yanzhi Liu Beijing University of Posts and Telecommunications
  • Jingjing Tian Peking University
  • Zhouyu Fu Alibaba Group
  • Shi Han Microsoft Research
  • Dongmei Zhang Microsoft Research

DOI:

https://doi.org/10.1609/aaai.v34i06.6569

Abstract

Skeleton Learning (SL) is the task for learning an undirected graph from the input data that captures their dependency relations. SL plays a pivotal role in causal learning and has attracted growing attention in the research community lately. Due to the high time complexity, anytime SL has emerged which learns a skeleton incrementally and improves it overtime. In this paper, we first propose and advocate the reliability requirement for anytime SL to be practically useful. Reliability requires the intermediately learned skeleton to have precision and persistency. We also present REAL, a novel Reliable and Efficient Anytime Learning algorithm of skeleton. Specifically, we point out that the commonly existing Functional Dependency (FD) among variables could make the learned skeleton violate faithfulness assumption, thus we propose a theory to resolve such incompatibility. Based on this, REAL conducts SL on a reduced set of variables with guaranteed correctness thus drastically improves efficiency. Furthermore, it employs a novel edge-insertion and best-first strategy in anytime fashion for skeleton growing to achieve high reliability and efficiency. We prove that the skeleton learned by REAL converges to the correct skeleton under standard assumptions. Thorough experiments were conducted on both benchmark and real-world datasets demonstrate that REAL significantly outperforms the other state-of-the-art algorithms.

Downloads

Published

2020-04-03

How to Cite

Ding, R., Liu, Y., Tian, J., Fu, Z., Han, S., & Zhang, D. (2020). Reliable and Efficient Anytime Skeleton Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06), 10101-10109. https://doi.org/10.1609/aaai.v34i06.6569

Issue

Section

AAAI Technical Track: Reasoning under Uncertainty