用差分子模优化加速贝叶斯网络结构学习，提升大规模数据下的求解质量。
Inexact Column Generation for Bayesian Network Structure Learning via Difference-of-Submodular Optimization
- 将定价问题转化为差分子模优化，用非精确DCA求解以降低计算开销
- 在高密度图和大规模数据下，相比主流评分方法获得更优解
- 适合处理大规模贝叶斯网络结构学习，尤其在高密度场景中表现突出
本文研究基于评分的整数规划（IP）方法求解贝叶斯网络结构学习（BNSL）问题。现有先进BNSL IP模型面临变量与约束指数级增长的挑战。标准解法采用行生成与列生成技术动态构建问题，但复杂的定价问题仍是计算瓶颈。针对ℓ₀正则化似然评分，本文提出将定价问题重构为差分子模优化，并应用差分凸算法（DCA）作为非精确求解方法，高效处理该问题。实验表明，在连续高斯数据下，所提行-列生成方法在图密度较高时，解的质量显著优于当前主流评分方法；在图规模增大时，性能可媲美基准约束型与混合型方法。
原文摘要 · Abstract (English)
In this paper, we consider a score-based Integer Programming (IP) approach for solving the Bayesian Network Structure Learning (BNSL) problem. State-of-the-art BNSL IP formulations suffer from the exponentially large number of variables and constraints. A standard approach in IP to address such challenges is to employ row and column generation techniques, which dynamically generate rows and columns, while the complex pricing problem remains a computational bottleneck for BNSL. For the general class of $\ell_0$-penalized likelihood scores, we show how the pricing problem can be reformulated as a difference of submodular optimization problem, and how the Difference of Convex Algorithm (DCA) can be applied as an inexact method to efficiently solve the pricing problems. Empirically, we show that, for continuous Gaussian data, our row and column generation approach yields solutions with higher quality than state-of-the-art score-based approaches, especially when the graph density increases, and achieves comparable performance against benchmark constraint-based and hybrid approaches, even when the graph size increases.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。