Press "Enter" to skip to content

从动力学角度看优化算法(七):SGD ≈ SVM?

众所周知,在深度学习之前,机器学习是SVM(Support Vector Machine,支持向量机)的天下,曾经的它可谓红遍机器学习的大江南北,迷倒万千研究人员,直至今日,“手撕SVM”仍然是大厂流行的面试题之一。然而,时过境迁,当深度学习流行起来之后,第一个革的就是SVM的命,现在只有在某些特别追求效率的场景以及大厂的面试题里边,才能看到SVM的踪迹了。

 

峰回路转的是,最近Arxiv上的一篇论文 《Every Model Learned by Gradient Descent Is Approximately a Kernel Machine》
做了一个非常“霸气”的宣言:

 

任何由梯度下降算法学出来的模型,都是可以近似看成是一个SVM!

 

这结论真不可谓不“霸气”,因为它已经不只是针对深度学习了,而且只要你用梯度下降优化的,都不过是一个SVM(的近似)。笔者看了一下原论文的分析,感觉确实挺有意思也挺合理的,有助于加深我们对很多模型的理解,遂跟大家分享一下。

 

一般的SVM可以表示为如下形式:

 

\begin{equation}y = g\left(\beta + \sum_i \alpha_i K(x, x_i)\right)\label{eq:svm}\end{equation}

 

其中$\{(x_i, y_i)\}$是训练数据对,$\alpha_i, \beta$是可学习参数,标准核机器的输出是一个标量,所以这里考虑的$y,\alpha_i, \beta$都是标量。$K(x, x_i)$则称为“核函数”,它衡量了输入$x$与训练样本$x_i$之间的某种相似度。SVM是更广义的“核机器(Kernel Machine)”模型的一种(可能是最出名的一种),属于“核方法”范畴。

 

直观理解,其实SVM就是一个检索模型,它检索了输入与所有训练样本的相似度$K(x, x_i)$,然后加权求和。所以,严格上来说,SVM的参数量除了各个$\alpha_i$和$\beta$外,还包括训练集的输入$x_i$,说白了,它就是把整个训练集都给记下来了。相比之下,深度学习模型也有很多参数,但这些参数都是直接由梯度下降求出来的,并不是直接把训练集存起来,而由于这个特点,所以深度学习模型通常认为是能自动学习到更智能的特征。

 

SVM理论不是本文的重点,我们知道它的形式如$\eqref{eq:svm}$即可。在这一节中,我们将会推导梯度下降的一个解析解,并且发现这个解跟式$\eqref{eq:svm}$具有非常相似的形式,因而我们说梯度下降出来的模型都可以近似看成一个SVM模型。

 

假设我们的模型是$y=f_{\theta}(x)$,$\theta$是可训练参数,单个样本的损失函数是$l(y_i, f_{\theta}(x_i))$,那幺训练所用的损失函数为

 

\begin{equation}L(\theta) = \sum_i l(y_i, f_{\theta}(x_i))\end{equation}

 

为了使得后面的推导更简洁,这里使用了求和的形式,一般情况下是求平均才对,但这不影响最终的结果。在“ 从动力学角度看优化算法
”系列文章中,我们坚持的观点是梯度下降求解参数$\theta$,相当于在求解动力系统

 

\begin{equation}\frac{d\theta}{dt} = -\frac{\partial L(\theta)}{\partial \theta}=-\sum_i \frac{\partial l(y_i, f_{\theta}(x_i))}{\partial \theta}=-\sum_i \frac{\partial l(y_i, f_{\theta}(x_i))}{\partial f_{\theta}(x_i)}\frac{\partial f_{\theta}(x_i)}{\partial \theta}\end{equation}

 

这同样也是本文的重要出发点。现在,我们考虑$f_{\theta}(x)$的变化情况:

 

\begin{equation}\begin{aligned}

 

\frac{df_{\theta}(x)}{dt} &= \sum_j \frac{\partial f_{\theta}(x)}{\partial \theta_j}\frac{d\theta_j}{dt}\\

 

&=-\sum_j \frac{\partial f_{\theta}(x)}{\partial \theta_j}\sum_i \frac{\partial l(y_i, f_{\theta}(x_i))}{\partial f_{\theta}(x_i)}\frac{\partial f_{\theta}(x_i)}{\partial \theta_j}\\

 

&=-\sum_i \frac{\partial l(y_i, f_{\theta}(x_i))}{\partial f_{\theta}(x_i)} \sum_j \frac{\partial f_{\theta}(x)}{\partial \theta_j} \frac{\partial f_{\theta}(x_i)}{\partial \theta_j}

 

\end{aligned}\end{equation}

 

可以看到,对$j$求和这一步,事实上就是梯度的内积$\langle\nabla_{\theta} f_{\theta}(x), \nabla_{\theta} f_{\theta}(x_i)\rangle$,我们将其记为

 

\begin{equation}K_{\theta}(x, x_i) = \langle\nabla_{\theta} f_{\theta}(x), \nabla_{\theta} f_{\theta}(x_i)\rangle = \sum_j \frac{\partial f_{\theta}(x)}{\partial \theta_j} \frac{\partial f_{\theta}(x_i)}{\partial \theta_j}\end{equation}

 

并且记$\alpha_{\theta,i}=-\frac{\partial l(y_i, f_{\theta}(x_i))}{\partial f_{\theta}(x_i)}$,那幺

 

\begin{equation}\frac{df_{\theta}(x)}{dt} = \sum_i \alpha_{\theta,i} K_{\theta}(x, x_i)\end{equation}

 

可以,模型$f_{\theta}(x)$每个时刻的变化量都是一个SVM,假如我们已经知道优化过程中$\theta$的变化轨迹为$\theta(t),t\in[0, T]$,那幺最终的模型就是

 

\begin{equation}f_{\theta_T}(x) = f_{\theta_0}(x) + \sum_i \int_0^T \alpha_{\theta(t),i} K_{\theta(t)}(x, x_i) dt\label{eq:sgdf}\end{equation}

 

经过一番推导,我们的得到了式$\eqref{eq:sgdf}$,它是当学习率趋于0的梯度下降的理论解。从推导过程可以看到,这个结果只依赖于梯度下降本身,跟模型具体结构没关系。对于式$\eqref{eq:sgdf}$,我们可以从下面的角度理解它。

 

首先,我们将记$\beta(x) = f_{\theta_0}(x)$,它其实就是初始化模型,尽管它理论上是依赖于$x$的,但很多时候它会表现得接近一个常数(比如多分类模型时,初始化模型的输出通常接近一个均匀分布),因此我们可以将当它是一个常数项。然后,我们可以记

 

\begin{equation}\alpha_i (x) = \frac{\int_0^T \alpha_{\theta(t),i} K_{\theta(t)}(x, x_i) dt}{\int_0^T K_{\theta(t)}(x, x_i) dt}, \quad K(x, x_i) = \int_0^T K_{\theta(t)}(x, x_i) dt

 

\end{equation}

 

那幺

 

\begin{equation}f_{\theta_T}(x) = \beta(x) + \sum_i \alpha_i (x) K(x, x_i)\end{equation}

 

这在形式上就跟SVM很像了,区别就在于SVM的$\alpha_i,\beta$应该是独立于$x$的,而这里则依赖于$x$。$\beta(x)$我们已经分析过了,而$\alpha_i(x)$由于它是数学期望的形式,被期望的对象不依赖于$x$,而是权重依赖于$x$,那幺它可能对$x$的依赖也相对弱些,因此跟$\beta(x)$一样,我们也许可以近似地忽略它对$x$的依赖。不过,在笔者看来,依不依赖$x$并不算是关键,最重要的是最终的结果呈现出了$\sum\limits_i \alpha_i(x) K(x, x_i)$的形式,那就意味着它在一定程度上也是学习到了一个检索训练集的过程,这才是它真正跟SVM的相似之处。

 

上述讨论的是输出标量的模型,如果输出是一个$d$维向量,那幺最终形式也是相同的,只不过此时$\beta(x),\alpha_i(x)$也是一个$d$维向量,而$K(x, x_i)$是一个$d\times d$的矩阵,这种情况下哪怕$\beta(x),\alpha_i(x)$与$x$无关,也不是我们通常意义下的(多分类)SVM模型。但它依然具有$\sum\limits_i \alpha_i(x) K(x, x_i)$的形式,因此某种意义上来说它仍然是检索训练集的操作。

 

此外,上述结论针对的是(全量)梯度下降,而对于随机梯度下降(SGD)来说,我们不再是用全量数据来算损失函数,对此我们在第一篇 《从动力学角度看优化算法(一):从SGD到动量加速》
也做过讨论,可以认为SGD是在梯度下降的基础上引入了噪声,也就是收敛路径$\theta(t)$带有随机噪声,其余结果基本不变,因此上述结论对SGD也是成立的。

 

那幺,这个结果能给我们带来什幺思想冲击呢?原论文在“Discussion”那一节花了相当长的篇幅讨论这个事情,这里我们也来琢磨一下这个事情。

 

从深度学习的视角来看,这个结果揭示了深层神经网络模型与传统的核方法之间的联系,借助核方法的可解释性来增强神经网络的可解释性。比如,通过梯度内积作为相似度度量,我们或许可以从训练集中检索出与输入相近的训练样本,以解释输出的决策过程。更进一步地,如果该方向能够得到更为精确的量化,那幺它有可能大大改进增量学习的方法,即对于新来的标注样本,我们可能只需要想办法往模型中添加$a_i(x) K(x, x_i)$的项,而不需要重新训练模型。

 

反过来看,该结果也许能促进核机器、核方法的发展。传统的核函数依赖于认为定义,而上述梯度内积形式的核函数给我们带来了新的构建核函数的思路,增强核方法对复杂函数的建模能力。同时,由于梯度下降与核机器的相似性,我们最终或许可以通过梯度下降来训练核机器,从而克服核机器在大规模数据下的训练难题,等等。

 

还有一些别的脑洞可以发散一下,比如我们知道对于凸优化问题有唯一解,并且理论上梯度下降总可以找到这个解,而前面又说梯度下降相当于一个SVM。所以,这是不是意味着所有凸优化问题的解都相当于一个SVM?这个脑洞够不够大?

 

总之,揭示梯度下降与核机器之间的联系,有助于两者的进一步借鉴与融合,并且有可能发展出一些新的研究思路。

 


转载到请包括本文地址:
https://kexue.fm/archives/8009

 


更详细的转载事宜请参考:

《科学空间FAQ》

 

如果您还有什幺疑惑或建议,欢迎在下方评论区继续讨论。

 

如果您觉得本文还不错,欢迎/本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!

 

如果您需要引用本文,请参考:

 

苏剑林. (2020, Dec 21). 《从动力学角度看优化算法(七):SGD ≈ SVM? 》[Blog post]. Retrieved from https://kexue.fm/archives/8009

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注