动机
机器学习中最常见的优化算法是基于梯度的优化方法,当目标函数是一个类似如下结构的随机函数 F(θ) 时:优化该类目标函数,最核心的计算问题是对随机函数 F(θ) 的梯度进行估计,即:
随机函数梯度估计在机器学习以及诸多领域都是核心计算问题,比如:变分推断,一种常见的近似贝叶斯推断方法;强化学习中的策略梯度算法;实验设计中的贝叶斯优化和主动学习方法等。其中,对于函数期望类目标问题,最常见的是基于蒙特卡洛采样的方法。
背景知识
要了解基于蒙特卡洛采样的梯度估计方法,首先先了解蒙特卡洛采样方法和随机优化方法。MCS 是一种经典的求解积分方法,公式(1)中的问题通常可以用 MCS 近似求解如下:其中, 采样自分布 p(x;θ),由于采样的不确定性和有限性,这里 是一个随机变量,公式(3)是公式(1)的蒙特卡洛估计器(MCE)。这类方法非常适用于求解形式如公式(1)的积分问题,尤其是当分布 p(x;θ) 非常容易进行采样的时候。1. 一致性,根据大数定理,当所采样的样本数量非常多时,MCE 的估计值将会收敛到积分的真值处。2. 无偏性,MCE 是对所求积分的一个无偏估计,简单推导如下:
3. 小方差,当几个估计方法都是无偏估计时,我们通常会选择方差较小的 MCE,因为更小方差的 MCE 会估计地更准,从而使得优化地效率更高、准确性更好。4. 可计算性,很多机器学习问题都是高维问题,如何提高 MCE 的可计算性,比如:减少采样、提高并行能力等变得十分重要。如图 1 所示,随机优化问题通常包含两个过程,一是仿真过程,输入优化变量,获得响应值 F(θ),然后计算出,其中是个随机变量 ;二是优化过程,基于梯度,迭代更新优化变量。不同于确定性优化,随机优化算法包含两个部分的随机性:应用
基于蒙特卡洛采样的梯度估计方法(MCGE)在很多研究领域都起到了核心作用,本节总结一下其在机器学习领域中的典型应用。变分推断(Variational Inference, VI)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)中的积分内是一个分布和代价函数的乘积,在对其梯度进行近似估计时,可以从两个方面进行求导。由此,可以将梯度估计方法大致分为两类:根据公式(2)待估计的梯度是,直接计算会非常困难,一个直观的思路是研究如何将期望的梯度转化为梯度的期望,从而可以利用 MCS 做无偏近似估计。本文将会介绍两种经典的方法,来解决这个问题。Score Function Gradient Estimator (SFGE)SFGE 是最经典的方法,也是适用性最好的方法,在强化学习中的策略梯度优化问题里,有一个算法叫做 REINFORCE,正是基于 SFGE 来做的。SFGE 也常常被用于解决目标函数不可导的优化问题以及一些黑盒优化问题。所谓的 score function 是,之所以选择这个函数,是因为以下两点原因:1. score function 的期望为 0,证明如下:这样会带来非常多的便利,比如:一种降低估计方差的思路,将代价函数 f(x) 改造为 f(x)-b,其中 b 是所谓的 baseline。因为 score function 的期望为 0,所以:2. score function 的方差是 Fisher 信息量。其中,。从上述推导中可以看到,通过引入 score function,可以成功地将期望的梯度变换为梯度的期望,从而实现梯度的近似估计。这中间有一个过程是将积分和微分操作的位置进行了对换,此操作并非可以随意进行,需要满足一定的条件,但一般的机器学习问题都会满足。代价函数 f(x) 可以是任意函数。比如可微的,不可微的;离散的,连续的;白箱的,黑箱的等。这个性质是其最大的优点,使得很多不可微的甚至没有具体函数的黑箱优化问题都可以利用梯度优化求解。
分布函数 p(x;θ) 必须对 θ 是可微的,从公式中也看得出来。
分布函数必须是便于采样的,因为梯度估计都是基于 MC 的,所以希望分布函数便于采样。
SFGE 的方差受很多因素影响,包括输入的维度和代价函数。
SFGE 由于其对代价函数没有限制,具有非常广阔的应用场景,以下是几个非常热门的应用:策略梯度优化算法 REINFORCE 及其变种
基于 GAN 的自然语言生成
基于自动微分的黑盒变分推断
Pathwise Gradient Estimator (PGE)不同于 SFGE 对代价函数没有任何约束,PGE 要求代价函数可微,虽然 SFGE 更具一般性,但 PGE 会有更好的性质。PGE在机器学习领域有一个重要的方法是 reparameterization trick,它是著名的深度生成模型 VAE 中一个重要的步骤。PGE 的思路是将待学习的参数从分布中变换到代价函数中,核心是做分布变换(即所谓的 reparameterization ,重参数化),计算原来分布下的期望梯度时,由于变换后的分布不包含求导参数,可将求导和积分操作进行对换,从而基于 MC 对梯度进行估计。如上述公式,从一个含参 θ 分布中采样,等同于从一个简单无参分布中采样,然后进行函数变换,并且此函数的参数也是 θ。变换前,采样是直接从所给分布中进行,而采用重参数化技巧后,采样是间接地从一个简单分布进行,然后再映射回去,这个映射是一个确定性的映射。其中,映射有很多中思路,比如:逆函数、极变换等方法。PGE 的一个重要理论依据是 Law of the Unconscious Statistician (LOTUS) ,即:从定理中可以看到,计算一个函数的期望,可以不知道其分布,只需要知道一个简单分布,以及从简单分布到当前分布的映射关系即可。基于 Law of the Unconscious Statistician (LOTUS) 对 PGE 进行推导,如下:其中 。从推导中可以看出,分布中的参数被 push 到了代价函数中,从而可以将求导和积分操作进行对换。分布变换是统计学中一个基本的操作,在计算机中实际产生各种常见分布的随机数时,都是基于均匀分布的变换来完成的。有一些常见的分布变换可参见下表:总结
蒙特卡洛采样(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.
[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.