Replica Symmetry Breaking in Bipartite Spin Glasses and Neural Networks
  Some interesting recent advances in the theoretical understanding of neural
networks have been informed by results from the physics of disordered many-body
systems. Motivated by these findings, this work uses the replica technique to
study the mathematically tractable bipartite Sherrington-Kirkpatrick (SK) spin
glass model, which is formally similar to a Restricted Boltzmann Machine (RBM)
neural network. The bipartite SK model has been previously studied assuming
replica symmetry; here this assumption is relaxed and a replica symmetry
breaking analysis is performed. The bipartite SK model is found to have many
features in common with Parisi's solution of the original, unipartite SK model,
including the existence of a multitude of pure states which are related in a
hierarchical, ultrametric fashion. As an application of this analysis, the
optimal cost for a graph partitioning problem is shown to be simply related to
the ground state energy of the bipartite SK model. As a second application,
empirical investigations reveal that the Gibbs sampled outputs of an RBM
trained on the MNIST data set are more ultrametrically distributed than the
input data itself.
