Combining Learned Representations for Combinatorial Optimization

We propose a new approach to combine Restricted Boltzmann Machines (RBMs) that can be used to solve combinatorial optimization problems. This allows synthesis of larger models from smaller RBMs that have been pretrained, thus effectively bypassing the problem of learning in large RBMs, and creating a system able to model a large, complex multi-modal space. We validate this approach by using learned representations to create "invertible boolean logic", where we can use Markov chain Monte Carlo (MCMC) approaches to find the solution to large scale boolean satisfiability problems and show viability towards other combinatorial optimization problems. Using this method, we are able to solve 64 bit addition based problems, as well as factorize 16 bit numbers. We find that these combined representations can provide a more accurate result for the same sample size as compared to a fully trained model. The Ising Problem has long been known to be in the class of NP-Hard problems, with no exact polynomial solution existing. Because of this, a large class of combinatorial optimization problems can be reformulated as Ising problems and solved by finding the ground state of that system (Barahona, 1982; Kirkpatrick et al., 1983; Lucas, 2014). The Boltzmann Machine (Ackley et al., 1987) was originally introduced as a constraint satisfaction network based on the Ising model problem, where the weights would encode some global constraints, and stochastic units were used to escape local minima. The original Boltzmann Machine found favor as a method to solve various combinatorial optimization problems (Korst & Aarts, 1989). However, learning was very slow with this model due to the difficulties with sampling and convergence, as well as the inability to exactly calculate the partition function.