Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.01661 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916578773172224 |
|---|---|
| author | Piquenot, Jason Bérar, Maxime Héroux, Pierre Ramel, Jean-Yves Raveaux, Romain Adam, Sébastien |
| author_facet | Piquenot, Jason Bérar, Maxime Héroux, Pierre Ramel, Jean-Yves Raveaux, Romain Adam, Sébastien |
| contents | This paper presents Grammar Reinforcement Learning (GRL), a reinforcement learning algorithm that uses Monte Carlo Tree Search (MCTS) and a transformer architecture that models a Pushdown Automaton (PDA) within a context-free grammar (CFG) framework. Taking as use case the problem of efficiently counting paths and cycles in graphs, a key challenge in network analysis, computer science, biology, and social sciences, GRL discovers new matrix-based formulas for path/cycle counting that improve computational efficiency by factors of two to six w.r.t state-of-the-art approaches. Our contributions include: (i) a framework for generating gramformers that operate within a CFG, (ii) the development of GRL for optimizing formulas within grammatical structures, and (iii) the discovery of novel formulas for graph substructure counting, leading to significant computational improvements. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_01661 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Finding path and cycle counting formulae in graphs with Deep Reinforcement Learning Piquenot, Jason Bérar, Maxime Héroux, Pierre Ramel, Jean-Yves Raveaux, Romain Adam, Sébastien Artificial Intelligence Formal Languages and Automata Theory This paper presents Grammar Reinforcement Learning (GRL), a reinforcement learning algorithm that uses Monte Carlo Tree Search (MCTS) and a transformer architecture that models a Pushdown Automaton (PDA) within a context-free grammar (CFG) framework. Taking as use case the problem of efficiently counting paths and cycles in graphs, a key challenge in network analysis, computer science, biology, and social sciences, GRL discovers new matrix-based formulas for path/cycle counting that improve computational efficiency by factors of two to six w.r.t state-of-the-art approaches. Our contributions include: (i) a framework for generating gramformers that operate within a CFG, (ii) the development of GRL for optimizing formulas within grammatical structures, and (iii) the discovery of novel formulas for graph substructure counting, leading to significant computational improvements. |
| title | Finding path and cycle counting formulae in graphs with Deep Reinforcement Learning |
| topic | Artificial Intelligence Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2410.01661 |