机器学习技法笔记(3)-对偶SVM

文章目录
  1. 对偶的引入
    1. 拉格朗日函数
    2. 对偶问题转化
  2. 求解对偶问题
    1. 最小化
    2. 最大化
    3. 模型求解
    4. 数据表示模型
  3. 后续

对偶SVM主要解决在非线性转换之后维度变高二次规划问题求解困难的问题。

在上一节的Linear SVM的最后提到了,在非线性分类问题中,我们一般作非线性转换\(\textbf{z}_n = \phi(\textbf{x}_n)\),从而在\(\textbf{z}\)空间里面进行线性分类,在非线性转换过程一般是一个升维的过程,将\(\textbf{z}\)的维度一般设为\(\tilde{d}\), 一般情况 \(\tilde{d} >> d\),(比如2维变5维,3维变19维等是一个非线性升高),这样在高维空间内部,在二次规划问题中的就会有\(\tilde{d}+1\)个变量,那么权值维度同样也为\(\tilde{d}+1\)维,以及\(N\)个约束,此外\(Q\) 矩阵维度会十分大,达到\(\tilde{d}^2\),因此,一旦\(\tilde{d}\)变大了, 二次规划问题求解就会变得很困难。

这一节就是通过引入对偶问题以及下一节的核,来消除SVM解决非线性问题转换到高维空间中对\(\tilde{d}\)依赖问题。

对偶的引入

我们的目标是将原始的非线性问题,转化为另外一个对等问题,使得新的对等问题的规模或者说复杂度(主要指二次规划问题的规模,比如变量数目,约束条件数目等)仅仅与原始数据的规模(样本量)有关,与转换的高维空间无关,如下:

拉格朗日函数

在引入对偶问题之前,在回顾上一节的二次规划问题SVM:

\[ \begin{align} & \min \limits_{b, \textbf{w}} \quad \frac{1}{2}\textbf{w}^T\textbf{w} \\& s.t. \quad y_n(\textbf{w}^T\textbf{x}+b) \geq 1 \end{align} \]

我们从另一个角度考虑,这里我们引入拉格朗日函数(Lagrange Function)来将约束条件和目标函数结合到一个式子:

\[\mathcal{L}(b, \textbf{w}, \mathbf{\alpha}) = \frac{1}{2}\textbf{w}^T \textbf{w} + \sum\limits_{n=1}^{N}\alpha_n(1-y_n(\mathbf{w}^T\mathbf{x}+b)), \quad \alpha_n \geq 0\]

其中\(\mathbf{\alpha}\) 为拉格朗日乘子(Lagrange Multiplier)。

下面我们将说明原始SVM二次规划问题与下式等价,即:

\[\mathbf{SVM} \equiv \min \limits_{b, \mathbf{w}} (\max \limits_{\alpha_n \geq 0} \mathcal{L}(b, \mathbf{w},\alpha))\]

首先右式表示多元变量的优化问题,首先在固定\(b,\mathbf{w}\)下,通过调整\(\alpha\),使得\(\mathcal{L}(b, \textbf{w}, \alpha)\) 最大,进而再优化外面的\(\min\)部分。

再看\(\max\)部分,分两种情况叙述:

  • \(\mathbf{w},b\)不满足约束条件\(y_n(\mathbf{w}^Tx+b) \geq 1\),即: \(1-y_n(\mathbf{w}^T\textbf{x}+b) > 0\),再结合\(\alpha_n \geq 0\),很显然, \(\max(\mathcal{L}) \to \infty\)
  • \(\mathbf{w},b\)满足\(1-y_n(\mathbf{w}^T\textbf{x}+b) \leq 0\),那么在求\(\max\)的时候,显然需要\(\alpha_n(1-y_n(\mathbf{\mathbf{w}^T\mathbf{x}+b})) = 0\),此时\(\max(\mathcal{L}) = \frac{1}{2}\textbf{w}^T \textbf{w}\)

显然,求完了\(\max\)之后,在优化外层求\(\min\)的时候,对于上述第一种\(\infty\)情况,肯定不会是最优解,因此最后的优化方程为: \(\min \frac{1}{2}\textbf{w}^T \textbf{w}\),因此与原始问题等价。这样,我们就把原始的含有约束条件的优化问题,转为不含条件的表达式。

对偶问题转化

接着化简,因为\(\max \geq any\),则对于任意一个给定的\(\alpha^{'}\),下式显然成立:

\[ \min \limits_{b, \mathbf{w}} (\max \limits_{\alpha_n \geq 0} \mathcal{L}(b, \mathbf{w},\alpha)) \geq \min\limits_{b, \mathbf{w}} \mathcal{L}(b, \mathbf{w},\alpha^{'})\]

既然上述的\(\alpha^{'}\)是任意给定的,那么左式也一定大于等于其中的那个最大的,那么下式也显然成立:

\[ \min \limits_{b, \mathbf{w}} (\max \limits_{\alpha_n \geq 0} \mathcal{L}(b, \mathbf{w},\alpha)) \geq \max\limits _{all \ \alpha_n \geq 0} (\min\limits_{b, \mathbf{w}} \mathcal{L}(b, \mathbf{w},\alpha^{'}))\]

到此为止: 观察上述不等式,最大化与最小化做了交换,这样的不等式,右式就称为左式的对偶问题,左式的下限就是右式。

此外,上述不等式关系属于一种弱对偶关系(Weak Duality)。如果满足下面的几个条件,则可以去掉不等号,从而转为强对偶关系(Strong Duality)

  • 原始问题为是凸优化问题 (convex primal)
  • 原始问题线性可分的(feasible primal)
  • 约束条件是线性的(Linear constraints)

显然,原始问题满足以上强对偶条件,也就是说存在一组最优解\(\mathbf{w},b,\alpha\)同时满足式子两边。到此,我们将原始的问题转化为其如下的对偶问题:

\[\begin{align*}\max\limits_{all \ \alpha_n \geq 0}{\left ( \min\limits_{b,\mathbf{w}}{ \underbrace{\frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum\limits_{n=1}^{N}\alpha_n(1-y_n(\mathbf{w}^T\mathbf{z}_n+b))}_{\mathcal{L}(b, \mathcal{w}, \alpha)}}\right)}\end{align*}\]

为什么要将原始问题,转换为对偶问题去求解呢?

开始说了, 目标是降低算法的规模或者说是复杂度。原始问题的最关于后需要解决的\(\min\limits_{b,\mathbf{w}}\)部分的复杂度是关于\(\mathbf{w}\)的,也就是高维空间的维度,求解很困难。而对偶问题最后要解决的\(\max\limits_{\alpha}\)则是关于\(\alpha_n\)的,复杂度跟样本数量\(N\)有关,在非线性分类中一般情况升维会达到很大的数量级(比如后续的高斯核是无穷维),远远大于样本数量,这个时候用对偶问题来求解就会容易。

此外,如果是线性分类且样本维度低于样本数量的话,那就直接使用原始问题求解即可,无需对偶。

求解对偶问题

最小化

固定\(\alpha\), 对拉格朗日函数\(\mathcal{L}\)最小化(凸函数),\(\mathcal{L}\)含有\(b, \mathbf{w}\)两个变量,因此分别求一阶微分:

首先对\(b\)求偏微分,得到:

\[\begin{align*} \frac{\partial\mathcal{L}(b, \mathbf{w}, \alpha)}{\partial \ b} = \sum\limits_{n=1}^{N}\alpha_ny_n = 0\end{align*}\]

因此我们最终得到的最优解应该满足上述条件,接着作一步转化:

\[\min\mathcal{L}(b, \mathbf{w},\alpha) = \min \frac{1}{2}\mathbf{w}^T\mathbf{w} + \sum\alpha_n(1-y_n\mathbf{w}^T\mathbf{z}^n) - {b*\sum\alpha_ny_n}\]

既然我们的最优解需要满足\(\sum\alpha_ny_n = 0\),那么上式也应该满足,那么蓝色部分就会变成0,问题得到了简化。

接着对\(\mathbf{w}\)求微分如下:

\[\begin{align*} \frac{\partial\mathcal{L}(b, \mathbf{w}, \alpha)}{\partial \ \mathbf{w}} = \mathbf{w} - \sum\limits_{n=1}^{N}\alpha_ny_n\mathbf{z}_n = \mathbf{0}\end{align*}\]

即最优解满足: \(\mathbf{w} = \sum\limits_{n=1}^{N}\alpha_ny_n\mathbf{z}_n\),接着继续化简\(\min\mathcal{L}\):

\[\begin{align} \min\mathcal{L}(b, \mathbf{w},\alpha) & \Leftrightarrow \min \frac{1}{2}\mathbf{w}^T\mathbf{w} + \sum\alpha_n(1-y_n\mathbf{w}^T\mathbf{z}^n) \\ &\Leftrightarrow \min \frac{1}{2}\mathbf{w}^T\mathbf{w} - \sum \alpha_ny_n\mathbf{z}^n\mathbf{w}^T+ \sum\alpha_n \\ & \Leftrightarrow {\min} -\frac{1}{2}\mathbf{w}^T\mathbf{w} + \sum\limits_{n=1}^{N}\alpha_n \\ & \Leftrightarrow -\frac{1}{2} \Arrowvert \sum\limits_{n=1}^{N}\alpha_ny_n\mathbf{z}_n\Arrowvert + \sum\limits_{n=1}^{N}\alpha_{n}\end{align} \]

经过分别求偏微分,并且将得到的条件代入到优化方程,最终去掉了\(\min\),仅仅与\(\alpha\)有关。

现在我们的问题化简至下式:

\[\begin{align*}\max\limits_{\alpha_n \geq 0, \ \sum\alpha_ny_n =0, \ \mathbf{w}=\sum\alpha_ny_n\mathbf{z}^n}\left( -\frac{1}{2}\Arrowvert\sum\limits_{n=1}^{N}\alpha_ny_n\mathbf{z}_n\Arrowvert^2+ \sum\limits_{n=1}^{N}\alpha_{n}\right)\end{align*}\]

至此最小化部分完成,完全转为了\(\alpha\)的问题。

最大化

上一步的最小化结束了,这一部分做外层的最大化,这里仅仅与\(\alpha\)有关。首先做一个转化,变为求\(\min\),然后展开平方如下:

\[\begin{align} \min\limits_{\alpha} & \quad \frac{1}{2}\sum\limits_{n=1}^{N}\sum\limits_{m=1}^{N}{\alpha_n\alpha_m} y_ny_m\mathbf{z}_n\mathbf{z}_m {-}\sum\limits_{n=1}^{N}\alpha_n \\ s.t. & \quad \alpha _n \geq 0, \ \sum\limits_{n=1}^{N}\alpha_ny_n =0 \end{align} \]

相当与将条件再提出来,就转化为QP问题求解!并且上式中\(N\)个变量\(\alpha_1...\alpha_N\),以及\(N+1\)个约束条件,这样就看着摆脱了高维,求解相对容易,这便得到就是标准SVM对偶问题

下面便是根据QP问题的格式,写出对应的\(Q,p,A,c\)

这里需要说明一下:

  • \(q_{m,n}\)表示矩阵\(Q\)的第\(m\)行第\(n\)列的元素
  • 对于\(\sum y_n\alpha_n =0\),改为两个不等式条件: \(\sum y_n \alpha_n \leq 0,\ \sum y_n\alpha_n \geq 0\),因此一共有\(N+2\)个约束条件。

模型求解

利用QP Solver 就可以解决上述的二次规划问题,得到最优的\(\alpha=[\alpha_1...\alpha_N]\),下面介绍如何根据\(\alpha\)求解最优的\(\mathbf{w},b\),进而得到模型。

到这里整理一下已经有的条件:

  • 对于原始问题有: \(y_n(\mathbf{w}^T\mathbf{z}_n+b) \geq 1\)
  • 对于对偶问题有: \(\alpha_n \geq 0\)
  • 对于对偶问题里层的\(\min\)优化求解中,有: \(\sum \alpha_ny_n =0; \ \mathbf{w}=\sum\alpha_ny_n\mathbf{z}_n\)
  • 对于原始问题里层的\(\max\)问题中:上面得到结论有: \(\alpha_n(1-y_n(\mathbf{\mathbf{w}^T\mathbf{z}_n+b})) = 0\) ,被称为complementary slackness

注:上述条件即使二次规划问题中的 KKT条件(Karush-Kuhn-Tucker Conditions)

根据条件3,便可得到 \(\mathbf{w} = \sum\limits_{n=1}^{N}\alpha_ny_n\mathbf{z}_n\)

根据条件4,我们知道\(\alpha_n\)以及\(1-y_n(\mathbf{w}^T\mathbf{z}_n + b)\) 至少有一个为0,我们只需要找到一个\(\alpha_n > 0\)的数据点,这样就会有:\(1-y_n(\mathbf{w}^T\mathbf{z}_n + b) = 0\),进而得到:

\[b = y_n - \mathbf{w}^T \mathbf{z}_n, \quad \alpha_n > 0\]

这里需要注意的是: \(\alpha_n > 0\)的点满足\(y_n(\mathbf{w}^T\mathbf{z}_n + b) = 1\),即分类边界上的点,也就是SV(Support Vector),这也就说明了 ,我们只需要SV就可以得到\(\mathbf{w},b\),这时候其它的点不需要。

简略总结一下标准对偶SVM的流程

  1. 根据训练数据,(非线性转换\(z_n = \phi(x_n)\), 写出QP问题的\(Q,p,a,c\)
  2. 使用QP Solover 求出最优的\(\alpha\)
  3. 根据条件约束,求出\(\mathbf{w},b\)
  4. 得到模型:\(g_{svm} = sign(\mathbf{w}^T\phi(\mathbf{x})+b)\)

数据表示模型

在开始介绍SVM的时候,就是以PLA为基础的,下面看看二者:

首先在Dual SVM中,\(\mathbf{w}\)是以\(y_n\mathbf{z}_n\)的线性组合求解的,其中参数为\(\alpha_n\); 在PLA中 同样,每个分类错误的点,都会加上\(y_n\mathbf{z}_n\),因此实质上\(\mathbf{w}\)同样线性组合求解得到。

其实还有很多线性模型或者算法,比如前面的Linear Regresson, Logistic Regression等如果初始化的\(\mathbf{w} = \mathbf{0}\),最终得到的最优解同样是数据的线性组合。

这个时候,我们就称参数w是被训练数据表示出来的(represented by data),只不过SVM的权重参数只需通过\(\alpha_n >0\)的SV表示即可。(PS:数据表示的模型可能造成数据泄漏?)

后续

这一节主要讲的是 标准对偶SVM,旨在解决高维空间下,二次规划问题求解困难的问题,下面对比Linear SVM与Dual SVM:

看起来我们的对偶问题的规模成功做到了只与数据样本量\(N\)有关,与高维空间的维度\(\tilde{d}\)无关,其实不然,实际内部的计算量还是很大的:

\(Q\)矩阵的元素: \(q_{n,m} = y_ny_m\mathbf{z}_m\mathbf{z}_n\),实际为\(R^{\tilde{d}}\)内的内积! 还是没有摆脱高维。不过对偶问题相比原始问题在非线性数据 的处理上,求解已经更加容易了。 至于如何在求解\(q_{n,m}\)的时候,彻底不再依赖\(\tilde{d}\),那就是下节的内容了,引入带核的SVM。