从零开始手推SVM

（2020年3月14日注：有些公式i与n等同，表迭代）

文章目录

• 问题的引入

• • "好"直线的定义
  • 点到超平面的欧氏距离计算
  • 简化

• 对偶的引入与推导

• • 无约束最优化问题的极小点条件
  • 拉格朗日函数
  • 求出SVM问题的拉格朗日函数，并证明合法性
  • 讨论拉格朗日函数的对偶
  • SVM的拉格朗日强对偶描述
  • 为什么叫支持向量机？
  • 使用QP标准库求解对偶问题

• 讨论核函数技巧

• • 多项式核函数
  • 高斯核函数与泰勒展开
  • Mercer定理与构造核函数

• 软间隔支持向量机

• • 提高稠密矩阵运算效率

• 序列最小最优化算法

• • 两个变量的选择
  • b的更新
  • SMO高效的原因

问题的引入

在输入维度为2的二分类问题中，假设训练样本完全线性可分，即所有训练样本点可以通过一条直线完全分开。

由上图可知，这样的直线往往不止一条。那么，我们应该选择哪一条直线作为模型，或者说这些直线中哪些直线可以被称之为“好”直线？

"好"直线的定义

我们将离直线最近的点定义为"危险点"，意味着我们对这个点的分类已经很危险了，一不小心就会分错。这是比较直观的感觉，数学的形式化描述详见Vapnik的著作以及相关概念这里不展开。
也就是说，如果直线离危险点越远，也就是间距越大，即发生误分类的可能性越小。那么我们可以得出在这种定义下的最好直线的一种表示。
\begin{array}{cl}{\max \limits_{\mathbf{w,b}}} & {\operatorname{间距}(\mathbf{w,b})} \\ {\text { s. t. }} & { y_{n} \mathbf{w}^{T} \mathbf{x}_{n}>0\text{//表示分类正确}} \\ {} & {\operatorname{间距}(\mathbf{w,b})=\min _{n=1, \ldots, N} \operatorname{距离}\left(\mathbf{x}_{n}, \mathbf{w,b}\right)}\end{array}

点到超平面的欧氏距离计算

二维的情况下计算点到直线的距离较为容易，现在我们将其扩展到多维空间中。则分类超平面可表示为w^Tx+b=0。
假设x’,x’‘两点在分类超平面上，那么
w^Tx'+b=0,w^Tx''+b=0。
那么w^T(x''-x')=0,(x''-x')是超平面上向量，因此w垂直于超平面，即w为法向量 如图
则计算平面外一点x到超平面的欧氏距离只要计算x-x’在w方向上的投影即可，那么不妨假设(x-x’)与w的夹角为\theta则点到超平面的距离为
\begin{aligned} \operatorname{distance}(x, b, w) &=\left|\left||x-x^{\prime}\right| \cos (\theta)\right|=\left|\left\|x-x^{\prime}\right\| \cdot \frac{\left(x-x^{\prime}\right) w}{\left\|x-x^{\prime}\right\| \cdot\|w\|}\right|= \frac{1}{\|w\|}\left|w^{T} x-w^{T} x^{\prime}\right| \end{aligned}
将w^Tx'+b=0代入上式
可得
\begin{aligned} \operatorname{distance}(x, b, w) &= \frac{1}{\|w\|}\left|w^{T} x+b\right| \end{aligned}
又因为y_n(w^Tx+b)>0 变换\begin{aligned} \operatorname{distance}(x, b, w) &= \frac{1}{\|w\|}y_{n}\left(w^{T} x_{n}+b\right) \end{aligned}
这是因为y_{n}\in\{-1,1\}因此可以去掉绝对值符号。那么我们最后就可以得到如下的最优化形式
\begin{array}{cl}{\max \limits_{\mathbf{w,b}}} & {\operatorname{间距}(\mathbf{w,b})} \\ {\text { s. t. }} & { y_{n} \mathbf{w}^{T} \mathbf{x}_{n}>0} \\ {} & {\operatorname{间距}(\mathbf{w,b})=\min _{n=1, \ldots, N} \frac{1}{\|w\|}y_{n}\left(w^{T} x_{n}+b\right) }\end{array}

简化

当我们对w和b进行等大缩放时，表示的超平面是唯一的，也就是说我们求出一个特解时，即可以求出该超平面的描述。因此我们不妨令距离分类超平面最近的点满足\begin{aligned} y_{n}\left(w^{T} x_{n}+b\right)=1 \end{aligned}那么间距(\mathbf{w,b})=\frac{1}{\|w\|}因此我们可以得到如下最优化表示
\begin{array}{cl}{\max \limits_{\mathbf{w,b}}} & {\frac{1}{\|\mathbf{w}\|}} \\ s.t. & { y_{n} \mathbf{w}^{T} \mathbf{x}_{n}>0} \\ {} & \min _{n=1, \ldots, N} y_{n}\left(w^{T} x_{n}+b\right)=1 \end{array}
易知y_{n} \mathbf{w}^{T} \mathbf{x}_{n}\ge1>0，不妨将最大化问题转为最小化问题，具体做法为去掉\sqrt{},加入\frac{1}{2}如下式
\begin{array}{cl}{\min \limits_{\mathbf{w,b}}} & {\frac{1}{2}{\mathbf{w}^{T}\mathbf{w}}} \\ s.t .& y_{n} (\mathbf{w}^{T} x_{n}+b)\ge1 \quad for\quad all \quad n\end{array}

因此最后得到了一个带不等式约束的凸二次规划问题。此时已经可以使用QP标准包进行求解，只需进行参数代换即可，

注意此时二次规划的求解依赖于特征维度，因此在非线性进行特征转换后，计算不太友好。我们希望摆脱对于特征维度的计算依赖。

对偶的引入与推导

\begin{array}{cl}{\min \limits_{\mathbf{w,b}}} & {\frac{1}{2}{\mathbf{w}^{T}\mathbf{w}}} \\ s.t .& y_{n} (\mathbf{w}^{T} x_{n}+b)\ge1 \quad for\quad all \quad n\end{array}上式是我们之前得到的带不等式约束的凸二次规划问题。我们希望对问题做一些等价的变换，最后能够比较高效的计算出结果。

无约束最优化问题的极小点条件

首先我们要讨论的是无约束最优化问题的一阶必要条件，考虑如下问题\begin{array}{cl}min&f(x)\\ s.t.& x\in R^n\end{array}其中f一阶连续可微，则局部极小点x^*一定满足\triangledown f(x^*)=\mathbf{0}这是必要条件而非充分条件，给出局部极小点的二阶充分条件
f二阶连续可微，x^*是约束集合内的内点(当约束集合为R^n时，任意点为内点)如果同时满足下列条件

1. \triangledown f(x^*)=0
2. F(x^*)>0

则x^*是严格局部极小点。
引入严格凸函数 的概念即Hessian矩阵F(x)处处严格正定，则这样的函数最多只有一个局部极小点，也就是说这个局部极小点是全局极小点。那么我们现在具备了求解无约束最优化问题的数学工具。

拉格朗日函数

我们现在想将带约束的最优化问题转换为我们已经掌握的无约束最优化问题。考虑求解最小化问题，不妨假设一个新的函数l，这个函数在原本函数的约束集合内与原本的目标函数f完全等价，在约束集合以外取值为+\infin，这样就可以把有约束问题转换成无约束问题，如下L(x)=\left\{ \begin{aligned} &f(x) &x \in 约束集合\\ &+\infin & x \notin 约束集合 \end{aligned} \right.

求出SVM问题的拉格朗日函数，并证明合法性

首先写出SVM的原始形式\begin{array}{cl}{\min\limits_{\mathbf{w,b}}} & {\frac{1}{2}{\mathbf{w}^{T}\mathbf{w}}} \\ s.t .& y_{n} (\mathbf{w}^{T} x_{n}+b)\ge1 \quad for\quad all \quad n\end{array}构造拉格朗日函数\begin{array} {cl}L(x,\lambda,\mu) &= f(x)+\lambda^{T}h(x)+\mu^{T}g(x) \\ L(\mathbf{w},b,\mu) &= \frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum\limits_{i=1}^n \mu^T(1-y_n(\mathbf{w}^Tx_n+b)) \\ &=\frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum\limits_{i=1}^n \mu^T-\sum\limits_{i=1}^n\mu^T y_n(\mathbf{w}^Tx_n+b) \end{array}目标函数为f(w,b)=\frac{1}{2}w^Tw，约束函数为g(w,b)=1-y_n(\mathbf{w}^Tx_n+b)\le 0,接下来证明\begin{array}{cl}{\min\limits_{\mathbf{w,b}}}\max\limits_{\mu} & {f(\mathbf w,b)+\mu^Tg(\mathbf w,b)} \\ s.t .& \mu\ge0\\ \end{array}与原始问题等价。
已知\mu\ge0当w,b在原问题可行域内，即满足原问题约束函数g(w,b)=1-y_n(\mathbf{w}^Tx_n+b)\le 0那么一定有\mu^Tg(w,b)\le0，那么拉格朗日函数先对其取最大值，此时\mu^Tg(w,b)=0，此时问题转化为\min\limits_{w,b}f(w,b)也就是无约束的最优化问题。
当w,b在可行域之外，即g(w,b)=1-y_n(\mathbf{w}^Tx_n+b)> 0又有\mu\ge0。那么对拉格朗日函数取最大值的结果是+\infin。此时拉格朗日问题转变成对正无穷取最小，自然不成立。因此\begin{array}{cl}{\min\limits_{\mathbf{w,b}}}\max\limits_{\mu} & {f(\mathbf w,b)+\mu^Tg(\mathbf w,b)} \\ s.t .& \mu\ge0\\ \end{array}与原始问题等价。

讨论拉格朗日函数的对偶

转换成拉格朗日表述后，问题依然难以求解，此时引入对偶函数dual=\max\limits_{\mu}\min\limits_{w,b}L(w,b,\mu)下面证明满足条件\mu\ge0,g(w,b)\le0时弱对偶性即不等式\min\limits_{w,b}\max\limits_{\mu}L(w,b,\mu)\ge\max\limits_{\mu}\min\limits_{w,b}L(w,b,\mu)恒成立。
设左式最优解为p^*对应w=w^*,b=b^*,右式最优解为d^{\triangle}对应\mu=\mu^{\triangle}则\begin{array}{cl}d^\triangle &= \min\limits_{w,b}L(w,b,\mu^\triangle) \\ &\le L(w,b,\mu^\triangle) {\forall w,b}\\ \therefore d^\triangle &\le L(w^*,b^*,\mu^\triangle)\\ &=f(w^*,b^*)+\mu^\triangle g(w^*,b^*)\\ \because\mu^\triangle g(w^*,b^*)&\le0\\ \therefore d^\triangle &\le f(w^*,b^*)=p^*\end{array}即弱对偶成立。由上式可知强对偶成立条件为\left\{ \begin{aligned} \mu^\triangle g(w^*,b^*) &=0 \\ \min\limits_{w,b}L(w,b,\mu^\triangle)&=L(w^*,b^*,\mu^\triangle) \end{aligned} \right.其中第二行即为无约束的优化问题，依靠无约束最优点的二阶充分条件即\frac{\partial L}{\partial w}|_{w=w^*}=0,\frac{\partial L}{\partial b}|_{b=b^*}=0则w^*=\sum\limits_{i=1}^n\mu_i^\triangle y_ix_i,\sum\limits_{i=1}^n\mu_iy_i=0此时成为强对偶问题。

SVM的拉格朗日强对偶描述

满足\left\{\begin{aligned}\mu &\ge0\\ g(w,b)=1-y_n(\mathbf{w}^Tx_n+b)&\le 0\\ \mu^\triangle g(w^*,b^*) &=0\\ w^*-\sum\limits_{i=1}^n\mu_i^\triangle y_ix_i&=0\\ \sum\limits_{i=1}^n\mu_i^\triangle y_i&=0\end{aligned}\right.时，最优化SVM原始形式等价于最优化极小极大拉格朗日函数，又因为强对偶性质，等价于最优化极大极小拉格朗日函数。写出最优化极大极小拉格朗日函数（上述条件隐去不写）\begin{array}{cl}&\max\limits_{\mu}\min\limits_{w,b}\frac{1}{2}\mathbf{w}^T\mathbf{w}+\sum\limits_{i=1}^n \mu_i-\sum\limits_{i=1}^n\mu_i y_i(\mathbf{w}^Tx_i+b)\\ &\to\max\limits_{\mu}-\frac{1}{2}\sum\limits_{i=1}^n\sum\limits_{j=1}^n\mu_i\mu_jy_iy_jx_i^Tx_j+\sum\limits_{i=1}^n\mu_i\\ &\to \min\limits_\mu \frac{1}{2}\sum\limits_{i=1}^n\sum\limits_{j=1}^n\mu_i\mu_jy_iy_jx_i^Tx_j-\sum\limits_{i=1}^n\mu_i\end{array}得到最后的优化目标函数\begin{array}{cl}\min\limits_\mu &\frac{1}{2}\sum\limits_{i=1}^n\sum\limits_{j=1}^n\mu_i\mu_jy_iy_jx_i^Tx_j-\sum\limits_{i=1}^n\mu_i\\ {s.t.}&\sum\limits_{i=1}^n\mu_i y_i=0\\ &\mu_i \ge0 ,i=1,2...,n\end{array}假设已经求出\mu后根据强对偶条件，得到\left\{\begin{aligned}w^*=\sum\limits_{i=1}^n\mu_i^\triangle y_ix_i \\ \mu_i^\triangle (y_i(\mathbf{w}^{*T}x_i+b^*)-1)=0 \\ y_i(\mathbf{w}^{*T}x_i+b^*)-1\ge0\\ \mu_i^\triangle\ge0\end{aligned}\right.如果\forall\mu_i^\triangle=0则必有w^*=0我们回到最原始的问题即求\max\frac{1}{||w||}显然w=0时不是问题的解。必然\exists \mu_j>0，此时y_j(\mathbf{w}^{*T}x_j+b^*)=1又有y_j^{2}=1,w^*=\sum\limits_{i=1}^n \mu_i^\triangle y_ix_i得到如下等式b^{*}=y_j-\sum\limits_{i=1}^n\mu^\triangle y_i(x_i·x_j)

为什么叫支持向量机？

根据上面的推论，我们可以发现w,b都由\mu_i >0的点来决定取值，因此超平面的方程只与这些点有关，所以这些点就被称为支持向量(support vector)，其他的点都与最优超平面的构造无关。得到如下表达\begin{aligned}w^*&=\sum\limits_{SV}\mu^\triangle_ny_nx_n \\ b^*&=y_n-w^Tx_n \quad with \quad SV\end{aligned}

使用QP标准库求解对偶问题

我们再次使用QP标准库来解决对偶后的问题\begin{array}{cl}\min\limits_\mu &\frac{1}{2}\sum\limits_{i=1}^n\sum\limits_{j=1}^n\mu_i\mu_jy_iy_jx_i^Tx_j-\sum\limits_{i=1}^n\mu_i\\ {s.t.}&\sum\limits_{i=1}^n\mu_i y_i=0\\ &\mu_i \ge0 ,i=1,2...,n\end{array}QP标准解法
因此使用QP标准库解法可以解决问题，关注Q矩阵q_{n,m}=y_ny_mx_n^Tx_m似乎摆脱了之前提到的对线性可分时维度的依赖？实际上并没有，我们可以看到在计算Q矩阵时还是了向量内积的运算，这使得在进行非线性的高维映射时即z=\phi(x)后假设z空间内样本线性可分，那么此时的Q矩阵计算依赖此时z空间的维度。
我们想要继续去掉对于z空间(线性可分时)维度的依赖，这是接下来需要解决的问题1。
还存在一个问题就是Q矩阵的大小依赖此时样本量数目，这是因为Q矩阵是一个样本量x样本量的矩阵，而且是一个稠密矩阵，所以计算量与占据的内存会非常的大，例如当样本量为30000时，将会占用3GB的内存，这是需要解决的问题2.

讨论核函数技巧

我们发现计算性能瓶颈在于q_{n,m}=y_ny_mz_n^Tz_m其中z=\phi(x)也就是对于x空间来说，我们首先要进行特征转换z=\phi(x)，再在z空间内做内积\phi(x_n)\phi(x_m)这样的计算处理方式必然会带入z空间的维度d。那么可不可以将特征转换和内积计算在较低维度的空间上工作计算呢？
观察二阶多项式特征转换\phi_2(x)=(1,x_1,x_2...,x_d,x_1^2,x_1x_2,...,x_1x_d,x_2^2,...,x_2x_d,...,x_d^2)为简化表述，包含x_1x_2,x_2x_1那么我们可以得到\begin{aligned}\phi(\mathbf x)^T\phi(\mathbf x')&=1+\sum\limits_{i=1}^dx_ix'_i+\sum\limits_{i=1}^d\sum\limits_{j=1}^dx_ix_jx'_ix'_j\\ &=1+\sum\limits_{i=1}^dx_ix'_i+\sum\limits_{i=1}^dx_ix'_i\sum\limits_{j=1}^dx_jx'_j\\ &=1+\mathbf {x}^T\mathbf {x}'+(\mathbf {x}^T\mathbf {x}')(\mathbf {x}^T\mathbf {x}')\end{aligned}所以我们可以得到z_nz_m=\phi(x_n)\phi(x_m)=1+x^T{x}'+({x}^T{x}')({x}^T {x}')也就是说，我们不再需要对特征转换做显式运算。只需要提前构造一个合适的核函数K来替代高维空间的内积\phi(x)\phi(x')。这样得到的结果数学上等价，且运算更加简便。

多项式核函数

对系数进行相应的放缩可以得到如下的式子。
\begin{aligned} \Phi_{2}(\mathbf{x})=\left(1, x_{1}, \ldots, x_{d}, x_{1}^{2}, \ldots, x_{d}^{2}\right) & \Leftrightarrow K_{\Phi_{2}}\left(\mathbf{x}, \mathbf{x}^{\prime}\right)=1+\mathbf{x}^{T} \mathbf{x}^{\prime}+\left(\mathbf{x}^{T} \mathbf{x}^{\prime}\right)^{2} \\ \Phi_{2}(\mathbf{x})=\left(1, \sqrt{2} x_{1}, \ldots, \sqrt{2} x_{d}, x_{1}^{2}, \ldots, x_{d}^{2}\right) & \Leftrightarrow K_{2}\left(\mathbf{x}, \mathbf{x}^{\prime}\right)=1+2 \mathbf{x}^{T} \mathbf{x}^{\prime}+\left(\mathbf{x}^{T} \mathbf{x}^{\prime}\right)^{2} \\ \Phi_{2}(\mathbf{x})=\left(1, \sqrt{2 \gamma} x_{1}, \ldots, \sqrt{2 \gamma} x_{d}, \gamma x_{1}^{2}, \ldots, \gamma x_{d}^{2}\right) &\Leftrightarrow K_{2}\left(\mathbf{x}, \mathbf{x}^{\prime}\right)=1+2 \gamma \mathbf{x}^{T} \mathbf{x}^{\prime}+\gamma^{2}\left(\mathbf{x}^{T} \mathbf{x}^{\prime}\right)^{2} \end{aligned}都是二次转换，对应到同一个z空间。但是，它们系数不同，内积就会有差异，那么
就代表有不同的距离，最终可能会得到不同的SVM间距。所以，系数不同，可能会得到不同的SVM分界线。通常情况下，第三行的简单一些，更加常用。

更一般的我们可以构建Q次多项式核函数
\begin{aligned}K_2(\mathbf{x,x'})&=(\zeta+\gamma\mathbf{x^Tx'})^2\text{with}\zeta\ge0,\gamma>0\\ K_3(\mathbf{x,x'})&=(\zeta+\gamma\mathbf{x^Tx'})^3\text{with}\zeta\ge0,\gamma>0\\ &\vdots\\ K_Q(\mathbf{x,x'})&=(\zeta+\gamma\mathbf{x^Tx'})^Q\text{with}\zeta\ge0,\gamma>0\end{aligned}这样我们就可以通过计算核函数的值来代替特征转换后计算高维空间的内积的步骤，提高计算效率。

高斯核函数与泰勒展开

已经讨论过关于有限Q维的多项式核函数，现在我们讨论关于无限维的情况，简化问题，我们讨论特征只有一个时的高斯函数K_g({x,x'})=e^{-(x-x')^2}利用反推法证明\begin{aligned}K(\mathbf{x,x'})=&\exp(-(\mathbf{x}-\mathbf{x'})^2)\\ =&\exp(-(\mathbf{x})^2)\exp(-(\mathbf{x'})^2)\exp(2\mathbf{x}\mathbf{x}')\\ \overset{Taylor}{=}&\exp(-(\mathbf{x})^2)\exp(-(\mathbf{x'})^2)\left( \sum\limits_{i=0}^\infin \frac{(2xx')^i}{i!}\right)\\ =&\sum\limits_{i=0}^\infin \left(\exp\left(-\left({x'}\right)^2\right)\exp\left(-\left({x}\right)^2\right)\sqrt \frac{2^i}{i!}\sqrt \frac{2^i}{i!}(x)^i(x')^i\right)\\ =&\Phi(\mathbf x)^T\Phi(\mathbf x')\end{aligned}那么可得\Phi(x)=e^{-x^{2}} \cdot\left(1, \sqrt{\frac{2}{1 !}} x, \sqrt{\frac{2^{2}}{2 !}} x^{2}, \cdots\right)所以\Phi(x)是一个无穷维的函数，我们就认为他是一个特征转换函数。一般地，引入缩放因子\gamma>0以及原空间不止一维的情况，得到高斯核函数K_g({x,x'})=e^{-\gamma||x-x'||^2}这时我们把核函数代入到原本的SVM中，我们会发现一个有趣的结论，这种情况下的SVM就是由支持向量的高斯函数的线性组合。H=\sum\limits_{SV}\mu_ny_n \exp(-\gamma||\mathbf {x-x_n}||^2)+b当\gamma取值发生变化，此时超平面发生变化，分类效果也不同。
这是因为\gamma越大，其对应的高斯核函数就越‘’尖瘦‘’，\gamma越小，高斯核函数就越平滑。这意味着在高维空间中，\gamma越大则样本和样本之间的相似度越低，也就是说每个样本点都会成为一类，反映在低维空间中就是形成类似’孤岛’的现象（注意\gamma=\frac{1}{2\sigma^2}）

Mercer定理与构造核函数

我们考虑一下核函数本质是什么。我们可以某种程度上认为，核函数考虑的就是两个数据经过特征转换后的相似度，在这里是内积。但不是任何计算相似度的就可以认为是核函数，一个有效的核函数必须得满足Mercer定理。K=\left[\begin{array}{cccc}{\Phi\left(\mathbf{x}_{1}\right)^{T} \Phi\left(\mathbf{x}_{1}\right)} & {\Phi\left(\mathbf{x}_{1}\right)^{T} \Phi\left(\mathbf{x}_{2}\right)} & {\dots} & {\mathbf{\Phi}\left(\mathbf{x}_{1}\right)^{T} \Phi\left(\mathbf{x}_{N}\right)} \\ {\Phi\left(\mathbf{x}_{2}\right)^{T} \Phi\left(\mathbf{x}_{1}\right)} & {\Phi\left(\mathbf{x}_{2}\right)^{T} \Phi\left(\mathbf{x}_{2}\right)} & {\ldots} & {\Phi\left(\mathbf{x}_{2}\right)^{T} \Phi\left(\mathbf{x}_{N}\right)} \\ { {\ldots}} & {\cdots} & {\cdots} & {\cdots} & {} \\ {\Phi\left(\mathbf{x}_{N}\right)^{T} \Phi\left(\mathbf{x}_{1}\right)} & {\Phi\left(\mathbf{x}_{N}\right)^{T} \Phi\left(\mathbf{x}_{2}\right)} & {\cdots} & {\Phi\left(\mathbf{x}_{N}\right)^{T} \Phi\left(\mathbf{x}_{N}\right)}\end{array}\right]其中

1. K是对称的
2. K是半正定的

软间隔支持向量机

可以想象SVM仍然会造成过拟合的情况发生，有两个原因，一是我们使用的核函数过于强大，SVM过于复杂，转换的维度太高。另外一个原因是我们坚持所有样本必须线性可分（即使是映射到高维空间仍然如此要求），不允许错误存在，造成的后果就是对数据点异常敏感，使得模型过于复杂。

因此我们想要降低这种过拟合的可能性，通过把严格线性可分，不允许错误分类这一条件进行松弛，变成允许错误分类，但尽可能的少。因此把硬间隔支持向量机进行适当地改造如下\begin{array}{cl}{\min\limits_{b, w}} & {\frac{1}{2} w^{T} w+C \cdot \sum\limits_{n=1}^{N}[[y_{n} \neq \operatorname{sign}\left(w^{T} \mathbf{x}_{n}+b\right)]]} \\ {\text { s.t. }} & {y_{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right) \geq 1-\infty \cdot[[ y_{n} \neq \operatorname{sign}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right)]]}\end{array}这种表示较为直观，对于分类正确的点仍然是y_{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right) \geq 1对于分类错误的点或者说噪声点则有y_{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right) \geq -\infin也就是没有限制，C是一个权衡用的变量，即权衡大间距还是噪声容忍度，当C越大说明该最优化问题侧重于对错分点越少越好，此时经验风险减小，结构风险增大，容易出现过拟合。反之则倾向于对间距越大越好，此时结构风险减小，经验风险增大，容易出现欠拟合。

但是上述的表示虽然直观，但是难以使用数学工具去最优化(QP标准包)，而且对于离边界近的错分点与离边界远的错分点，两者在此表示中是等价的，没有区别的。因此我们进行修正，引入\xi表示每个点犯错误的程度，用点到应正确的分类超平面边界(同样y值对应的支持向量所在的超平面)的距离表示，当正确分类时，\xi=0。
得到如下最优化问题\begin{aligned}\min\limits_{b, w, \xi} &{\frac{1}{2} w^{T} w+C \cdot \sum_{n=1}^{N} \xi_{n}} \\ \text { s.t. } &y_{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right) \geq 1-\xi_{n} \\ &\xi_{n} \geq 0 \text { for all } n\end{aligned}一样地，我们使用拉格朗日函数L(w,b,\xi,\alpha,\beta)={\frac{1}{2} w^{T} w+C \cdot \sum_{n=1}^{N} \xi_{n}}+\sum\limits_{n=1}^N\alpha_n(1-\xi_{n}-y_n(\mathbf{w}^{T} \mathbf{x}_{n}+b))+\sum\limits_{n=1}^N\beta_n(-\xi_n)同样的构造极小极大问题，这个问题与原问题等价，证明略去\begin{aligned}\min\limits_{b, w, \xi} \max\limits_{\alpha,\beta}&{\frac{1}{2} w^{T} w+C \cdot \sum_{n=1}^{N} \xi_{n}}+\sum\limits_{n=1}^N\alpha_n(1-\xi_{n}-y_n(\mathbf{w}^{T} \mathbf{x}_{n}+b))+\sum\limits_{n=1}^N\beta_n(-\xi_n) \\ \text { s.t. } &\alpha_n \ge 0,\beta_n\ge 0\end{aligned}同样地我们可以通过弱对偶，强对偶方法得到强对偶的最优化问题如下\begin{aligned} \max\limits_{\alpha,\beta}\min\limits_{b, w, \xi}&{\frac{1}{2} w^{T} w+C \cdot \sum_{n=1}^{N} \xi_{n}}+\sum\limits_{n=1}^N\alpha_n(1-\xi_{n}-y_n(\mathbf{w}^{T} \mathbf{x}_{n}+b))+\sum\limits_{n=1}^N\beta_n(-\xi_n) \\ \text { s.t. } &\alpha_n \ge 0,\beta_n\ge 0\end{aligned}强对偶条件略去，请读者自行推理。依照强对偶成立条件(梯度为0)可以得到\begin{aligned}\frac{\partial L}{\partial \xi_n}=C-\alpha_n-\beta_n=0\end{aligned}又有\beta_n \ge0,所以有0\le\alpha\le C。将\beta_n=C-\alpha_n代回问题，则有如下表示\begin{aligned} \max\limits_{\alpha,\beta}\min\limits_{b, w}&{\frac{1}{2} w^{T} w}+\sum\limits_{n=1}^N\alpha_n(1-y_n(\mathbf{w}^{T} \mathbf{x}_{n}+b)) \\ \text { s.t. } &C\ge\alpha_n \ge 0,\beta_n= C-\alpha_n\end{aligned}同样依照强对偶条件(梯度为0)可以得到\begin{array}{l}{\sum\limits_{n=1}^{N} \alpha_{n} y_{n}=0} \\ {w=\sum\limits_{n=1}^{N} \alpha_{n} y_{n} x_{n}}\end{array}经过一系列的化简最后得到\begin{array}{cl}\min\limits_\alpha &\frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha _i\alpha _jy_iy_jx_i^Tx_j-\sum\limits_{i=1}^N\alpha _i\\ {s.t.}&\sum\limits_{i=1}^N\alpha _i y_i=0\\ &C\ge\alpha _i \ge0 ,i=1,2...,n \\ &\beta_i=C-\alpha_i,i=1,2...,n\end{array}我们此时可以通过QP标准包，求解出\alpha。
我们可以通过w=\sum\limits_{n=1}^{N} \alpha_{n} y_{n} x_{n}求解出此时的w。而b的求解依赖于以下两个式子(互补松弛条件)\left\{\begin{aligned}&\alpha_n(1-\xi_{n}-y_n(\mathbf{w}^{T} \mathbf{x}_{n}+b))=0\\ &(C-\alpha_n)(-\xi_n)=0\end{aligned} \right.当0< \alpha_n< C时，有\xi_n=0,那么b=y_n-\mathbf{w}^{T} x_{n}.这些点就是支持向量。
当\alpha_n=0时有\xi_n=0,那么说明该点没有犯错，且不是支持向量，表示被正确分类。
当\alpha_n=C时，不能确定\xi_n的值，得到\xi_n=1-y_n(\mathbf{w}^{T} \mathbf{x}_{n}+b)表示错误的程度，当\xi_n=0表示仍然分类正确，点在间距边界上，0<\xi_n<1表示有一定错误，在间距边界与分离超平面之间，但仍然分类正确，\xi_n=1说明该点恰好在分离超平面上,\xi_n>1表明该点越过分离超平面，分类错误。根据\alpha,\xi的取值可以得到点的大概分布位置。如下图
同样，我们可以引入核技巧来进行特征转换运算的简化。

提高稠密矩阵运算效率

我们之前提到过可以使用QP标准库来计算出强对偶问题中最优的情况，但是存在一个Q稠密矩阵，这个稠密矩阵大小与样本量有关，举个例子,当样本量N>30000时，将会耗费3GB的内存。所以使用QP标准包来解决这个问题似乎效率会比较低下，因此我们产生两个想法

1. 动态的计算q_{nm}而不是全部一次性载入
2. 采用更高效的算法

我们接下来要讨论的就是platt在1998年提出的序列最小最优化SMO算法

序列最小最优化算法

考虑最优化问题形如\begin{array}{cl}\min\limits_\alpha &\frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha _i\alpha _jy_iy_jK(x_i,x_j)-\sum\limits_{i=1}^N\alpha _i\\ {s.t.}&\sum\limits_{i=1}^N\alpha _i y_i=0\\ &C\ge\alpha _i \ge0 ,i=1,2...,n \end{array}何种情况可以认为该问题得到了最优情况？我们观察之前软间隔支持SVM最优化之后点的分布结果
当0< \alpha_n< C时，点为支持向量有1-(y_i\sum\limits_{i=1}^N\alpha_iy_iK(x_i,x_n)+b)=0成立。
当\alpha_n=0时有1-(y_i\sum\limits_{i=1}^N\alpha_iy_iK(x_i,x_n)+b)\le0,那么说明该点不是支持向量，并被正确分类。
当\alpha_n=C时，有\xi_n=1-(y_i\sum\limits_{i=1}^N\alpha_iy_iK(x_i,x_n)+b)\ge0表示错误的程度，当\xi_n=0表示仍然分类正确，点在间距边界上，0<\xi_n<1表示有一定错误，在间距边界与分离超平面之间，但仍然分类正确，\xi_n=1说明该点恰好在分离超平面上,\xi_n>1表明该点越过分离超平面，分类错误。
软间隔SVM最优化之后必有上述点的分布，有上述点的分布时，必有软间隔SVM最优化。那么SMO的想法就是我们使得所有的点都满足上述分布，即得到了上述问题的最优解。
因此最优化问题得到解决时，必有上述三个充分必要条件成立。
于是将上述问题进行拆分，每次对两个变量进行优化，使得更加接近原始问题的解，这是因为优化后，原始目标的值就会变得更小。SMO算法之所以速度快，是因为两个变量的子问题可以通过解析法求出。因此SMO算法就是一个不断拆分成双变量子问题，并求出子问题的解析解，使得目标值不断减小，最后终止条件即为上述三个充分必要条件都得到满足。

**为什么一次要对两个变量进行优化？**注意上述问题中有等式约束\sum\limits_{i=1}^N\alpha _i y_i=0，因此一次必须对两个变量进行优化（如果一次只优化一个，其他都为固定值，此时由等式约束，待优化的一个值也确定下来了，优化无法进行），注意，两个变量中，实际上只有一个是在自由变动的这是因为有等式约束存在，因此若\alpha_2确定则有\alpha_1满足以下式子\alpha_1=-y_1\sum\limits_{i=2}^N\alpha_iy_i
也得到了确定。我们构造关于\alpha_1,\alpha_2为变量，其他\alpha_i(i=3,\cdots,N)是固定值。得到原问题的子问题\begin{aligned}\min\limits_{\alpha_1,\alpha_2}W(\alpha_1,\alpha_2)&= \frac{1}{2} \sum_{i=1}^{N}\left(\sum_{j=1}^{2} y_{i} y_{j} \alpha_{i} \alpha_{j} K(x_{i}, x_{j})+\sum_{j=3}^{N} y_{i} y_{j} \alpha_{i} \alpha_{j} K(x_{i} ,x_{j})\right)-(\alpha_{1}+\alpha_{2})-\sum_{i=3}^{N} \alpha_{i}\\ &=\frac{1}{2} \sum_{i=1}^{2}\left(\sum_{j=1}^{2} y_{i} y_{j} \alpha_{i} \alpha_{j} K(x_{i}, x_{j})+\sum_{j=3}^{N} y_{i} y_{j} \alpha_{i} \alpha_{j} K(x_{i} ,x_{j})\right)+\frac{1}{2} \sum_{i=3}^{N}\left(\sum_{j=1}^{2} y_{i} y_{j} \alpha_{i} \alpha_{j} K(x_{i}, x_{j})+\sum_{j=3}^{N} y_{i} y_{j} \alpha_{i} \alpha_{j} K(x_{i} ,x_{j})\right)-(\alpha_{1}+\alpha_{2})-\sum_{i=3}^{N} \alpha_{i}\\ &=\frac{1}{2} \sum_{i=1}^{2}\sum_{j=1}^{2} y_{i} y_{j} \alpha_{i} \alpha_{j} K(x_{i}, x_{j})+\sum_{i=1}^{2}\sum_{j=3}^{N} y_{i} y_{j} \alpha_{i} \alpha_{j} K(x_{i} ,x_{j})+\frac{1}{2}\sum_{i=3}^{N}\sum_{j=3}^{N} y_{i} y_{j} \alpha_{i} \alpha_{j} K(x_{i} ,x_{j})-(\alpha_{1}+\alpha_{2})-\sum_{i=3}^{N} \alpha_{i}\\ &=\frac{1}{2}K(x_1,x_1)\alpha_1^2+\frac{1}{2}K(x_2,x_2)\alpha_2^2+y_1y_2K(x_1,x_2)\alpha_1\alpha_2-(\alpha_1+\alpha_2)+y_1\alpha_1\sum_{i=3}^Ny_i\alpha_iK(x_i,x_1)+y_2\alpha_2\sum_{i=3}^Ny_i\alpha_iK(x_i,x_2)\\ {s.t.}\qquad&\alpha_1y_1+\alpha_2y_2=-\sum_{i=3}^Ny_i\alpha_i=\zeta\\ &0\le\alpha_j\le C,j=1,2 \end{aligned}假设y_1y_2<0也就是异号，之前的满足可行条件的解\alpha_1^{old},\alpha_2^{old}已知，希望得到更优时的\alpha_1^{new},\alpha_2^{new}且有以下约束\alpha_1^{old}-\alpha_2^{old}=\alpha_1^{new}-\alpha_2^{new}=\zeta\\ 0\le\alpha_1\le C\\ 0\le\alpha_2\le C那么做一个简单的代换可以得到0\le\alpha_2\le C\\ \alpha_2^{old}-\alpha_1^{old}\le\alpha_2\le C+\alpha_2^{old}-\alpha_1^{old}要严格满足此约束因此L=\max(\alpha_2^{old}-\alpha_1^{old},0)\le\alpha_2\le \min(C,C+\alpha_2^{old}-\alpha_1^{old})=H如果y_1y_2>0即同号则同理可得L=\max(\alpha_2^{old}+\alpha_1^{old}-C,0)\le\alpha_2\le \min(C,\alpha_2^{old}+\alpha_1^{old})=H
所以一定有L\le \alpha_2^{new} \le H示意图如下
接下来计算满足约束条件\alpha_1y_1+\alpha_2y_2=-\sum\limits_{i=3}^Ny_i\alpha_i=\zeta但未考虑不等式约束0\le\alpha\le C的更优解（换个角度想，其实就是SMO求解硬间隔的SVM）目标函数可以写成如下形式\begin{aligned}\min\limits_{\alpha_1,\alpha_2}W(\alpha_1,\alpha_2)&=\frac{1}{2}K(x_1,x_1)\alpha_1^2+\frac{1}{2}K(x_2,x_2)\alpha_2^2+y_1y_2K(x_1,x_2)\alpha_1\alpha_2-(\alpha_1+\alpha_2)+y_1\alpha_1\sum_{i=3}^Ny_i\alpha_iK(x_i,x_1)+y_2\alpha_2\sum_{i=3}^Ny_i\alpha_iK(x_i,x_2)\end{aligned}此时我们有\alpha_1y_1=\zeta-\alpha_2y_2,y_i^2=1所以可得\alpha_1=(\zeta-y_2\alpha_2)y_1
目标函数变换为只有\alpha_2为变量的形式，如下：\begin{aligned}\min\limits_{\alpha_2}W(\alpha_2)&=\frac{1}{2}K(x_1,x_1)\alpha_1^2+\frac{1}{2}K(x_2,x_2)\alpha_2^2+y_1y_2K(x_1,x_2)\alpha_1\alpha_2-(\alpha_1+\alpha_2)+y_1\alpha_1\sum_{i=3}^Ny_i\alpha_iK(x_i,x_1)+y_2\alpha_2\sum_{i=3}^Ny_i\alpha_iK(x_i,x_2)\\ &=\frac{1}{2}K(x_1,x_1)(\zeta-y_2\alpha_2)^2+\frac{1}{2}K(x_2,x_2)\alpha_2^2+y_2K(x_1,x_2)(\zeta-y_2\alpha_2)\alpha_2-(\zeta-y_2\alpha_2)y_1-\alpha_2+(\zeta-y_2\alpha_2)\sum_{i=3}^Ny_i\alpha_iK(x_i,x_1)+y_2\alpha_2\sum_{i=3}^Ny_i\alpha_iK(x_i,x_2)\end{aligned}对\alpha_2求二次偏导有\begin{aligned}\frac{\partial^2 W}{\partial \alpha_2^2}&=K(x_1,x_1)-2K(x_1,x_2)+K(x_2,x_2)\\ &=||\Phi(x_1)-\Phi(x_2)||^2\\ & \ge 0\end{aligned}其中\Phi(x_i)是样本到核函数所映射的特征空间的映射。实际上，因此目标函数是关于\alpha_2的凸优化问题。当两个样本点不重叠时，此问题是一个严格凸问题，由极值点的二阶充分条件可知\frac{\partial W}{\partial \alpha_2}=0则有\begin{aligned}(K(x_1,x_1)+K(x_2,x_2)-2K(x_1,x_2))\alpha_2&=y_2(y_2-y_1+\zeta K(x_1,x_1)-\zeta K(x_1,x_2)+\sum_{i=3}^Ny_i\alpha_iK(x_i,x_1)-\sum_{i=3}^Ny_i\alpha_iK(x_i,x_2))\\ &=y_2\left(y_2-y_1+\zeta K(x_1,x_1)-\zeta K(x_2,x_2)+\left(\sum_{i=1}^Ny_i\alpha_iK(x_i,x_1)-\sum_{j=1}^2y_j\alpha_jK(x_j,x_1)+b-b\right)-\left(\sum_{i=1}^Ny_i\alpha_iK(x_i,x_2)-\sum_{j=1}^2y_j\alpha_jK(x_j,x_2)+b-b\right)\right)\end{aligned}我们将\zeta=\alpha_1^{old}y_1+\alpha_2^{old}y_2代入上式得到\begin{aligned}(K(x_1,x_1)+K(x_2,x_2)-2K(x_1,x_2))\alpha_2^{new,unc}&=y_2\left((K(x_1,x_1)+K(x_2,x_2)-2K(x_1,x_2))\alpha_2^{old}y_2+y_2-y_1+\left(\sum_{i=1}^Ny_i\alpha_iK(x_i,x_1)+b\right)-\left(\sum_{i=1}^Ny_i\alpha_iK(x_i,x_2)+b\right)\right)\\ &=(K(x_1,x_1)+K(x_2,x_2)-2K(x_1,x_2))\alpha_2^{old}+y_2\left(\left(\sum_{i=1}^Ny_i\alpha_iK(x_i,x_1)+b-y_1\right)-\left(\sum_{i=1}^Ny_i\alpha_iK(x_i,x_2)+b-y_2\right)\right)\end{aligned}
所以迭代更新公式如下\alpha_2^{new,unc}=\alpha_2^{old}+\frac{y_2\left(\left(\sum_{i=1}^Ny_i\alpha_iK(x_i,x_1)+b-y_1\right)-\left(\sum_{i=1}^Ny_i\alpha_iK(x_i,x_2)+b-y_2\right)\right)}{K(x_1,x_1)+K(x_2,x_2)-2K(x_1,x_2)}之后只需剪辑即满足不等式约束0\le \alpha_2 \le C即可。依照如下方法剪辑\alpha_2^{new}\left\{\begin{aligned}&H,&\alpha_2^{new,unc}>H\\ &\alpha_2^{new,unc},&L\le \alpha_2^{new,unc}\le H\\ &L,&\alpha_2^{new,unc}\right.求出\alpha_2后就依等式约束可以推出\alpha_1

两个变量的选择

第一个变量称为外层循环，我们选择违反分布条件最严重 的点，也就是说对应的计算结果与分布的要求差距最大的点，具体地，我们首先检查在边界上的支持向量0<\alpha_i的样本点，如果他们都满足分布条件，检查剩下的所有样本，如果都满足分布，则程序结束。
第二个变量称为内层循环，我们选择能够使\alpha_2变化最大的点。由上式可知\alpha_2变化与\left|\left(\sum\limits_{i=1}^Ny_i\alpha_iK(x_i,x_1)+b-y_1\right)-\left(\sum\limits_{i=1}^Ny_i\alpha_iK(x_i,x_2)+b-y_2\right)\right|有关，其值越大则\alpha_2变化越大，若上述方法下降不足，则遍历间隔边界上的支持向量点试用，若仍无效，则遍历整个数据集合，若仍无效，则放弃\alpha_1进入外层循环。

b的更新

对在间隔边界上的支持向量点有0<\alpha因此若0<\alpha_1\begin{aligned}b_1^{new}&=y_1-\sum\limits_{i=3}^N\alpha_iy_iK(x_i,x_1)-\alpha_1^{new}y_1K(x_1,x_1)-\alpha_2^{new}y_2K(x_2,x_1)\\ &=-\left(\sum\limits_{i=1}^Ny_i\alpha_iK(x_i,x_1)+b-y_1\right)-y_1K(x_1,x_1)(\alpha_1^{new}-\alpha_1^{old})-y_2K(x_1,x_2)(\alpha_2^{new}-\alpha_2^{old})+b^{old}\end{aligned}
同理可以计算b_2^{new}当0<\alpha_1，0<\alpha_2时b_2^{new}=b_1^{new}，当\alpha_1,\alpha_2取其他值，b_2^{new}与b_1^{new}以及之间的数皆可，此时取中点即可。

SMO高效的原因

采用近似的思想，求解二次规划问题，分解成每次优化两个变量的子问题，这些子问题拥有解析解。因此计算会高效。