借一步网
作者：
在
在机器学习和数据挖掘的世界里，Top-k操作（即从一组分数中找出前k大的元素）就像是某种“暗黑魔法”。它广泛应用于信息检索、图像分类、神经网络翻译等任务中，举个简单的例子，比如在图像检索中，我们经常需要找到与输入图像距离最近的k个邻居。然而，问题来了，尽管Top-k操作很常见，但它本质上是不可微的，这意味着我们无法用常见的梯度下降等方法来训练包含Top-k操作的模型。就如同试图在一颗布满尖刺的仙人掌上跳舞，Top-k的“指数交换”和“离散映射”让生成平滑的梯度简直比登天还难。
想象一下，你在比较两个分数和，Top-1操作会返回一个二进制的向量，告诉你哪个分数大。假设，那么输出是，否则是。但是，一旦和几乎相等，Top-1的输出会突然从跳到，这就是我们常说的不连续性。梯度在这里就像一个“开关”，要么全有要么全无，完全不给你过渡的空间。这种非连续性严重限制了常见的端到端训练方法。
为了绕过Top-k的不可微性，现有的做法通常采用“先分蛋再炒蛋”的策略，也就是先用某种替代损失函数（比如交叉熵）训练模型，然后在预测阶段用Top-k做最终决策。这种两阶段训练方法虽然可行，但却引发了另一个问题：训练和预测之间的不匹配。就像你教会了厨师如何煮水煮蛋，但最后却要他去炒一个鸡蛋，效果可想而知。
如何解决这个问题呢？Xie等人提出了一种名为SOFT（Scalable Optimal Transport-based Differentiable）Top-k操作的解决方案。这个操作基于一种叫做熵正则化最优传输（Entropic Optimal Transport, EOT）的问题，通过引入熵正则化来平滑化Top-k操作，使其可微分。
Top-k操作可以被重新表述为一个最优传输问题。在这个框架下，我们的目标是将一组输入分数映射到一个二进制集合（即Top-k集合的指示向量），通过最小化传输代价来找到最佳传输方案。尽管这种重新表述依旧不可微，但通过加入熵正则化，我们可以将其平滑化，使得Top-k操作能够近似为一个可微的运算。
我们可以通过下图更直观地理解这一过程：
graph LR A[输入分数] B[Top-k操作] C[最优传输] D[熵正则化] E[平滑Top-k输出] A --> B --> C --> D --> E
在这个图中，原始的Top-k操作通过最优传输问题转化为一种离散的映射，再通过熵正则化将其平滑化，最终得到一个可微的近似Top-k输出。
为了验证SOFT Top-k算子的有效性，研究人员分别将其应用于k最近邻分类和神经机器翻译中的Beam Search。
在经典的kNN分类问题中，SOFT Top-k算子被嵌入到神经网络中，使得整个kNN过程可以端到端地训练。实验结果表明，SOFT Top-k不仅提高了kNN分类的准确率（在MNIST和CIFAR-10数据集上分别达到了99.4%和92.6%），还解决了两阶段训练中预测与训练不匹配的问题。
在神经机器翻译的Beam Search过程中，传统的Beam Search只能在解码阶段使用，无法直接参与训练。而通过SOFT Top-k算子，研究人员将Beam Search集成到了训练过程中，显著提高了翻译任务的BLEU分数。
SOFT Top-k的梯度可以通过最优传输问题的KKT条件（Karush-Kuhn-Tucker条件）高效推导出来。具体来说：
其中，是最优传输矩阵，是传输成本矩阵，是熵正则化参数， 和 是对偶变量。通过这个公式，我们可以高效地计算SOFT Top-k操作在每个迭代步骤的梯度。
SOFT Top-k操作为Top-k问题的可微分性提供了一种优雅的解决方案，它通过最优传输和熵正则化成功将离散、跳跃的Top-k操作平滑化，使其能够融入到端到端的训练流程中。这不仅为kNN分类和Beam Search等经典算法带来了显著的性能提升，还为未来更多涉及Top-k操作的任务提供了新的思路。
未来，随着SOFT Top-k操作的进一步发展和优化，我们有理由相信，这种创新方法将会在更多领域中展现出其潜力，推动机器学习和数据挖掘领域的进一步进步。
四、实验验证 图像分类任务：将 SOFT Top-k 操作应用于图像分类任务中，实验结果显示，SOFT Top-k 操作使得 kNN 分类器的准确率比传统方法提高了近 2%。 k 近邻分类任务：使用 GradTopK 操作进行 k 近邻分类，结果表明该操作能够提供有效的梯度信息，从而实现端到端的训练。 五、结论与展望 可微分 Top-k 操作为解决经典 Top-k 操作不可微分问题提供了一种有效的解决方案，通过引入最优传输和熵正则化等方法，使得 Top-k 操作能够嵌入到深度学习模型中进行端到端训练。未来，随着可微分 Top-k 操作的进一步发展和优化，其有望在更多领域中得到应用和推广。 Read less
OT 最小传输问题，是非常经典的一个优化问题
两阶段方法，问题多
要发表评论，您必须先登录。
🎯 引言：Top-k操作为何让人头疼？
在机器学习和数据挖掘的世界里，Top-k操作（即从一组分数中找出前k大的元素）就像是某种“暗黑魔法”。它广泛应用于信息检索、图像分类、神经网络翻译等任务中，举个简单的例子，比如在图像检索中，我们经常需要找到与输入图像距离最近的k个邻居。然而，问题来了，尽管Top-k操作很常见，但它本质上是不可微的，这意味着我们无法用常见的梯度下降等方法来训练包含Top-k操作的模型。就如同试图在一颗布满尖刺的仙人掌上跳舞，Top-k的“指数交换”和“离散映射”让生成平滑的梯度简直比登天还难。
🚧 Top-k的“不可微”困境
🥥 硬壳问题：跳跃的非连续性
想象一下，你在比较两个分数
和
，Top-1操作会返回一个二进制的向量，告诉你哪个分数大。假设
，那么输出是
，否则是
。但是，一旦
和
几乎相等，Top-1的输出会突然从
跳到
，这就是我们常说的不连续性。梯度在这里就像一个“开关”，要么全有要么全无，完全不给你过渡的空间。这种非连续性严重限制了常见的端到端训练方法。
🍳 “炒蛋式”解决方案：两阶段训练
为了绕过Top-k的不可微性，现有的做法通常采用“先分蛋再炒蛋”的策略，也就是先用某种替代损失函数（比如交叉熵）训练模型，然后在预测阶段用Top-k做最终决策。这种两阶段训练方法虽然可行，但却引发了另一个问题：训练和预测之间的不匹配。就像你教会了厨师如何煮水煮蛋，但最后却要他去炒一个鸡蛋，效果可想而知。
🧪 软化Top-k的“魔法”：SOFT Top-k算子
如何解决这个问题呢？Xie等人提出了一种名为SOFT（Scalable Optimal Transport-based Differentiable）Top-k操作的解决方案。这个操作基于一种叫做熵正则化最优传输（Entropic Optimal Transport, EOT）的问题，通过引入熵正则化来平滑化Top-k操作，使其可微分。
🔑 核心思路：从最优传输到平滑Top-k
Top-k操作可以被重新表述为一个最优传输问题。在这个框架下，我们的目标是将一组输入分数映射到一个二进制集合（即Top-k集合的指示向量），通过最小化传输代价来找到最佳传输方案。尽管这种重新表述依旧不可微，但通过加入熵正则化，我们可以将其平滑化，使得Top-k操作能够近似为一个可微的运算。
🎨 可视化理解：从硬到软的转变
我们可以通过下图更直观地理解这一过程：
在这个图中，原始的Top-k操作通过最优传输问题转化为一种离散的映射，再通过熵正则化将其平滑化，最终得到一个可微的近似Top-k输出。
🚀 实验验证：SOFT Top-k真的有效吗？
为了验证SOFT Top-k算子的有效性，研究人员分别将其应用于k最近邻分类和神经机器翻译中的Beam Search。
🍎 k最近邻分类中的应用
在经典的kNN分类问题中，SOFT Top-k算子被嵌入到神经网络中，使得整个kNN过程可以端到端地训练。实验结果表明，SOFT Top-k不仅提高了kNN分类的准确率（在MNIST和CIFAR-10数据集上分别达到了99.4%和92.6%），还解决了两阶段训练中预测与训练不匹配的问题。
🚀 Beam Search中的应用
在神经机器翻译的Beam Search过程中，传统的Beam Search只能在解码阶段使用，无法直接参与训练。而通过SOFT Top-k算子，研究人员将Beam Search集成到了训练过程中，显著提高了翻译任务的BLEU分数。
🔍 数学推导：SOFT Top-k的梯度计算
🧮 梯度计算公式
SOFT Top-k的梯度可以通过最优传输问题的KKT条件（Karush-Kuhn-Tucker条件）高效推导出来。具体来说：
其中，
是最优传输矩阵，
是传输成本矩阵，
是熵正则化参数，
和
是对偶变量。通过这个公式，我们可以高效地计算SOFT Top-k操作在每个迭代步骤的梯度。
🎉 结论与展望：从理论到应用
SOFT Top-k操作为Top-k问题的可微分性提供了一种优雅的解决方案，它通过最优传输和熵正则化成功将离散、跳跃的Top-k操作平滑化，使其能够融入到端到端的训练流程中。这不仅为kNN分类和Beam Search等经典算法带来了显著的性能提升，还为未来更多涉及Top-k操作的任务提供了新的思路。
未来，随着SOFT Top-k操作的进一步发展和优化，我们有理由相信，这种创新方法将会在更多领域中展现出其潜力，推动机器学习和数据挖掘领域的进一步进步。
📚 参考文献