正确进行双层 Softmax 采样：纠正由规模不平衡和离散度导致的偏差

arXiv:2610.10483v1 发布类型：新 摘要：从 Softmax 分布中进行采样是机器学习中的一项基础操作，但其关于项目数量的线性复杂度使得大规模场景下的精确采样难以实现。双层 Softmax（2LS）采样是一种广受欢迎的替代方案，能够实现次线性时间采样。假设项目被划分为多个簇，2LS 首先对簇进行采样，然后在所选簇内对项目进行采样。在本文中，我们表明，尽管 2LS 具有诸多优势，但它会引入系统性且不理想的采样偏差；这些偏差源于对簇的权重分配不当，即忽略了簇规模不平衡和簇内相似度离散程度。我们提出了两种采样方法：Size-Corrected 2LS（S-2LS）和 Size- and Dispersion-Corrected 2LS（SD-2LS），它们能够纠正这些偏差，并以几乎可以忽略不计甚至不存在的额外计算开销，提供有理论保证的更优 Softmax 近似。在五个大规模数据集上的深入实验验证了我们方法改进后的采样特性。我们建议未来的研究始终使用这些方法来替代标准 2LS。