本文经AI新媒体量子位（公众号ID：QbitAI）授权转载，转载请联系出处。可以在没有乘加的情况下计算矩阵乘法吗？矩阵乘法包含大量的a+b×c运算，因此常将乘法器和加法器组合成一个计算单元进行乘法和累加运算。使用近似算法，它确实如此！这是麻省理工学院的最新研究。他们提出了一种新的逼近算法MADDNESS，在保证一定精度的情况下，将速度提高到现有逼近算法的10倍，比精确算法快100倍。它被ICML2021收录。该研究还认为，新算法可能比最近流行的稀疏化、因式分解等操作更有前途。目前，作者已经开源了算法代码，感兴趣的朋友可以尝试一下。让我们来看看。使用K聚类算法创建查找表的算法借用了一种称为ProductQuantization的方法。其中，量化本质上是一种近似运算。由于矩阵乘法中的每个元素都可以看作是两个向量的点积，因此可以通过寻找相似的向量来近似向量的点积，而无需进行大量的乘法运算。乘积量化的具体原理如下：当我们输入一个待计算的向量a时，函数g(·)会对a进行逼近运算，从预先设定的数值查表值中找到最接近它的那个,并输出一个近似向量g(a)。同时，这个表中的每一个值都已经预先计算好了，所以在输出g(a)的同时，也可以查到查询向量（queryvector）b(b)对应的近似点积计算结果h，输出。最后，您只需要使用f(·,·)函数将g(a)和h(b)相加，而不是将它们相乘。简单来说，就是通过近似查表的方式，节省了矩阵乘法中乘法的计算时间。那么，这样的数值查找表应该设置什么值，才能保证近似计算过程中计算精度的损失最小呢？这里参考一下K-means的思想，就是将数据预先分成K组，随机选择K个对象作为初始聚类中心，然后通过迭代训练保证样本被分成K个类。当时，每个样本与其类中心的距离之和最小。△可视化K聚类算法该方法计算的数值查找表可以更准确地逼近矩阵乘法的数值计算结果。基于这个想法，作者提出了一种高效的向量乘积量化函数，可以在单个CPU中每秒编码超过100GB的数据；同时，他们还提出了一种用于低位宽整数的高速求和函数。然后，基于这两类函数，开发了一套新的矩阵乘法算法MADDNESS。这个近似算法有多有效？保持准确性，效率提高数倍。该算法对计算能力要求不高，在搭载英特尔酷睿i7-4960HQ（2.6GHz）处理器的MacbookPro上即可完成。他们在Keras版本的VGG16模型上进行测试，使用的数据集为CIFAR-10/100，评估了一系列最新的近似算法：从图中可以看出，在效率提升近10倍的情况下，使用MADDNESS（红色图中的线）在CIFAR-10上仍然可以保持几乎不变的精度。即使在CIFAR-100上，在精度几乎不变的情况下，MADDNESS和MADDNESS-PQ也达到了效率最大化的结果。除了最新的算法外，与现有的其他算法（包括作者在2017年提出的Bolt算法）相比，效果也非常突出。比较计算速度，MADDNESS的点积速度可以比现有最快的方法快两倍左右。当然，也有读者指出，本文还存在一些需要解决的问题：①论文采用了VGG16模型，但并未在Transformer等更经典的模型（如BERT）中进行测试；②虽然矩阵乘法得到了加速，但毕竟只是一种近似算法，有潜在的精度损失；③评估结果未在GPU中测试。但他仍然认为这是一项非常有趣的研究。作者介绍了DavisBlalock，他是麻省理工学院计算机科学系的博士生，致力于开发快速机器学习算法。他认为速度是衡量机器学习模型的一个非常重要的因素。麻省理工学院计算机科学系教授JohnGuttag研究机器学习、人工智能和计算机视觉。他目前的研究项目主要集中在医学人工智能和医学影像。值得一提的是，这两位研究者此前曾炮轰过神经网络中的剪枝算法。他们对其中的81种算法进行了横向比较，发现“没有明确的证据表明这些算法在10年内显着提高了任务性能”。该研究的第一作者DavisBlalock也认为，这些改进是所谓的“微调”，而不是研究人员所宣称的“核心创新”，有些改进方法可能根本不存在。两位作者在提高AI模型的效率上确实非常严格。项目地址：https://github.com/dblalock/bolt论文地址：https://arxiv.org/abs/2106.10860
