Discovering faster matrix multiplication algorithms with reinforcement learning.
Discovering faster matrix multiplication algorithms with reinforcement learning.
复制标题
DOI：
10.1038/s41586-022-05172-4
复制
发表时间：
2022-10
期刊：
影响因子：
64.8
通讯作者：
Kohli, Pushmeet
中科院分区：
文献类型：
--
作者：
Fawzi, Alhussein;Balog, Matej;Huang, Aja;Hubert, Thomas;Romera-Paredes, Bernardino;Barekatain, Mohammadamin;Novikov, Alexander;Ruiz, Francisco J. R.;Schrittwieser, Julian;Swirszcz, Grzegorz;Silver, David;Hassabis, Demis;Kohli, Pushmeet
提高基础计算算法的效率可以产生广泛的影响，因为它可以影响大量计算的整体速度。矩阵乘法就是这样一个基本的任务，出现在许多系统中，从神经网络到科学计算程序。使用机器学习自动发现算法提供了超越人类直觉并超越当前最好的人类设计算法的前景。然而，自动化算法发现过程是复杂的，因为可能的算法的空间是巨大的。在这里，我们报告了一种基于AlphaZero的深度强化学习方法，用于发现任意矩阵乘法的有效且可证明正确的算法。我们的智能体AlphaTensor被训练来玩单人游戏，目标是在有限因子空间内找到张量分解。AlphaTensor发现了在许多矩阵大小下都优于最先进复杂度的算法。特别相关的是有限域中的4 × 4矩阵的情况，据我们所知，AlphaTensor算法自50年前发现以来首次改进了斯特拉森的两级算法。我们通过不同的用例进一步展示了AlphaTensor的灵活性：具有最先进复杂性的结构化矩阵乘法算法，并通过优化特定硬件上运行时的矩阵乘法来提高实际效率。我们的研究结果突出了AlphaTensor在一系列问题上加速算法发现过程并针对不同标准进行优化的能力。基于AlphaZero的强化学习方法用于发现有效且可证明正确的矩阵乘法算法，为各种矩阵大小找到更快的算法。
Improving the efficiency of algorithms for fundamental computations can have a widespread impact, as it can affect the overall speed of a large amount of computations. Matrix multiplication is one such primitive task, occurring in many systems—from neural networks to scientific computing routines. The automatic discovery of algorithms using machine learning offers the prospect of reaching beyond human intuition and outperforming the current best human-designed algorithms. However, automating the algorithm discovery procedure is intricate, as the space of possible algorithms is enormous. Here we report a deep reinforcement learning approach based on AlphaZero for discovering efficient and provably correct algorithms for the multiplication of arbitrary matrices. Our agent, AlphaTensor, is trained to play a single-player game where the objective is finding tensor decompositions within a finite factor space. AlphaTensor discovered algorithms that outperform the state-of-the-art complexity for many matrix sizes. Particularly relevant is the case of 4 × 4 matrices in a finite field, where AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. We further showcase the flexibility of AlphaTensor through different use-cases: algorithms with state-of-the-art complexity for structured matrix multiplication and improved practical efficiency by optimizing matrix multiplication for runtime on specific hardware. Our results highlight AlphaTensor’s ability to accelerate the process of algorithmic discovery on a range of problems, and to optimize for different criteria. A reinforcement learning approach based on AlphaZero is used to discover efficient and provably correct algorithms for matrix multiplication, finding faster algorithms for a variety of matrix sizes.
登录
查看更多内容
影响因子：
--
作者：
Benson, Austin R.;Ballard, Grey
通讯作者：
Ballard, Grey
影响因子：
0.5
作者：
Chiantini, Luca;Ikenmeyer, Christian;Ottaviani, Giorgio
通讯作者：
Ottaviani, Giorgio
影响因子：
0.7
作者：
Heule, Marijn J. H.;Kauers, Manuel;Seidl, Martina
通讯作者：
Seidl, Martina
影响因子：
7.6
作者：
Dalgaard, Mogens;Motzoi, Felix;Sherson, Jacob
通讯作者：
Sherson, Jacob
影响因子：
0.7
作者：
COPPERSMITH, D;WINOGRAD, S
通讯作者：
WINOGRAD, S