论文标题
分解二次：学习贝叶斯网络的有效QUBO公式
Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network
论文作者
论文摘要
用于解决二次无约束二进制优化（QUBO）问题的算法和硬件已取得了重大进展。这种进步将注意力集中在制定组合优化问题作为二次多项式的组合问题上。为了提高解决较大的QUBO问题的性能，必须最大程度地减少目标函数中使用的二进制变量数量。在本文中，我们提出了一种QUBO公式，该QUBO公式比常规二次化技术具有一点容量的优势。作为关键应用，该公式大大减少了基于得分的贝叶斯网络结构学习所需的二进制变量数量。 $ 16 $实例的实验结果，范围从$ 37 $到$ 223 $变量，表明我们的方法所需的二进制变量要少于二等变量。此外，实施我们公式的退火计算机在得分最大化方面的表现优于现有算法。
Algorithms and hardware for solving quadratic unconstrained binary optimization (QUBO) problems have made significant recent progress. This advancement has focused attention on formulating combinatorial optimization problems as quadratic polynomials. To improve the performance of solving large QUBO problems, it is essential to minimize the number of binary variables used in the objective function. In this paper, we propose a QUBO formulation that offers a bit capacity advantage over conventional quadratization techniques. As a key application, this formulation significantly reduces the number of binary variables required for score-based Bayesian network structure learning. Experimental results on $16$ instances, ranging from $37$ to $223$ variables, demonstrate that our approach requires notably fewer binary variables than quadratization. Moreover, an annealing machine that implement our formulation have outperformed existing algorithms in score maximization.
