多篇顶会论文看DRO (Distributionally Robust Optimization) 最新进展

©PaperWeekly 原创 · 作者 | 张一帆

学校 | 中科院自动化所博士生

研究方向 | 计算机视觉

常见的算法使用经验风险最小化（ERM）的范式，有一个模型参数为 ，一个损失函数 和数据分布 ，通常情况下我们只能看到训练数据分布 ，那么 ERM 可以写作：

当测试数据集 的时候，ERM 往往性能会大幅度下降。Distributionally Robust Optimization (DRO) 为这个问题提供了一个解决方案，即在一个预先确定的分布族 (uncertainty set) 中，用最糟糕的预期风险替换一个单一分布下的预期风险。

如果 包含了 ，那么 DRO 的目标函数就会成为 上平均损失的上界。然而我们不总是能得到域的分布，即将 划分为多个分布  ，当我们没有 domain 的先验知识的时候，如何去构造 是 DRO 成功的关键，目前大概有如下几种方式：

1. 基于 moment constraint，对数据分布的一阶矩，二阶矩进行约束。这种方法需要从数据中估计一阶矩，二阶矩，目前只能在比较 toy 的数据集上使用；

2. 基于 divergence；

3. 基于 Wasserstein/MMD ball；

4. 基于 coarse-grained mixture models。本文通过几篇高引和最新的顶会文章对 DRO 进行简单介绍。

基于 divergence 的方法

1.1 开篇之作

论文标题：

Kullback-Leibler Divergence Constrained Distributionally Robust Optimization

论文链接：

http://www.optimization-online.org/DB_FILE/2012/11/3677.pdf 

由于年代比较久远，文中使用的 notation 和我们现在的稍有差别，其对 DRO 的定义为：

这里的 是参数集而 是 的数据分布， 作为 uncertainty set。本文第一次采取了如下方法来定义 uncertainty set，其中 是 KL 散度， 是我们对真实数据集的估计。

这里的超参数 控制 了uncertainty set 的大小。我们知道 KL 散度隐式的假设了 相对于 是处处连续的，并且他可以写作：

到现在为止，我们内层的优化目标是概率分布 ，而 并没有在目标函数中出现，这就很难优化。作者采用了 change-of-measure 的技巧，首先我们记 为似然比（likelihood ratio），也称之为迪姆导数（Radon-Nikodym derivative），我们可以轻易的得到 ，然后使用 change-of-measure 将 KL 散度转化为：

同样地，对目标函数使用 change-of-measure 的技巧，我们可以得到：

这样的话内层优化就从依赖于 的优化问题转化成了对于 的：

因为本文关注于凸优化的场景，也就是说 是凸集， 是凸函数，作者根据一定的假设，直接推出了内层优化的闭式解：

这里的 是 Lagrangian multiplier。内层优化有闭式解意味着什么？意味着我们这个 worst-case distribution 有闭式的概率分布，根据 的定义，我们只需要找到使得内层优化最大的 然后乘上 即可，因此我们可以得到：*

如果我们在外层优化找到了最优的 ，那么他的概率测度可以写作*：

* 这是一个非常有趣的现象，内层优化的最优分布和数据分布 成正比，比例因子为 。所以这个 bi-level 的优化问题直接变成了单层的优化问题：

1.2 P-DRO

论文标题：

Modeling the Second Player in Distributionally Robust Optimization

收录会议：

ICLR 2021

论文链接：

https://arxiv.org/abs/2103.10282

代码链接：

https://github.com/pmichel31415/P-DRO

本文使用生成模型对 uncertainty set 进行建模。但是不是所有的生成模型都可以表达有用的数据分布（如果 太大就会有噪音数据），因此文中使用 KL 散度约束模型分布与真实数据分布之间的距离，文中提出的 Parametirc DRO 如下所示：

他的优化过程比较麻烦主要有两个注意点：

1.难以保证学到的数据分布真实

因为外层分布的优化是基于一个良好的数据分布 的，我们不能保证 是有效的数据分布，因此作者将该问题转化成了一个 importance sampling 的问题，这样保证了数据点 是从真实数据中采样得到的。

不过真实数据分布 我们依然不知道，因此还需要去估计他，这个 estimator 靠如下方式得到：

即在所有生成模型中选择一个对数似然估计的最准的，那么接下来模型变成了如下形式，这就是一个简单的加权损失函数，为了训练的稳定，在一开始的时候 是一样的，也就是 ERM。

2.生成模型的训练过程

要最大化上述损失有两个难点：

1. 这个 KL ball 的限制难以达到；
2. 最大化这个期望会导致训练的不稳定（large gradient variance）。

为了解决这个问题，作者首先将 KL 散度使用 lagrangian 松散一下：

作者证明了：

其中：

于是巧妙地将这个最大化期望损失的问题转换成了最小化两个分布的 KL 散度，其中 依赖于真实数据分布 ，这是我们无法得到的，因此作者将这一项看作常数，再经过一系列转换变成了：

整体的 model 记作：

基于 Wasserstein/MMD ball

2.1 Wasserstein ball-based

这一块推荐两篇文章都非常的硬核，在这里只陈述他们大概的思路。

论文标题：

Certifying Some Distributional Robustnesswith Principled Adversarial Training

收录会议：

ICLR 2018 Oral

论文链接：

https://arxiv.org/abs/1710.10571

代码链接：

https://github.com/duchi-lab/certifiable-distributional-robustness

同样，先拿出 DRO 的优化目标：

不确定集 的选择影响了模型的鲁棒性和可计算性。他们的方法大概总结如下：对一个将数据点 扰动到 的扰动器，我们规定一个 cost function：，通常情况下 。

考虑一个鲁棒性区域 是一个数据分布 附近的 -ball， 是 Wasserstein metric。直接解决这个 bi-level 的问题是非常难的，因此作者使用拉格朗日乘子对问题进行简化并重新公式化为：

式子中的 可以控制对抗攻击的强度。

训练的算法其实是非常简单的，只不过文中涉及了对算法性质比如鲁棒性，收敛性的大量证明，感兴趣的读者建议深度阅读原文。

2.2 MMD-based

论文标题：

Distributionally Robust Optimization and Generalization in Kernel Methods

收录会议：

NeurIPS 2019

论文链接：

https://arxiv.org/abs/1905.10943

代码链接：

https://github.com/mstaib/mmd-dro-code

本文首先提出了以往方法的两种缺陷：

1. 基于 -divergence 的 uncertainty set 只能包含真实数据分布附近的数据点，不能偏离真实数据分布太多，因此很难使得 worst-case distribution 包含测试分布，所以不是很能保证一个很好的泛化性能；

2. 基于 Wasserstein distance 的 uncertainty set 包含了一个连续分布，克服了上述问题，但是这种方法非常难以实现，并且理论过程需要复杂的假设。

本文使用 MMD（maximummean discrepancy）对 uncertainty set 进行建模，得到了 MMD DRO。亮点有三：

1. 本文证明了 MMD DRO 等价于 ERM 加上一个对损失函数的希尔伯特范数的惩罚项；

2. 在 Gaussian kernel ridge regression 的场景下，作者证明了一个新的泛化损失上界；

3. 作者给出了近似的易于实现的算法。

首先两个数据分布 之间的 MMD（max min discrepancy）距离定义如下，不了解 MMD 的可以参考这篇文章 [1]。

我们定义均值 embedding 为 ，那么 MMD 可以写作：

到这里我们就可以定义本文的核心问题了 MMD Dro：

这里的 是一个有 个样本点的经验数据分布。接下来使用 表示 DRO 的 uncertainty set，这是一个包含经验数据分布的分布， 是从 uncertainty set 中采样的分布， 表示真实数据分布。

如果 半径足够大，那么它就更有可能包含真实数据分布。但是半径太大这个问题又会很难处理（包含很多噪音样本），作者给出了如下两个定理来对泛化性能的 bound 进行讨论：

Lemma 1. 对于一个有上界的核函数 ，有 的概率下式成立：

这里 是样本数目，显然样本数目越多 更有可能逼近真实数据分布。

Corollary 1. 如果我们设置 ，那么我们有 的概率使得下述的 bound 成立。

本文称右端的式子为 DRO 的对抗问题，接下来会对这个对抗问题进行 bound。

现在引入额外假设 ，此时 risk 可以写作内积的形式 ，那么我们就可以得到：

之所以这里是一个不等式，是因为不是所有 空间内的函数都是某些分布的   mean embedding。上述形式下，我们的分析就会变得更加容易些。

Theorem 1. 假设 ，那么下述不等式成立：

可以看到直接把 MMD 整没了，那么我们总体的 DRO 就转化成了：

回顾一下 Lemma 1.，右端内层的  优化是真实数据分布 empirical loss 的上界，所以最终的优化目标体现了这样一个事情：只要在经验数据分布上优化 ，再加上对 的一个范数的优化，就有大概率能够提供一个 bound 给分布外的数据。当然了，上式并不是完全体，因为我们不能保证 ，所以作者还进行了进一步的推论，对这一项正则项进行近似，最终将对 loss 的 penalty 转化为了对 的。

有意思的是，本文还将 MMD DRO 进行了另一个角度的解释，因为搜索所有在 MMD ball 中的分布 是非常难做到的，因此作者将问题进行化简，只关注和经验分布 具有相同 support 的分布（直观来看也就是含有相同的样本但权重不一样），那么 MMD DRO 问题可以简化为：

进一步的，作者验证了这个简化版的问题的最优解为：

其中 是高斯核矩阵， 姑且当作是 就好，巧妙的是，当我们将高斯核矩阵设置为 identity 的时候，这个式子就变成了：

也就是说，我们从 MMD DRO 出发，其实得到了常用的 empirical variance penalty，这里的方差在以往工作中定义为：

Coarse-grained mixture models

3.1 Distributionally Robust Language Modeling

论文标题：

Distributionally Robust Language Modeling

收录会议：

EMNLP 2019

论文链接：

https://arxiv.org/abs/1909.02060

代码链接：

https://worksheets.codalab.org/worksheets/0xf8122ebd24e94209a2a1764007509098

本文关注的场景是 NLP 下的，但是对于 CV,ML 也很有借鉴意义。现在的语言模型都是大大数据集上进行训练的，而训练数据集有非常多的主题（新闻，评论等），而测试的数据集往往是未知的。那么我们能否训练一个通用模型在所有测试数据集上表现良好呢？本文提供了一种思路。

首先，使用 MLE 会失败！为什么？虽然数据越多越好，但是如果训练过程中用的数据与测试无关，那么测试效果会下降（测试，训练数据都是新闻时，增加评论相关的训练数据就是使得模型效果下降），而这个下降的原因是：MLE 强调的是在训练数据中的平均效果，从而忽略了出现次数比较少而重要的数据。考虑我们的数据集 10% 是评论，90% 是新闻，那么 MLE 就会把重点放在新闻上，而我们需要的是将这个关注”搬回来“，让模型对两种数据同样重视。

我们先来看一看问题的建模，数据，训练数据分布，测试数据分布记为 。语言模型 通常使用如下的 MLE 损失被训练去近似训练数据分布 。

当测试训练数据独立同分布，传统的统计理论告诉我们只要数据够多，MLE 就能效果卓越。但是测试数据分布往往可能是训练数据中很少的一部分（上述例子中的评论），这时 MLE 就会效果极差。

这时我们定义一个潜在的测试数据分布集合 作为 uncertainty set，如果一个模型在 中表现很好，那么他也能在 中表现良好。而 DRO 的关在在于 uncertainty set 和 loss，作者分别对这两个关键点进行了设计。

Uncertainty Set：本文的 uncertainty set 定义为如下形式：

也就是说 是 的集合，而 们组成了训练数据 。为了在所有可能的测试集上表现良好，我们的训练目标变为：

这个目标可以通过 upweighting 损失比较大的数据来实现在所有测试分布上的一个比较均匀的表现（这也是 mixture models 和之前几种模型的核心差距，个人理解 mixture models 更像是 data-centric 的方法，对自身数据进行 mixture 或者 reweighting 从而获得更好的鲁棒性）。

上式有一个致命的缺陷，他约束的是任意分布，如果有一个 sample 是噪音数据，那么模型将会给他分配很高的权重。为了解决这个问题，作者提出了要将 uncertainty set 约束到有效分布上而不是任意分布。有一个方法可以避免这个问题：“我们不要逐 sentence 进行加权，我们根据 topic 进行加权”。

作者假设每个句子都属于一个 topic ，那么句子分布记作 。这时我们将上述的 uncertainty set 和 worst case topic distribution 分别进行改写：

这一方法通过调整 topic 之间的权重来取得一个较为均匀的表现。

本文对于 uncertainty set 的 loss 形式如下：

那么加上 MLE loss，我们的总体损失函数可以写作如下形式：

也就是说训练模型 来匹配每个可能的测试分布 ，使每个 density 尽可能一致。可以还是难以理解，那我们对比一下：

不同之处在于 可以看作一个常数，但是 依赖于 因此对于外层优化而言不能看做 constant。

Algorithm 现在难点在于 这一项不好处理。本文对每个 topic 训练一个模型 然后用以估计这一项的值 。整体优化的思路分两步：

1. 在多个 step 中选择使得总体损失最大的 ，即我们存储到第 次优化时每个 topic 产生的平均损失（通过 exponential weighted moving average），然后选择使得该 loss 最大的 :；

2. 有了 ，我们就可以根据下式更新参数，这里的 是我们对概率分布 的估计。

这时候就有人会问了，这个 难道真的要遍历所有排列组合吗？其实不用，我们只需要将 从高到低对所有 topic 排序，然后依次赋予 的概率值。举个栗子：

给定 ,，那么 。第三个 topic 因为 loss 最大，所以赋予了 的概率值，而第一个 topic loss 第二大，但此时，不够分，所以把剩余的概率都给他，topic 2 没有概率。这时上面对梯度的权重就变成了 。

3.2 DRSL

论文标题：

Does Distributionally Robust Supervised Learning Give Robust Classifiers

收录会议：

ICML 2018 Oral

论文链接：

https://arxiv.org/abs/1611.02041

先说结论，本文之所以能作为 oral 出现，他的 intuition 非常关键,本文依然选择 KL-divergence 作为 uncertainty set 的建模工具,但是抛出了一个重磅结论：DRO 训练得到的分类器并不比 ERM 的好！ 我们必须添加一些结构化的假设，引入 domain 相关的信息（gender，style 等）才能真正超越 ERM，训练出 robust classifier。

先来看看本文的建模，是 density ratio， 则为 divergence，第一个约束就是 uncertainty set 和 empirical distribution 之前的 divergence，将这个 density ratio 作为权重对所有样本重新进行加权，第二个约束说所有权重的和为 1。

参考文献

[1] https://zhuanlan.zhihu.com/p/163839117

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：[e-mail] 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·