江苏龙网

  1. 首页 > 资讯 > 科技 > >

##谷歌大脑重磅研究：快速可微分排序算法，速度快出一个数量级

鱼羊 十三 发自 凹非寺 量子位 报道 | 公众号 QbitAI
快排堆排冒泡排 。排序 ， 在计算机中是再常见不过的算法 。
在机器学习中 ， 排序也经常用于统计数据、信息检索等领域 。
那么问题来了 ， 排序算法在函数角度上是分段线性的 ， 也就是说 ， 在几个分段的“节点”处是不可微的 。这样 ， 就给反向传播造成了困难 。
现在 ， 谷歌大脑针对这一问题 ， 提出了一种快速可微分排序算法 ， 并且 ， 时间复杂度达到了O(nlogn) ， 空间复杂度达为O(n) 。
速度比现有方法快出一个数量级！
##谷歌大脑重磅研究：快速可微分排序算法，速度快出一个数量级
文章图片

文章图片

代码的PyTorch、TensorFlow和JAX版本即将开源 。快速可微分排序算法
现代深度学习架构通常是通过组合参数化功能块来构建 ， 并使用梯度反向传播进行端到端的训练 。
这也就激发了像LeCun提出的可微分编程 (differentiable programming)的概念 。
虽然在经验上取得了较大的成功 ， 但是许多操作仍旧存在不可微分的问题 ， 这就限制了可以计算梯度的体系结构集 。
诸如此类的操作就包括排序 (sorting)和排名 (ranking) 。
从函数角度来看都是分段线性函数 ， 排序的问题在于 ， 它的向量包含许多不可微分的“节点” ， 而排名的秩要比排序还要麻烦 。
首先将排序和排名操作转换为在排列多面体(permutahedron)上的线性过程 ， 如下图所示 。
##谷歌大脑重磅研究：快速可微分排序算法，速度快出一个数量级
文章图片

文章图片

△排列多面体说明
在这一过程后 ， 可以发现对于r(θ) ， 若是θ出现微小“扰动” ， 就会导致线性程序跳转到另外一个排序 ， 使得r(θ)不连续 。
也就意味着导数要么为null ， 要么就是“未定义” ， 这就阻碍了梯度反向传播 。
为了解决上述的问题 ， 就需要对排序和排名运算符 ， 进行有效可计算的近似设计 。
谷歌大脑团队提出的方法 ， 就是通过在线性规划公式中引入强凸正则化来实现这一目标 。
这就让它们转换成高效可计算的投影算子(projection operator) ， 可微分 ， 且服从于形式分析(formal analysis) 。
在投影到排列多面体之后 ， 可以根据这些投影来定义软排序(soft sorting)和软排名(soft ranking)操作符 。
##谷歌大脑重磅研究：快速可微分排序算法，速度快出一个数量级
文章图片

文章图片

△软排序和软排名操作符
在此基础上 ， 要想完成快速计算和微分 ， 一个关键步骤就是将投影简化为保序优化 (isotonic optimization) 。
【##谷歌大脑重磅研究：快速可微分排序算法，速度快出一个数量级】##谷歌大脑重磅研究：快速可微分排序算法，速度快出一个数量级
文章图片

文章图片

接下来是将保序优化进行微分 ， 此处采用的是雅可比矩阵(Jacobian) ， 因为它简单的块级结构 ， 使得导数很容易分析 。
##谷歌大脑重磅研究：快速可微分排序算法，速度快出一个数量级
文章图片

文章图片

而后 ， 结合命题3和引理2 ， 可以描述投影到排列多面体上的雅可比矩阵 。
需要强调的是 ， 与保序优化的雅可比矩阵不同 ， 投影的雅可比矩阵不是块对角的 ， 因为我们需要对它的行和列进行转置 。
最终 ， 可以用O(n)时间和空间中的软算子雅可比矩阵相乘 。实验结果


推荐阅读


上一篇：■用现在的技术，“复刻”诺基亚5310，会是什么样子？

下一篇：「电视剧」内容扩充+技术创新，内容服务商才能推进OTT革新