最优传输及其在公平中的应用

80 阅读 0 评论 53 点赞

我是靠谱客的博主粗犷彩虹，最近开发中收集的这篇文章主要介绍最优传输及其在公平中的应用，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

最佳运输起源于经济学，是作为一种如何最好地分配资源的工具而开发的。最佳运输理论本身的起源可以追溯到 1781 年，当时 Gaspard Monge 研究了最有效的土方运输方式，以便为拿破仑的军队建造防御工事。概括地说，最佳运输是一个问题，即如何将所有资源（例如铁）从起点集合（铁矿）移动到终点集合（铁工厂），同时最小化资源的总距离不得不去旅行。从数学上讲，我们想要找到一个函数，它获取每个起点并将其映射到目的地，同时最小化起点与其相应目的地之间的总距离。尽管它的描述无伤大雅，但在这个问题的原始表述上取得了进展，

解决问题的第一次真正飞跃发生在 1940 年代，当时苏联数学家列昂尼德·康托罗维奇 (Leonid Kantorovich) 将问题的表述调整为现代版本，即现在所说的 Monge-Kantorovich 表述。这里的新颖之处在于允许来自同一个矿山的一些铁被送到不同的工厂。例如，一个矿山的 60% 的铁可以送到一家工厂，而该矿山剩下的 40% 的铁可以送到另一家工厂。从数学上讲，这不再是一个函数，因为同一个起点现在可能映射到许多目的地。相反，这被称为联轴器始发地分布和目的地分布之间的关系如下图所示；从蓝色分布（原点）中挑选一个矿井并沿图中垂直移动显示了该铁被发送到的工厂（目的地）的分布。

图表、直方图、散点图描述自动生成

作为这一新发展的一部分，Kantorivich 引入了一个重要的概念，称为 Wasserstein 距离。与地图上两点之间的距离类似，Wasserstein 距离（也称为推土机距离，受其原始上下文启发）测量两个分布之间的距离，例如本例中的蓝色和品红色分布。例如，如果所有的铁矿都离所有的铁工厂都很远，那么矿山分布（位置）与工厂分布之间的 Wasserstein 距离就会非常大。即使有了这些新的改进，仍然不清楚是否真的存在一种最好的资源运输方式，更不用说那种方式了。最后，在 1990 年代，由于数学分析和优化的改进导致问题的部分解决方案，该理论开始迅速发展。也是在这个时候和进入 21 世纪，最优传输开始渗透到其他领域，例如粒子物理学、流体动力学，甚至统计学和机器学习。

现代最优交通
随着新发展理论的爆炸式增长，最优运输已成为许多新统计和 AI 算法的核心近二十年内出现。实际上，在每个统计算法中，数据都被明确或隐含地建模为具有某种潜在的概率分布。例如，如果您正在收集不同国家/地区个人收入的数据，那么每个国家/地区的人口收入都有一个概率分布。如果我们想根据两国人口的收入分布来比较两个国家，那么我们需要一种方法来衡量这两种分布之间的差距。这正是最优传输（尤其是 Wasserstein 距离）在数据科学中变得如此有用的原因。然而，Wasserstein 距离并不是衡量两个概率分布相距多远的唯一指标。实际上，两种选择——L-2 距离和 Kullback-Leibler (KL) 散度——由于它们与物理学和信息论的联系而在历史上更为普遍。Wasserstein 距离相对于这些替代方案的主要优势在于它同时采用了在计算距离时考虑值及其概率，而 L-2 距离和 KL 散度仅考虑概率。下图显示了关于三个虚构国家收入的人工数据集示例。 

在这种情况下，由于分布不重叠，蓝色和品红色分布之间的 L-2 距离（或 KL 散度）将与蓝色和绿色分布之间的 L-2 距离大致相同。另一方面，蓝色和品红色分布之间的 Wasserstein 距离将远小于蓝色和绿色分布之间的 Wasserstein 距离，因为值（水平分离）存在显着差异。Wasserstein 距离的这一特性使其非常适合量化分布之间的差异，尤其是数据集之间的差异。

以最佳运输方式实现公平
随着每天收集大量数据，机器学习在许多行业变得越来越普遍，数据科学家必须越来越小心，不要让他们的分析和算法延续数据中现有的偏见和成见。例如，如果住房抵押贷款批准的数据集包含申请人的种族信息，但由于使用的方法或无意识的偏见，少数民族在收集过程中受到歧视，那么基于该数据训练的模型将在一定程度上反映潜在的偏见。可以利用最佳传输来帮助减轻这种偏差并提高公平性以两种方式。第一种也是最简单的方法是使用 Wasserstein 距离来确定数据集中是否存在潜在偏差。例如，我们可以估计为女性批准的贷款金额分布与为男性批准的贷款金额分布之间的 Wasserstein 距离，如果 Wasserstein 距离非常大，即统计显着，那么我们可能会怀疑存在潜在偏差。这种测试两组之间是否存在差异的想法在统计学中被称为双样本假设检验。

或者，当底层数据集本身存在偏差时，最优传输甚至可以用于在模型中强制执行公平性。从实际的角度来看，这是非常有用的，因为许多真实的数据集会表现出一定程度的偏差，而收集无偏差的数据可能非常昂贵、耗时或不可行。因此，无论数据多么不完美，使用我们可用的数据并尝试确保我们的模型减轻这种偏差要实用得多。这是通过强制执行称为“ 强人口统计均等 ”的约束来实现的在我们的模型中，这迫使模型预测在统计上独立于任何敏感属性。一种方法是将模型预测的分布映射到不依赖于敏感属性的调整后预测的分布。然而，调整预测也会改变模型的性能和准确性，因此在模型性能和模型对敏感属性的依赖程度（即公平性）之间存在权衡。 

最佳传输通过尽可能少地更改预测来发挥作用，以确保最佳模型性能，同时仍然保证新预测独立于敏感属性。这种调整后的模型预测的新分布被称为 Wasserstein 重心，它在过去十年中一直是许多研究的主题。Wasserstein 重心类似于概率分布的平均值，因为它最小化了从自身到所有其他分布的总距离。下图显示了三种分布（绿色、蓝色和洋红色）以及它们的红色 Wasserstein 重心。 

在上面的例子中，假设我们建立了一个模型来预测一个人的年龄和收入，该数据集包含一个敏感属性，例如婚姻状况，可以采用三个可能的值：单身（蓝色）、已婚（绿色）和丧偶/离婚（洋红色）。散点图显示了每个不同值的模型预测分布。但是，我们想要调整这些，以便新模型预测对一个人的婚姻状况视而不见。我们可以使用最优传输将这些分布中的每一个映射到红色的重心。因为所有值都映射到相同的分布，我们不能再根据收入和年龄判断一个人的婚姻状况，反之亦然。重心尽可能保持模型的保真度。

数据和机器学习模型的日益普及在企业和政府决策中的使用导致了对确保其公平应用的新的社会和伦理关注的兴起。许多数据集由于其收集方式的性质而包含某种偏见，因此重要的是，基于它们训练的模型不会加剧这种偏见或任何历史歧视。优化交通只是解决这一问题的一种方法，近年来这种方法势头正盛。如今，有快速有效的方法来计算最佳运输地图和距离，使这种方法适用于现代大型数据集。随着我们越来越依赖基于数据的模型和洞察力，公平性已经成为并将继续成为数据科学的核心问题，而最佳传输将在实现这一目标方面发挥关键作用。