从动力学角度看优化算法(七):SGD ≈ SVM?
By 苏剑林 | 2020-12-21 | 36431位读者 |众所周知,在深度学习之前,机器学习是SVM(Support Vector Machine,支持向量机)的天下,曾经的它可谓红遍机器学习的大江南北,迷倒万千研究人员,直至今日,“手撕SVM”仍然是大厂流行的面试题之一。然而,时过境迁,当深度学习流行起来之后,第一个革的就是SVM的命,现在只有在某些特别追求效率的场景以及大厂的面试题里边,才能看到SVM的踪迹了。
峰回路转的是,最近Arxiv上的一篇论文《Every Model Learned by Gradient Descent Is Approximately a Kernel Machine》做了一个非常“霸气”的宣言:
任何由梯度下降算法学出来的模型,都是可以近似看成是一个SVM!
这结论真不可谓不“霸气”,因为它已经不只是针对深度学习了,而是只要你用梯度下降优化的,都不过是一个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$,在神经网络中它还有一个非常酷的名字,叫做“Neural Tangent Kernel”,我们将其记为
\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://www.kexue.fm/archives/8009
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Dec. 21, 2020). 《从动力学角度看优化算法(七):SGD ≈ SVM? 》[Blog post]. Retrieved from https://www.kexue.fm/archives/8009
@online{kexuefm-8009,
title={从动力学角度看优化算法(七):SGD ≈ SVM?},
author={苏剑林},
year={2020},
month={Dec},
url={\url{https://www.kexue.fm/archives/8009}},
}
December 21st, 2020
[...]苏剑林. (2020, Dec 21). 《从动力学角度看优化算法(七):SGD ≈ SVM? 》[Blog post]. Retrieved from https://kexue.fm/archives/8009[...]
March 11th, 2021
意味着DNN的能力可能应该是小于等于SVM的? 如果我们提高了SVM的检索速度是不是至少也能打平DNN。
你这样理解也没错,但问题的关键在于SVM的效果依赖于核函数的定义,核函数相当于两个样本之间的相似度,如何去衡量两个样本的相似度这没有通用的解法,比如两张图片的相似度不能用MSE简单度量,而两个句子的相似度就更复杂了。
所以如何根据具体数据来得到更合理的度量?可能还是需要神经网络来学一个度量。OK,这又绕回来神经网络了。
May 20th, 2021
苏神,SVM中α大于0小于C时表示支持向量的点。请求公式(9)中的α的物理含义是什么?
不能是同样的含义吗?
April 29th, 2022
苏老师,如果按照式(7),如果$n$个样本训练模型有:
$f^{n}_{\theta_T}(x) = f_{\theta_0}(x) + \sum_{i\leq n} \int_0^T \alpha_{\theta(t),i} K_{\theta(t)}(x, x_i) dt$
$m$个样本训练模型有:
$f^{m}_{\theta_T}(x) = f_{\theta_0}(x) + \sum_{i\leq m} \int_0^T \alpha_{\theta(t),i} K_{\theta(t)}(x, x_i) dt$
$m+n$个样本训练模型有:
$f_{\theta_T}(x) = f_{\theta_0}(x) + \sum_{i\leq (m+n)} \int_0^T \alpha_{\theta(t),i} K_{\theta(t)}(x, x_i) dt$
也就是 $m+n$个样本训练模型与$m$个样本和$n$个样本独立训练得到的模型有如下关系?
$f_{\theta_T}(x)=f^{n}_{\theta_T}(x)+f^{m}_{\theta_T}(x)-f_{\theta_0}(x)$
其实这只是个有启发性的形式解,它并不像看上去那么显式。比如不同数目样本训练的时候,其实$\theta(t)$也是不一样的,所以严格来讲$\theta(t)$也是样本的函数,因此你这个分解就不成立了(也就是说前三个式子的$\theta(t)$并非同一个$\theta(t)$)