On the use of associative memory in Hopfield networks designed to solve propositional satisfiability problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916146046828544 |
|---|---|
| author | Weber, Natalya Koch, Werner Erdem, Ozan Froese, Tom |
| author_facet | Weber, Natalya Koch, Werner Erdem, Ozan Froese, Tom |
| contents | Hopfield networks are an attractive choice for solving many types of computational problems because they provide a biologically plausible mechanism. The Self-Optimization (SO) model adds to the Hopfield network by using a biologically founded Hebbian learning rule, in combination with repeated network resets to arbitrary initial states, for optimizing its own behavior towards some desirable goal state encoded in the network. In order to better understand that process, we demonstrate first that the SO model can solve concrete combinatorial problems in SAT form, using two examples of the Liars problem and the map coloring problem. In addition, we show how under some conditions critical information might get lost forever with the learned network producing seemingly optimal solutions that are in fact inappropriate for the problem it was tasked to solve. What appears to be an undesirable side-effect of the SO model, can provide insight into its process for solving intractable problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_16807 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the use of associative memory in Hopfield networks designed to solve propositional satisfiability problems Weber, Natalya Koch, Werner Erdem, Ozan Froese, Tom Adaptation and Self-Organizing Systems Artificial Intelligence Neurons and Cognition Hopfield networks are an attractive choice for solving many types of computational problems because they provide a biologically plausible mechanism. The Self-Optimization (SO) model adds to the Hopfield network by using a biologically founded Hebbian learning rule, in combination with repeated network resets to arbitrary initial states, for optimizing its own behavior towards some desirable goal state encoded in the network. In order to better understand that process, we demonstrate first that the SO model can solve concrete combinatorial problems in SAT form, using two examples of the Liars problem and the map coloring problem. In addition, we show how under some conditions critical information might get lost forever with the learned network producing seemingly optimal solutions that are in fact inappropriate for the problem it was tasked to solve. What appears to be an undesirable side-effect of the SO model, can provide insight into its process for solving intractable problems. |
| title | On the use of associative memory in Hopfield networks designed to solve propositional satisfiability problems |
| topic | Adaptation and Self-Organizing Systems Artificial Intelligence Neurons and Cognition |
| url | https://arxiv.org/abs/2307.16807 |