1.3万人参会NeurIPS2019获奖论文公布，微软华人学者获经典论文奖

机器之心编辑部

作为人工智能领域的国际顶级会议，今年的 NeurlPS 如同往年一样备受关注。因注册人数过多，今年参会门票都要凭运气抽彩票决定。

在论文方面，今年大会投稿数量也创下了历史新高，一度使 NeurIPS 服务器宕机。最终，共提交6743 篇有效论文，接收 1428 篇，接受率为 21.17%。

此前，还有一些学者与 AI 从业者因签证问题无法参会。

据大会官方统计，今年参会总人数已经突破了 13000 人，申请「抽奖」的人数更是达到了 15000 人。2018 年的参会人数不到 9000，一年之间参会人数几乎上涨了 50%。

根据机器之心记者在现场看到的情况，今年的大会确实盛况空前：在主办场地温哥华会展中心，参会领取入场卡的人群早早地从 B1 楼排到了二楼。

而且到了二楼还要排上一整圈：

目前 NeurIPS 正在进行的活动还仅仅是展览和部分 Tutorial，虽然大会主要议程将在当地时间 12 月 10 日才会开始，但就在几个小时前，NeurIPS 官方公布了最引人关注的杰出论文等奖项的评选结果。

值得注意的是，除了杰出论文奖（Outstanding Paper Award）和经典论文奖（Test of Time Award），今年组委会还增设了「杰出新方向论文奖」，以此表彰在「面向未来研究的创新途径」方面表现优秀的研究者。

杰出论文奖

论文名称：Distribution-Independent PAC Learning of Halfspaces with Massart Noise

作者：Ilias Diakonikolas、Themis Gouleakis、Christos Tzamos

机构：威斯康辛大学麦迪逊分校、马普所

论文地址：https://papers.nips.cc/paper/8722-distribution-independent-pac-learning-of-halfspaces-with-massart-noise

摘要：本文作者研究了分布独立的半空间（half-space）下的 PAC 学习问题（在 Massart 噪声下）。具体而言，给定一组带标签样本（x, y），采样于 R^d+1 维的分布 D，如此以来，未带标签点 x 上的边缘分布是任意的，并且标签 y 通过一个未知半空间生成，而这个未知半空间被 Massart 噪声破坏，其中噪声率η

。对于这个问题，作者提出了误分类误差为η+ε的 poly (d, 1/ε) 时间算法。此外，他们还提供了证据证明其算法的误差保证（error guarantee）在计算上可能很难实现。作者表示，在他们的研究之前，即使是针对析取类（class of disjunction）而言，在这个模型中也没有出现高效的弱（独立分布）学习器。这种针对半空间（或甚至于析取而言）的算法在各项研究中一直是悬而未决的问题，从 Solan（1988）、Cohen（1997）到最近的 Avrim Blum 的 FOCS 2003 教程都强调了这一问题。

评语：这篇论文研究了线性阈方程（linear threshold function）在二分类的，有着未知的、有边界标签噪声训练数据的情况。它解决了一个非常基础且长期开放的问题，并提出了一个高效的算法用于学习。这是机器学习核心领域的长期开放的问题，而这篇论文做出了巨大的贡献。其贡献在于：在 Massart 噪声下高效地学习半空间（half-space）。举一个例子：在 1%Massart 噪声下，弱学习析取（误差率为 49%）也是开放的。该论文展示了如何高效地实现与 Massart 噪声和 epsilon（并如预期那样及时地执行 poly(1/epsilon)）相当的超额风险。该算法非常复杂，结果在技术上也难以确定。最终的目的是能够高效地获得与 epsilon（及时执行 poly(1/epsilon)）相当的超额风险。

杰出新方向论文奖

论文名称：Uniform convergence may be unable to explain generalization in deep learning

作者：Vaishnavh Nagarajan、J. Zico Kolter

机构：卡耐基梅隆大学、博世人工智能中心

论文地址：https://papers.nips.cc/paper/8722-distribution-independent-pac-learning-of-halfspaces-with-massart-noise

摘要：为了解释过参数化深度网络令人惊讶的良好泛化性能，近期的论文为深度学习开发出了各种泛化边界，这些边界都是基于一致收敛（uniform convergence）理论上的基本学习技巧。

众所周知，许多现有的边界在数值上都很大，通过大量的实验，研究者揭示了这些界限的一个更值得关注的方面：实际上，这些边界可以随着训练数据集的增大而增大。根据观察结果，他们随后给出了一些用梯度下降（gradient descent, GD）训练的过参数化线性分类器和神经网络的例子，而在这些例子中，一致收敛被证明不能「解释泛化」——即使尽可能充分地考虑了梯度下降的隐含偏见。更加确切地说，即使只考虑梯度下降输出的分类器集，这些分类器的测试误差小于设置中的一些小的ε。研究者也表明，对这组分类器应用（双边，two-sided）一致收敛将只产生一个空洞的大于 1-ε的泛化保证。通过这些发现，研究者对基于一致收敛的泛化边界的能力提出了质疑，从而全面了解为什么过参数化深度网络泛化得很好。

评语：这篇论文从根本上呈现了一些负面结果，表明许多现有的（基于 norm 的）深度学习算法性能边界都没有达到他们所宣称的结果。作者进一步说明，当那些研究者继续学习双边一致收敛机制时，他们无法达到自己宣称的结果。虽然该论文没有解决（或假装解决）深度神经网络中的泛化问题，但这是一个起点，表明社区开始以一种新的视角看待深度学习。

杰出论文奖荣誉提名

论文名称：Nonparametric density estimation & convergence of GANs under Besov IPM losses

作者：Ananya Uppal、Shashank Singh、Barnabás Póczos

机构：卡耐基梅隆大学

论文地址：https://papers.nips.cc/paper/9109-nonparametric-density-estimation-convergence-rates-for-gans-under-besov-ipm-losses

摘要：在本文中，研究者探究了大型损失函数族（Besov IPM）的非参概率密度估计问题，该函数族包括 L^p 距离、总变分距离，以及 Wasserstein 距离和 KolmogorovSmirnov 距离的泛华版本。对于各种损失函数设置，研究者提供了上下界，精确明确了损失函数与数据假设的选择，如何影响极小极大最优收敛率的确定。

研究者同样展示了线性分布估计经常不能达到最优收敛率，例如经验分布或核密度估计器等线性分布。他们得出来的上下界能帮助泛化、统一或提升一些最经典研究成果。此外，IPM 可以用于形式化生成对抗网络的统计模型。因此，研究者展示了该结果如何表明 GAN 的统计误差边界，例如 GAN 要严格超越最好的线性估计器。

评语：该论文以严谨的理论论证，说明了 GAN 在概率密度估计要比线性方法更有优势（就收敛速度而言）。利用之前关于小波收缩（wavelet shrinkage）的研究结果，该论文提供了关于 GAN 表征能力的新见解。具体而言，研究者在拥有大量类别的损失（称之为积分概率度量）和大型函数类别（Besov 空间）的环境下，为非参数化概率密度估计推导了极小极大收敛率。

评审者认为这篇论文对于非参数化估计和 GAN 的研究工作有非常深远的影响。

论文名称：Fast and Accurate Least-Mean-Squares Solvers

作者：Alaa Maalouf、Ibrahim Jubran、Dan Feldman

机构：以色列海法大学

论文地址：https://papers.nips.cc/paper/9040-fast-and-accurate-least-mean-squares-solvers

摘要：从线性回归到决策树与矩阵分解，最小均方求解器都非常重要。研究者倡导一种新算法，它输入一个 n 维实数向量的有限集合，并输出 d + 1 个向量的加权子集，每个向量的和都是相等的。Caratheodory's Theorem (1907) 证明过程计算这样的子集需要 O(n^2*d^2 ) 时间复杂度，因此在实践中并不实用。

研究者的算法计算这样的子集只需要 O(nd) 的时间复杂度，且在更小但更「智能」的子集上 O(log n) 次调用 Caratheodory 构建。这是不同数据总结技术之间混合的新范式，例如 sketches 和 coresets。作为应用示例，研究者展示了该算法如何用于提升现有 LMS 求解器的性能，例如 scikit-learn 库中的算法，加速能达到 100 倍。最后，现有的实验结果与开源代码都有提供。

下图所示为 FAST-CARATHEODORY-SET 算法的概览，其依次计算均衡的切分、每个集群的 sketch、所有 sketch 并集的核心集合（coreset）B、计算所有切分的联合集合 C，它对应于前面计算的 B、最后递归地计算 C 的核心集合，直到找到一个足够小的核心集合。

评语：从线性、Lasso 回归到奇异值分解和弹性网络，最小均方求解器（Least Mean-Square solver）在许多机器学习算法种处于核心地位。这篇论文展示了如何降低最小均方求解器的计算复杂度一到两个数量级，而且这种复杂度的降低不会带来精度的损失，且能提升数值的稳定性。

该方法依赖于 Caratheodory 定理，其表明一个核心集合（d2 + 1 的点集合，维度为 d）足够表征凸集中所有 n 个点。该论文的新颖之处在于它提出了分治算法（divide-and-conquer），从而通过可接受的复杂度（O(nd + d5 log n)，其中 d

评审者强调了该方法的重要性，它作为实践方法能快速实现并提升现有算法的性能，同时它也可以扩展到其它算法，因为该方法的递归分块原则具有很强的泛化性。

杰出新方向论文奖荣誉提名

论文名称：Putting An End to End-to-End: Gradient-Isolated Learning of Representations

作者：Sindy Löwe、Peter O'Connor、Bastiaan Veeling

机构：阿姆斯特丹大学

论文地址：https://papers.nips.cc/paper/8568-putting-an-end-to-end-to-end-gradient-isolated-learning-of-representations

摘要：在本文中，研究者提出了一种用于局部自监督表征学习的新型深度学习方法。该方法无需标签或端到端反向传播，而是利用数据中的自然顺序。生物神经似乎不需要反向传播全局误差信号就能学习，受此启发，研究者将一个深度神经网络分割成若干梯度独立模块。训练过程中，每个模块都利用 Oord 等人 [2018] 提出的 InfoNCE 边界最大限度地保留该模块的输入信息。尽管这是一种贪婪训练方法，但结果依然表明，每个模块都在前一个模块的输出基础上得到了提高。在视听领域，最上面的模块创造的表征在下游分类任务上得到了非常有竞争力的结果。本文提出的方法支持模块的异步优化，允许非常深的神经网络在未标记数据集上进行大规模分布式训练。

评语：本文依据 Oord 等人提出的无监督标准，重新探讨了深度网络的分层构建，特别是当前输入表征与时空输入表征之间的交互信息。这种感知网络中的自组织也许在算法（避开端到端的优化，因其巨大的内存占用和计算问题）和认知（借「慢功能」的特征转向一种带有生物学合理性的学习过程）方面提供了新的启发。

论文名称：Scene Representation Networks: Continuous 3D-Structure-Aware Neural Scene Representations

作者：Vincent Sitzmann 、Michael Zollhöfer、Gordon Wetzstein

机构：斯坦福大学

论文地址：https://papers.nips.cc/paper/8396-scene-representation-networks-continuous-3d-structure-aware-neural-scene-representations

摘要：利用生成模型进行无监督学习具有发现 3D 场景丰富表征的潜力。虽然几何深度学习已经探索了场景几何的 3D 结构感知表征，但这些模型通常需要显式的 3D 监督。新兴的神经场景表征只能使用各种姿态 2D 图像进行训练，但现有的方法忽略了场景的三维结构。在本文中，研究者提出了场景表征网络（scene representation network，SRN），这是一种连续的 3D 结构感知场景表征，它会同时编码几何和外观。SRN 将场景表征为连续的函数，将世界坐标（world coordinate）映射为局部场景属性的一个特征表征。通过将成像系统地描述为一个可微的 ray-marching 算法，SRN 可以进行端到端的训练，只需要利用 2D 图像和这些图像的摄像机机位，无需深度或形状。这种方法可以在不同场景之间自然泛化，学习过程中强大的几何和外观先验。

评语：该论文将 CV 中的两种主要方法——多视图几何方法和深度表征方法完美地结合在一起。具体而言，本文有三大贡献：1）基于每个体素的神经渲染器，实现了场景的 3D 感知无分辨率渲染；2）一种可微的 ray-marching 算法，解决了沿摄像机投射光线寻找曲面交点的难题；3）一种潜在的场景表征方法，利用自动编码器和超网络对场景表征网络的参数进行回归。

经典论文奖（Test of Time Award）

去年，NeurIPS 大会的经典论文奖发给了 NEC 和谷歌的研究者。经典论文奖的授予原则为「重要贡献、持久影响和广泛吸引力」，本届大会从 2009 年 NIPS 的 18 篇引用最多的论文中选出了持续影响力最高、对研究领域具有杰出贡献的研究。

最终，今年的这一奖项授予 NIPS 2009 论文《Dual Averaging Method for Regularized Stochastic Learning and Online Optimization》及其作者，微软首席研究员 Lin Xiao。Lin Xiao 曾就读于北京航空航天大学和斯坦福大学，自 2006 年起就职于微软研究院。

论文链接：https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/xiao10JMLR.pdf

该研究提出了一种全新在线算法：正则化双重平均算法（RDA），实验证明，RDA 对于ℓ1 正则化的稀疏在线学习非常有效。