矩阵乘法

斯特拉森的算法对于一对2乘2的矩阵显得很繁琐。但它适用于更大的矩阵。这是因为矩阵的元素本身可以是矩阵。例如，一个具有20,000行和20,000列的矩阵可以被重新解构成一个2 × 2矩阵，其中四个元素都是10,000 × 10,000的矩阵。每个矩阵又可以再细分为4个5000 × 5000的矩阵，以此类推。斯特拉森可以应用他的方法在这个嵌套层次结构的每一层乘2 × 2矩阵。随着矩阵大小的增加，通过更少的乘法节省的成本也在增加。

斯特拉森的发现促使人们寻找矩阵乘法的有效算法，并由此激发了两个不同的子领域。其中一个关注的是一个原理问题：如果你想象两个n × n矩阵相乘，让n趋于无穷，在最快的可能算法中，乘法步骤的数量如何随n增长？目前的最佳缩减记录是n^2.3728596。

第二个子领域的矩阵规模较小。在斯特拉森的工作完成后不久，研究人员指出斯特拉森已经达到了一个理论极限：2 × 2矩阵的乘法运算步骤不可能少于7步。但对于所有其他矩阵大小，所需乘法的最小次数仍然是一个悬而未决的问题。针对小矩阵的快速算法可能会产生巨大的影响，因为当合理大小的矩阵相乘时，这种算法的重复迭代可能会击败斯特拉森的算法。

不幸的是，即使对于3 × 3矩阵，可能的算法数量也超过了宇宙中原子的数量。

面对如此庞大的选项，研究人员已经取得了进展，将矩阵乘法转化为一个看起来完全不同的数学问题——一个更容易由计算机处理的问题。可以将两个矩阵相乘的抽象任务表示为一种特定的数学对象：一种称为张量的三维数字数组。然后，研究人员可以将这个张量分解为基本分量的和，称为“秩1”张量；每一个都代表对应矩阵乘法算法的不同步骤。这意味着找到一个有效的乘法算法相当于在一个张量分解中最小化项的数量，项越少，所涉及的步骤越少。

通过这种方式，研究人员发现了新的算法，对于许多小的矩阵，用比标准的n^3乘法步骤更少的时间乘n × n矩阵。但是，那些不仅优于标准算法，而且优于斯特拉森的小矩阵算法的算法仍然是遥不可及的。

算法介绍

DeepMind团队通过将张量分解转化为单人游戏来解决这个问题。他们从AlphaGo衍生出的深度学习算法开始，AlphaGo在2016年学会了围棋，足以击败顶尖的人类棋手。

所有的深度学习算法都是围绕着神经网络建立的：人工神经元的网络被分成几层，连接的强度可以变化，代表每一层神经元对下一层神经元的影响程度。这些连接的强度是在训练过程的多次迭代中调整的，在此过程中，神经网络学会将接收到的每个输入转换为帮助算法实现总体目标的输出。

在DeepMind的名为AlphaTensor的新算法中，输入代表通向有效矩阵乘法方案的步骤。神经网络的第一个输入是原始矩阵乘法张量，它的输出是AlphaTensor选择的第一次移动的第1个张量。该算法从初始输入中减去这个秩1张量，生成一个更新的张量，该张量作为新的输入反馈到网络中。这个过程不断重复，直到最终起始张量中的每一个元素都被降为零，这意味着不再有排在第1位的张量要去掉。

在这一点上，神经网络已经发现了一个有效的张量分解，因为它在数学上保证了所有秩1张量的和完全等于起始张量。得到它的步骤可以转换回对应矩阵乘法算法的步骤。

游戏是这样的：AlphaTensor反复地将一个张量分解为一组秩1分量。每次，如果AlphaTensor找到减少步数的方法，它就会获得奖励。但通往胜利的捷径根本不是凭直觉就能找到的。

该团队现在有了一个算法，理论上可以解决他们的问题。他们只需要先训练一下。

新路径

像所有的神经网络一样，AlphaTensor需要大量的数据进行训练，但张量分解是一个众所周知的难题。很少有研究人员可以为网络提供有效分解的例子。相反，他们通过训练算法解决更简单的逆问题来帮助算法开始：将一堆随机生成的秩1张量相加。

布朗大学的计算机科学家迈克尔·利特曼说：

他们正在利用简单的问题为困难的问题生成更多的数据。将这种向后训练过程与强化学习相结合，AlphaTensor在寻找有效分解时产生自己的训练数据，比单独的任何一种训练方法都要有效得多。

DeepMind团队训练AlphaTensor分解代表12 × 12矩阵乘法的张量。它寻找普通实数矩阵相乘的快速算法，也寻找特定于更有约束的算法，称为模2算法。

这是基于两个数字的数学，所以矩阵元素只能是0或1，并且1 + 1 = 0。

研究人员通常从这个更有限但仍然广阔的空间开始，希望这里发现的算法可以适用于实数矩阵。

经过训练，AlphaTensor在几分钟内重新发现了斯特拉森的算法。然后，它针对每种矩阵大小发现了多达数千种新的快速算法。这些算法与标准算法不同，但乘法步骤数相同。

在一些案例中，AlphaTensor甚至打破了现有的记录。它最令人惊讶的发现发生在模2算法中，它发现了一种用47个乘法步骤将4 × 4矩阵相乘的新算法，这比斯特拉森算法两次迭代所需的49个乘法步骤有所改进。它还击败了最著名的5 × 5模2矩阵算法，将所需的乘法次数从以前的98次减少到96次。

但这个新记录仍然落后于91步，而要击败使用5 × 5矩阵的斯特拉森算法需要91步。

最后的转折