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 paper proposes to combine several smaller, pretrained RBMs into a larger model as a way to solve combinatorial optimization problems. Results are presented on RBMs trained to implement binary addition, multiplication, and factorization, where the proposed approach is compared with the baseline of training a full model from scratch.
I found the paper confusing at times. It is well-written from a syntactical and grammatical point of view, but some key concepts are stated without being explained, which gives the impression that the authors have a clear understanding of the material presented in the paper but communicate only part of the full picture to the reader.
For instance, there’s a brief exposition of the connection between Boltzmann machines and combinatorial optimization problems: the latter is mapped onto the former by expressing constraints as a fixed set of Boltzmann machine weights and biases, and low-energy states (i.e. more optimal solutions) are found by sampling from the model, which involves no training. What’s less clear to me is what kinds of combinatorial optimization problems can be mapped onto the RBM *training* problem. The paper states that the problem of training "large modules" is "equivalent to solving the optimization problem", but does not explain how.
Similarly, the paper mentions that the "general approach to solving these combinatorial optimization problems is to recognize the atomic unit necessary to solve the problem", but at that point the reader has no concrete example of what combinatorial optimization problem would be mapped onto training and inference in RBMS.
A concrete example is provided in the Experiments section: the authors propose to implement invertible (reversible?) boolean logic circuits by combining smaller pre-trained RBMs which implement certain logical operations into larger circuits. I have two issues with the chosen example: 1) the connection with combinatorial optimization is not clear to me, and 2) it’s not very well explained. As far as I understand, these reversible boolean logic operations are expressed as sampling a subset of the RBM’s inputs conditioned on another subset of its inputs. An example is presented in Figure 3 but is not expanded upon in the main text. I’d like the authors to validate my understanding:
An RBM is trained to implement a complete binary adder circuit by having it model the joint distribution of the adder’s inputs and outputs [A, B, Cin, S, Cout] (A is the first input bit, B is the second input bit, Cin is the input carry bit, S is the output sum bit, and Cout is the output carry bit), where (I assume) the distribution over [A, B, Cin] is uniform, and where S and Cout follow deterministically from [A, B, Cin]. After training, the output of the circuit is computed from [A, B, Cin] by clamping [A, B, Cin] and sampling [S, Cout] given [A, B, Cin] using Gibbs sampling.
The alternative to this, which is examined in the paper, is to train individual XOR, AND, and OR gates in the same way and compose them into a complete binary adder circuit as prescribed by Section 3.
I think the paper has the potential to be a lot more transparent to the reader in explaining these concepts, which would avoid them spending quite a bit of time inferring meaning from figures.
I’m also confused by the presentation of the results. For instance, I don’t know what "log", "FA1", "FA2", etc. refer to in Figure 6. Also, Figure 6 is referenced in the text in the context of binary multiplication ("[...] is able to outperform a multiplier created just by training, as can be seen in Figure 6"), but presents results for addition and factorization only.
The way I see it, implementing reversible boolean logic circuits using RBMs is an artificial problem, and the key idea of the paper -- which I find interesting -- is that in some cases it appears to be possible to combine RBMs trained for sub-problems into larger RBMs without needing to fine-tune the model. I think there are interesting large-scale applications of this, such as building an autoregressive RBM for image generation by training a smaller RBM on a more restricted inpainting task. The connection to combinatorial optimization, however, is much less clear to me.