静园5号院科研讲座:斯坦福大学叶荫宇教授谈机器学习中的数学原理

  2019年4月10日,斯坦福大学管理科学与工程系及计算数学工程研究院的首席教授、冯·诺依曼理论奖(运筹管理学领域最高奖项)唯一一位华人得主叶荫宇教授访问北京大学前沿计算研究中心,并在静园五院做了题为“Distributionally Robust Stochastic and Online Optimization Driven by Data/Samples”的报告。报告由中心讲席教授邓小铁老师主持,听众包括来自北京大学信息科学技术学院、数学学院等单位的师生。

 

叶荫宇教授访问北京大学前沿计算研究中心

  

  在这次讲座中,叶荫宇教授从数学家的角度分析机器学习中的各类问题,深入浅出地给大家介绍了关于分布鲁棒性优化(Distributionally Robust Optimization, DRO)、相关性代价(Price of Correlation, POC)及在线线性优化(Online Linear Optimization)等研究理论。

  

  1. 分布鲁棒性优化(Distributionally Robust Optimization)

  传统的随机优化问题多关注于根据数据的分布,寻找合适的模型参数来最大化期望的效用函数。在多数情况下,期望值是对效用很好的估计,所以算法会有不错的表现。但使用这种方法必须要知悉确切的数据分布才能做优化,而现实世界中,因为我们只能根据数据样本来估计真实的数据分布,这样得到的优化结果很可能不是最优的。

 

  

  上图演示了即便是使用随机优化方法做得很好的分类器也很容易被误导。只需要在左边的熊猫图片中加入微量噪声,就能使分类器把熊猫的图片错误分类成长臂猿。

  

  因为这种对抗样本的存在,研究者们提出了鲁棒性的优化方法。

  

  

  上图演示了即便是使用随机优化方法做得很好的分类器也很容易被误导。只需要在左边的熊猫图片中加入微量噪声,就能使分类器把熊猫的图片错误分类成长臂猿。

  

  因为这种对抗样本的存在,研究者们提出了鲁棒性的优化方法。

  

  

  一种比较有效的思路是,与其优化模型在最坏样本点上的表现,不如优化它在距离真实数据分布不远的一组分布中的最坏分布下的性能。这就是分布鲁棒性优化的基本思路。为了要给出这样一组分布,需要度量这组分布和真实分布的距离。叶教授分别给出了使用Moment Bounds、Likelihood Bounds和Wasserstein distance这三种度量下的分布簇。

  

  

  有意思的是,当使用Wasserstein distance作为分布距离的度量,将分布鲁棒性优化用于逻辑回归时,这种方法等价于在逻辑回归的损失函数上加上了一个正则项。

  

  

  分布鲁棒性优化为我们提供了一种在概率分布上具有置信区间保证的解,可以将这种方法用于很多运筹优化和机器学习的问题上。

  

  2. 相关性代价(Price of Correlation)

  在处理多个随机变量的联合概率分布时,有些时候为了简化计算,会将这些随机变量假设为独立的,这样联合概率就可以直接写成边缘分布的乘积。那么,这样做的风险有多大?什么情况下可以较为“安全地”这样假设呢?为此,叶教授给出了相关性代价POC的定义。

  

  

  POC是一个比值,分子是使用独立分布求解得到的函数值,而分母是使用分布鲁棒性优化得到的函数值。POC通常会大于1,越接近1说明使用独立分布的风险越小;而POC越大说明直接丢弃随机变量间的相关性,风险会很大。

  

  

  叶教授也给出了一些直接的例子,例如,submodular的函数POC较小,而supermodular的函数POC较大。

  

  3. 在线线性优化(Online Linear Optimization)

  叶教授最后给出了他们在在线线性优化领域的一些工作。考虑在一家店里卖衣服的问题,顾客会依次到来并且报出自己的价位,那么店家该如何做决策才能最大化自己的利益呢?

  

  

  传统的方法会将这些顾客“集中起来”,然后统一采用离线算法给出决策。但现实中因为顾客到来后就必须决策,所以只能采用在线优化的算法。

  

  

  因为在线算法必然会依赖于顾客达到的顺序,叶教授在这里展示了不同算法能够达到的理论上下界。

  

  

  叶教授的讲座以数学家的视角来审视机器学习的问题,无论是计算机系还是数学系的同学都受益良多。

  

叶荫宇教授讲座中

  

  讲座视频回看请至北京大学讲座网:http://resource.pku.edu.cn/index.php?r=lecturevideo/view&id=42305

  报告信息、报告人简介请见:https://cfcs.pku.edu.cn/announcement/invited_talks/235837.htm