机器之心编辑部
人工智能顶级会议 ICML 2018 即将于 7 月 10 日至 15 日在瑞典首都斯德哥尔摩举行。昨天，大会提前公布了最佳论文获奖名单，在超过 600 篇被接收论文中，来自 MIT 和 UC Berkeley 的研究人员分享了最佳论文的殊荣。值得一提的是，此前攻破 ICLR 2018 大会七篇对抗样本防御方法的研究众望所归地成为了最佳论文。
而复旦大学副教授黄增峰一人署名的论文《Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices》则和 DeepMind、斯坦福大学的两篇论文一同位居「亚军」论文行列。
Best Paper Awards
来自 MIT 的 Anish Athalye 与来自 UC Berkely 的 Nicholas Carlini 和 David Wagner 获得了最佳论文。早在今年 2 月份，这项攻破 ICLR 2018 七篇对抗样本防御论文的研究就引起了深度学习社区的热烈讨论。该研究定义了一种被称为「混淆梯度」（obfuscated gradients）的现象。在面对强大的基于优化的攻击之下，它可以实现对对抗样本的鲁棒性防御。这项研究引起了深度学习社区的讨论，GAN 提出者 Ian Goodfellow 也参与其中。机器之心曾对此做过报道。
论文：Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples
论文地址：https://arxiv.org/abs/1802.00420
项目地址：https://github.com/anishathalye/obfuscated-gradients
摘要：我们发现了一种「混淆梯度」（obfuscated gradient）现象，它给对抗样本的防御带来虚假的安全感。尽管基于混淆梯度的防御看起来击败了基于优化的攻击，但是我们发现依赖于此的防御并非万无一失。对于我们发现的三种混淆梯度，我们会描述展示这一效果的防御指标，并开发攻击技术来克服它。在案例研究中，我们试验了 ICLR 2018 接收的 8 篇论文，发现混淆梯度是一种常见现象，其中有 7 篇论文依赖于混淆梯度，并被我们的这一新型攻击技术成功攻克。
来自 UC Berkeley EECS 的 Lydia T. Liu、Sarah Dean、Esther Rolf、Max Simchowitz 和 Moritz Hardt 的论文同样也获得了最佳论文奖。由于机器学习系统易受到数据偏见而导致歧视性行为，人们认为有必要在某些应用场景中用公平性准则约束系统的行为，并期待其能保护弱势群体和带来长期收益。该研究探索了静态公平性准则的长期影响，发现结果和人们的期望相去甚远。
论文：Delayed Impact of Fair Machine Learning
论文地址：https://arxiv.org/abs/1803.04383
摘要：机器学习的公平性主要在静态分类设置中得到研究，但没有关注这些决策如何随时间改变潜在的群体。传统的观点认为公平性准能提升他们想保护的群体的长期利益。
我们研究了静态公平性标准如何与暂时的利益指标相互作用，例如利益变量的长期提升、停滞和下降。我们证实了即使在一步反馈模型中，常见的公平性准则没有随时间带来改善，并可能实际上给特定案例带来伤害（无约束的目标函数反而不会）。
我们完整地总结了三个标准准则的延迟影响，对照了和这些准则的行为存在质的不同的制度。此外，我们发现一种自然形式的度量误差可以放宽公平性准则能够在其中顺利执行的制度。
我们的结果强调了评估公平性准则的度量和时序建模的重要性，展示了一系列的新挑战和权衡问题。
BAIR 博客此前曾经介绍过这篇论文，参见：前沿 | BAIR 探索机器学习公平准则的长期影响：对弱势群体的善意真的种出了善果？
Best Paper Runner Up Awards
在最佳论文亚军（Runner Up）论文中，复旦大学数据科学学院副教授黄增峰完成的在线流（online streaming）算法获得了这一荣誉，黄增峰为这篇论文的唯一作者。该论文讨论的这种在线流算法可以在只有非常小的协方差误差的情况下，从大型矩阵抽取出最能近似它的小矩阵。
论文：Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices
论文地址：https://203.187.160.132:9011/www.cse.ust.hk/c3pr90ntc0td/~huangzf/ICML18.pdf
摘要：给定一个 n×d 维的大型的矩阵 A，我们考虑计算一个 l×d 维的概要矩阵（sketch matrix）B，概要矩阵的维度 l 要显著小于原矩阵 A，但它仍是矩阵 A 优良的近似。我们希望最小化协方差误差：
现在我们考虑流模型（streaming model）中的问题，其中的算法只能在有限的工作空间内传输输入一次。而流行的 Frequent Directions 算法（Liberty, 2013）与它的变体实现了最优空间和误差间的权衡。然而运行时间是否能提升还是一个悬而未决的问题。在本论文中，我们几乎可以解决这个问题的时间复杂度。特别是，我们提供了有更快运行时间的新型空间-最优（space-optimal）算法。此外，除非矩阵乘法的当前最优运行时间能显著提升，否则我们算法的运行时间是近似最优的（near-optimal）。
对于大规模矩阵运算，精确的算法通常会非常慢，因此有非常多的研究聚焦于设计一种快速的随机近似算法。为了加速计算，采用小矩阵近似大矩阵的矩阵概要是常用的技术。而在实际应用中，数据通常以流式的形式传输，将整个数据集储存在主内存中通常是不切实际和不可能的。
在本论文中，作者黄增峰研究了在小的协方差下保留概要矩阵的在线流算法。在流模型中，输入矩阵的行秩能一次降低到 1；该算法只允许在有限的工作空间内传输一次，这是持续保留概要矩阵所必须的。
流行的 Frequent Directions 算法在空间占用和近似误差间实现了最优的权衡，该算法目前已经广泛应用于在线学习。然而，我们仍然不太清楚它们的运行时间是否能提升，也许我们只能寄希望于得到线性（稀疏）时间的算法，这在很多矩阵问题上是可能的。本论文主要由以下问题驱动：
是否存在输入稀疏时间的 Frequent Directions 算法，能够实现同等最优的空间-误差权衡？
以下展示了黄增峰提出的主要算法，他的核心思想是在原始 FD 中使用快速逼近的 SVD，产生次优的时间。
来自 DeepMind 和牛津大学的研究者也获得了 Best Paper Runner Up Awards。
论文：The Mechanics of n-Player Differentiable Games
作者：David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, Thore Graepel
论文地址：https://arxiv.org/abs/1802.05642
摘要：支撑深度学习的基石是保证目标函数能利用梯度下降收敛到局部极小值。不幸的是，这个保证在某些情况下会失效，例如生成对抗网络，其中有多个交互损失。在博弈中，基于梯度的方法的行为并没有得到很好的理解，随着对抗性和多目标架构的数量激增，这变得越来越重要。在这篇论文中，我们开发了新的技术来理解和控制一般博弈中的动态。主要的结果是将二阶动态分解为两个部分。第一个和潜博弈（potential game）相关，可以用内含的函数简化为梯度下降；第二个和哈密顿博弈相关，这是一种新的博弈类型，遵循一种守恒定律——类似于经典力学系统中的守恒定律。该分解启发了辛梯度调整（Symplectic Gradient Adjustment，SGA），这是一种用于寻找一般博弈中的稳定不动点的新算法。基础实验表明 SGA 的性能和近期提出的寻找 GAN 稳定不动点的算法不相上下，同时可以应用到更多的一般博弈中，并保证收敛性。
同样获得该荣誉的还有来自斯坦福大学的研究者。
论文：Fairness Without Demographics in Repeated Loss Minimization
作者：Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, Percy Liang
论文地址：https://arxiv.org/abs/1806.08010
摘要：机器学习模型（如语音识别器）通常被训练以最小化平均损失，这导致了表征差异（representation disparity）——少数群体（如非母语说话者）对训练目标函数的贡献较少，并因此带来了更高的损失。更糟糕的是，由于模型准确率会影响用户保留，因此少数群体的数量会随着时间而日益减少。本论文首先展示了经验风险最小化（ERM）的现状放大了表征差异，这甚至使得最初公平的模型也变得不公平了。为了缓解这一问题，我们开发了一种基于分布式鲁棒优化（distributionally robust optimization，DRO）的方法，可以最小化所有分布上的最大风险，使其接近经验分布。我们证明了该方法可以控制每个时间步的少数群体风险，使其符合罗尔斯分配正义，同时该方法对群体的标识并不清楚。我们证明 DRO 可以阻止样本的表征差异扩大，而这是 ERM 做不到的，我们还在现实世界的文本自动完成任务上证明了该方法对少数群体用户满意度的改进。
