学习排序算法的情况

我们已经看到机器学习彻底渗透到网络巨头，在大型消费者公司取得了重大进展，并开始向传统企业推进。因此，ML正迅速成为我们构建各种形状和大小的应用程序不可或缺的一部分。但是系统软件呢？这还是早期的事情，但是“学习索引结构的案例”(第1部分，第2部分)、SageDB和其他公司正在为我们指明方向。

今天的论文选择建立在SageDB所做工作的基础上，并集中在一个经典的计算机科学问题上：排序。在10亿个项目的数据集上，Learned Sort的性能比第二好的竞争对手RadixSort高出1.49倍。真正让我大吃一惊的是，这个结果包括训练使用的模型所花费的时间！

假设您有一个模型，该模型给定一个列表中的数据项，可以预测它在该列表的排序版本中的位置。0.239806？它将在287号位置！如果模型有100%的准确率，那么只需遍历数据集并将每个项目放到其预测位置，就可以给我们一个完整的排序。不过，这有个问题。一个100%准确率的模型基本上必须看到整个数据集中的每一项并记住它的位置-没有办法训练，然后使用这样的模型比仅仅排序更快，因为排序是其训练的一部分！但也许我们可以通过学习对CDF(累积分布函数)的近似，来采样数据的子集，并得到一个有用的近似模型。

如果我们可以快速构建这样一个模型的足够有用的版本(我们可以，我们稍后将讨论如何构建)，那么我们可以通过以下方式进行快速排序：首先扫描列表，使用模型的预测将每一项放到其近似位置，然后使用与接近排序的数组配合良好的排序算法(插入排序)将几乎排序的列表转换为完全排序的列表。这就是学问分类的本质。

学习排序的基本版本是位置不正确的排序，这意味着它将排序的元素复制到新的目标数组中。它使用该模型为列表中的每一项预测目标数组中的槽。但是，如果模型预测(例如)插槽287，但该插槽的目标数组中已经有一个条目，该怎么办呢？这是一次碰撞。候选解决方案包括：

溢出桶：如果目的地槽已经满了，只需将物品放入一个特殊的溢出桶中即可。在传递结束时，将溢出桶与目标数组排序并合并。

作者对这三种方法都进行了实验，发现溢油桶方法对他们最有效。

最终的性能取决于模型预测的质量，更高质量的模型导致更少的冲突，以及在最终插入排序过程中要修补的无序项目更少。由于我们目前只讨论模型的细节，一个有趣的问题是，当您为这种学习过的类型提供一个完美的、零开销的先知作为模型时会发生什么？假设我们要对从0到10亿的所有数字进行排序。只需将项值作为位置预测，就可以建立一个完美的零开销预言书。1456？它将放在1456年…的位置

当作者试图使用这个完美的零开销神谕对数字进行排序时，发生了什么？

令我们惊讶的是，在这个微型实验中，我们观察到，尽管使用了零开销的Oracle函数，但将密钥分发到其最终排序位置所需的时间为38.7秒，RadixSort为37.5秒。

为什么？如果你追求的是高性能，你不能忽视机械的同情。基数排序经过精心设计，可有效利用二级缓存和顺序内存访问，而学习排序则在目标数组中进行随机访问。

如何调整学习排序以使其缓存效率更高？解决方案是将学习排序的第一遍更改为级联桶排序。不是确定目标数组中的最终位置，而是使用模型预测来确定元素应该进入哪个桶(或桶)。

假设$f$是存储桶的数量($f$用于扇出)。学习排序的第一阶段是级联桶排序。第一次传递使用模型预测将输入元素放入$f$有序存储桶中的一个。然后，这些存储桶中的每个都被分成另外的$f$存储桶，依此类推，直到达到阈值存储桶大小$t$。如果在任何阶段，模型预测放置在已经满的桶中的项中，则该项只是被移到溢出桶中。

一旦我们到达大小为$t$的存储桶，就会使用模型预测对每个存储桶进行大致排序，以便将元素放置在存储桶中准确的预测位置。

按顺序连接已排序的存储桶(有些存储桶中的元素可能少于$t$)，并使用插入排序来修补排序中的任何差异。

使用学习排序获得良好性能的秘诀是选择$f$和$t$，这样每个存储桶中至少有一个缓存线可以放入缓存中，从而使内存访问模式更加顺序化。设置$f$的权衡如下：较大的$f$允许我们在每一步更多地利用模型的预测能力，较小的$f$增加了我们可以在不导致缓存未命中的情况下附加到给定存储桶的机会。为获得最佳性能，应设置$f$，以便所有热内存位置都能放入二级缓存中。对于评估设置来说，这意味着$f$大约是1,000美元。

参数$t$影响可能在溢出桶中结束的元素的数量。经验性地，作者发现，当少于5%的元素最终出现在溢出桶中时，获得最大性能，这相当于对于大型数据集来说，$t$约为100(见§3.1.2)。

有了这些更改后，如果要排序的元素数量接近键域大小(例如，使用32位键对$2^{32}$元素进行排序)，则学习排序的执行方式与基数排序几乎相同。但当元素数远小于键域大小时，Learne排序的性能明显优于基数排序。

当然，所有这一切都依赖于能够训练出足够精确的模型，该模型可以做出足够快的预测，以便学习排序的总运行时间(包括训练时间)仍然胜过基数排序。为此，作者使用了递归模型索引(Recursive Model Index，RMI)体系结构，如“学习索引结构的情况”中首次介绍的那样。简而言之，RMI使用层次分明的简单线性模型，有点像专家的混合体。

在推理过程中，模型的每一层都将关键字作为输入，并对其进行线性变换以获得一个值，该值用作选择下一层模型的索引。

作者在这里介绍的主要创新是使用线性样条拟合进行训练(而不是使用MSE损失函数的线性回归)。样条曲线拟合的计算成本更低，单调性更好(减少了插入排序阶段所花费的时间)。每个单独的样条线模型比其闭合形式的线性回归模型拟合得更差，但层次会进行补偿。线性样条的训练速度提高了2.7倍，在插入排序过程中最多减少了35%的键交换。

在包含服从标准正态分布的双精度键的合成数据集上，作者将学习的排序与各种缓存优化和高度调优的替代排序算法的C++实现进行了比较，在结果中呈现了最具竞争力的替代算法。下图显示了输入数据集大小(从100万到10亿个项目)的排序率。

学习排序在所有大小上都优于备选排序，但当数据不再适合L3缓存时，优势最为显著-平均吞吐量比次优算法高30%。

结果表明，与优化的快速排序混合算法C++STL Sort相比，我们的方法平均提高了3.38倍的性能，比顺序基数排序提高了1.49倍，比Java和Python的默认排序函数Tim-Sort的C++实现提高了5.54倍。

与真实数据集相比，学习排序的优势同样存在(§6.1适用于测试中包含的数据集)，并且适用于不同的元素类型：

与竞争最激烈、使用最广泛的排序算法相比，[学习排序]带来了显著的性能改进，并标志着在构建ML增强的算法和数据结构方面迈出了重要的一步。

本文还描述了学习排序的几个扩展，包括就地排序、对其他键类型(初始为字符串)进行排序，以及提高包含许多重复项的数据集的性能。