🔥 热搜 🔥
百度今日热点微信公众平台贴吧opggdnf私服百度贴吧知乎dnf公益服百度傻逼
分类
社会娱乐国际人权科技经济其它
🔥 热搜 🔥
上海习近平新疆鄂州父女瓜乌鲁木齐疫情H工口小学生赛高习明泽芊川一笑图包印尼排华
分类
社会娱乐国际人权科技经济其它
查看原文
其他

蒙特卡洛梯度估计方法（MCGE）简述

亦弛 PaperWeekly 2021-09-10


动机


机器学习中最常见的优化算法是基于梯度的优化方法，当目标函数是一个类似如下结构的随机函数 F(θ) 时：



优化该类目标函数，最核心的计算问题是对随机函数 F(θ) 的梯度进行估计，即：



随机函数梯度估计在机器学习以及诸多领域都是核心计算问题，比如：变分推断，一种常见的近似贝叶斯推断方法；强化学习中的策略梯度算法；实验设计中的贝叶斯优化和主动学习方法等。其中，对于函数期望类目标问题，最常见的是基于蒙特卡洛采样的方法。


本文将总结以下内容：


  • 随机梯度估计方法的相关背景知识，包括：蒙特卡洛采样和随机优化

  • 几种经典应用，包括：变分推断、强化学习、实验设计

  • 两类经典的梯度估计算法


背景知识


要了解基于蒙特卡洛采样的梯度估计方法，首先先了解蒙特卡洛采样方法和随机优化方法。


蒙特卡洛采样（MCS）


MCS 是一种经典的求解积分方法，公式（1）中的问题通常可以用 MCS 近似求解如下：



其中， 采样自分布 p(x;θ)，由于采样的不确定性和有限性，这里  是一个随机变量，公式（3）是公式（1）的蒙特卡洛估计器（MCE）。这类方法非常适用于求解形式如公式（1）的积分问题，尤其是当分布 p(x;θ) 非常容易进行采样的时候。


在使用 MCE 时，往往关注其以下四个性质：
1. 一致性，根据大数定理，当所采样的样本数量非常多时，MCE 的估计值将会收敛到积分的真值处。
2. 无偏性，MCE 是对所求积分的一个无偏估计，简单推导如下：



MCE 的无偏性是随机优化算法收敛的重要保证。
3. 小方差，当几个估计方法都是无偏估计时，我们通常会选择方差较小的 MCE，因为更小方差的 MCE 会估计地更准，从而使得优化地效率更高、准确性更好。


4. 可计算性，很多机器学习问题都是高维问题，如何提高 MCE 的可计算性，比如：减少采样、提高并行能力等变得十分重要。
随机优化（SO）
▲ 图1. 随机优化
如图 1 所示，随机优化问题通常包含两个过程，一是仿真过程，输入优化变量，获得响应值 F(θ)，然后计算出，其中是个随机变量 ；二是优化过程，基于梯度，迭代更新优化变量。
不同于确定性优化，随机优化算法包含两个部分的随机性：

  • 仿真过程中，由于系统响应 F(θ) 是随机变量，因此其梯度以及 Hessian 矩阵等都是随机的，需要近似估计；


  • 优化过程中，由于采用一些近似处理手段，比如用 mini batch 来估计梯度会产生随机性。

应用


基于蒙特卡洛采样的梯度估计方法（MCGE）在很多研究领域都起到了核心作用，本节总结一下其在机器学习领域中的典型应用。


变分推断（Variational Inference, VI）
▲ 图2. VI和MCMC


VI 是贝叶斯推断中的一大类方法，在统计机器学习（贝叶斯视角）中具有广泛的应用。从上图中可以看出，变分推断 (VI) 的思想非常简单。假设一个变分分布簇，在概率空间中找到一个离真实分布最近的分布。VI 巧妙地将一个推断问题转化为了优化问题，优化目标是 KL(Q||P)，即待求分布 Q 和真实后验分布 P 的距离，优化的变量是分布 Q 的描述参数。


VI 方法综述将在另外一篇文章中详细介绍，本文只简单说明其目标函数是一个形如公式（1）的问题。考虑一个生成模型问题 p(z)p(x|z)，其中 z 是隐变量，x 是观测变量，p(z) 是先验分布，p(x|z) 是似然函数。根据贝叶斯公式：



其中 p(x)=ʃp(z)p(z|x)，称为 evidence，通常 p(x) 是一个不可积的多重积分，导致后验分布 p(z|x) 无法获得解析解。如上述思路所述，假设后验分布用一个变分分布 q(z|x;θ) 来近似，通过构造如下优化问题：



来求解使得两个分布距离最小的变分分布参数 θ，从而得到近似后验分布。


因为真实后验分布是未知的，直接优化公式（6）是一件比较有挑战的事情，VI 巧妙地将其转化为优化 ELBO 的问题。


简单的推导过程如下：



等号两边移动一下可得：


由 KL 散度的定义可知，KL(q(z|x;ф)||p(z|x;θ))≥0，同时 logp(x;θ) 是个常数，所以求优化问题（6）等价于求如下优化问题：



相当于求解 log evidence lower bound，即 eblo。继续推导如下：



公式（10）的形式如公式（1），可以用 MCGE 进行梯度估计，从而优化求解。


变分推断方法是一个热门研究领域，而核心问题是如何高效求解 elbo 优化问题，在统计物理、信息论、贝叶斯推断、机器学习等诸多领域由广泛的应用。


强化学习


强化学习是机器学习中一大类热门研究领域，尤其是 AlphaGo 的横空出世，为强化学习带来了更多的关注和更多的研究人员。本文将不对强化学习的任务和各种概念进行赘述，强化学习中的一大类问题是无模型的策略搜索问题，即通过优化累计回报的均值学习到最优策略。所谓累计回报的均值形式如下：



公式（11）形式亦如公式（1），可以用 MCGE 进行梯度估计，从而优化求解。
实验设计
实验设计是个非常广泛的领域，主要是研究如何为实验设置合适的配置，比如：自动机器学习中的超参数调优（HPO）、神经架构搜索（NAS），通过主动学习（Active Learning）选择更加合适的样本进行标注，老虎机问题的求解（Bandit）等等。


这类任务中经常会遇到一个问题，如何选择下一个更好的配置，使得选择之后比选择之前性能的概率会有所提升。因此需要优化如下问题：



公式（12）形式亦如公式（1），可以用 MCGE 进行梯度估计，从而优化求解。


简单总结一下，优化是机器学习训练中最重要的部分，而其中很多优化问题都是形如公式（1）的问题，而 MCGE 是解决这类问题的有效手段，接下来介绍两种经典的 MCGE 方法。


方法综述


公式（1）中的积分内是一个分布和代价函数的乘积，在对其梯度进行近似估计时，可以从两个方面进行求导。由此，可以将梯度估计方法大致分为两类：

  • 求解分布测度的导数，包括本文介绍的 score function gradient estimator

  • 求解代价函数的导数，包括本文介绍的 pathwise gradient estimator


根据公式（2）待估计的梯度是，直接计算会非常困难，一个直观的思路是研究如何将期望的梯度转化为梯度的期望，从而可以利用 MCS 做无偏近似估计。本文将会介绍两种经典的方法，来解决这个问题。


Score Function Gradient Estimator (SFGE)


SFGE 是最经典的方法，也是适用性最好的方法，在强化学习中的策略梯度优化问题里，有一个算法叫做 REINFORCE，正是基于 SFGE 来做的。SFGE 也常常被用于解决目标函数不可导的优化问题以及一些黑盒优化问题。


Score Function 简介


所谓的 score function 是，之所以选择这个函数，是因为以下两点原因：


1. score function 的期望为 0，证明如下：



这样会带来非常多的便利，比如：一种降低估计方差的思路，将代价函数 f(x) 改造为 f(x)-b，其中 b 是所谓的 baseline。因为 score function 的期望为 0，所以：



2. score function 的方差是 Fisher 信息量。


SFGE的推导过程



推导中，用到了一个复合函数求导的公式，如下：



利用 MC 采样可以估计出梯度，如下：



其中，。


从上述推导中可以看到，通过引入 score function，可以成功地将期望的梯度变换为梯度的期望，从而实现梯度的近似估计。


这中间有一个过程是将积分和微分操作的位置进行了对换，此操作并非可以随意进行，需要满足一定的条件，但一般的机器学习问题都会满足。


SFGE的性质


  • 代价函数 f(x) 可以是任意函数。比如可微的，不可微的；离散的，连续的；白箱的，黑箱的等。这个性质是其最大的优点，使得很多不可微的甚至没有具体函数的黑箱优化问题都可以利用梯度优化求解。


  • 分布函数 p(x;θ) 必须对 θ 是可微的，从公式中也看得出来。


  • 分布函数必须是便于采样的，因为梯度估计都是基于 MC 的，所以希望分布函数便于采样。


  • SFGE 的方差受很多因素影响，包括输入的维度和代价函数。


SFGE的典型应用


SFGE 由于其对代价函数没有限制，具有非常广阔的应用场景，以下是几个非常热门的应用：


  • 策略梯度优化算法 REINFORCE 及其变种

  • 基于 GAN 的自然语言生成

  • 基于自动微分的黑盒变分推断


这些典型的应用，后续可专门写一篇文章进行介绍。


Pathwise Gradient Estimator (PGE)


不同于 SFGE 对代价函数没有任何约束，PGE 要求代价函数可微，虽然 SFGE 更具一般性，但 PGE 会有更好的性质。PGE在机器学习领域有一个重要的方法是 reparameterization trick，它是著名的深度生成模型 VAE 中一个重要的步骤。


PGE简介


PGE 的思路是将待学习的参数从分布中变换到代价函数中，核心是做分布变换（即所谓的 reparameterization ，重参数化），计算原来分布下的期望梯度时，由于变换后的分布不包含求导参数，可将求导和积分操作进行对换，从而基于 MC 对梯度进行估计。



如上述公式，从一个含参 θ 分布中采样，等同于从一个简单无参分布中采样，然后进行函数变换，并且此函数的参数也是 θ。变换前，采样是直接从所给分布中进行，而采用重参数化技巧后，采样是间接地从一个简单分布进行，然后再映射回去，这个映射是一个确定性的映射。其中，映射有很多中思路，比如：逆函数、极变换等方法。


PGE 的一个重要理论依据是 Law of the Unconscious Statistician (LOTUS) ，即：



从定理中可以看到，计算一个函数的期望，可以不知道其分布，只需要知道一个简单分布，以及从简单分布到当前分布的映射关系即可。


PGE推导过程


基于 Law of the Unconscious Statistician (LOTUS) 对 PGE 进行推导，如下：



利用 MC 可以估计出梯度为：



其中 。从推导中可以看出，分布中的参数被 push 到了代价函数中，从而可以将求导和积分操作进行对换。
分布变换是统计学中一个基本的操作，在计算机中实际产生各种常见分布的随机数时，都是基于均匀分布的变换来完成的。有一些常见的分布变换可参见下表：

▲ 图3. 常见分布变换
PGE的性质

  • 代价函数要求是可微的，比 SFGE 更严格

  • 在使用 PGE 时，并不需要显式知道分布的形式，只需要知道一个基础分布和从该基础分布到原分布的一个映射关系即可，这意味着，不管原来分布多么复杂，只要能获取到以上两点信息，都可以进行梯度估计；而 SFGE 则需要尽量选择一个易采样的分布

  • PGE 的方差受代价函数的光滑性影响


PGE的典型应用


  • 深度生成模型 VAE 和 GAN 的训练

  • 基于 Normalising Flow 的变分推断

  • 用于连续控制问题的强化学习


总结


蒙特卡洛采样（MCS）是求解函数期望的常用近似方法，优点是简单易用，通过一定的变换，可以对期望的梯度进行估计，从而完成对代价函数的优化，实现很多任务。
但 MCS 的缺点也非常明显，为了保证一定的估计效果，往往需要很大量的采样规模，对于大数据、高维度等实际问题来说，过多的采样会导致算法效率极低，从而降低了算法的实用性。从这个角度来说，如何研究一些新方法，来提高期望或者期望梯度的近似估计效率是一个非常重要的问题。最后，推荐两篇 2019 年的工作 [4] [5]，旨在尝试解决这个问题。 
上述研究虽然有一定的局限性，但尝试了新的思路来解决这一问题。其中第 [5] 篇，尝试用一些 Uncertainty Qualification (UQ) 的方法，比如用一些不确定性传播的估计方法，对期望进行确定性估 计，而非随机采样估计，在一定的假设下，确实有非常显著的效果。


参考文献


[1] Mohamed, S., Rosca, M., Figurnov, M., & Mnih, A. (2019). Monte Carlo Gradient Estimation in Machine Learning. ArXiv Preprint ArXiv:1906.10652. 

[2] Fu, M. C. (2005). Stochastic Gradient Estimation, 105–147. 

[3] Shakir's Machine Learning Blog http://blog.shakirm.com 

[4] Postels, J., Ferroni, F., Coskun, H., Navab, N., & Tombari, F. (2019). Sampling-free Epistemic Uncertainty Estimation Using Approximated Variance Propagation. ArXiv Preprint ArXiv:1908.00598. 

[5] Wu, A., Nowozin, S., Meeds, T., Turner, R. E., Lobato, J. M. H., & Gaunt, A. (2019). Deterministic Variational Inference for Robust Bayesian Neural Networks. In ICLR 2019 : 7th International Conference on Learning Representations.




点击以下标题查看更多往期内容： 





#投 稿 通 道#

 让你的论文被更多人看到 



如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。


总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 


PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学习心得或技术干货。我们的目的只有一个，让知识真正流动起来。


📝 来稿标准：

• 稿件确系个人原创作品，来稿需注明作者个人信息（姓名+学校/工作单位+学历/职位+研究方向） 

• 如果文章并非首发，请在投稿时提醒并附上所有已发布链接 

• PaperWeekly 默认每篇文章都是首发，均会添加“原创”标志


📬 投稿邮箱：

• 投稿邮箱：hr@paperweekly.site 

• 所有文章配图，请单独在附件中发送 

• 请留下即时联系方式（微信或手机），以便我们在编辑发布时和作者沟通




🔍


现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧



关于PaperWeekly


PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。


▽ 点击 | 阅读原文 | 获取最新论文推荐

: ， . Video Mini Program Like ，轻点两下取消赞 Wow ，轻点两下取消在看

您可能也对以下帖子感兴趣

文章有问题？点此查看未经处理的缓存