Bayesian Network Structure Learning Using Quantum Annealing
arXiv:1407.3897 · doi:10.1140/epjst/e2015-02349-9
Abstract
We introduce a method for the problem of learning the structure of a Bayesian network using the quantum adiabatic algorithm. We do so by introducing an efficient reformulation of a standard posterior-probability scoring function on graphs as a pseudo-Boolean function, which is equivalent to a system of 2-body Ising spins, as well as suitable penalty terms for enforcing the constraints necessary for the reformulation; our proposed method requires qubits for Bayesian network variables. Furthermore, we prove lower bounds on the necessary weighting of these penalty terms. The logical structure resulting from the mapping has the appealing property that it is instance-independent for a given number of Bayesian network variables, as well as being independent of the number of data cases.
References in corpus (10)
- Data Analysis with Bayesian Networks: A Bootstrap Approach
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- A practical heuristic for finding graph minors
- On the construction of model Hamiltonians for adiabatic quantum computation and its application to finding low energy conformations of lattice protein models
- A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
- Bayesian network learning by compiling to weighted MAX-SAT
- On Quadratization of Pseudo-Boolean Functions
- An Introduction to Quantum Bayesian Networks for Mixed States
- Construction of non-convex polynomial loss functions for training a binary classifier with quantum annealing
- Quantum Circuit For Discovering from Data the Structure of Classical Bayesian Networks