作者介绍： Davis Blalock :麻省理工的博士生，由John Guttag教授指导。 主要的研究方向是设计高性能的机器学习算法以减少机器学习速度、准确性、隐私和安全性的妥协。 John Guttag :领导麻省理工学院计算机科学与电气工程教授、ACM Fellow、麻省理工学院计算机科学与人工智能实验室(CSAIL )的临床与应用机械小组。 该小组负责开发和应用先进的机器学习和计算机视觉技术，解决各种临床相关问题。
矩阵乘法是机器学习中最基本、计算量最大的操作之一，因此其速度对整个机器学习算法的速度至关重要。 于是，研究者在零乘法加法的基础上，提出了以混合hldhb、平均和字节变换为中心的新算法，其运行速度比正确的矩阵积几乎快100倍，比现有的所有近似方法快约10倍。
算法背景
该算法基于内积量化算法(Product Quantization )，简称PQ，是典型的矩阵内积和个性相近的犀牛距离的矢量量化算法，几乎是所有类似方法的基础。 该算法基于具有小而特殊的结构以便内积可以高速计算的想法。 PQ算法具体分为以下四个步骤。
一、原型学习(Prototype Learning )。
作为训练集，k是各子空间的原型数，c是多个子空间，是与各子空间相关联的互斥的、集合详细的索引集。 PQ的训练任务是学习和最小化c组的原型和分配。 这是通过在每个子空间中单独执行k均值算法，然后使用生成的重心和赋值填充和来实现的。
二、编码函数(编码函数)。
给出学习的原型后，PQ将a的各行a替换为各c子空间的k均值重心分配。 形式将得到的索引序列称为a的代码，将k重心集作为码本。
三、制作表格(表格构造) )。
使用这些相同的原型，PQ算法在b的各列b的各c部分空间中构建了查找表。 其中，研究人员的实验表明，将K=16和查找表量化为8位将带来较大的加速。
四、聚合(Aggregation ) )。
给出a的编码和b的查找表，可以直观地理解乘积，近似如下图所示。 g () )函数返回与各子空间中的数据向量a最类似的原型的索引。 h ()函数计算查询向量b和各子空间内的各原型之间的点积的查找表。 聚合函数f (，) )按索引汇总相应的表条目。
图1 (文献[1]的图表2 ) )。
作者基于PQ算法，引入了新的g(a )函数，使得即使是更小的矩阵也能进行较大的加速。 这个函数背后的主要思想是通过局部敏感的散列来确定“最相似”的原型。 也就是说，该算法计算子向量和各个原型之间的欧几里德距离，并不选择最接近的原型作为近似，而是散列为倾向于散列到同一bucket的K-buckets (实际上是k比特的散列值) 将“原型”(prototype )设定为散列到同一bucket的子向量的平均值。
基于这一想法，研究者试图采用训练集，但同时希望的工作远远少于线性变换。 结果表明，现有的hldhb函数不满足要求。 因此，作者设计了自己可以训练的哈雷函数族。 所选出的hldhb函数家族是平衡二叉回归树，树的各叶节点为一个hldhbbucket。 如果索引j的值低于节点特定的阈值v，则通过从根目录遍历树并将其移动到左侧的子节点来选择向量x的叶。 右边的子节点也一样。 算法1如下所示。
算法1
从形式上看，考虑4个指标和4个分割阈值数组的集合，vt的长度为。 该算法将向量x映射到哈希值索引。 该函数仅依赖于输入向量中的常数的索引，只要编码后的行矩阵按照列的主顺序存储，就能够容易地进行向量化。
进一步通过算法2学习hldhb函数的参数，分割指数和分割阈值利用贪婪树构造算法对训练矩阵进行了优化。为了描述这个算法，研究者引入了bucket()的概念，它是在树的t级（对应平衡二叉回归树节点的深度）中映射到节点i（同一深度的某个节点）的向量集。树的根是0级，包含所有的向量。定义误差(SSE)损失的平方和如下：算法2如下：
算法2
对原型进行优化
研究者并没有直接将基于hldhb的编码函数放到PQ和近似矩阵积中，而是提供了两种额外的改进方法：一种无运行时开销的原型优化方法，以及一种快速求和低比特宽整数的方法。
一、选择原型
设是一个矩阵，其大小为的对角线块由每个子空间c中的K个学到的原型组成。训练矩阵可以近似地重建为，其中G可以在每个子空间中选择合适的原型。G的行通过连接对应一行的每个分配的一个one-hot编码表示而形成。现在需要在G和的条件下优化P。这是一个普通的最小二乘问题，可以用岭回归来解决：岭回归中可以通过交叉验证找到λ来获得更好的性能，文中为了简单起见，固定λ=1。
二、快速8位汇集 设为B中所有M列的查找表的张量。给定编码G，将函数定义为：在非饱和加法指令的情况下, 因为T的条目存储为8位值，所以在执行任何求和指令之前如果立即将每个查找条目上转换到16位，将导致其存取吞吐量是直接用8位值的一半。因此该方法求和过程不使用additional指令，而是采用averaging指令，如此做法之后计算结果造成的精度损失将发生在低bit位而非高bit位，整体误差会变大，但计算速度大大提升，即选择牺牲少量的准确性来显著提高速度。
MADDNESS 到底有多快？
研究者首先分析了MADDNESS的原始速度。他们为各种矢量量化方法计算 g(A) 函数的时间，结果表明，MADDNESS 比现有方法快两个数量级，其吞吐量随矩阵行的数量而增加。
且如下图所示，MADDNESS的速度几乎是 Bolt（上图蓝色虚线）的两倍：
在广泛使用的 CIFAR-10 和 CIFAR-100 数据集上和近似Softmax线性分类器的对比也可以看出，MADDNESS 实现了比任何现有方法更好的速度精度权衡：
进一步，为了评估该方法在更大、多样性更强的数据集上的表现，研究者在来自UCR的Time Series Archive 数据集上训练了kernel分类器。结果表明，MADDNESS 在给定准确率的情况下明显快于其他方案：
为了测试MADDNESS的极限，研究者对将小滤波器应用于图像的各种技术能力进行了基准测试。结果表明，只有 MADDNESS 比精确矩阵乘积更有优势：
参考文献
[1] Blalock, D. & Guttag, J. (2021). Multiplying Matrices Without Multiplying (cite arxiv:2106.10860Comment: To appear at ICML 2021)