PDF(Pubmed)
Abstract：
Bayesian Networks (BNs) represent conditional probability relations among a set of random variables (nodes) in the form of a directed acyclic graph (DAG), and have found diverse applications in knowledge discovery. We study the problem of learning the sparse DAG structure of a BN from continuous observational data. The central problem can be modeled as a mixed-integer program with an objective function composed of a convex quadratic loss function and a regularization penalty subject to linear constraints. The optimal solution to this mathematical program is known to have desirable statistical properties under certain conditions. However, the state-of-the-art optimization solvers are not able to obtain provably optimal solutions to the existing mathematical formulations for medium-size problems within reasonable computational times. To address this difficulty, we tackle the problem from both computational and statistical perspectives. On the one hand, we propose a concrete early stopping criterion to terminate the branch-and-bound process in order to obtain a near-optimal solution to the mixed-integer program, and establish the consistency of this approximate solution. On the other hand, we improve the existing formulations by replacing the linear \"big- M \" constraints that represent the relationship between the continuous and binary indicator variables with second-order conic constraints. Our numerical results demonstrate the effectiveness of the proposed approaches.
摘要：
贝叶斯网络（BNs）以有向无环图（DAG）的形式表示一组随机变量（节点）之间的条件概率关系，并在知识发现中发现了不同的应用。我们研究了从连续观测数据中学习BN的稀疏DAG结构的问题。中心问题可以建模为混合整数程序，其目标函数由凸二次损失函数和受线性约束的正则化惩罚组成。已知此数学程序的最佳解决方案在某些条件下具有所需的统计特性。然而,最先进的优化求解器无法在合理的计算时间内为中等尺寸问题的现有数学公式获得可证明的最佳解决方案。为了解决这个困难，我们从计算和统计的角度来解决这个问题。一方面,我们提出了一个具体的提前停止准则来终止分支定界过程，以获得混合整数程序的近似最优解，并建立此近似解的一致性。另一方面,我们通过用二阶圆锥约束代替表示连续和二元指标变量之间关系的线性“big-M”约束来改进现有公式。我们的数值结果证明了所提出方法的有效性。
