DeepMind 用 AlphaTensor 发现新型算法

DeepMind 这篇 2022 年 10 月 5 日的博客介绍 AlphaTensor，由 Alhussein Fawzi、Matej Balog、Bernardino Romera-Paredes、Demis Hassabis、Pushmeet Kohli 共同署名，论文同步发表在 Nature。文章把矩阵乘法的算法发现追溯到 Strassen 在 1969 年的突破：他证明两个 2x2 矩阵相乘只需 7 次标量乘法而非教科书的 8 次，颠覆了延续数百年的“标准算法已是最优”假设。半个多世纪过去，更大尺寸如 3x3 的最优乘法次数依然未知，AlphaTensor 把这一长期悬而未决的问题转化为单人游戏求解。

游戏的状态是一个三维张量，刻画当前算法距离正确还差多远；玩家通过一组合法动作修改张量，把所有元素归零即得到可证正确的矩阵乘法算法，步数越少效率越高。每一步的可能动作数超过 10 的 33 次方，比围棋大 30 个数量级。研究者基于 AlphaZero 框架，引入针对该问题的神经网络归纳偏置、合成数据生成流程与对称性利用机制，从零知识开始训练强化学习 agent。AlphaTensor 先重新发现了 Strassen 的经典构造，随后越过人类直觉边界：在 4x5 乘 5x5 矩阵上，把人类此前的 80 次乘法降到 76 次，并在某有限域上首次改进 Strassen 的二层算法；对每个矩阵尺寸都能找到上千种具备 SOTA 复杂度的不同算法。

AlphaTensor 还可针对特定硬件优化。把 Nvidia V100 GPU 或 Google TPU v2 上的实际运行时反馈给 agent，它会发现比常规算法快 10% 至 20% 的实现，证明同一目标可以根据硬件特性产出不同最优解。对数学与计算机科学读者而言，这项工作的意义有两层：一是为复杂度理论提供了更广阔的算法空间证据，矩阵乘法的渐近复杂度这一基础开问题有了新的探索方向；二是表明 AlphaZero 的对弈范式可以泛化到数学发现，为算法设计、能耗优化、数值稳定性等其他基础计算任务开辟了由 AI 主动搜索的可能。