德扑 AI 不完全信息博弈论文领衔，NIPS 2017最佳论文 3 + 1 已经揭晓

本文作者：杨晓凡

编辑：郭奕欣

2017-12-05 15:13

导语：论文接收名单出来已久，今天终于知道花落谁家

雷锋网 AI 科技评论按：人工智能领域最热门会议之一的 NIPS 已经开幕了，新鲜报道纷至沓来。

今年 NIPS 2017 中，接近6000人参会、3240篇论文投稿、678篇接收论文的几个数字都创下了历史记录；甚至仅仅谷歌一家公司就有450人到场、45篇收录论文，可以说是非常吓人了。我们甚至担心，所有参加会议的接近6000名参会者的吃饭问题怎么解决，本届 NIPS 不提供一日三餐，而附近只有十一二家集中的餐馆……（详情见抢先看：6000个满脑子机器学习的人一起开会会是什么样？）

随着正会开始，NIPS 2017 的三篇最佳论文奖和一篇 Test of Time Award 获奖论文都已经公布出来，我们先放下前面的担忧，看看这几篇论文内容如何。

Safe and Nested Subgame Solving for Imperfect-Information Games

在不完全信息博弈中安全、嵌套地求解子博弈（卡内基梅隆大学德扑 AI 的论文）
论文摘要：对于不完全信息的博弈来说，一个子博弈的最优策略可能也会取决于其它的、没有遇到的子博弈中的策略。所以一个子博弈不可以单独求解，必须把基于整个博弈考虑策略；这和围棋象棋之类的完全信息博弈不同。但不管怎么说，首先对整个博弈求解，然后再对子博弈分别求解以改善原来的解的方法也是可行的。这种方法就称作“子博弈求解”。论文中作者们提出了一种子博弈求解方法，它在理论和实际效果方面都要超越以往的方法。作者们同时展示了如何适配这种方法以及以往的子博弈求解方法，以便能够处理原来的动作抽象范围之外的对手动作；这也比先前的最好方法“动作翻译”的效果好得多。最后，作者们表明子博弈求解可以在博弈沿着分支树向下进行的过程中反复运用，这也带来了远低小于之前的探索空间。这些技术都是第一个在一对一无限注德州扑克单挑中打败顶尖人类选手的 AI 的关键组成部分。
论文地址：https://arxiv.org/pdf/1705.02955.pdf
更多报道：德扑 AI 之父托马斯·桑德霍姆：扑克 AI 如何完虐人类，和 AlphaGo 大不同
雷锋网字幕组翻译的论文作者的论文介绍视频

Variance-based Regularization with Convex Objectives

带有凸对象的基于方差的正则化方法
作者们开发了一种风险最小化和随机优化的方法，该方法为方差提供了一个凸代替项（convex surrogate），并能够允许在近似和估计误差之间实现接近最优且计算效率高的权衡。作者们的方法建立在分布鲁棒性优化和 Owen 经验似然值的技术基础之上，并用一些有限样本和渐近结果来表征估计的理论性能。特别是，作者们证明了他们的过程是最优的，在某些情景下他们的方法要比通过自动平衡偏差和方差的经验风险最小化方法有更快地收敛速率。他们给出的经验性证据表明，在实践中估计值确实会在训练样本的方差和绝对性能之间进行权衡。这种权衡相比于很多标准的经验性风险最小化方法，在许多分类问题上的测试性能都提升。
论文地址：https://papers.nips.cc/paper/6890-variance-based-regularization-with-convex-objectives.pdf

A Linear-Time Kernel Goodness-of-Fit Test

一种线性时间核的拟合优度测试方法
作者们提出了一中全新的拟合优度（goodness-of-fit）的适应性测试，其计算成本与样本的数量呈线性关系。作者们通过最小化假阴性率（the false negative rate）来学习最能表明观测样本和参考样本之间差异的测试特性。这种特性是通过 Stein 方法构造的，这意味着没有必要计算模型的归一化常数。作者们分析了新测试的渐近 Bahadur 效率，并证明了在均值偏移的情况下，无论测试中的那个参数都比之前的线性时间核测试具有更高的相对效率。在实验中，作者们的方法的性能超过早期的线性时间测试，与二次时序核测试的能力相匹配（甚至超过它）。在高维以及可以使用模型结构的情况下，作者们的拟合优度测试即使只用从模型中抽取的样本，也能比基于最大平均偏差（Maximum Mean Discrepancy）的二次时序、双样本测试表现得更好。
论文地址：https://papers.nips.cc/paper/6630-a-linear-time-kernel-goodness-of-fit-test.pdf

Random Features for Large-Scale Kernel Machines （NIPS 2007）
用于大规模核学习机器的随机特征方法
论文摘要：为了提高核学习机器的训练速度，这篇论文中提出了一种把输入数据映射到随机的低维特征空间中，然后再使用现有的快速线性化算法的方法。作者们是按照这样的条件设计随机特征的：映射后的数据的内积要和用户指定的具有平移不变性的核的特征空间中的数据内积近似相等。作者们在两组随机的特征上进行了实验，并给它们的逼近各种径向基函数的能力设定了收敛界限，结果表明在大规模分类和回归任务中，使用了这些特征的线性机器学习算法要比当前最好的大规模核学习机器表现更好。
论文地址：http://www.seas.upenn.edu/~cis520/papers/random_features_for_SVM.pdf

NIPS 2017 会一直进行到 12月9日（北京时间12月10日），会议进行期间雷锋网 AI 科技评论会继续带来各方面报道，请继续关注我们。

雷峰网原创文章，未经授权禁止转载。详情见转载须知。