提出可微分的背包与Top-k选择方法，让神经网络能优化离散选择。
Differentiable Knapsack and Top-k Operators via Dynamic Programming
- 将背包和Top-k问题建模为动态规划，通过平滑递推实现可微分。
- 支持并行计算和反向传播，可在约束强化学习中应用。
- 理论证明熵是唯一保持排列对称性的正则项，适合稀疏选择。
背包和Top-k算子可用于选择离散变量子集，但因其分段常数特性，在神经网络中难以求导。本文提出统一框架，将这些算子视为动态规划问题，并通过平滑底层递推关系构造可微分松弛。算法上，设计高效并行算法，支持确定性和随机前向传播，以及向量-雅可比乘积用于反向传播。理论上，证明香农熵是唯一使算子具备排列等变性的正则化项，并刻画了诱导稀疏选择的正则化形式。实验上，在决策导向学习基准、带约束的动态商品组合强化学习任务及离散变分自编码器扩展中验证了该框架的有效性。
原文摘要 · Abstract (English)
Knapsack and Top-k operators are useful for selecting discrete subsets of variables. However, their integration into neural networks is challenging as they are piecewise constant, yielding gradients that are zero almost everywhere. In this paper, we propose a unified framework casting these operators as dynamic programs, and derive differentiable relaxations by smoothing the underlying recursions. On the algorithmic side, we develop efficient parallel algorithms supporting both deterministic and stochastic forward passes, and vector-Jacobian products for the backward pass. On the theoretical side, we prove that Shannon entropy is the unique regularization choice yielding permutation-equivariant operators, and characterize regularizers inducing sparse selections. Finally, on the experimental side, we demonstrate our framework on a decision-focused learning benchmark, a constrained dynamic assortment RL problem, and an extension of discrete VAEs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。