第673章 矩阵乘法无需相乘，速度提升100倍
在一篇被ICML2021接收的论文中，MIT的一位计算机科学博士生及其业界大佬导师为矩阵乘法引入了一种基于学习的算法，该算法具有一个有趣的特性——需要的乘加运算为零。在来自不同领域的数百个矩阵的实验中，这种学习算法的运行速度是精确矩阵乘积的100倍，是当前近似方法的10倍。
矩阵乘法是机器学习中最基础和计算密集型的操作之一。因此，研究社区在高效逼近矩阵乘法方面已经做了大量工作，比如实现高速矩阵乘法库、设计自定义硬件加速特定矩阵的乘法运算、计算分布式矩阵乘法以及在各种假设下设计高效逼近矩阵乘法（AMM）等。
在MIT计算机科学博士生DavisBlalock及其导师JohnGuttag教授发表的论文《MultiplyingMatricesWithoutMultiplying》中，他们为逼近矩阵乘法任务引入了一种基于学习的算法，结果显示该算法显著优于现有方法。在来自不同领域的数百个矩阵的实验中，这种学习算法的运行速度是精确矩阵乘积的100倍，是当前近似方法的10倍。这篇论文入选了机器学习顶会ICML2021。
此外，在一个矩阵提前已知的常见情况下，研究者提出的方法还具有一个有趣的特性——需要的乘加运算（multiply-adds）为零。
这些结果表明，相较于最近重点进行了大量研究与硬件投入的稀疏化、因式分解和/或标量量化矩阵乘积而言，研究者所提方法中的核心操作——哈希、求平均值和byteshuffling结合可能是更有前途的机器学习构建块。
也有网友表示：「这篇论文为实现更高效的AI打开了一扇门。」
对于有网友提到的「该研究在硬件实现方面似乎很有发展前景」，一作本人现身reddit并给出了回复：「我们的编码表示是密集矩阵，所以布局和访问模式看上去基本与GEMM内核相同，也就意味着可以很容易地使用脉动阵列或修正张量核心来实现。在x86上，一般只需要一个vpshufb-add指令和一个4-bit解包指令就可以了。」
具体来说，该研究专注于AMM任务，并假设矩阵是高的（tall），并且相对密集，存在于单个机器内存中。在这种设置下，研究者遇到的主要挑战是在给定保真度水平下最小化近似线性运算所需的计算时间。这种设置会很自然地出现在机器学习和数据挖掘中，当一个数据矩阵A的行是样本，而一个线性算子B希望应用这些样本，B可以是一个线性分类器、线性回归器，或嵌入矩阵，以及其他可能性。
举例来说，考虑一个近似softmax分类器的任务，以预测来自神经网络嵌入的图像标签。在这里，A的行是每个图像的嵌入，B的列是每个类的权值向量。分类是通过计算乘积AB并在结果的每一行中取argmax来执行的。图1结果表明，在CIFAR-10和CIFAR-100数据集上，使用该研究的方法及其最佳性能竞争对手的方法近似AB的结果。
该研究所用方法与传统方法背离，传统的AMM方法构造矩阵V_A，V_B∈R^(D×d)，d<
通常，V_A、V_B是稀疏的，包含某种采样方案，或者具有其他结构，使得这些投影操作比密集矩阵乘法更快。简而言之，这些方法使用线性函数对A和B进行预处理，并将问题简化为低维空间中的精确矩阵乘法。
该研究提出MADDNESS方法，该方法采用非线性预处理函数，将问题简化为查表。此外，在B提前已知的情况下，即将训练好的线性模型应用于新数据等情况时，MADDNESS不需要任何乘-加运算。该方法与用于相似性搜索的矢量量化方法密切相关。然而，该研究没有使用太多的乘-加量化函数，而是引入了一系列不需要乘-加的量化函数。
一个高效的学习矢量量化函数族，可以在单个CPU线程中每秒编码超过100GB的数据。
一种用于低位宽整数（low-bitwidthintegers）的高速求和算法，可避免upcasting、饱和和溢出。
基于这些函数的近似矩阵乘法算法。数百个不同矩阵的实验表明，该算法明显优于现有替代方案。并且还具有理论质量保证。
为了评估MADDNESS的有效性，研究者用c++和Python实现了该算法和其他几个现有算法。评估结果如下。
MADDNESS到底有多快？
研究者首先分析了MADDNESS的原始速度。在图3中，他们为各种矢量量化方法计算g(A)函数的时间，结果表明，MADDNESS比现有方法快两个数量级，其吞吐量随行的长度而增加。
从上图可以看出，Bolt（蓝色虚线）是与MADDNESS最接近的竞争对手。研究者还使用与Bolt相同的基线分析了聚合函数f(·，·)的速度。如图4所示，他们基于average的、matrix-aware的聚合方法明显快于Bolt基于upcasting的方法。
前面说过，研究者在广泛使用的CIFAR-10和CIFAR-100数据集上近似线性分类器。如图5所示，MADDNESS显著优于所有现有方法，几乎达到了与精确乘法相同的准确率，但比精确乘法快了一个数量级。而且，MADDNESS是在硬件支持较差的情况下实现了这种性能。
为了评估该方法在更大、多样性更强的数据集上的表现，研究者在来自UCRTimeSeriesArchive的数据集上训练了kernel分类器。结果如下图6所示，MADDNESS在给定准确率的情况下明显快于替代方案。
为了测试MADDNESS的极限，研究者对将小滤波器应用于图像的各种技术能力进行了基准测试。结果如下图7所示，只有MADDNESS比精确矩阵乘积更有优势。
DavisBlalock是麻省理工学院的博士生，由JohnGuttag教授指导。他的主要研究方向是设计高性能的机器学习算法，以减少人们在机器学习速度、准确性、隐私和安全性之间的妥协。他于2014年获得弗吉尼亚大学学士学位，2016年获得麻省理工学院硕士学位。他是QualcommInnovationFellow、NSFGraduateResearchFellow和BarryM.GoldwaterScholar。
JohnGuttag是麻省理工学院计算机科学与电气工程教授、ACMFellow。他领导着麻省理工学院计算机科学和人工智能实验室（CSAIL）的临床与应用机器组。该小组负责开发和应用先进的机器学习和计算机视觉技术，以解决各种临床相关问题，目前的研究项目包括预测和减少不良医疗事件，帮助患者匹配治疗方法和治疗者，以及医学成像。
。