GoogleBrain的主要研究：FastDifferentiableSortingAlgorithm，快一个数量级的Quickrow，heaprow，bubblingrow。排序是计算机中极为常见的算法。在机器学习中，排序也常用于统计、信息检索等领域。那么问题来了，排序算法在函数上是分段线性的，即在几个分段“节点”处不可微。这使得反向传播变得困难。现在，谷歌大脑针对这个问题提出了一种快速可微分排序算法，时间复杂度达到了O(nlogn)，空间复杂度达到了O(n)。比现有方法快一个数量级！PyTorch、TensorFlow和JAX版本的代码将很快开源。快速可微分排序算法现代深度学习架构通常是通过组合参数化功能块构建的，并使用梯度反向传播进行端到端训练。这也启发了LeCun提出的可微分编程（differentiableprogramming）的概念。尽管在经验上是成功的，但许多操作仍然是不可微分的，这限制了可以计算梯度的架构集。此类操作包括排序和排名。从函数的角度来看，它们都是分段线性函数。排序的问题在于它的向量中包含很多不可微的“节点”，排名的等级比排序更麻烦。首先将排序和排名操作转化为置换面体上的线性过程，如下图所示。△排列多面体表明，经过这个过程可以发现，对于r(θ)，如果θ有轻微的“扰动”，就会导致线性规划跳到另一排序，使得r(θ)不连续.这意味着导数为空或“未定义”，这会阻止梯度反向传播。为了解决上述问题，需要一种高效且可计算的排序和排序算子的近似设计。GoogleBrain团队提出的方法通过在线性规划公式中引入强凸正则化来实现这一点。这将它们变成了高效且可计算的投影算子，这些投影算子是可微分的并且可以进行形式分析。在对置换多面体进行投影后，可以根据这些投影定义软排序和软排序算子。△Softsortingandsoftrankingoperators在此基础上，要完成快速计算和微分，一个关键步骤是将投影简化为等渗优化。下一步是区分保序优化。这里使用的是雅可比矩阵（Jacobian），由于其块级结构简单，导数容易分析。然后，结合命题3和引理2，可以描述投影到置换多面体上的雅可比矩阵。需要强调的是，与保序优化雅可比行列式不同，投影雅可比行列式不是块对角线，因为我们需要转置其行和列。最后，可以在O(n)时间和空间中使用软运算符进行雅可比矩阵乘法。实验结果研究人员在CIFAR-10和CIFAR-100数据集上进行了实验。实验中使用的CNN包含4个Conv2D，2个最大池化层，RelU激活，2个全连接层；ADAM优化器的步长恒定为10-4，k=1。与O(Tn2)的OT方法和O(n2)的All-pairs方法相比。△rQ和rE是新算法的结果。结果表明，新算法在CIFAR-10和CIFAR-100上取得了与OT方法相同的精度，而且速度明显更快。在CIFAR-100上训练600个epochs，OT耗时29小时，rQ耗时21小时，rE耗时23小时，All-pairs耗时16小时。CIFAR-10上的结果相似。在检查输入大小对运行时间的影响时，研究人员使用了具有64GBRAM的6核英特尔至强W-2135和GeForceGTX1080Ti。禁用反向传播时，计算一批，OT和All-pairs分别在n=2000和n=3000时内存不足。当启用反向传播时，OT和All-pairs分别在n=1000和n=2500时耗尽内存。开辟新的可能性曾在谷歌和NASA工作过的机器学习工程师BradNeuberg认为，从机器学习的角度来看，快速可微排序和排序算法似乎非常重要。而谷歌新的排序算法也在reddit、黑客新闻等平台上引起热议。有网友更详细地讨论了它带来的“新的可能性”：我认为可微分排序产生的梯度信息量更大，使得梯度下降更快，可以进一步提高训练速度。我认为这意味着某些基于排名的指标以后可以以可区分的形式表示。也就是说，神经网络可以很容易地直接针对这些结果进行优化。对于谷歌，这显然适用于网络搜索，以及标签分配之类的事情。也有网友指出，该算法虽然不是第一个解决排序不可微问题的方法，但其效率无疑更高。门户论文：https://arxiv.org/pdf/2002.08871.pdf讨论：https://news.ycombinator.com/item?id=22393790https://www.reddit.com/r/MachineLearning/comments/f85yp4/r_fast_differentiable_sorting_and_ranking/
