Google的DeepMind研究小组最近开发了“ Alphatensor”。第一个用于发现新型算法以执行基本任务（例如矩阵乘法）的系统。该应用程序为50年历史的数学挑战带来了创新，即找到乘以两个矩阵的最快方法。让我们分解这一发现的重要性。

什么是矩阵乘法？

我们大多数人首先在中学或高中遇到矩阵乘法。它由一系列乘法和添加的预定顺序组成，用于查找两个N度张量的乘积。乘以两个矩阵的最著名的机制是使用行和列的点产品（图1）。

在K-12教育之外，这种数学操作影响了现代计算，并且是数字系统的基石。几乎所有可以被象征化或编码为数字的多维表示的数据类型都需要一些矩阵乘法。图像处理和计算机视觉应用程序从有效的矩阵操作中受益匪浅。

在卷积神经网络中（图2），离散卷积等同于在滤波器权重和滤波器下方的值之间取点产物 - 简而言之，另一个矩阵乘法应用程序。

数百年来，数学家认为，标准点产品是乘以矩阵的最佳，最有效的方法。直到Colker Strassen引入了Strassen的算法（图3），并通过证明存在更有效的算法来震惊世界。与传统方法相比，Strassen的算法使用的标量乘以少。

尽管Strassen的算法包含更少的算术操作，但必须考虑到，对于当前生成CPU，乘数可以在每个机器周期中产生结果，但是加法器也可以。乘数需要更多的门，并具有更长的延迟以获得第一个结果，但是它们的吞吐量是相同的速度。乘法比加法具有更高的“大O”复杂性（图4）。总之，Strassen更有效，因为他执行了一个较少的乘法步骤。

Alphatensor通过使用AI技术通过通过自我游戏和强化学习来发现新的矩阵乘法算法来进一步发现新的矩阵乘法算法。

什么是深度强化学习？

深度强化学习（深RL）利用深神经网络的力量来优化特定问题的解决方案。我们采用代理，环境和奖励的概念作为现实世界系统的模型，其目标是使代理在特定环境中最大化其奖励。

假设您考虑国际象棋游戏（图5），目的是捕捉对手的碎片并检查他们的国王。在这种情况下，对于板上的所有可能场景，都存在一组最佳移动，这将最大程度地增加成功的几率。对于这种情况，RL模式可以定义如下：

• 代理人将是国际象棋球员。
• 环境将是董事会和所有碎片。
• 奖励框架：
  - 添加2分，以靠近对手的董事会
  - 添加5点捕获典当
  - 添加10分以捕获骑士或主教
  - 添加50分以捕获女王
  - 减去10分的损失
  - 减去失去女王的50分

我们将为每一步提供适当的奖励，直到任何一名球员都在检查员或有平局为止（图6）。这个过程将进行迭代执行，直到我们的模型得分始终高到足以满足我们的需求为止。

Alphatensor做的事情与发现数学操作最佳组合非常相似，以新颖有效的方式执行矩阵乘法。

Alphatensor如何自动化算法发现？

使用自我播放的概念，DeepMind的团队构建了强化学习模式，以优化矩阵乘法问题。

他们的架构，如他们所述纸，看起来像这样：

• Alphatensor代理在不了解现有矩阵乘法算法的情况下开始，并负责编译一组操作，以最大程度地减少矩阵乘法的正确值及其结果之间的误差。
• 环境是正在操作的矩阵的实际定义。在这种情况下，DeepMind使用3D张量。
• 奖励被定义为新算法结果中误差度量的组合以及将张量的步骤数（地址为涉及矩阵的所有组件）所采取的步骤数。

该模式导致一个搜索空间，其中可能的算法大大超过了宇宙中的原子。作为参考，DeepMind在几年前解决的GO游戏（图7）的每个步骤的可能动作比Alphatensor遇到的复杂性少了30个数量级。

为了提高这项工作的可行性，Alphatensor采用了“一种新型的神经网络结构，结合了特定问题的诱导偏见，一种生成有用的合成数据的程序以及一种配方来利用问题的对称性。”

随着时间的流逝，DeepMind团队观察到Alphatensor重新发现可行算法的能力，例如Strassen的算法，并最终超过了人类定义的方法，以比探索的任何算法更快。

在使用Strassen的算法和Alphatensor乘以5x5和5x5（图8）矩阵的测试中，我们发现Alphatensor可以在76个乘法中与Strassen的80乘以解决该操作！

为什么这很重要？

Alphatensor已帮助阐明了矩阵乘法算法的丰富性。这些学习无疑将影响多维数据处理的速度和效率的未来。

Alphatensor还证明，机器学习技术可用于发现超过人类创造力的数学创新。这种深厚的增强学习的味道是在早期的，而载语的工作比直接解决方案更能证明可行性。这是计算优化和自我优化AGI的激动人心的一步。

DeepMind的GitHub包括Alphatensor发现的一些算法和一本带有用于加载和测试的说明的Jupyter笔记本。我已经将其链接在来源中。

不要忘记跟随我的资料有关更多文章像这样！

资料来源：

• 发现使用αentenor的新型算法|https://www.deepmind.com/blog/discovering-novel-algorithms-with-alphatensor
• 数学操作的计算复杂性|https://en.wikipedia.org/wiki/computational_complexity_of_mathematical_operations#arithmetic_functions
• alphatensor github |https://github.com/deepmind/alphatensor
• 通过增强学习发现更快的矩阵乘法算法|Fawzi，A。等。|https://www.nature.com/articles/s41586-022-05172-4