介绍
数学家喜欢好的谜题。 当您尝试找到最有效的方法时，即使像乘法矩阵（二维数字表）这样抽象的东西也会感觉像一场游戏。 这有点像尝试用尽可能少的步骤解开魔方——具有挑战性，但也很诱人。 除了魔方，每一步可能移动的次数是18； 对于矩阵乘法，即使在比较简单的情况下，每一步都可以呈现超过 1012 选项。
在过去的 50 年里，研究人员以多种方式解决了这个问题，所有这些都是基于人类直觉辅助的计算机搜索。 上个月，人工智能公司 DeepMind 的一个团队展示了如何从一个新的方向解决这个问题，报告中 纸 in 自然 他们已经成功地训练了一个神经网络来发现新的快速矩阵乘法算法。 就好像人工智能找到了一种未知的策略来解决一个极其复杂的魔方。
“这是一个非常好的结果，”说 乔什·阿尔曼（Josh Alman），哥伦比亚大学计算机科学家。 但他和其他矩阵乘法专家也强调，这种人工智能辅助将补充而不是取代现有方法——至少在短期内是这样。 “这就像对可能成为突破的事物的概念验证，”Alman 说。 结果只会帮助研究人员完成他们的任务。
仿佛要证明这一点，三天后 自然 论文发表后，一对奥地利研究人员说明了新旧方法如何相互补充。 他们使用传统的计算机辅助搜索来 进一步提高 神经网络发现的算法之一。
结果表明，就像解决魔方的过程一样，通往更好算法的道路将充满曲折。
乘法矩阵
矩阵乘法是所有数学中最基本和最普遍的运算之一。 乘以一对 n逐n 矩阵，每个都有 n2 元素，您将这些元素以特定组合相乘并相加以生成产品，第三个 n逐n 矩阵。 两个乘法的标准配方 n逐n 矩阵需要 n3 乘法运算，例如，一个 2×2 矩阵需要八次乘法。
对于具有数千行和列的较大矩阵，此过程很快就会变得麻烦。 但在 1969 年，数学家 Volker Strassen 发现了一个程序 使用七个而不是八个乘法步骤将一对 2×2 矩阵相乘，代价是引入更多的加法步骤。
如果您只想乘以一对 2×2 矩阵，则 Strassen 算法不必要地复杂化。 但他意识到它也适用于更大的矩阵。 那是因为矩阵的元素本身可以是矩阵。 例如，可以将具有 20,000 行和 20,000 列的矩阵重新设想为一个 2×2 矩阵，其四个元素各为 10,000×10,000 矩阵。 然后可以将这些矩阵中的每一个细分为四个 5,000×5,000 块，依此类推。 Strassen 可以应用他的方法在此嵌套层次结构的每一层上乘以 2×2 矩阵。 随着矩阵大小的增加，减少乘法所节省的成本也会增加。
Strassen 的发现导致人们开始寻找矩阵乘法的有效算法，此后启发了两个不同的子领域。 一个侧重于一个原则问题：如果你想象将两个相乘 n逐n 矩阵并让 n 向无穷大运行，最快算法中的乘法步骤数如何与 n？ 该 当前记录 为了获得最佳缩放比例， n2.3728596，属于阿尔曼和 弗吉尼亚·瓦西列夫斯卡·威廉姆斯（Virginia Vassilevska Williams），麻省理工学院的计算机科学家。 （最近未发表的 预印本 报告了使用新技术的微小改进。）但是这些算法纯粹是理论上的兴趣，仅在荒谬的大矩阵上胜过像 Strassen 这样的方法。
第二个子领域的思考规模较小。 在 Strassen 的工作之后不久，以色列裔美国计算机科学家 Shmuel Winograd 显示 Strassen 已经达到了理论极限：不可能用少于七个乘法步骤将 2×2 矩阵相乘。 但对于所有其他矩阵大小，所需乘法的最小数量仍然是一个悬而未决的问题。 小矩阵的快速算法可能会产生巨大的影响，因为当乘以合理大小的矩阵时，这种算法的重复迭代可能会击败 Strassen 的算法。
不幸的是，可能性的数量是巨大的。 即使对于 3×3 矩阵，“可能的算法数量也超过了宇宙中的原子数量，”说 阿尔侯赛因法齐，一名 DeepMind 研究员，也是新工作的领导者之一。
面对这些令人眼花缭乱的选项，研究人员通过将矩阵乘法转化为一个看起来完全不同的数学问题——一个计算机更容易处理的问题——取得了进展。 可以将两个矩阵相乘的抽象任务表示为一种特定类型的数学对象：称为张量的三维数字数组。 然后，研究人员可以将这个张量分解为基本分量的总和，称为“rank-1”张量； 这些中的每一个都代表相应矩阵乘法算法中的不同步骤。 这意味着找到一个有效的乘法算法相当于最小化张量分解中的项数——项越少，涉及的步骤就越少。
通过这种方式，研究人员发现了新的 算法 乘以 n逐n 使用少于标准的矩阵 n3 许多小矩阵尺寸的乘法步骤。 但是，不仅优于标准而且优于 Strassen 小矩阵算法的算法仍然遥不可及——直到现在。
游戏
DeepMind 团队通过将张量分解变成单人游戏来解决这个问题。 他们从 AlphaGo 的深度学习算法入手——AlphaGo 是 2016 年推出的另一种 DeepMind AI 学会了玩棋盘游戏 Go 足以击败顶级人类玩家。
所有的深度学习算法都是围绕神经网络构建的：人工神经元网络被分类成层，连接强度可以变化，代表每个神经元对下一层神经元的影响程度。 这些连接的强度在训练过程的多次迭代中得到调整，在此期间神经网络学习将它接收到的每个输入转换为有助于算法实现其总体目标的输出。
在 DeepMind 的新算法（称为 AlphaTensor）中，输入代表通往有效矩阵乘法方案的步骤。 神经网络的第一个输入是原始矩阵乘法张量，其输出是 AlphaTensor 为其第一步选择的 rank-1 张量。 该算法从初始输入中减去这个 rank-1 张量，产生一个更新的张量，该张量作为新输入反馈到网络中。 重复该过程，直到最终起始张量中的每个元素都减少为零，这意味着没有更多的 rank-1 张量可以取出。
在这一点上，神经网络发现了一个有效的张量分解，因为它在数学上保证了所有 rank-1 张量的总和恰好等于起始张量。 到达那里所采取的步骤可以转换回相应的矩阵乘法算法的步骤。
游戏是这样的：AlphaTensor 反复将张量分解为一组 rank-1 分量。 每次，如果 AlphaTensor 找到减少步数的方法，它就会获得奖励。 但是胜利的捷径一点也不直观，就像您有时必须在魔方上打乱一张完美有序的脸才能解决整个问题一样。
该团队现在有了一种算法，理论上可以解决他们的问题。 他们只需要先训练它。
新路径
与所有神经网络一样，AlphaTensor 需要大量数据进行训练，但张量分解是一个众所周知的难题。 研究人员可以为网络提供有效分解的例子很少。 相反，他们通过在更简单的逆问题上进行训练来帮助算法开始：将一堆随机生成的 rank-1 张量相加。
“他们正在使用简单的问题来为难题生成更多数据，”说 迈克尔·利特曼，布朗大学计算机科学家。 将这种向后训练过程与强化学习相结合，其中 AlphaTensor 在寻找有效分解时会产生自己的训练数据，其效果比单独使用任何一种训练方法都要好得多。
DeepMind 团队训练 AlphaTensor 来分解代表矩阵乘法的张量，最高可达 12×12。 它寻求用于将普通实数矩阵相乘的快速算法，以及特定于更受约束的设置（称为模 2 算术）的算法。 （这是仅基于两个数字的数学，因此矩阵元素只能是 0 或 1，并且 1 + 1 = 0。）研究人员通常从这个更受限制但仍然广阔的空间开始，希望这里发现的算法可以适应处理实数矩阵。
训练后，AlphaTensor 在几分钟内重新发现了 Strassen 的算法。 然后，它针对每种矩阵大小发现了多达数千种新的快速算法。 这些与最著名的算法不同，但具有相同数量的乘法步骤。
在少数情况下，AlphaTensor 甚至打破了现有记录。 它最令人惊讶的发现发生在模 2 运算中，它发现了一种新算法，可以在 4 个乘法步骤中将 4×47 矩阵相乘，比 Strassen 算法两次迭代所需的 49 个步骤有所改进。 它还打破了最著名的 5×5 模 2 矩阵算法，将所需的乘法次数从之前的 98 次记录减少到 96 次。（但这一新记录仍然落后于打破所需的 91 步）使用 5×5 矩阵的 Strassen 算法。）
新的高调结果引起了很多兴奋， 一些研究人员 对基于 AI 的现状改进大加赞赏。 但并非矩阵乘法社区中的每个人都对此印象深刻。 “我觉得它有点被夸大了，”Vassilevska Williams 说。 “这是另一种工具。 这不像是，‘哦，计算机打败了人类，’你知道吗？”
研究人员还强调，破纪录的 4×4 算法的直接应用将受到限制：它不仅仅在模 2 算法中有效，而且在现实生活中，除了速度之外还有其他重要的考虑因素。
Fawzi 同意，真的，这仅仅是个开始。 “有很大的改进和研究空间，这是一件好事，”他说。
最后的转折
相对于成熟的计算机搜索方法，AlphaTensor 的最大优势也是它最大的弱点：它不受人类直觉的约束，因此它无法解释其选择。 这使得研究人员很难从其成就中学习。
但这可能并不像看起来那么大。 在 AlphaTensor 结果出来几天后，数学家 曼纽尔·考尔斯 和他的研究生 雅各布穆斯鲍尔, 奥地利林茨约翰内斯开普勒大学的两位学者报告说又向前迈进了一步。
介绍
当 DeepMind 论文发表时，考尔斯和穆斯鲍尔正在使用传统的计算机辅助搜索来寻找新的乘法算法。 但与大多数以新的指导原则重新开始的此类搜索不同，他们的方法通过反复调整现有算法来工作，希望从中挤出更多的乘法节省。 以 AlphaTensor 的 5×5 模 2 矩阵算法为起点，他们惊讶地发现，他们的方法仅经过几秒钟的计算就将乘法步骤从 96 减少到 95。
AlphaTensor 还间接帮助他们进行了另一项改进。 此前，Kauers 和 Moosbauer 并没有费心去探索 4×4 矩阵的空间，他们认为不可能击败 Strassen 算法的两次迭代。 AlphaTensor 结果促使他们重新考虑，在从头开始计算一周后，他们的方法出现了另一种 47 步算法，与 AlphaTensor 发现的算法无关。 “如果有人告诉我们 4×4 有什么值得发现的东西，我们本可以早点做到这一点，”考尔斯说。 “但是，好吧，这就是它的工作原理。”
利特曼预计会有更多这样的惊喜，他将这种情况比作跑步者第一次在四分钟内跑完一英里，这一壮举曾被广泛认为是不可能的。 “人们就像，'哦，等等，我们可以做到这一点，'现在很多人都可以做到，”他说。
展望未来，Fawzi 希望推广 AlphaTensor 以解决更广泛的数学和计算任务，就像它的祖先 AlphaGo 最终扩展到其他游戏一样。
Kauers 认为这是将机器学习应用于发现新算法的真正试金石。 他指出，寻求快速矩阵乘法算法是一个组合问题，无论有无人工协助，计算机搜索都非常适合。 但并不是所有的数学问题都那么容易确定。 他说，如果机器学习能够发现一种全新的算法理念，“这将改变游戏规则。”
