提出对偶SVM的动机
上一讲提到的线性SVM可以很容易地被延展到非线性的情况，只需要引入非线性特征变换\(\boldsymbol{\Phi}\)就可以。引入以后的问题描述为 \[ \begin{align*} \min_{ {\bf w}, b} \hspace{3ex}&\frac{1}{2}{\bf w^\mathsf{T}w}\\ {\rm subject\ to}\hspace{3ex} &y_n({\bf w^\mathsf{T}}\underbrace{ {\bf z}_n}_{\boldsymbol{\Phi}({\bf x}_n)} + b) \ge 1{\rm\ for\ }n = 1,2,\ldots, N \end{align*} \] 非线性硬间隔SVM的算法就可以被修改为
- 设置\({\rm Q} = \left[\begin{matrix} 0 & {\bf 0}_\tilde{d}^\mathsf{T} \\ {\bf 0}_\tilde{d} & {\rm I}_\tilde{d}\end{matrix}\right];{\bf p} = {\bf 0}_{\tilde{d}+1};{\bf a}_n^\mathsf{T} = y_n\left[\begin{array}{c}1 & {\bf z}_n^\mathsf{T}\end{array}\right] ;c_n = 1\)
- \(\left[\begin{array}{c} b \\ {\bf w}\end{array}\right] \leftarrow {\rm QP}({\rm Q}, {\bf p}, {\rm A}, {\bf c})\)
- 将\(b \in \mathbb{R}\)和\({\bf w} \in \mathbb{R}^\tilde{d}\)返回为\(g_{\rm SVM}({\bf x}) = {\rm sign}({\bf w}^\mathsf{T}\boldsymbol{\Phi}({\bf x}) + b)\)
非线性硬间隔SVM的思路是将SVM的优点（间隔大，有效VC维低，鲁棒性强）和特征变换的优点（能够形成非线性的边界）结合起来。但是这里有个问题：\(\bf x\)经过非线性特征转换以后，映射到新空间里得到的\(\bf z\)通常维度比较高。记映射后向量的维度为\(\tilde{d}\)，则求解QP时需要面对\(\tilde{d}+1\)个变量和\(N\)个限制条件。因此，需要探索一种方法使得SVM不去依赖\(\tilde{d}\)
这种方法的核心思路为，将原来的二次规划问题（有\(\tilde{d}+1\)个变量和\(N\)个限制条件）转换为一个等价的二次规划问题（有\(N\)个变量和\(N+1\)个限制条件）。这种新的问题被称为原始SVM的对偶问题
回顾第14讲介绍正则化时，要求解的原始问题也是带了一个限制条件。当时的做法是进行了一些变换，转而求解一个没有条件，称为“放大误差”的最优化问题。即这两个问题也存在一个等价关系： \[ \min_{\bf w} E_{\rm in}({\bf w})\ {\rm s.t.\ }{\bf w^\mathsf{T}w} \le C \Leftrightarrow \min_{\bf w} E_{\rm aug}({\bf w}) = E_{\rm in}({\bf w}) + \frac{\lambda}{N}{\bf w^\mathsf{T}w} \] 这里用到的工具称为拉格朗日乘子，也就是\(\lambda\)。做法是把限制条件乘上一个\(\lambda\)，再加到要求解的式子里。这时，\(\lambda\)可以看做是限制条件中参数\(C\)的一个对应。同样的思想也可以用来求解前述的非线性硬间隔SVM，不过具体做法会稍微有点不同：此时这些拉格朗日乘子都会被看做是一个变量，去解跟这个变量有关的对偶问题。而每个限制条件都会对应一个拉格朗日乘子，因此最后会有\(N\)个未知的\(\lambda\)
所以，第一步要做的就是移除原有问题中的条件限制。这一步可以通过引入拉格朗日乘子（这里不再记为\(\lambda\)，而是记为\(\alpha\)）和定义拉格朗日函数做到。这里的拉格朗日函数为 \[ \mathcal{L}(b, {\bf w}, \boldsymbol{\alpha}) = \underbrace{\frac{1}{2}{\bf w^\mathsf{T}w}}_{\rm objective} + \sum_{n=1}^N \alpha_n \underbrace{(1-y_n({\bf w^\mathsf{T}z}_n+b))}_{\rm constraint} \] 为什么拉格朗日函数定义是合理的？下面试着进行说明：原有的问题其实等价于 \[ {\rm SVM} \equiv \min_{b, {\bf w}} \left(\max_{ {\rm all\ }\alpha_n \ge 0}\mathcal{L}(b, {\bf w}, \boldsymbol{\alpha})\right) \] 这个式子的意思是
- 先考察所有\(b\)和\(\bf w\)。对于给定的\(b\)和\(\bf w\)，寻找所有可能的\(N\)个非负的\(\alpha_n\)，满足\(\mathcal{L}\)最大的\(\boldsymbol{\alpha}\)是要找的\(\boldsymbol{\alpha}\)
- 这样，对所有\(b\)和\(\bf w\)，都能找到它们能做到的\(\mathcal{L}\)的最大值。在这些最大值中，求一个最小值。满足这个最小值的\(b\)和\(\bf w\)就是要找的\(b\)和\(\bf w\)
那么问题来了，为什么这个等价关系存在？事实上，对所有的\(b\)和\(\bf w\)，可以分为两组：
- “坏的”，也就是违反了（某一个）限制条件的\(b\)和\(\bf w\)（violate）。限制条件要求\(y_n({\bf w^\mathsf{T}z}_n + b) \ge 1\)，对应的就是\(1 - y_n({\bf w^\mathsf{T}x}_n + b) \le 0\)。如果这组\(b\)和\(\bf w\)违反了限制条件，那么就会有\(1 - y_n({\bf w^\mathsf{T}x}_n + b) > 0\)。将其带入到拉格朗日函数里，求和项中有至少一项的限制条件就会是个正数。前面说，要找到所有可能的\(N\)个非负的\(\alpha_n\)，满足\(\mathcal{L}\)最大。由于目标函数是非负的，限制项中又有至少一个正数，因此只要让限制条件为正数的项的系数随意大就可以无限制地最大化\(\mathcal{L}\)。即在此情况下，\(\max_{ {\rm all\ }\alpha_n \ge 0}\mathcal{L}(b, {\bf w}, \boldsymbol{\alpha}) \rightarrow +\infty\)
- “好的”，也就是遵守全部限制条件的\(b\)和\(\bf w\)（feasible）。在这种情况下，拉格朗日函数中所有限制项都是非正数。为了让\(\mathcal{L}\)尽可能大，最方便的方法就是让所有\(\alpha_n=0\)，这个时候\(\max_{ {\rm all\ }\alpha_n \ge 0}\mathcal{L}(b, {\bf w}, \boldsymbol{\alpha}) = \frac{1}{2}{\bf w^\mathsf{T}w}\)。再对这些\(b\)和\(\bf w\)找到最小的\(\mathcal{L}\)，其实就是去找到最小的\(\frac{1}{2}{\bf w^\mathsf{T}w}\)，跟原来要求解的最优化问题一样
也就是说，原来的限制条件隐藏在了内层的最大化函数里。即 \[ {\rm SVM} \equiv \min_{b, {\bf w}} \left(\max_{ {\rm all\ }\alpha_n \ge 0}\mathcal{L}(b, {\bf w}, \boldsymbol{\alpha})\right) = \min_{b, {\bf w}}\left(\infty {\rm\ if\ violate;\ }\frac{1}{2}{\bf w^\mathsf{T}w}{\rm \ if\ feasible}\right) \]
拉格朗日对偶SVM
现在的问题是，如何继续对问题做转换。由于内层是一个最大化函数，因此对任意给定的\(\boldsymbol{\alpha}' \ (\forall \alpha_n' \ge 0)\)，肯定有 \[ \min_{b, {\bf w}} \left(\max_{ {\rm all\ }\alpha_n \ge 0}\mathcal{L}(b, {\bf w}, \boldsymbol{\alpha})\right) \ge \min_{b, {\bf w}}\mathcal{L}(b, {\bf w}, \boldsymbol{\alpha}') \] 因为任何函数的最大值肯定比其任意给定参数对应的值要大。进一步地，使得上面不等式右侧式子取得最大值的\(\boldsymbol{\alpha}'\)，肯定还有（由于\(\boldsymbol{\alpha}'\)的任意性，可以把\(\boldsymbol{\alpha}'\)再用\(\boldsymbol{\alpha}\)代替） \[ \min_{b, {\bf w}} \left(\max_{ {\rm all\ }\alpha_n \ge 0}\mathcal{L}(b, {\bf w}, \boldsymbol{\alpha})\right) \ge \max_{ {\rm all\ }\alpha_n \ge 0}\left(\min_{b, {\bf w}}\mathcal{L}(b, {\bf w}, \boldsymbol{\alpha})\right) \] （课程中讲的意思大概是说，因为右边不等式是对任意可能的值求极值，肯定不如上来直接求到的极值大。不过这实际上是max-min不等式。化用wiki里的证明方式，可以做简单的证明 \[ \begin{align*} {\rm Define\ }&g(x) = \min_y f(x, y) \\ \Rightarrow &g(x) \le f(x,y), \forall x, y \\ \Rightarrow &\max_x g(x) \le \max_x f(x, y), \forall y \\ \Rightarrow &\max_x\min_y f(x,y) \le \max_x f(x, y), \forall y\\ \Rightarrow &\max_x\min_y f(x, y) \le \min_y\max_xf(x,y)\hspace{2ex}\blacksquare \end{align*} \] 也就对应了民间谚语“瘦死的骆驼比马大”）
这样做实际上交换了min和max的顺序，得到的问题称为是拉格朗日对偶问题 ，而对偶问题的解是原问题的解的下限。事实上，“\(\ge\)”是一个弱对偶关系，只有当两边的式子相等时，这两个问题才构成强对偶关系。对于二次规划问题，如果满足以下三个条件（统称为约束规范 ），则等号成立：
- 原问题是凸的
- 原问题是可解的
- 原问题的约束条件是线性的
原始SVM问题正好满足上述约束规范，因此等号成立（如果经过多项式变换\(\boldsymbol{\Phi}\)数据集在新的空间线性可分，那么原问题就是可解的）。在强对偶关系下，解左边的问题和解右边的问题一样，或者换句话说，使右式最优的\((b, {\bf w}, {\boldsymbol{\alpha}})\)也可以使左式最优，反之亦然
这样，就可以写出对偶问题的完整形式 \[ \max_{ {\rm all\ }\alpha_n \ge 0} \left(\min_{b, {\bf w}} \frac{1}{2}{\bf w^\mathsf{T}w} + \sum_{n=1}^N \alpha_n(1-y_n({\bf w^\mathsf{T}z}_n + b))\right) \] 现在，最小化的这个函数（也就是拉格朗日函数）没有任何限制条件，可以看看能不能化简。由于其没有限制条件，因此最优的\(b\)肯定使函数对其的偏导数为0，即 \[ \frac{\partial \mathcal{L}(b, {\bf w}, \boldsymbol{\alpha})}{\partial b} = 0 \Rightarrow -\sum_{n=1}^N\alpha_ny_n = 0 \] 由于最优解必定导致如上的结论，因此把这个结论作为条件加上，并不会改变最优解。而且由于拉格朗日函数展开以后关于\(b\)的项是\(-\sum_{n=1}^N \alpha_ny_n \cdot b = -b\sum_{n=1}^N \alpha_ny_n\)。由于\(\sum_{n=1}^N \alpha_n y_n = 0\)，因此加上这个条件以后，可以直接把关于\(b\)的项去掉，即对偶问题可以化简为 \[ \max_{ {\rm all\ }\alpha_n \ge 0, \sum y_n\alpha_n=0} \left(\min_{ {\bf w}} \frac{1}{2}{\bf w^\mathsf{T}w} + \sum_{n=1}^N \alpha_n(1-y_n({\bf w^\mathsf{T}z}_n))\right) \] 同样的道理，现在对\(\bf w\)求偏导数，有 \[ \frac{\partial \mathcal{L}(b, {\bf w}, \boldsymbol{\alpha})}{\partial {\bf w}} = 0 \Rightarrow {\bf w} = \sum_{n=1}^N\alpha_ny_n{\bf z}_n \] 将上面的式子作为约束条件，并将\({\bf w} = \sum_{n=1}^N\alpha_ny_n{\bf z}_n\)代入式子，且考虑到\({\bf w^\mathsf{T}w} = |\!|{\bf w}|\!|^2\) ，可以得到 \[ \begin{align*} &\max_{ {\rm all\ }\alpha_n \ge 0, \sum y_n\alpha_n=0} \left(\min_{ {\bf w}} \frac{1}{2}{\bf w^\mathsf{T}w} + \sum_{n=1}^N \alpha_n(1-y_n({\bf w^\mathsf{T}z}_n))\right) \\ \Leftrightarrow & \max_{ {\rm all\ }\alpha_n \ge 0, \sum y_n\alpha_n=0, {\bf w}=\sum \alpha_ny_n{\bf z}_n} \left(\min_{\bf w} \frac{1}{2} {\bf w^\mathsf{T}w} + \sum_{n=1}^N \alpha_n - {\bf w^\mathsf{T}w}\right) \\ \Leftrightarrow & \max_{ {\rm all\ }\alpha_n \ge 0, \sum y_n\alpha_n=0, {\bf w}=\sum \alpha_ny_n{\bf z}_n} \left(-\frac{1}{2}\left|\!\left| \sum_{n=1}^N\alpha_ny_n{\bf z}_n\right|\!\right|^2 + \sum_{n=1}^N\alpha_n\right) \end{align*} \] 这就转化成了一个几乎只有\(\boldsymbol{\alpha}\)的最优化问题，实际上是简化版的拉格朗日对偶问题。也就是说，最优的\(\boldsymbol{\alpha}\)和最优的\(b\)和\(\bf w\)需要满足一些关系，它们才能同时是原问题和对偶问题的最优解。这些关系统称为KKT条件（Karush-Kuhn-Tucker conditions），包括
- \(y_n({\bf w}^\mathsf{T}{\bf z}_n + b) \ge 1\)
- \(\alpha_n \ge 0\)
- \(\sum y_n\alpha_n = 0; {\bf w}=\sum \alpha_n y_n {\bf z}_n\)
- \(\alpha_n (1-y_n({\bf w^\mathsf{T}z}_n + b)) = 0\)
之后，就要用KKT条件求解最优的\(\boldsymbol{\alpha}\)，进而求解最优的\((b, {\bf w})\)
求解对偶SVM
将之前的对偶问题稍作如下变换
- 将求最大值问题转为求最小值问题（取相反数即可）
- 展开向量的内积
可以得到硬间隔SVM对偶问题的标准形式： \[ \begin{align*} \min_{\boldsymbol{\alpha}} \hspace{2ex}&\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N \alpha_n\alpha_m y_ny_m{\bf z}_n^\mathsf{T}{\bf z}_m - \sum_{n=1}^N\alpha_n \\ {\rm subject\ to} \hspace{2ex}&\sum_{n=1}^Ny_n\alpha_n = 0; \\ & \alpha_n \ge 0, {\rm for\ }n=1,2,\ldots,N \end{align*} \] 这是一个有\(N\)个变量和\(N+1\)个约束条件的凸二次规划问题，可以将其转换成二次规划的标准形式 \[ \begin{align*} {\rm optimal\ }\boldsymbol{\alpha} &\leftarrow {\rm QP(Q}, {\bf p}, {\rm A}, {\bf c}) \\ q_{n, m} &= y_ny_m{\bf z}_n^\mathsf{T}{\bf z}_m \\ {\bf p } &= -{\bf 1}_N \\ {\bf a}_\ge &= {\bf y}, {\bf a}_\le = -{\bf y}; {\bf a}_n^\mathsf{T} = n{\rm th. unit\ direction} \\ c_\ge &=0, c_\le = 0; c_n = 0 \end{align*} \] 记对偶问题的\(\rm Q\)为\(\rm Q_D\)，由上面的定义可知\(\rm Q\)是稠密矩阵。如果\(N=30000\)，那\(\rm Q\)可以占3G内存！所以要解对偶问题，需要一个特殊的求解器，它不存储整个\(\rm Q_D\)或者使用某些特殊的限制，以应付\(N\)很大的情况
求出最优的\(\boldsymbol{\alpha}\)以后，可以根据KKT条件算出最优的\(b\)和\(\bf w\)。最优的\(\bf w\)很容易求，\({\bf w} = \sum \alpha_ny_n{\bf z}_n\)。而由\(\alpha_n (1-y_n({\bf w^\mathsf{T}z}_n + b)) = 0\)，可知如果有任意\(\alpha_n > 0\)，就可以算出\(b = y_n - {\bf w^\mathsf{T}z}_n\)（不同的\(\alpha_n > 0\)应该算出同样的\(b\)）。注意此时有\(y_n({\bf w^\mathsf{T}z}_n + b) = 1\)，即对任一点\(n\)如果有\(\alpha_n > 0\)，则说明这个点在“胖”的边界上
（这里其实说明了将原始问题转化成对偶问题的两个好处：
- 只需要优化\(\boldsymbol{\alpha}\)而不是\(b\)和\(\bf w\)，减小了计算量，降低了算法的时间复杂度
- 通过判断\(\alpha_n\)是否为0可以找出支持向量）
对偶SVM传递的信息
在前一讲中曾经得到一个结论，即支持向量机只关注那些在“胖”边界上的点，而其它点则不需要。上一节又证明，如果某个点有\(\alpha_n > 0\)，则这个点一定在“胖”边界上。称所有\(\alpha_n > 0\)的样本\(({\bf z}_n , y_n)\)为支持向量。也就是说有\({\rm SV(positive\ }\alpha_n) \subseteq {\rm SV\ candidates\ (on\ boundary)}\)。这意味着只需要用支持向量计算\(\bf w\)和\(b\)（对于那些不是支持向量的点，算出来的\(\bf w\)和\(b\)也都是0），而SVM也是通过对偶问题的最优解找出支持向量（即有用的向量），进而学到最大间隔超平面的算法
因此，SVM的权重可以写为\({\bf w}_{\rm SVM} = \sum_{n=1}^N \alpha_n(y_n{\bf z}_n)\)，其中\(\alpha_n\)来自于对偶问题的解。这个形式其实跟之前PLA算法得到的权重类似：PLA的权重可以写为\({\bf w}_{\rm PLA} = \sum_{n=1}^N \beta_n(y_n{\bf z}_n)\)，其中\(\beta_n\)是对错分样本进行纠正的次数。即SVM和PLA得到的解都是原始数据的线性组合。更广泛地讲，对基于梯度下降的算法，如果设初始的\({\bf w}_0 = 0\)，那么最后求出的解还是原始数据的线性组合。称这种现象为最优的权重\(\bf w\)可以被数据表示。其中SVM更特殊一些，最优的权重只用支持向量就能表示（PLA是用错分点表示）
这样，到目前为止，一共介绍了两种SVM：
- 原始的硬间隔SVM，一共有\(\tilde{d}+1\)个变量和\(N\)个限制条件。如果数据维度比较小，则适用。其物理意义是对\((b, {\bf w})\)进行缩放，得到一个合适的值
- 对偶的硬间隔SVM，一共有\(N\)个变量和\(N+1\)个简单的限制条件。如果数据量比较小，则适用。其物理意义是找出起作用的支持向量和它们的\(\alpha_n\)
无论使用哪种做法，都可以得到最优的\((b, {\bf w})\)，进而得到最优的假设函数为 \[ g_{\rm SVM}({\bf x}) = {\rm sign}({\bf w}^\mathsf{T}{\boldsymbol{\Phi}}({\bf x}) + b) \] 但是问题还没有结束。回想提SVM对偶问题的动机，是为了避免对数据维度\(\tilde{d}\)的依赖。尽管看上去最后求解时只依赖了数据量\(N\)（求解\(N\)个变量和\(N+1\)个限制条件），但是构造矩阵\(\rm Q_D\)时还是在\(\mathbb{R}^{\tilde{d}}\)空间做内积。如果直接计算的话，运算的时间复杂度还是\(O(\tilde{d})\)。因此，之后要解决的问题就是如何避免直接计算内积
