作者：南山牧野
2022年11月4日上午10:00-11:00，复旦大学大数据学院邀请了中国人民大学孟澄教授作题为“Efficient algorithms for large-scale optimal transport problems”报告。此次报告由复旦大学大数据学院张楠老师主持。
孟澄老师此次报告的主要内容是大规模最优传输问题的高效算法。孟老师首先带大家回顾了最优传输问题及最小传输代价Wasserstein距离，领略了最优传输在统计和机器学习领域诸多有趣的应用。
近年来，Wasserstein距离的surrogates更多地被提出和使用，这其中包括sliced-Wasserstein距离（SW）及它的推广max-SW, GSW, Tree-SW等。SW首先随机地沿着不同方向将高维概率分布线性投影到一维空间，再在一维空间中衡量两个分布Wasserstein距离。因为具有凸代价函数的一维最优传输问题可以由排序算法极快地求解，如SW这些surrogates方法在计算上是非常高效的。然而，这类方法也有局限性，其一是SW对Wasserstein距离的近似效果有可能不甚理想。此处，孟老师用动画演示了一个例子。此例中，源数据的分布在圆环上（紫色），而目标数据除了在这一圆环上分布外还有一部分概率质量处于中心点的位置。在将目标数据中心点的概率质量逐步移到圆环上的过程中，Wasserstein距离和Sinkhorn距离均不断减小，但SW及其衍生方法得到的距离却令人意外地在不断上升。从此例中，SW与通常Wasserstein距离相异之处可见一斑。此外，在SW投影得到的一维空间中得到的最优传输方案与原问题的最优传输方案也常常有较大差异。
基于以上研究，孟澄老师提出了Hilbert curve projection（HCP）距离作为Wasserstein距离的一个新的surrogate。相较于线性投影，HCP将高维的数据投影到样本空间的一条Hilbert curve上。由于Hilbert curve具有locality-preserving的性质，高维数据的局部空间结构在投影中得以留存。投影之后，我们计算投影到Hilbert curve上的样本在原空间中的传输距离作为HCP距离。对于如此定义的HCP的距离，孟澄老师的研究对其性质进行了深入的分析。在理论性质上，可证明HCP距离在一定限制下是一个良定的度量，且有着大样本下的统计收敛性。在实验效果上，我们看到在模拟实验中HCP计算速度很快，CPU耗时小于SW类surrogate方法。其中一个实验案例展示了HCP和SW等不同距离下的Wasserstein flow。从实验结果中可见，使用HCP距离时逼近目标分布的速度更快。最后，研究还提出了在数据维度较高时HCP的两种变体。
结束了第一部分关于HCP的报告，孟澄老师带来了第二部分内容，介绍Sinkhorn方法的加速计算。Sinkhorn这一最优传输问题中的重要方法，在大规模数据上的计算效率主要受制于其中核矩阵的乘法运算。有研究者提出将核矩阵替换为其低秩近似，然而由于核矩阵实际上常常近乎满秩，低秩近似法可能会表现不好。不过，注意到核矩阵有高度稀疏的特点，我们可以利用稀疏结构进行加速计算。孟澄老师的研究提出了按矩阵元素的重要性采样，利用稀疏矩阵高效计算的Spar-Sink方法。在重要性采样的阶段，研究给出了采样概率的详细构建方法。最终，经实验验证，Spar-Sink相较于对照方法，既能用相对较少的采样得到较高的精确度，也能在相对较小的CPU耗时内完成计算，最终在精确度和计算速度之间实现了良好的权衡。
最后，孟澄教授对报告进行了总结，热情回答了张楠老师和参会嘉宾的提问。