AI内参_11_010_精读2017年NIPS最佳研究论文之一如何解决非凸优化问题

你好，我是洪亮杰。

今天我和你分享的主题是精读二零一七年NIPS最佳研究论文之一。

如何解决非凸优化问题？机器学习和人工智能领域的顶级会议神经信息处理系统大会NIPS从一九八七年开始举办，已经有三十多年的历史NIPS二零一七大会于二零一七年十二月四号的九号在美国加利福尼亚州的长滩举行。

每年大会都会在众多的学术论文中挑选出几篇最有新意和价值的论文。

作为最佳研究论文。

在NIPS二零一七上，一共有三篇论文获得了最佳论文的称号。

今天我就带你认真剖析一下其中的一篇具有凸目标的基于方差的正则化。

这篇论文的两位作者都是来自斯坦福大学的学者。

这篇文章理论性很强，主要研究的是一种健壮的优化问题。

也就是说，我们在优化一个损失函数的时候，不仅要考虑损失函数的均值，还要考虑损失函数的方差。

然而，一个既要考虑均值，又要考虑方差的综合的损失函数，往往是一个非凸的问题。

对于一般的非凸优化问题来说，我们往往不能找到一个全局的最优解，甚至是找到局部最优解也很困难。

这篇文章就是要来解决这么一个问题，我先来介绍一下作者群信息。

第一作者，洪生，南空是斯坦福大学运筹学的一名在读博士研究生，他的导师分别是约翰达奇和彼得格林。

二零一三年到斯坦福之前，南空在韩国的韩国科学与技术高级研究所有时候又被称为KAIST,获得工业工程和数学学士学位。

最近两三年，南空已经发表了两篇NIPS的文章，包括我们今天分享的这篇最佳论文以及一篇ICML的论文。

第二，作者约翰达奇是南空的导师之一，达奇可以说是师出名门。

他于二零零七年从斯坦福本科毕业，接着在斯坦福跟随机器学习权威达菲。

科勒拿到了计算机科学的硕士学位，然后又到加州大学伯克利分校跟随统计学习权威。

迈克尔乔丹拿到了计算机科学的博士教位。

在博士阶段的暑假里，达奇还到google研究院中追随约然辛格，积累了非常有价值的实习经验。

之后，他来到了斯坦福大学，担任统计和电气电子工程系的助理教授。

有了这些良好的基础，达奇的学术成绩可以说是非常扎实。

他于二零一零年获得了ICML最佳论文奖。

紧接着二零一一年在google实习期间的工作。

A da grad成为了现在机器学习优化领域的经典算法。

这个工作的论文有超过两千五百次的引用，而且也是深度学习优化算法的一个重要基础。

目前达奇所有论文的引用数超过六千次。

我们首先来看一下这篇文章的主要贡献。

理解文章主要解决了一个什么场景下的问题。

很多机器学习问题其实都可以最终归结于优化一个目标函数，或者有时候叫做损失函数的问题。

针对训练数据集上损失函数的优化，也就是最大化或最小化，并且在测试集上表现优异，是可以被证明为最终能够较好泛化的一种体现。

那么通常情况下，这个损失函数都是针对均值的一个描述。

比如在整个训练数据集上的平均误差，或者说在整个训练数据集上的平均准确度。

然而我们都知道，在一些很偏斜的数据分布上，均值并不是很好的一个数据描述。

即便我们的函数能够在平均的情况下优化一个损失函数，这个函数也有可能在一些甚至大部分数据点上表现不尽如人意。

于是，研究人员就引入了健壮的优化问题，也就是我们希望损失函数在更多的点上有优异的表现。

那么损失函数的健壮性使用损失函数的方差来衡量的。

也就是说我们希望损失函数在不同数据点上的波动压小有了这个概念之后，下一步就显得比较自然啦。

那就是把损失函数的均值部分，也就是我们通常要做的部分和有方差的部分串联起来，形成一个新的目标函数。

这个目标函数有两个部分，第一部分就是均值部分。

第二个部分就是方差的部分，中间有一个自由的参数，把这两个部分衔接起来。

这样我们就有了一个既考虑均值又考虑方差的新的健壮化的优化问题。

然而，一个既要考虑均值，又要考虑方差的综合的损失函数，往往是一个非凸的问题。

什么叫做非凸函数？一个凸问题可以简单理解为函数只有唯一的最小值，并且我们具备有效算法来找到这个最小值。

而对于非凸问题来说，我们往往不能找到一个全局的最优解，或者找到局部最优解也很困难。

健壮优化问题已经在之前的研究中提了出来。

那么这篇文章的主要贡献在于为健壮优化问题，找到了一个凸问题的逼近表达，并基于此提出了一个优化算法，解决了这个新提出的凸问题的近似解。

这里值得注意的一点是，对于非凸问题提出凸问题的近似表达，有解决非凸问题一个重要思路，有很多经典的非凸问题都是通过凸问题的近似来得到解决或者部分解决的。

从这个思路来说，这篇文章是延续了解决这种问题的一贯的策略。

这篇论文的核心方法以及证明都有很强的理论性，需要有一定的数学功底和类似研究背景，才能更好的理解。

如果对文章内容有兴趣，建议不仅要阅读原文的NIPS论文，还需要去阅读其附加的文档，一共有五十多页才能比较全面的理解这篇文章的细节。

我们在这里仅仅从概念上做一个高度浓缩的概略。

作者们在文章中提出了一种叫健壮化的正则风险的目标函数。

这个新的目标函数不是建立在一个叫经验分布上的散度，而这个新的健壮化正则风险是一个凸问题。

直白一点说，这个健壮化的正则风险可以被认为是一个包含两项的式子。

这两项是在数据集上的损失函数的期望加上一个损失函数的方差。

在这个新的两项的式子中，期望和方差都是定义在数据的经验分布上。

于是这样就把这个新提出的风险式子和我们实际需要解决的问题挂上了钩。

当然后面大段的论文就是要证明这两个式子之间的差距到底有多少，是不是新的式子提供了一个比较紧的界限。

紧接着，这篇文章其实讨论了这个健壮化的正则风险，可以写成一个更加相对简单的优化问题。

然后文章在附录中提供了这个简化的优化问题的求解。

虽然这篇文章的核心内容是一个理论结果或者是算法革新，但是这篇文章依然是在两个数据集中做了实验，一个是在UCIML的数据集上展示乐提出的新的健壮化的目标函数，达到了比一般的目标函数更好的效果。

另外一个则是在RCV一文本分类的问题上，比一般的优化目标函数有更好的效果。

今天我为你讲了NIPS二零一七的最佳研究论文之一，文章非常理论化。

文章的一个核心观点是，希望能够通过对损失函数的均值和方差。

同时建模，从而达到让目标函数健壮化的目的。

一起来回顾一下要点。

第一，我们简要介绍了这篇文章的作者群信息。

第二，我们详细介绍了这篇文章要解决的问题以及贡献。

第三，我们简要的介绍了文章提出的方法，核心内容，最后给你留一个思考题，要想控制目标函数的预测结果的方差，除了本文提出的，把均值和方差都涉及到目标函数里，还有没有别的方法？欢迎你给我留言，和我一起讨论。