OpenAI的FFT算法与其说是突破，不如说是恶意利用

# 更快的傅里叶变换 来源：https://www.argmin.net/p/faster-fourier-transforms *嗨，argmin 的读者们！今天的帖子来看看 OpenAI 数学仓库中声称能计算更快傅里叶变换的部分。这篇比平常技术性更强，但我尝试为需要信号处理或计算复杂度基础复习的读者加入了一些教程内容。* 快速傅里叶变换是数字信号处理中最重要的创新之一，也是我最喜欢的算法之一。FFT 是一种快速提取信号频率内容的方法，让你能够迅速分析、过滤和操作不同频段上的频率。 傅里叶变换通过简单的点积来计算每个频段中的能量。1 (https://www.argmin.net/p/faster-fourier-transforms#footnote-1)设 x 为你的输入，即一个长度为 n 的采样数组，f 为某个频率。那么 x 在频率 f 处的频率含量可以通过以下公式计算： 对于数字信号，一点数学推导告诉你只需要计算 n 个这样的点积，即在频率 2π/n 的每个倍数处各计算一个，就能理解全部频率内容。朴素地看，每个频率需要 n 次乘法和加法。因此，计算整个傅里叶变换似乎需要 n² 次算术运算。 *快速*傅里叶变换是 James Cooley 和 John Tukey 在 1965 年设计的一个巧妙递归过程。2 (https://www.argmin.net/p/faster-fourier-transforms#footnote-2)核心思想是：长度为 n 的傅里叶变换可以通过对输入向量进行重排，对重排后的分量计算两个长度为 n/2 的傅里叶变换，然后使用基本算术运算将输出重新组合来计算。重排和重新组合需要线性数量的算术运算。迭代重复此过程 log₂(n) 次，即可计算出完整的离散傅里叶变换。加上簿记开销，FFT 在不到 5n log₂(n) 次算术运算内就能完成长度为 n 的傅里叶变换。 为了使这个加速更具体化：当 n 为 1,000 时，n² 是 1,000,000，而 5 × n log n 约为 50,000，即 20 倍加速。当 n 为 1,000,000 时，加速倍数为 10,000 倍。这些加速可能决定了一个变换在信号处理应用的约束条件下是否可行。 自 FFT 发明以来，人们一直在寻找更快的傅里叶变换。一个问题是：你到底能有多快。看起来你至少需要 n 次运算来计算 FFT，因为光是把它写下来就需要 n 步。FFT 比这个合理的速度上限慢 5*log₂(n) 倍，而这个 5*log₂(n) 因子可能很大。当 n 为一万亿时，它是 200。你能不能做点巧妙的事情把这个 200 的前置因子降低？ 好吧，你看，在 OpenAI 上周向数学界倾泻的海量论文中，他们声称拥有了一种更快的傅里叶变换。他们那个命名颇具倾向性的"main.pdf"的主要声明是 我对这里到底在做什么很感兴趣。理论上，log(n) 项比标准 FFT 的确实小了那么一丁点。 我读了这篇论文吗？当然没有。OpenAI 里也没人读了这篇论文，那我为什么要读？我做了世界上其他每一个数学家对 AI 粗制滥造数学的做法：把它喂回给粗制滥造的机器，通过聊天机器人界面运行一次信息检索会话来提取关键事实。拟人地说：我问 ChatGPT 它对自己输出的看法。这就是我们现在做数学研究的方式。真是一个什么样的世界啊。 不幸的是，我没有找到更快的傅里叶变换。相反，我发现了应用数学理论中滋生的腐烂——当形式主义与现实脱节到如此程度，以至于一个"突破"不过是数学家们无法在自然语言中正确指定他们游戏规则的产物。 首先，"大 O"记号被滥用到已经变得毫无意义的程度。让我们回顾一下定义，这个定义在本科时曾令我印象深刻。一个算法的运行时间 T(n) = O(F(n))，如果存在整数 N 和常数 C 使得 也就是说，只要 n 足够大，算法实际执行的步骤数就有一个上界，该上界是某个方便的函数 F(n) 乘以一个常数。F(n) 通常是某种熟悉且可解释的东西，比如多项式函数或指数函数。这个记号的意思是我们只关心计算规模大时的情况。我们关心的是计算时间的*渐近*增长率。所有常数都是等价的。 大 O 记号对于算法记账中的简写很有用，但它也允许了显著的逻辑懒惰。如果我们想要一个实际上更快的 FFT，我们想要的是一个在合理规模的 n 下所需运算少于 50n 次的算法。但 O(n) 并不意味着 50n。它可能意味着 10⁸⁰n。这仍然会被视为"线性时间"算法。一个需要 n + 10⁸⁰ 次运算的算法在大 O 范畴内同样被视为线性时间算法。一个只有在 n 大于 10⁸⁰ 时才具有线性时间保证的算法同样被视为线性时间。10⁸⁰ 近似等于已知宇宙中的原子数。这就是为什么 Richard Lipton 和 Ken Regan 称那些隐藏常数大到不可想象的算法为*银河系算法* (https://link.springer.com/chapter/10.1007/978-3-642-41422-0_20)。 OpenAI 的 FFT 算法绝对是银河系级别的。当 N=10¹² 时，估计的 C 值为 10¹⁰⁰。所以即使 n=10¹⁰⁰，德高望重的 Cooley-Tukey-Gauss FFT 仍然快 10⁹⁹ 倍。 那为什么这个新的 FFT 结果有趣呢？请注意，在大 O 记号中，它在技术上比 Cooley-Tukey 算法*渐近*更快，因为 我是说，当然了。但鉴于这些常数，这个算法只有在 n 大到不可能的情况下才能运行得更快。粗略地说，你需要 天知道那个数字意味着什么。 Lipton 和 Regan 认为银河系算法是有用的，因为它们能推动研究。一旦你证明了某个运行时间在渐近意义上是可行的，你就可以花时间去寻找一个实际达到这个可证明运行时间的算法。也许你可以派你的 AI 智能体群去研究它。你想怎么干就怎么干。也许你能搞出一个实用算法，但我不知道有任何真实的例子证明这种情况发生过。我对此特别怀疑，因为 OpenAI 使用的"计算"模型与实际计算机毫无相似之处。 "该模型使用精确复数算术。"这意味着它假设你可以以任意精度存储和乘法运算复数。事实上，该算法要求你乘法运算模长随 n*超多项式*增长的复数。如果你将这些数存储为比特，内存需求将实际上是输入长度的指数级。它假设你可以在单次运算中乘法运算任意大的复数。我们没有能这样做的计算机。所以即使 main.pdf 中的这个定理是"真的"（没人知道，我也不在乎），它实际上并没有解决我们在寻找更快 FFT 时最初想要解决的问题。 对于熟悉 FFT 理论分析的人来说，你需要一个荒谬的计算模型才能突破 FFT 速度限制并不令人惊讶。1973 年，Jacques Morgenstern 证明了 (https://dl.acm.org/doi/10.1145/321752.321761)如果要求计算中使用的复数系数具有有界模长，你不可能得到比 1/2 n log n 更快的傅里叶变换。这本该是故事的终点！但事实并非如此。人们说 Morgenstern 的系数限制模型太严格了。四十年后，Nir Ailon 证明了你不能在不引起严重数值不稳定性 (https://arxiv.org/abs/1403.1307) (https://arxiv.org/abs/1404.1741) 的情况下计算出比 n log n 更快的 FFT。我想这对某些人来说也太严格了。 因此，这个新的 OpenAI 结果与其说是数学突破，不如说是计算机科学家不擅长形式化他们设计规格的怪异产物。计算机的"理论"定义与我们实际建造的计算机相去甚远。这个"更快"的傅里叶变换仅仅是一个理论与原始问题彻底脱钩的例子，以至于一个"开放问题"不过变成了一个学术地位谜题。这种情况的解决方式，就像你让计算机器人面对不可能的问题，结果发现它们从事非法黑客活动一样 (https://en.wikipedia.org/wiki/OpenAI_rogue_agent_breach_of_Hugging_Face)。 这个 OpenAI 粗制滥造仓库中许多其他"重大"结果也可以用同样的方式批评。例如，其中一个结果是一个以 O(n^2.25) 次运算乘法运算两个矩阵的银河系算法。论文中使用的构造甚至无法让你估计隐藏在大 O 里面的常数。3 (https://www.argmin.net/p/faster-fourier-transforms#footnote-3)它可能就是无穷大，只有用天体的神圣音乐才能计算出来。 尽管如此，如果写得好得多，这些论文本来是可以进入计算机科学理论领域最负盛名的发表场所的（即 STOC 或 FOCS 的同行评审会议论文集）。4 (https://www.argmin.net/p/faster-fourier-transforms#footnote-4)矩阵乘法论文本来可能会获奖。但这两者都与计算机毫无关系！ 这是因为计算机科学理论有一种文化，积极阻止在计算机上运行算法。在理论会议上，写一篇声称某个算法存在却从不把它写出来的论文是可以接受的。计算机科学理论已经变成了一种不关心计算机的数学形式，对于这些数学追求之外的影响力几乎不给予任何回报。我向一个朋友解释了这一点，他评论说"理论"的跨学科含义是"藏身于自己制造的晦涩之中"。 AI 非常擅长自动化我们最糟糕的倾向。它放大了那些没人喜欢但单个人又无法合理偏离的不成文文化惯例。它利用了那些抵制集体行动的机械化传统。在这个意义上，AI 现在能写出毫无用处的理论论文了。但也许，在这堆令人反感的 OpenAI 垃圾证明的荒诞之中，我们都能抬起头来，共同意识到我们应该考虑做一些别的事情。