从采样看优化:可导优化与不可导优化的统一视角
By 苏剑林 | 2020-06-23 | 55927位读者 |不少读者都应该知道,损失函数与评测指标的不一致性是机器学习的典型现象之一,比如分类问题中损失函数用交叉熵,评测指标则是准确率或者F1,又比如文本生成中损失函数是teacher-forcing形式的交叉熵,评测指标则是BLEU、ROUGE等。理想情况下,当然是评测什么指标,我们就去优化这个指标,然而评测指标通常都是不可导的,而我们多数都是使用基于梯度的优化器,这就要求最小化的目标必须是可导的,这是不一致性的来源。
前些天在arxiv刷到了一篇名为《MLE-guided parameter search for task loss minimization in neural sequence modeling》的论文,顾名思义,它是研究如何直接优化文本生成的评测指标的。经过阅读,笔者发现这篇论文很有价值,事实上它提供了一种优化评测指标的新思路,适用范围并不局限于文本生成中。不仅如此,它甚至还包含了一种理解可导优化与不可导优化的统一视角。
采样视角 #
首先,我们可以通过采样的视角来重新看待优化问题:设模型当前参数为$\theta$,优化目标为$l(\theta)$,我们希望决定下一步的更新量$\Delta\theta$,为此,我们先构建分布
\begin{equation}p(\Delta\theta|\theta)=\frac{e^{-[l(\theta + \Delta\theta) - l(\theta)]/\alpha}}{Z(\theta)},\quad Z(\theta) = \int e^{-[l(\theta + \Delta\theta) - l(\theta)]/\alpha} d(\Delta\theta)\end{equation}
其中$\alpha > 0$是一个超参数。这个分布的意义很明显,就是将$\Delta\theta$视为一个随机变量,而使得$l(\theta + \Delta\theta)$越小的$\Delta\theta$出现概率则越大。有了这个分布之后,我们定义下一步的更新量为它的期望
\begin{equation}\Delta\theta_* = \int p(\Delta\theta|\theta)\Delta\theta d(\Delta\theta) = \mathbb{E}_{\Delta\theta\sim p(\Delta\theta|\theta)}[\Delta\theta]\label{eq:delta}\end{equation}
在这个视角里边,我们并没有对$l(\theta)$的可导性做假设,因此上述定义对于可导和不可导的优化都是通用的。另外,我们可以通过调节$\alpha$来控制更新的稳定性,当$\alpha\to 0$时,由$p(\Delta\theta|\theta)$的定义可知只有使得$l(\theta + \Delta\theta)$最小的$\Delta\theta$的概率才不为0,这意味着$\Delta\theta_*$就是下降得最快的方向;当$\alpha\to +\infty$时,$p(\Delta\theta|\theta)$趋于均匀分布,所以$\Delta\theta_*$趋于0,也就是最稳。通过选择一个适合的$\alpha$,理论上可以让优化过程在“快”与“稳”之间达到一个好的平衡,这在直觉上能取得泛化性能更好的结果。
当然,到目前为止的定义还是理论上的,我们还不知道$p(\Delta\theta|\theta)$的解析形式,也不知道如何从里边采样,更不用说算它的期望值的。下面我们将会看到,这个理论形式是如何逐步实践到可导场景和不可导场景的。
可导目标 #
对于可导的$l(\theta)$,我们虽然不能精确求出$p(\Delta\theta|\theta)$来,但是我们可以做泰勒展开得到一个近似分布,进而去估算$\Delta\theta_*$。结果显示,展开到一阶、二阶近似,我们分别可以得到梯度下降法和牛顿法。也就是说,梯度下降和牛顿法某种意义上都只是该视角下的一个特例。
梯度下降 #
作为第一次尝试,我们假设$l(\theta)$是一阶可导的,那么由泰勒展式可以得到
\begin{equation}l(\theta + \Delta\theta) - l(\theta)\approx \Delta\theta^{\top}\nabla_{\theta}l(\theta)\end{equation}
这也就是$p(\Delta\theta|\theta)\sim e^{-\Delta\theta^{\top}\nabla_{\theta}l(\theta)/\alpha}$,如果$\Delta\theta$无约束,那么是无法完成归一化的,我们不妨限制$\Vert\Delta\theta\Vert\leq \epsilon$,并且记$\nabla_{\theta}l(\theta)=g$,那么
\begin{equation}p(\Delta\theta|\theta) = \frac{e^{-\Delta\theta^{\top}g/\alpha}}{Z(g)},\quad Z(g)=\int_{\Vert\Delta\theta\Vert\leq\epsilon}e^{-\Delta\theta^{\top}g/\alpha}d(\Delta\theta)\end{equation}
而很明显$\Delta\theta_* = -\nabla_g \ln Z(g)$,所以关键是求出$Z(g)$。设$\Delta\theta$与$g$的夹角为$\eta$,那么
\begin{equation}Z(g)=\int_{\Vert\Delta\theta\Vert\leq\epsilon}e^{-\Vert\Delta\theta\Vert\times\Vert g\Vert \times (\cos\eta) / \alpha}d(\Delta\theta)\end{equation}
这是一个在高维超球内的积分,由于各向同性的存在,所以当模长$\Vert g\Vert$固定后,整个积分结果也就固定了,也就是说$Z(g)$只跟$g$的模长有关,跟它的方向无关,所以也可以记为$Z(\Vert g\Vert)$。我们不需要知道$Z(\Vert g\Vert)$的具体形式,知道它仅仅是模长$\Vert g\Vert$的函数就行了,这时候
\begin{equation}\Delta\theta_* = -\nabla_g \ln Z(g)= - \frac{Z'(\Vert g\Vert)}{Z(\Vert g\Vert)}\nabla_g\Vert g\Vert = - \frac{Z'(\Vert g\Vert)}{Z(\Vert g\Vert)}\frac{g}{\Vert g\Vert}\end{equation}
所以$\Delta\theta_*$的方向就是$-g$的方向,也就是梯度的反方向,这样我们就导出梯度下降了,可以说它是式$\eqref{eq:delta}$的一阶近似。另外,具体算出$Z(g)$也是可以的,只不过它并非初等函数,过程可以参考stackexchange上的讨论 Integral of exp over the unit ball。
牛顿法 #
如果$l(\theta)$是二阶可导的,那么可以展开到二阶
\begin{equation}l(\theta + \Delta\theta) - l(\theta)\approx \Delta\theta^{\top}\nabla_{\theta}l(\theta) + \frac{1}{2}\Delta\theta^{\top}\nabla_{\theta}^2 l(\theta) \Delta\theta\end{equation}
记$g=\nabla_{\theta}l(\theta),\mathcal{H}=\nabla_{\theta}^2 l(\theta)$,我们就有
\begin{equation}\begin{aligned}
\log p(\Delta\theta|\theta)\sim&\, -\Delta\theta^{\top}g - \frac{1}{2}\Delta\theta^{\top} \mathcal{H} \Delta\theta\\
=&\, - \frac{1}{2}\left(\Delta\theta+\mathcal{H}^{-1}g\right)^{\top}\mathcal{H}\left(\Delta\theta+\mathcal{H}^{-1}g\right)+ \frac{1}{2}g^{\top} \mathcal{H} g
\end{aligned}\end{equation}
很明显,因为$p(\Delta\theta|\theta)$的指数部分关于$\theta$是二次的,所以$p(\Delta\theta|\theta)$是一个高斯分布,而上式则意味着该高斯分布的均值为$-\mathcal{H}^{-1}g$、协方差矩阵为$\mathcal{H}^{-1}$,所以$\Delta\theta_*=-\mathcal{H}^{-1}g$,这个结果对应的就是牛顿法了,因此可以说牛顿法是式$\eqref{eq:delta}$的二阶近似。
不可导目标 #
对于不可导的$l(\theta)$,上述的泰勒展开近似也就无法做到了,理论上我们只能通过直接采样的方式去估算$\Delta\theta_*$了,而原论文则提出,我们可以通过重要性采样来提高采样效率和估算精度,这就是论文的核心思想和主要贡献了。
重要性采样 #
这里先一般化地简介一下重要性采样(Importance Sampling)概念。设有概率分布$p(x)$,以及函数$f(x)$,我们要估算
\begin{equation}\int p(x)f(x)dx = \mathbb{E}_{x\sim p(x)}[f(x)]\end{equation}
这也要求我们从$p(x)$中采样出若干个样本$x_1,x_2,\dots,x_n$出来,然后去算$\frac{1}{n}\sum\limits_{i=1}^n f(x_i)$。然而,这里边可能存在两个困难:
1、我们可能根本不知道怎么从$p(x)$里边采样;
2、就算我们知道怎么从$p(x)$中采样,但对于类似变分自编码器的场景,$p(x)$是带参数的,需要保留梯度,而直接采样计算不一定能做到这一点。
这种情况下,或许重要性采样能帮助我们,它需要我们找到一个既知道概率密度的表达式、又方便采样的分布$q(x)$,然后作如下改写:
\begin{equation}\int p(x)f(x)dx = \int q(x)\left[\frac{p(x)}{q(x)}f(x)\right]dx = \mathbb{E}_{x\sim q(x)}\left[\frac{p(x)}{q(x)}f(x)\right]\label{eq:is}\end{equation}
这时候采样转移到了$q(x)$上,而根据我们的假设,$q(x)$采样是容易进行的,并且$q(x)$的解析式已经知道,所以$\frac{p(x)}{q(x)}f(x)$也是可以计算的,如果$p(x)$有参数需要计算梯度,那么它的梯度也得到了保留。很明显,如果$q(x)$越接近$p(x)$,估算效率就越高,$q(x)$代表着对$p(x)$各个样本的“重要性”的一种先验估计,因此这种思路就称为重要性采样。
这样一来,假设$x_1,x_2,\dots,x_n\sim q(x)$,我们就有
\begin{equation}\mathbb{E}_{x\sim p(x)}[f(x)]\approx \frac{1}{n}\sum_{i=1}^n \frac{p(x_i)}{q(x_i)}f(x_i)\label{eq:is-2}\end{equation}
不过,还有一个小问题,式$\eqref{eq:is}$或式$\eqref{eq:is-2}$都要求我们知道$p(x)$的精确表达式,有时候这一点我们也不能做到,比如前面的$p(\Delta\theta|\theta)$我们只知道它正比于$e^{-[l(\theta + \Delta\theta) - l(\theta)]/\alpha}$,其归一化因子是没法直接算出来的。这种情况下,我们可以借助关系式
\begin{equation}1=\int p(x)dx=\int q(x)\left[\frac{p(x)}{q(x)}\right]dx=\mathbb{E}_{x\sim q(x)}\left[\frac{p(x)}{q(x)}\right]\approx\frac{1}{n}\sum_{i=1}^n \frac{p(x_i)}{q(x_i)}\end{equation}
也就是说$\left[\frac{1}{n}\frac{p(x_1)}{q(x_1)},\frac{1}{n}\frac{p(x_2)}{q(x_2)},\dots,\frac{1}{n}\frac{p(x_n)}{q(x_n)}\right]$应当是近似归一化的,如果我们只知道$p(x)\sim \rho(x)$而不知道归一化因子,那么我们可以手动完成归一化,此时式$\eqref{eq:is-2}$变为
\begin{equation}\mathbb{E}_{x\sim p(x)}[f(x)]\approx \sum_{i=1}^n \frac{\rho(x_i)\big/q(x_i)}{\sum\limits_{i=1}^n \rho(x_i)\big/q(x_i)}f(x_i)\label{eq:is-3}\end{equation}
这就省去了归一化因子的计算。
借力可导 #
至此,我们所需要的数学工具都已经准备齐全了,可以正式迎接我们的不可导目标了。假设是$l(\theta)$是评测指标,比如是平均正确率、平均BLEU等,它是我们需要优化的最终目标,但它是不可导的。不过在大多数场景下,我们都能找到一个可导的(近似的)优化目标$\tilde{l}(\theta)$,而通常我们都是直接用梯度下降优化$\tilde{l}(\theta)$,这就造成了优化目标与评测指标的不一致性。
但不得不说,很多时候$\tilde{l}(\theta)$确实是$l(\theta)$的一个良好近似,换言之$-\nabla_{\theta}\tilde{l}(\theta)$确实指出了一个比较靠谱(但不是最优)的更新方向,这时候我们就可以借助重要性采样了。构建$q(\Delta\theta|\theta)$为正态分布$\mathcal{N}(\Delta\theta; -\nabla_{\theta}\tilde{l}(\theta), \sigma^2)$,根据重要性采样的式$\eqref{eq:is-3}$,我们有
\begin{equation}
\Delta\theta_*=\mathbb{E}_{\Delta\theta\sim q(\Delta\theta|\theta)}\left[\frac{p(\Delta\theta|\theta)}{q(\Delta\theta|\theta)}\Delta\theta\right]\approx\sum_{i=1}^n \frac{e^{-[l(\theta + \Delta\theta_i) - l(\theta)]/\alpha}\big/\mathcal{N}(\Delta\theta_i; -\nabla_{\theta}\tilde{l}(\theta), \sigma^2)}{\sum\limits_{i=1}^n e^{-[l(\theta + \Delta\theta_i) - l(\theta)]/\alpha}\big/\mathcal{N}(\Delta\theta_i; -\nabla_{\theta}\tilde{l}(\theta), \sigma^2)}\Delta\theta_i
\label{eq:sg}\end{equation}
其中$\Delta\theta_1,\Delta\theta_2,\dots,\Delta\theta_n\sim\mathcal{N}(\Delta\theta; -\nabla_{\theta}\tilde{l}(\theta), \sigma^2)$。除此之外,$q(\Delta\theta|\theta)$还可以使用混合模型,原论文使用的是:
\begin{equation}q(\Delta\theta|\theta)=\lambda \mathcal{N}(\Delta\theta; 0, \sigma^2) + (1-\lambda)\mathcal{N}(\Delta\theta; -\nabla_{\theta}\tilde{l}(\theta), \sigma^2)\end{equation}
大家可能比较关心采样数目,原论文在文本生成任务中选择了$n=4$,结果就有明显的改善了,说明有了$q(\Delta\theta|\theta)$的“指引”后,$n$不需要太大。
策略梯度 #
一般情况下,如果需要直接优化评测指标,常见的方法是通过强化学习中的“策略梯度(Policy Gradient)”,所以看到这里的读者也许会有疑问:上述方法跟策略梯度有什么区别吗?孰优孰劣?
假设单个样本的评测指标为$l(y_t,y_p)$,其中$y_t$是真实标签,$y_p$是预测结果,那么总的平均指标为
\begin{equation}l(\theta)=\mathbb{E}_{(x_t,y_t)\sim\mathcal{D}}\left[l\left(y_t, \mathop{\text{argmax}}_y p_{\theta}(y|x_t)\right)\right]\end{equation}
不可导源于$\mathop{\text{argmax}}$操作,而策略梯度将其变为
\begin{equation}\tilde{l}(\theta)=\mathbb{E}_{(x_t,y_t)\sim\mathcal{D}}\left[\mathbb{E}_{y\sim p_{\theta}(y|x_t)}\left[l\left(y_t,y\right)\right]\right]\end{equation}
然后利用(参考《漫谈重参数:从正态分布到Gumbel Softmax》)
\begin{equation}\nabla_{\theta}\int p_{\theta}(x)f(x)dx = \int f(x)\nabla_{\theta}p_{\theta}(x)dx =\int p_{\theta}(x)f(x)\nabla_{\theta}\log p_{\theta}(x)dx\end{equation}
得到
\begin{equation}\nabla_{\theta}\tilde{l}(\theta)=\mathbb{E}_{(x_t,y_t)\sim\mathcal{D}}\left[\mathbb{E}_{y\sim p_{\theta}(y|x_t)}\left[l\left(y_t,y\right)\nabla_{\theta}\log p_{\theta}(y|x_t)\right]\right]\label{eq:pg}\end{equation}
这就是策略梯度的一般形式,也称为REINFORCE估计。
式$\eqref{eq:sg}$和式$\eqref{eq:pg}$是两种从不同的角度得出的更新方向,它们的区别在哪呢?可以看到,核心的区别在于采样对象:式$\eqref{eq:sg}$的采样是$\mathbb{E}_{\Delta\theta\sim q(\Delta\theta|\theta)}$,$\eqref{eq:pg}$的采样是$\mathbb{E}_{y\sim p_{\theta}(y|x_t)}$。所以原论文提供的式$\eqref{eq:sg}$是“采样多组参数、每组参数输出一个样本”来计算更新量,策略梯度的式$\eqref{eq:pg}$则是“只需一组参数、但要采样输出多个样本”来计算更新量。
从计算量来看,应当是策略梯度计算量少一些,因为$\mathbb{E}_{y\sim p_{\theta}(y|x_t)}$这一步采样多个样本可以并行来;当然,理论上$\mathbb{E}_{\Delta\theta\sim q(\Delta\theta|\theta)}$采样多组参数来预测各自的样本也可以并行来,但并不好写。不过,策略梯度的问题也不少,典型问题就是梯度估计的方差太大,所以都需要普通的似然目标来预训练到差不多了,然后才用策略梯度来微调;而原论文的式$\eqref{eq:sg}$则自始至终都试图直接优化评测指标,并且借助可导目标来实现重要性采样,结合了可导优化和不可导优化的优势。
文章小结 #
本文介绍了一个理解优化算法的新视角,在该视角之下可导和不可导目标的优化得到了统一:对于可导的目标函数,在该视角之下分别做一阶和二阶展开,我们分别可以得到梯度下降法和牛顿法;而对于不可导的目标函数,我们借助可导近似来进行重要性采样,同样也可以完成不可导的目标优化。
转载到请包括本文地址:https://spaces.ac.cn/archives/7521
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Jun. 23, 2020). 《从采样看优化:可导优化与不可导优化的统一视角 》[Blog post]. Retrieved from https://spaces.ac.cn/archives/7521
@online{kexuefm-7521,
title={从采样看优化:可导优化与不可导优化的统一视角},
author={苏剑林},
year={2020},
month={Jun},
url={\url{https://spaces.ac.cn/archives/7521}},
}
June 30th, 2020
通过阅读这篇文章,我了解到一种通过采样,对不可导的评测目标进行可导近似的方法,以实现优化目标与评测目标一致的目的。但我注意到,全文仅对评测目标的可导性进行了讨论。在我的理解里,不使用评测目标作为优化目标的原因,除了不可导,还可能是因为评测目标函数非凸。那么,在应用这种方法时,是否应该对近似函数的凸性进行讨论?
讨论这个没有什么意义,因为不管可不可导,深度学习的优化目标就没有几个是凸的,换句话说深度学习的优化目标几乎都是非凸的,而我们就只想要一个极小值点。
August 26th, 2020
你好,可以解释下为什么从(4),推出增量的最佳选择呢
不明白你想问什么,能表达清晰一点吗?
“很明显Δθ∗=−∇glnZ(g)“ 这里我也不太明白
直接根据$Z(g)$的定义算一下$\nabla_g \ln Z(g)$就可以了。
January 9th, 2021
为何将期望(公式2)做为下一步的更新量,这么做是出于什么样的考虑呢?
相当于枚举所有的$\Delta\theta$,看$l(\theta+\Delta\theta)$相比于$l(\theta)$的下降程度来定义一个权重,然后将所有的$\Delta\theta$加权平均,作为最终的更新方向,直觉上应该是这样的选择是一个比较稳妥的做法?
并且可以通过调节$\alpha$来调节平滑程度。比如$\alpha\to 0$的话,实际上就相当于取使得$l(\theta+\Delta\theta)$最小的那个$\Delta\theta$(但其实我们做不到)。
July 13th, 2021
请问“Ey∼pθ(y|xt)这一步采样多个样本可以并行来;当然,理论上EΔθ∼q(Δθ|θ)采样多组参数来预测各自的样本也可以并行来,但并不好写”这部分可以具体讲一下吗?为什么策略梯度的采样可以并行来?
从$p(y|x)$中采样一般都可以并行来的啊,比如seq2seq模型,对于给定输入$x$,可以通过随机采样算法,一次性解码出多个结果,甚至可以同时输入多个$x$,同时解码一批输出,这都不难实现。这取决于$p(y|x)$本身的设计,跟优化算法没关系。
就是我理解的程序应该是{[采样第一次,计算结果]、[采样第二次,计算结果]……[采样第n次,计算结果],对n次计算取平均}。您说的同时解码出多个结果是怎么样的一个形式吗,我还没有get到
采样也就是一种预测,预测时batch_size=1你就那么容易理解,batch_size > 1你就这么难理解?
还有,如果我要从正态分布中采样100个数,非得要采样完一个之后才能采样下一个?我不能np.random.randn(100)一次性生成?
独立重复采样,既然都说了“独立、重复”,每个样本的采样互不影响,那么可并行性是显然成立的。究竟你心中有哪个信条,让你对这么显然成立的事实都有所怀疑?
April 7th, 2024
(6)中 $\nabla_\theta \| g\| $ 下标写错啦
谢谢,已经修正。