Paper ID: 2006.06926 • Published Jun 12, 2020
Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network
Yuta Shikuri
TL;DR
Get AI-generated summaries with premium
Get AI-generated summaries with premium
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 fewer binary variables than
quadratization by orders of magnitude. Moreover, an annealing machine that
implement our formulation have outperformed existing algorithms in score
maximization.