AI 与机器学习2020arxiv.org
快速可微排序与排名
Fast Differentiable Sorting and Ranking
专业 · 约 90 分钟读完前置知识：深度学习与自动微分、凸优化/投影、等渗回归（PAV）
导读
这篇论文研究如何让排序和排名这类离散操作变得可微，从而能在神经网络中端到端训练。作者把排序表述为线性规划/投影问题，并利用等渗回归（isotonic regression）和 PAV 等方法来高效计算可微的软排序与排名。
HN 关注点：HN 读者被“离散排序也能用光滑函数可微且高效实现”的反直觉性吸引，同时讨论它在深度学习中的实际用途和适用场景。
后来怎么样
该论文提出的基于 permutahedron 投影与等渗回归的可微排序/排名方法，成为可微排序研究中的常用基线，并启发了后续可微 top-k、排序损失与可微优化工作。
HN 评论精选
这几条评论里：支持 1 质疑 2 补充 1
补充排序可经 Birkhoff–von Neumann/线性规划表述，若 LP 解可微则排序可微，这是论文的关键背景。
我此前不知道、但可能有助于理解这篇论文的一点是：可以用 Birkhoff–von Neumann 定理巧妙地定义向量排序（涉及双随机矩阵），更好的解释是把排序看成一个线性规划。显然这一点至少半个世纪前就已知。不过，如果线性规划的解能以可微方式求出，那么排序操作也就可以是可微的。这似乎是论文的诀窍，而且他们似乎也有相对快速的计算方法，我觉得很有意思。
kxyvr查看英文原文
Something that I didn't know, and may help others understand this paper better, is that there's a way to define the sorting a vector through the creative use of the Birkhoff–von Neumann theorem: https://en.wikipedia.org/wiki/Doubly_stochastic_matrix which is better explained here: https://cs.stackexchange.com/questions/4805/sorting-as-a-linear-program where the sorting operation is defined as a linear program. Evidently, this has been known for at least half a century. That said, if a solution to a linear program can be found in a way that's differentiable, this means that the operation of sorting can be found to be differentiable as well. This appears to be trick in the paper and they appear to have a relatively fast way to compute this solution as well, which I think is interesting.
质疑实际用途存疑：阈值预排序/分位数近似/比较损失常够用，精确可微排序只在中等 n 的甜点区有意义。
论文引用：“虽然我们的软算子比 OT 快数小时，但比 All-pairs 慢，尽管后者是 O(n^2)；这是因为 n=100 时 All-pairs 在 GPU 上非常高效，而我们的 PAV 实现跑在 CPU 上。”论文有趣，但还不确定实际用途。我实践中需要可微排序时，通常先做阈值预排序（只保留分数高于常数、最佳分数某比例或第 K 名的值），然后在 n=10 或 20 时付出二次代价。我看不出垃圾结果之间的排名相关性真的重要。n 变大且不想忽略差结果时，通常分位数近似就够。在他们引用的应用里：6.4 节用 Huber loss 对阈值做交叉验证，在他们自己的图中 3 次有 2 次更好；其他顺序重要的用例（如 6.3 节排名作为输入），n 小时付二次代价，n 大时通常因内存逐子集处理样本并用 triplet loss 等比较损失。所以只有需要精确计算且 n 处于中间甜点区时才相关。
GistNoesis查看英文原文
>"While our soft operators are several hours faster than OT, they are slower than All-pairs, despite its O(n^2)complexity. This is due the fact that, with n= 100, All-pairs is very efficient on GPUs, while our PAV implementation runs on CPU" Paper is interesting but not yet sure of practical uses. The trick I use in practice when I need a differentiable sort, is usually a pre-sort step which involves thresholding (i.e. selecting with sparsity only values greater than a certain score (usually either a constant, or a fraction of the best score, or the Kth score ) ). Then pay the quadratic price with n=10 or 20. I don't see when the relevance of rank between garbage results would really matter. When n get bigger and you don't want to ignore bad results, usually quantile approximations suffice. In the applications they cite : The smart use (cross-validation) of threshold by the Huber loss in section 6.4 works better 2 out of 3 times in their own graphs). The other use cases when order matters (for example like in section 6.3 is where the rankings are given as input). If n is low you pay the quadratic cost, if n is high you usually need to process samples a subset at a time for memory reasons and use some comparison losses (triplet loss...). So this is relevant only in the sweet spot in between if you need exact calculations.
质疑赞叹可微排序的反直觉性，但质疑其深度学习意义，并询问梯度信息量和高阶导数。
我觉得这篇论文很酷，也很反直觉：像排序这样离散的操作竟能完全用光滑函数完成，而且效率还高。但我必须承认没有完全理解其影响。为什么深度学习首先真的需要可微排序？它打开了什么新可能？我不专业的猜测是：可微排序产生的梯度比普通分段排序更有信息量，让梯度下降进展更快、训练更快。（想想解析函数可由任意小邻域完全确定；这些排序函数也是解析的吗？）我的直觉是，这种技术产生的导数让优化器能看到跨类的真实梯度。这里高阶导数也有意义吗？
etaioinshrdlu查看英文原文
I find this paper super cool, and highly unintuitive that an operation as discrete as sorting can be done entirely with smooth functions, and efficiently to boot. However I must admit that I do not fully grasp the implications of this paper. Why do we really need differentiable sorting for deep learning in the first place? What new possibilities open up as a result? My best uneducated guess is that the gradients produced by differentiable sorting are more informative than regular piecewise sorting, and this allows the gradient descent to progress faster, therefore training faster. (Think about how you can know an entire analytic function can be completely known from any small neighborhood. Are these sorting functions analytic too?) My intuition tells me that the derivatives produced with this technique allow the optimizer to see true gradients across classes. Are higher order derivatives also meaningful here?
支持关注几何投影+等渗优化实现，并追问该算法作为传统排序算法到底在做什么。
嗯，我只粗略读了论文，但看起来确实很酷。我不会想到通过几何投影到一个极其巨大的多边形上实现排序，再把该投影转化为等渗优化（isotonic optimization）来优化。我不确定我的几何功力足以理解方法细节。不过我有一个问题：如果把它当作传统排序算法而非几何操作来分析，得到的算法实际在“做”什么？
quotemstr查看英文原文
Huh. I've only read the paper superficially, but it definitely looks cool. I wouldn't have thought to implement sorting by geometric projection onto an unfathomably huge polygon, then optimizing the projection by transforming it into isotonic optimization ([1], apparently?). I'm not sure my geometry-fu is strong enough to properly understand the details of the approach. I do have one question though: what is the resulting algorithm actually "doing" when analyzed as a conventional sorting algorithm and not a geometric operation? [1] https://en.wikipedia.org/wiki/Isotonic_regression
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2020Hacker News 讨论帖263 分 · 41 评
同领域还值得读
DeepSeek-R1：通过强化学习激励 LLM 的推理能力
DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via RL
研究如何用强化学习激励大语言模型的推理能力，提出 DeepSeek-R1，并探讨 RL 训练对模型推理表现的影响。
AI 与机器学习2025 · 1,351 分 · 1,056 评 · 引用 30进阶 · 约 80 分钟编辑精选1-bit LLM 时代：面向低成本计算的三值参数
The Era of 1-bit LLMs: ternary parameters for cost-effective computing
提出用三值参数 {-1, 0, 1} 替代 LLM 中的浮点权重，即所谓“1-bit LLM”。
AI 与机器学习2024 · 1,040 分 · 447 评 · 引用 19进阶 · 约 45 分钟编辑精选DeepSeek-V3.2：推进开放大语言模型的前沿
DeepSeek-v3.2: Pushing the frontier of open large language models
这是 DeepSeek-V3.2 的技术报告，延续了 DeepSeek 开源权重模型的路线，目标是让开放模型继续逼近甚至追平前沿闭源模型。
AI 与机器学习2025 · 982 分 · 465 评进阶 · 约 90 分钟编辑精选通过自我对弈与通用强化学习掌握国际象棋和将棋（AlphaZero）
Mastering Chess and Shogi by Self-Play with General Reinforcement Learning
DeepMind 的 AlphaZero 论文：用通用强化学习算法（自我博弈 + MCTS + 神经网络），从零开始仅数小时训练便在国际象棋和将棋上击败了世界顶级引擎 Stock…
AI 与机器学习2017 · 539 分 · 270 评 · 引用 13进阶 · 约 90 分钟编辑精选用强化学习发现更快的矩阵乘法算法
Discovering faster matrix multiplication algorithms with reinforcement learning
论文提出 AlphaTensor，用强化学习搜索矩阵乘法算法。
AI 与机器学习2022 · 518 分 · 111 评专业 · 约 90 分钟编辑精选