算法|最近，人工智能推进了数学研究的进程，揭示了矩阵乘法的新可能性 deepmind

文章图片

文章图片

当试图找到最有效的方法时，甚至像矩阵乘法这样抽象的事情也会像游戏一样。这有点像用尽可能少的步骤来解魔方。对于矩阵乘法，即使在相对简单的情况下，每一步都可以有超过10^12个选项。
在过去的50年里，研究人员用了很多方法来解决矩阵乘法问题，所有的方法都是基于计算机搜索和人类直觉的辅助。上个月，人工智能公司DeepMind的一个团队展示了如何从一个新的方向解决这个问题，他们在《自然》杂志的一篇论文中报告说，他们已经成功地训练了一个神经网络，以发现矩阵乘法的新的快速算法。这就好像人工智能找到了一个策略来解决一个极其复杂的魔方。
似乎是为了证明这一点，在《自然》杂志的论文发表三天后，两位奥地利研究人员说明了新方法和旧方法是如何相互补充的。他们使用传统的计算机辅助搜索来进一步改进神经网络发现的一种算法。
结果表明，就像解决魔方的过程一样，通向更好算法的道路将充满曲折。
矩阵乘法矩阵乘法是所有数学中最基本和最普遍的运算之一。要乘一对n × n矩阵，需要将这些元素以特定的组合相乘并相加，以生成第三个n × n矩阵。两个n × n矩阵相乘的标准方法需要进行n^3次乘法运算。

对于具有数千行和列的较大矩阵，这个过程会非常繁琐。但在1969年，数学家沃尔克·斯特拉森发现了一种方法，可以用7步而不是8步的乘法步骤将一对2 × 2矩阵相乘，代价是引入更多的加法步骤。

斯特拉森的算法对于一对2乘2的矩阵显得很繁琐。但它适用于更大的矩阵。这是因为矩阵的元素本身可以是矩阵。例如，一个具有20000行和20000列的矩阵可以被重新解构成一个2 × 2矩阵，其中四个元素都是10000 × 10000的矩阵。每个矩阵又可以再细分为4个5000 × 5000的矩阵，以此类推。斯特拉森可以应用他的方法在这个嵌套层次结构的每一层乘2 × 2矩阵。随着矩阵大小的增加，通过更少的乘法节省的成本也在增加。
斯特拉森的发现促使人们寻找矩阵乘法的有效算法，并由此激发了两个不同的子领域。其中一个关注的是一个原理问题：如果你想象两个n × n矩阵相乘，让n趋于无穷，在最快的可能算法中，乘法步骤的数量如何随n增长？目前的最佳缩减记录是n^2.3728596 。
第二个子领域的矩阵规模较小。在斯特拉森的工作完成后不久，研究人员指出斯特拉森已经达到了一个理论极限：2 × 2矩阵的乘法运算步骤不可能少于7步。但对于所有其他矩阵大小，所需乘法的最小次数仍然是一个悬而未决的问题。针对小矩阵的快速算法可能会产生巨大的影响，因为当合理大小的矩阵相乘时，这种算法的重复迭代可能会击败斯特拉森的算法。
不幸的是，即使对于3 × 3矩阵，可能的算法数量也超过了宇宙中原子的数量。
面对如此庞大的选项，研究人员已经取得了进展，将矩阵乘法转化为一个看起来完全不同的数学问题——一个更容易由计算机处理的问题。可以将两个矩阵相乘的抽象任务表示为一种特定的数学对象：一种称为张量的三维数字数组。然后，研究人员可以将这个张量分解为基本分量的和，称为“秩1”张量；每一个都代表对应矩阵乘法算法的不同步骤。这意味着找到一个有效的乘法算法相当于在一个张量分解中最小化项的数量，项越少，所涉及的步骤越少。