Reproduce “On the use of associative memory in Hopfield networks designed to solve propositional satisfiability problems” on OpenResearch

About this paper

Natalya Weber, Werner Koch, Ozan Erdem, Tom Froese

Researchers at the Okinawa Institute of Science and Technology Graduate University and independent scholars demonstrated a method for applying the Self-Optimization (SO) model, based on Hopfield networks, to propositional satisfiability (SAT) problems by converting logical formulas into network weights. The study revealed that Hebbian learning can significantly alter the network's energy landscape, occasionally leading to a "loss of critical information" where easily fixable constraint violations become stable states.

Key insights

• The inherent structure of a SAT problem greatly influences the SO model's performance; highly structured problems converge faster and require much lower learning rates compared to unstructured problems.
• For inherently unsolvable SAT problems, the SO model finds minimized non-zero energy states that represent the 'optimal' achievable solution under the given constraints, and external weighting can explicitly guide constraint prioritization.
• Aggressive Hebbian learning can profoundly modify the Hopfield network's energy landscape, leading to a "loss of critical information" where states with trivially fixable constraint violations become robust local minima, effectively erasing the original constraint from the learned network.

Summary by alphaXiv.