Learning selection strategies in Buchberger's algorithm
Learning selection strategies in Buchberger's algorithm
复制标题
DOI：
--
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Dylan Peifer;M. Stillman;Daniel Halpern-Leistner
中科院分区：
文献类型：
--
作者：
Dylan Peifer;M. Stillman;Daniel Halpern-Leistner
研究多项式方程组的精确解集在很大程度上依赖于一个迭代算法，即Buchberger算法。该算法的优化版本对于许多计算机代数系统（例如，Mathematica, Maple, Sage）至关重要。我们为Buchberger的算法引入了一种新方法，该方法使用强化学习代理来执行s对选择，这是算法的关键步骤。然后，我们研究了问题的难度如何取决于多项式的定义域和分布的选择，关于这一点我们知之甚少。最后，我们使用近端策略优化（PPO）训练策略模型来学习二项式方程随机系统的s对选择策略。在某些领域，经过训练的模型在执行的多项式加法总数上优于最先进的选择启发式，这提供了一个概念证明，即机器学习的最新发展有可能提高符号计算算法的性能。
Studying the set of exact solutions of a system of polynomial equations largely depends on a single iterative algorithm, known as Buchberger's algorithm. Optimized versions of this algorithm are crucial for many computer algebra systems (e.g., Mathematica, Maple, Sage). We introduce a new approach to Buchberger's algorithm that uses reinforcement learning agents to perform S-pair selection, a key step in the algorithm. We then study how the difficulty of the problem depends on the choices of domain and distribution of polynomials, about which little is known. Finally, we train a policy model using proximal policy optimization (PPO) to learn S-pair selection strategies for random systems of binomial equations. In certain domains, the trained model outperforms state-of-the-art selection heuristics in total number of polynomial additions performed, which provides a proof-of-concept that recent developments in machine learning have the potential to improve performance of algorithms in symbolic computation.