Neural Algorithmic Reasoning with Multiple Correct Solutions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916730419281920 |
|---|---|
| author | Kujawa, Zeno Poole, John Georgiev, Dobrik Numeroso, Danilo Fleischmann, Henry Liò, Pietro |
| author_facet | Kujawa, Zeno Poole, John Georgiev, Dobrik Numeroso, Danilo Fleischmann, Henry Liò, Pietro |
| contents | Neural Algorithmic Reasoning (NAR) extends classical algorithms to higher dimensional data. However, canonical implementations of NAR train neural networks to return only a single solution, even when there are multiple correct solutions to a problem, such as single-source shortest paths. For some applications, it is desirable to recover more than one correct solution. To that end, we give the first method for NAR with multiple solutions. We demonstrate our method on two classical algorithms: Bellman-Ford (BF) and Depth-First Search (DFS), favouring deeper insight into two algorithms over a broader survey of algorithms. This method involves generating appropriate training data as well as sampling and validating solutions from model output. Each step of our method, which can serve as a framework for neural algorithmic reasoning beyond the tasks presented in this paper, might be of independent interest to the field and our results represent the first attempt at this task in the NAR literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06953 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Neural Algorithmic Reasoning with Multiple Correct Solutions Kujawa, Zeno Poole, John Georgiev, Dobrik Numeroso, Danilo Fleischmann, Henry Liò, Pietro Machine Learning Artificial Intelligence Neural Algorithmic Reasoning (NAR) extends classical algorithms to higher dimensional data. However, canonical implementations of NAR train neural networks to return only a single solution, even when there are multiple correct solutions to a problem, such as single-source shortest paths. For some applications, it is desirable to recover more than one correct solution. To that end, we give the first method for NAR with multiple solutions. We demonstrate our method on two classical algorithms: Bellman-Ford (BF) and Depth-First Search (DFS), favouring deeper insight into two algorithms over a broader survey of algorithms. This method involves generating appropriate training data as well as sampling and validating solutions from model output. Each step of our method, which can serve as a framework for neural algorithmic reasoning beyond the tasks presented in this paper, might be of independent interest to the field and our results represent the first attempt at this task in the NAR literature. |
| title | Neural Algorithmic Reasoning with Multiple Correct Solutions |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2409.06953 |