MIT CSAIL 开源 MADDNESS 算法，加速机器学习矩阵乘法

麻省理工学院计算机科学与人工智能实验室（CSAIL）的研究人员开源了一种名为 MADDNESS（Multiply-ADDitioN-lESS）的算法，该算法通过近似矩阵乘法（AMM）加速机器学习。MADDNESS 无需乘加操作，运行速度比其他近似方法快 10 倍，比精确乘法快 100 倍。

主要观点

1. 算法优势：

   • MADDNESS 通过一组高效的哈希函数实现矩阵乘法，无需乘加操作，编码速率可达 100GB/秒（仅使用单个 CPU 线程）。
   • 尽管算法会引入一些误差，但其误差具有理论上限，且可以通过速度与精度之间的权衡进行控制。
   • 在图像分类实验中，MADDNESS 在保持与精确乘法几乎相同精度的同时，速度提升了 10 倍。

2. 技术背景：

   • 矩阵乘法是机器学习中的核心操作，但由于大量乘加指令的使用，其计算耗时较长。
   • GPU 和 TPU 芯片虽然能够并行执行大量乘加操作，但其成本较高，不适合预算有限的研究人员或资源受限的应用（如物联网）。因此，AMM 算法成为研究热点，通过牺牲精度来换取速度。

3. 算法假设：

   • MADDNESS 假设相乘的矩阵是“高且相对稠密的，并存储在同一台机器的内存中”，这在许多机器学习应用中很常见。
   • 其中一个矩阵包含固定值（如分类模型的权重），另一个矩阵表示输入数据（如图像像素）。

4. 算法原理：

   • MADDNESS 基于向量量化算法中的乘积量化（PQ），通过分析大量输入向量生成少量原型向量，并预先计算这些原型向量与固定权重向量的乘积。
   • 使用哈希函数将新输入向量映射到最相似的原型向量，从而快速查找预计算的结果。
   • 算法的核心创新在于通过预处理生成无需乘加操作的快速哈希函数，这些函数基于二叉回归树，每个树有 16 个叶子节点表示哈希桶。

5. 性能优化：

   • 原型优化：选择一组能够最小化原始矩阵重建误差的原型向量。
   • 8 位快速聚合：使用硬件特定的平均指令而非加法来组合多个乘积，进一步提升性能。

6. 实验对比：

   • 在 CIFAR 数据集上的图像分类实验中，MADDNESS 优于其他六种 AMM 算法（包括 PCA 和 Bolt），并在速度与精度之间取得了更好的平衡。
   • 在 UCR 时间序列数据集上的核分类实验中，MADDNESS 在相同精度下显著快于其他算法。

7. 未来扩展：

   • 主要作者 Davis Blalock 表示，团队正在研究将算法扩展到其他线性函数（如卷积），并尝试在神经网络中智能替换线性操作。不过，目前尚未直接研究非线性函数的近似，因为非线性操作本身计算成本较低。

8. 开源代码：

   • MADDNESS 的源代码已发布在 GitHub 上，供研究人员和开发者使用。

总结

MADDNESS 是一种创新的近似矩阵乘法算法，通过哈希函数和预计算技术大幅提升了机器学习中的矩阵乘法速度，同时保持了较高的精度。其开源代码为资源受限的应用场景提供了高效的计算解决方案。