Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914001160503296 |
|---|---|
| author | Shikuri, Yuta |
| author_facet | Shikuri, Yuta |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2006_06926 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network Shikuri, Yuta Machine Learning 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. |
| title | Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2006.06926 |