arXiv:2410.16100cs.LGstat.ML2024-10

用扩展混合整数规划学动态贝叶斯网络,更准更快。

ExDBN: Learning Dynamic Bayesian Networks using Extended Mixed-Integer Programming Formulations

  • 用扩展混合整数规划建模,避免生成指数级环约束。
  • 在含80个时间序列的合成数据上准确率优于现有方法。
  • 适合生物科学与金融领域中小规模动态因果分析。

从数据中学习因果关系近年来备受关注。贝叶斯网络可用于捕捉因果关系,通过加权有向无环图表示随机变量及其之间的因果强度。该方法进一步扩展以捕捉动态效应,引入对历史数据的依赖,可通过结构方程模型实现。本文提出一种基于评分的学习算法,构建混合整数二次规划模型,并采用分支切割(“惰性约束”)方法避免预先生成指数级的无环约束。相比当前最优方法,在包含最多80个时间序列的小中型合成实例上,所提方法展现出更高的准确性。此外,将该方法直接应用于生物科学和金融领域的两个实际案例,凸显了开发高精度、全局收敛的求解器对处理中等规模实例的重要性。

原文摘要 · Abstract (English)

Causal learning from data has received much attention recently. Bayesian networks can be used to capture causal relationships. There, one recovers a weighted directed acyclic graph in which random variables are represented by vertices, and the weights associated with each edge represent the strengths of the causal relationships between them. This concept is extended to capture dynamic effects by introducing a dependency on past data, which may be captured by the structural equation model. This formalism is utilized in the present contribution to propose a score-based learning algorithm. A mixed-integer quadratic program is formulated and an algorithmic solution proposed, in which the pre-generation of exponentially many acyclicity constraints is avoided by utilizing the so-called branch-and-cut (``lazy constraint'') method. Comparing the novel approach to the state-of-the-art, we show that the proposed approach turns out to produce more accurate results when applied to small and medium-sized synthetic instances containing up to 80 time series. Lastly, two interesting applications in bioscience and finance, to which the method is directly applied, further stress the importance of developing highly accurate, globally convergent solvers that can handle instances of modest size.

贝叶斯网络动态建模优化算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。