AI推动算法发现的自动化
首先，我们将寻找矩阵乘法的有效算法问题转化为一个单人游戏。在这个游戏中，棋盘是一个三维张量（数字阵列），记录了当前算法离正确的程度。
通过一组与算法指令相对应的允许移动，玩家试图修改张量并将其条目清零。当玩家成功做到这一点时，对于任何一对矩阵来说，都会产生一个可证明正确的矩阵乘法算法，而其效率则由将张量清零所需的步骤数来体现。这个游戏具有令人难以置信的挑战性--要考虑的可能算法的数量远远大于宇宙中的原子数量，即使是对于矩阵乘法的小案例。与几十年来一直是人工智能挑战的围棋游戏相比，我们的游戏每一步可能的动作数量要大30个数量级。从本质上讲，要玩好这个游戏，相当于要在「巨大的干草堆中找出最小的那根针」。为了应对这个明显不同于传统游戏的领域的挑战，我们开发了多个关键组件，包括一个新的神经网络架构，其中包括特定问题的归纳偏见，一个生成有用的合成数据的程序，以及一个利用问题的对称性的配方。然后，我们利用强化学习训练了一个AlphaTensor智能体来玩一个单人游戏（Tensor Game），开始时没有任何关于现有矩阵乘法算法的知识。
AlphaTensor在TensorGame中的目标则是在有限因子空间内找到张量分解 (Tensor Decomposition)。在介绍张量分解之前，我们可能需要先简单地了解一下张量是什么，然后再考虑张量分解有什么用途。从初中到大学，我们接触最多的可能只是标量（scalar）、向量（vector）和矩阵（matrix），而张量则不那么常见，但实际上，标量是第0阶张量，向量是第1阶张量，矩阵是第2阶张量，第3阶或阶数更高的张量被称为高阶张量（higher-order tensor），一般提到的张量都是特指高阶张量。
我们也知道，在一个矩阵中，某一元素的位置可以说成“第几行第几列”的形式，要表达某一元素的位置需要两个索引构成的组合 ，类似地，在一个第3阶张量里面，表达某一元素的位置需要三个索引构成的组合 。在处理稀疏矩阵和稀疏张量时，用索引来标记元素的位置会带来很多便利。另外，阶数的张量可以理解为矩阵的维泛化，在这里，阶数其实就是空间维度（spatial dimension），张量可以被视为多维数组。张量分解从本质上来说是矩阵分解的高阶泛化。对矩阵分解有所了解的读者可能知道，矩阵分解有三个很明显的用途，即降维处理、缺失数据填补和隐性关系挖掘，而张量分解也能够很好地满足这些用途。为了解决TensorGame并找到有效的矩阵乘法算法，我们开发了一个DRL智能体AlphaTensor。通过学习，AlphaTensor随着时间的推移逐渐改进，重新发现了历史上的快速矩阵乘法算法，如Strassen的算法，最终超越了人类的直觉领域，发现的算法比以前已知的更快。 
由AlphaTensor玩的单人游戏，目标是找到一个正确的矩阵乘法算法。游戏的状态是一个由数字组成的立方体数组（显示为灰色为0，蓝色为1，绿色为-1），代表着要做的剩余工作。例如，如果学校里教的传统算法是用100次乘法对一个4x5乘以5x5的矩阵进行乘法，而这个数字在人类的聪明才智下被减少到80次，AlphaTensor已经找到了只用76次乘法就能完成同样操作的算法。 
除此之外，AlphaTensor的算法自50年前发现以来，首次在有限域中改进了Strassen的两级算法。这些小矩阵的乘法算法可以作为基元来乘以任意大小的大得多的矩阵。此外，AlphaTensor还发现了一组具有最先进复杂度的多样化算法--每种大小的矩阵乘法算法多达数千种，表明矩阵乘法算法的空间比以前想象的要丰富。在这个丰富的空间中的算法具有不同的数学和实践属性。利用这种多样性，我们对AlphaTensor进行了调整，以专门寻找在特定硬件上速度快的算法，如Nvidia V100 GPU，和谷歌TPU v2。这些算法在相同的硬件上比常用的算法快10-20%，这展示了AlphaTensor在优化任意目标上的灵活性。 
AlphaTensor的目标是对应于算法的运行时间。当发现一个正确的矩阵乘法算法时，会在目标硬件上进行基准测试，然后反馈给AlphaTensor，以便在目标硬件上学习更有效的算法。
未来的研究和应用
从数学的角度来看，我们的结果可以指导复杂性理论的进一步研究，其目的是确定解决计算问题的最快算法。通过以比以前的方法更有效的方式探索可能的算法空间，AlphaTensor有助于推进我们对矩阵乘法算法的丰富性的理解。了解这个空间可能会释放出新的结果，帮助确定矩阵乘法的渐进复杂性，这是计算机科学中最基本的开放问题之一。因为矩阵乘法是许多计算任务的核心组成部分，涵盖了计算机图形、数字通信、神经网络训练和科学计算，AlphaTensor发现的算法可以使这些领域的计算效率大大提升。
图为AlphaTensor网络架构AlphaTensor在考虑任何类型的目标方面的灵活性也可以刺激新的应用，以设计优化能源使用和数值稳定性等指标的算法，帮助防止小的四舍五入错误随着算法的工作而滚雪球。虽然我们在这里集中讨论了矩阵乘法这一特殊问题，但我们希望我们的论文能够启发其他人使用人工智能来指导其他基本计算任务的算法发现。我们的研究还表明，AlphaZero是一个强大的算法，可以远远超出传统游戏的领域，帮助解决数学中的开放问题。在我们的研究基础上，我们希望能够推动更多的工作--应用人工智能来帮助社会解决数学和整个科学领域的一些最重要的挑战。
参考资料：https://www.nature.com/articles/s41586-022-05172-4https://www.newscientist.com/article/2340343-deepmind-ai-finds-new-way-to-multiply-numbers-and-speed-up-computers/
