Integer programming for learning directed acyclic graphs from nonidentifiable Gaussian models
针对线性高斯结构方程模型中的有向无环图学习问题，提出一种混合整数规划框架，能处理任意异方差噪声并保证渐近最优解，数值实验表明其优于现有方法。
We study the problem of learning directed acyclic graphs from continuous observational data, generated according to a linear Gaussian structural equation model. State-of-the-art structure learning methods for this setting have at least one of the following shortcomings: (i) they cannot provide optimality guarantees and can suffer from learning suboptimal models; (ii) they rely on the stringent assumption that the noise is homoscedastic, and hence the underlying model is fully identifiable. We overcome these shortcomings and develop a computationally efficient mixed-integer programming framework for learning medium-sized problems that accounts for arbitrary heteroscedastic noise. We present an early stopping criterion under which we can terminate the branch-and-bound procedure to achieve an asymptotically optimal solution and establish the consistency of this approximate solution. In addition, we show via numerical experiments that our method outperforms state-of-the-art algorithms and is robust to noise heteroscedasticity, whereas the performance of some competing methods deteriorates under strong violations of the identifiability assumption. The software implementation of our method is available as the Python package micodag.