1. 什么是支持向量机
首先从分类任务谈起，分类任务的核心思想就是在样本空间中找到一个超平面，能将样本分类。
我们以简单的二维空间为例，如下图：
上图中每个样本拥有两个属性，分类为$x_1,x_2$，左上角代表一类样本，右下角代表一类样本，我们想要找到一个超平面将上述样本分类，那么上图中所有的直线都可以达到这个目的，那么我们到底应该选择哪个呢？
凭直觉，我们应该选中间颜色最深的，因为它相对两类样本的距离最远。专业角度说，中间那条线的分类结果是最鲁棒的，对未见的样本泛化能力最强。
一个超平面可以通过一个线性方程描述：
\[\textbf w^T\textbf x+b=0 ，标记为(\textbf w,b) \tag{1-1}\]上述方程中，$\textbf w$为法向量，决定了超平面的方向，例如上图中的直线，$\textbf w$即为斜率；b为位移项，决定了超平面与原点之间的距离。如果不好理解，转化成二维平面就可以了。
超平面可以通过线性方程表示，那么怎么求得一个点到超平面的距离呢？
我们还是以二维平面为例，问题转换为求$(x_1,x_2)$到平面$wx_1+wx_2+b=0$的距离：
概念：连接直线外一点与直线上各点的所有线段中，垂线段最短，这条垂线段的长度，叫做点到直线的距离。
法1：计算通过点$(x_1,x_2)$且与的直线$wx_1+wx_2+b=0$相交的直线，然后求取两条直线的交点，进而计算交点与$(x_1,x_2)$的距离。
法2：通过三角形面积公式，具体不展开。
最后得出的公式为：
\[r=\frac{|wx_1+wx_2+b=0|}{\sqrt {a^2+ b^2}}\\\tag{1-2} \textbf ||w||=\sqrt {a^2+ b^2}\\ r=\frac{|wx_1+wx_2+b=0|}{\textbf ||w||}\\\]上述公式就是在二维平面中求取点到超平面的距离。
能否扩展到多维平面呢？我们来看另一种投影法：
\[\frac{||\textbf w^T (\textbf x-\textbf x_0)|}{|\textbf w|}=\frac{|\textbf w^T \textbf x+b|}{|\textbf w|}\tag{1-3}\]假如目前存在超平面$(\textbf w,b)$，能够正确分类，即y=1时，$\textbf w^T\textbf x+b>0$;y=-1时，$\textbf w^T\textbf x+b<0$，
此时，我们令：
\[\begin{cases} \textbf w^T\textbf x+b\geq+1,y=+1\\ \textbf w^T\textbf x+b\leq-1,y=-1 \end{cases}\tag{1-4}\]我们称上式中使等号成立（即$\textbf w^T\textbf x+b=+1$）的样本点即为“支持向量”，两个异类支持向量，即分别满足上式等号成立的点到超平面的距离之和为：
\[\gamma=\frac{2}{||\textbf w||}\tag{1-5}\]我们称所求的$\gamma$为间隔，求解过程如下图所示：
之前我们提到过，要寻找分类结果最鲁棒的超平面，即间隔最大的超平面。
求取最大间隔超平面，转换为公式为：
\[\max_{\textbf w,b}\frac{2}{||\textbf w||}\\ s.t. y_i(\textbf w^Tx_i+b)\geq1,i=1,2,...,m.\tag{1-6}\]间隔明明只跟参数$\textbf w$有关系，为啥要求取 $b$呢？事实上，虽然从表面看间隔仅与$\textbf w$有关系，事实上求取$\textbf w$，$b$的前提是$(\textbf w,b)$超平面，因此$b$会隐式约束$\textbf w$的值。
我们可以对上式进一步简化:
最大化间隔$\to$最大化$|\textbf w|^{-1}\to$最小化$|\textbf w|^2$，具体公式为：
\[\min_{\textbf w,b}\frac{1}{2}{||\textbf w||^2}\\ s.t. \quad y_i(\textbf w^Tx_i+b)\geq1,i=1,2,...,m.\tag{1-7}\]上面的公式就是支持向量机，即SVM的基本型。
知识储备：拉格朗日乘子法
拉格朗日乘子法是什么？
用一句话描述：寻找多元函数在一组约束下的极值的方法。
可以理解为：目标为多元函数的极值，条件为是存在一组约束的。
整体思想：通过引入拉格朗日乘子，可将有$d$个变量、$k$个约束的最优化问题转换为$d+k$个变量的无约束优化问题。
思想示意图：
等式约束的优化问题
问题：$x$为$d$维向量，求$x$满足使$f(x)$最小的$x_*$且满足个$g(x)=0$的约束。
从几何角度分析，上述问题转换成在由方程$g(x)=0$的$d-1$曲面上寻找能使目标函数法$f(x)$最小化的点。
从几何方向得出的结论：
-
对于约束曲面上的任意点x，该点的梯度$\nabla g(x)$正交于约束曲面。
-
对于最优点$x_$，目标函数在该点的梯度$\nabla f(x_)$正交于约束曲面。
因此，在最优点，$\nabla g(x)$与$\nabla f(x_*)$方向相同或相反，即存在$\lambda \neq0$，使得
\[\nabla f(x_*)+\lambda \nabla g(x)=0\]此处的$\lambda$即为拉格朗日乘子
拉格朗日函数定义为：
\[L(\textbf x,\lambda)=f(x)+\lambda g(x)\]此时，带有约束的问题就转化为对拉格朗日函数的无约束优化问题，我们来验证一下。
假如通过$L(\textbf x,\lambda)$求得最优值为$x_,\lambda$，那么要满足公式$\nabla f(x_)+\lambda \nabla g(x)=0$和$g(x)=0$。
- 求$\nabla x(\textbf x,\lambda)=0$，那么满足$\nabla f(x*)+\lambda \nabla g(x)=0$
- 求得$\nabla _\lambda (\textbf x,\lambda)=0$那么满足$g(x)=0$
因此，拉格朗日函数即为我们转换的无约束优化问题。
不等式约束的优化问题
将等式约束的优化问题的约束改为不等式，即$g(x)\leq0$。
此时最优值$x_*$可能在$g(x)=0$边界上，也可能在$g(x)<0$里面，如下图所示：
我们按照这两种情况分类分析：
- 当$g(x)<0$时，约束$g(x)\leq0$不起作用，直接通过$\nabla f(x)$求得最优解。即为\lambda = 0，然后求$\nabla _x(\textbf x,\lambda)=0$。
- 当g(x)=0时，与等式约束分析类似，但是此时$\lambda$ 必然大于0。
结合以上两种情况，可以得到转换后的最优化问题：
最小化拉格朗日函数，约束为：
\[\begin{cases} g(\textbf x)\leq0\\ \lambda \geq 0\\ \lambda g(\textbf x)=0 \end{cases}\]上述约束条件称为KKT条件(Karush-Kuhn-Tucker)
多约束问题
当问题具有$m$个等式约束，$n$个非等式约束情况时：
\[\min _xf(x)\\ s.t.\ h_i(\textbf x)=0(i=1,...,m)\\ g_j(\textbf x)\leq0(j=1,...,n)\]引入拉格朗日乘子$ \bf \lambda =(\lambda_1,\lambda_2,…,\lambda_m)^T$和$\bf \mu=(\mu_1,\mu_2,…,\mu_n)^T$，相应的拉格朗日函数为：
\[L(\bf x,\bf \lambda,\bf \mu)=f(x)+\sum_{i=1}^{m}\lambda _ih_i(\bf x)+\sum_{j=1}^{n}\mu _jg_j(\textbf x)\]对应的KKT条件为：
\[\begin{cases} g_j(\bf x)\leq0;\\ \mu_j \geq 0;\\ \mu_jg_j(\bf x)=0 \end{cases}\]我们在将上式规范一下，即成为对偶函数：
\[\Gamma(\bf \lambda,\bf \mu)=\inf_{x\in \Bbb D}L(\bf x,\bf \lambda,\bf \mu)=\inf_{x\in \Bbb D}(f(x)+\sum_{i=1}^{m}\lambda _ih_i(\bf x)+\sum_{j=1}^{n}\mu _jg_j(\textbf x))\]若$\tilde x \in \Bbb D$为可行域中的点，那么KKT条件的第一项和第三项就可以省略了，则对任意的$\mu \geq 0$和$\lambda$可以推导出：
\[\sum_{i=1}^{m}\lambda _ih_i(\bf x)+\sum_{j=1}^{n}\mu _jg_j(\textbf x)\leq0\]原因是$h_i(\bf x)$为0，那么第一项为0；$g(\textbf x)\leq0$，$\mu _j\geq0$，那么第二项小于等于0；因此整体小于等于0.
进而有：
\[\Gamma(\bf \lambda,\bf \mu)=\inf_{x\in \Bbb D}L(\bf x,\bf \lambda,\bf \mu)\leq L(\bf \tilde x,\bf \lambda,\bf \mu)\leq f(\tilde x)\]若主问题的最优解为$p^*$,则对任意的$\mu \geq 0$和$\lambda$有：
\[\Gamma(\bf \lambda,\bf \mu)\leq p^*\]可以理解为对偶函数给出了主问题的最优值的下界，$\Gamma(\bf \lambda,\bf \mu)$决定了主问题的下界，那么最好下界是什么呢？又成为求解$\Gamma(\bf \lambda,\bf \mu)$的最大值问题，转换为公式为：
\[\max _x \; \Gamma(\bf \lambda,\bf \mu)\quad s.t.\mu \geq 0\]上式就是主问题的对偶问题，其中$\lambda$ 和$\mu$ 被称为对偶变量，此时无论主问题的凸性如何，对偶问题一定是凸优化问题。
若上式的最优值为$d^$，则有$d^ \leq p^$，我们称其为弱对偶性成立；若$d^ = p^*$，则称强对偶性成立。显然，强对偶性成立时能够获取主问题的最优下界。
什么情况下强对偶性可以判定成立呢？当主问题为凸优化问题且可行域中至少有一点使不等式约束严格成立，此时强对偶性成立。在强对偶性成立时，可以将拉格朗日函数分别对原变量和对偶变量求导，再令导数等于0，即得原变量和对偶变量的数值关系，因此对偶问题解决，主问题也解决。
2. SVM标准型的对偶问题
强对偶性问题
首先，我们令拉格朗日乘子为$\alpha\geq 0$，则拉格朗日函数可写为：
\[\begin{aligned} L(\boldsymbol{w},b,\boldsymbol{\alpha}) &= \frac{1}{2}||\boldsymbol{w}||^2+\sum_{i=1}^m\alpha_i(1-y_i(\boldsymbol{w}^T\boldsymbol{x}i+b)) \\ & = \frac{1}{2}||\boldsymbol{w}||^2+\sum_{i=1}^m(\alpha_i-\alpha_iy_i \boldsymbol{w}^T\boldsymbol{x}i-\alpha_iy_ib)\\ & =\frac{1}{2}\boldsymbol{w}^T\boldsymbol{w}+\sum_{i=1}^m\alpha_i -\sum_{i=1}^m\alpha_iy_i\boldsymbol{w}^T\boldsymbol{x}i-\sum_{i=1}^m\alpha_iy_ib \end{aligned}\tag{2-1}\]令$L(\bf w,b,\bf \alpha)$对$w,b$求导且令其为0：
\[\frac {\partial L}{\partial \boldsymbol{w}}=\frac{1}{2}\times2\times\boldsymbol{w} + 0 - \sum_{i=1}^{m}\alpha_iy_i \boldsymbol{x}i-0= 0 \Longrightarrow \boldsymbol{w}=\sum_{i=1}^{m}\alpha_iy_i \boldsymbol{x}_i \tag{2-2}\\ \frac {\partial L}{\partial b}=0+0-0-\sum_{i=1}^{m}\alpha_iy_i=0 \Longrightarrow \sum_{i=1}^{m}\alpha_iy_i=0\]通过上式对拉格朗日函数进行化简，即可得对偶问题：
\[\begin{aligned} \max_{\boldsymbol{\alpha}} & \sum_{i=1}^m\alpha_i - \frac{1}{2}\sum_{i = 1}^m\sum_{j=1}^m\alpha_i \alpha_j y_iy_j\boldsymbol{x}i^T\boldsymbol{x}j \\ s.t. & \sum_{i=1}^m \alpha_i y_i =0 \\ & \alpha_i \geq 0 \quad i=1,2,\dots ,m \end{aligned}\tag{2-3}\\\]对应的KKT条件为：
\[\begin{cases} \alpha_i \geq 0；\\ y_if(x_i)-1 \geq 0\\ \alpha_i(y_if(x_i)-1) = 0 \end{cases} \tag{2-4}\]证明过程如下：
\[\begin{aligned} \min_{\boldsymbol{w},b} L(\boldsymbol{w},b,\boldsymbol{\alpha}) &=\frac{1}{2}\boldsymbol{w}^T\boldsymbol{w}+\sum_{i=1}^m\alpha_i -\sum_{i=1}^m\alpha_iy_i\boldsymbol{w}^T\boldsymbol{x}i-\sum_{i=1}^m\alpha_iy_ib \\ &=\frac {1}{2}\boldsymbol{w}^T\sum _{i=1}^m\alpha_iy_i\boldsymbol{x}_i-\boldsymbol{w}^T\sum _{i=1}^m\alpha_iy_i\boldsymbol{x}_i+\sum_{i=1}^m\alpha i -b\sum _{i=1}^m\alpha_iy_i \\ & = -\frac {1}{2}\boldsymbol{w}^T\sum _{i=1}^m\alpha_iy_i\boldsymbol{x}_i+\sum_{i=1}^m\alpha_i -b\sum_{i=1}^m\alpha_iy_i \end{aligned}\\ 又\sum_\limits{i=1}^{m}\alpha_iy_i=0\\ \begin{aligned} \min_{\boldsymbol{w},b} L(\boldsymbol{w},b,\boldsymbol{\alpha}) &= -\frac {1}{2}\boldsymbol{w}^T\sum _{i=1}^m\alpha_iy_i\boldsymbol{x}_i+\sum_{i=1}^m\alpha_i \\ &=-\frac {1}{2}(\sum_{i=1}^{m}\alpha_iy_i\boldsymbol{x}_i)^T(\sum _{i=1}^m\alpha_iy_i\boldsymbol{x}i)+\sum_{i=1}^m\alpha_i \\ &=-\frac {1}{2}\sum_{i=1}^{m}\alpha_iy_i\boldsymbol{x}i^T\sum _{i=1}^m\alpha_iy_i\boldsymbol{x}i+\sum_{i=1}^m\alpha_i \\ &=\sum_{i=1}^m\alpha_i-\frac {1}{2}\sum_{i=1 }^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_j\boldsymbol{x}i^T\boldsymbol{x}j \end{aligned}\\ \max_{\boldsymbol{\alpha}}\min_{\boldsymbol{w},b} L(\boldsymbol{w},b,\boldsymbol{\alpha}) =\max_{\boldsymbol{\alpha}} \sum_{i=1}^m\alpha_i - \frac{1}{2}\sum_{i = 1}^m\sum_{j=1}^m\alpha_i \alpha_j y_iy_j\boldsymbol{x}_i^T\boldsymbol{x}_j\tag{2-5}\]使用公式2-2可求得模型：
\[\begin{align} f(x)&=\bf w^T\bf x + b\\ &=\sum_{i=1}^m\alpha_iy_i\textbf {x}_i^T \textbf x + b \end{align}\tag{2-6}\]公式2-5存在的未知的参数是$\alpha_i$，$\alpha_i$是拉格朗日乘子，它与第$i$个样本有关。我们对第$i$个样本进行分析，事实上，第$i$个样本可以代表所有样本。
通过拉格朗日函数的KKT条件（公式2-4）我们知道，$\alpha_i \geq 0$且$\alpha_i(y_if(x_i)-1) = 0$。我们对$\alpha_i$分类进行分析：
- 当$\alpha_i = 0$时，模型与样本没关系，这个结论通过公式2-6可以得出。
- 当$\alpha_i > 0$时，$y_if(x_i)-1=0$，即$y_if(x_i)=1$，即第$i$个样本恰好是支持向量。
得出结论：最终模型仅与支持向量有关，其他样本不需要保留。
我们得出了对偶问题，通过求解对偶问题即可求解主问题。那么对偶问题，即公式2-3如何求解呢。
对偶问题是一个二次规划问题，可以使用二次规划问题求解，但是对偶问题的规模正比于训练样本数，导致消耗资源过多，因此需要找到更有效的算法。
3. 通过SMO算法求解对偶问题
基本思路：
固定除$\alpha _i$之外的所有参数，然后求$\alpha _i$的极值。
具体方法：
SMO每次选取两个变量$\alpha _i$,$\alpha _j$，固定其他参数，然后求解公式2-3，得出更新后的$\alpha _i$,$\alpha _j$；不断重复上述步骤，直至收敛。
SMO选择两个变量的原则为：使选取的两个变量所对应样本之间的间隔最大。
这样选取变量的原因是，按照上述方式选择后，会给目标函数的数值带来更大的变化。
我们来具体分析一下选取两个变量$\alpha _i,$$\alpha _j$后，是怎样具体更新的。
公式2-3的约束可简化为：
\[\alpha_iy_i+\alpha_jy_j=c ,\; \alpha_i \geq 0, \; \alpha_j \geq 0 \tag{3-1}\]其中$c=-\sum_{k\neq i,j}\alpha_ky_k$。
我们可以使用3-1消去公式2-3中的$\alpha_j$,得到仅仅关于$\alpha_i$的二次规划问题，可以通过基本的数学知识算出更新后的$\alpha _i,$$\alpha _j$。
公式2-6是我们的目标，即求解SVM的模型，此时，在公式2-6中，未知的变量仅剩下$b$了，下面介绍求解$b$的方法：
根据支持向量的定义，任意的支持向量都有$y_if(x_i)=1$,因此：
\[y_i(\sum_{i=1}^m\alpha_iy_i\textbf {x}_i^T + b )=1 \tag{3-2}\]实际上，通过公式3-2可知，我们可以选择任意支持向量求解$b$的值，但是更鲁邦的做法，是通过所有的支持向量求解平均值：
\[b=\frac{1}{|S|}\sum_{s\in S}(\frac{1}{y_i}-\sum_{i=1}^ma_iy_i\textbf x_i^T\textbf x_s)\]4. 核函数
之前的内容都是所有的样本线性可分的情况，如果样本线性不可分，那么就不能使用SVM了吗？
答案是否定的，作为统计学习著名算法之一的SVM，怎么能仅解决线性可分的样本需求呢。
事实上，对于样本在原始空间中线性不可分时，我们可以将其映射到更高维的样本空间中，使其线性可分。
可是还有一个疑问：一定存在一个更高维的空间，使得样本线性可分吗？答案是肯定的。
定理：若样本的原始空间的维度是有限的，那么一定存在一个高维特征空间，使得样本线性可分。
如上图所示的亦或问题，在二维空间中是线性不可分的，但是将其映射到三维空间中，我们可以找到一个超平面使其线性可分。
令$\phi(x)$代表$x$映射到高维空间的特征向量，那么在高维空间中的超平面可以表示为：
\[f(x)=\textbf w^T\phi(\textbf x) + b \tag{4-1}\]同理，我们将其转化为SVM的标准型：
\[\min_{\textbf w,b}\frac{1}{2} ||\textbf w||^2\\\tag{4-2} s.t. \;\;y_i(\textbf w^T\phi(\textbf x) + b) \geq 1 ,\;\; i=1,2,...,m.\]引入拉格朗日乘子$\alpha$，通过拉格朗日乘子法转换为对偶问题：
\[\max_\alpha \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\phi(\textbf x_i)^T\phi(\textbf x_j)\tag{4-3}\\ s.t. \quad \sum_{i=1}^m\alpha_iy_i=0\\ \alpha_i \geq 0, \quad i=1,2,...,m.\]求解对偶函数我们可以使用SMO算法，但是在当前情况下，会遇到一个问题：计算$\phi(\textbf x_i)^T\phi(\textbf x_j)$时，$\phi (x)$的维度可能很高，此时计算内积，维度更高。
因此，我们要想办法越过这个障碍：
设想这样的函数：
\[\kappa(\textbf x_i,\textbf x_j)=\langle \phi(\textbf x_i),\phi(\textbf x_j) \rangle=\phi(\textbf x_i)^T\phi(\textbf x_j) \tag{4-4}\]即我们不必直接计算$\phi(\textbf x_i)^T\phi(\textbf x_j)$的值，而是通过函数$\kappa$计算$x$在原始样本空间的值，它等于高维空间$\phi(\textbf x_i)^T\phi(\textbf x_j)$的内积。
于是，我们将公式4-3改写为：
\[\max_\alpha \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\kappa(\textbf x_i,\textbf x_j)\tag{4-3}\\ s.t. \quad \sum_{i=1}^m\alpha_iy_i=0\\ \alpha_i \geq 0, \quad i=1,2,...,m.\]同时，我们可以求解出公式2-6对应的模型：
\[\begin{align} f(x)&=\bf w^T \phi (\textbf x) + b\\ &=\sum_{i=1}^m\alpha_iy_i\phi(\textbf x_i)^T\phi(\textbf x_j) + b \\ &=\sum_{i=1}^m\alpha_iy_i\kappa(\textbf x_i,\textbf x_j) + b \end{align}\tag{4-4}\\\]上述几个公式中，我们设想的$\kappa$函数就是核函数，公式4-4就是通过核函数展开模型，称为支持向量展式。
上面我们介绍的核函数比较抽象，仅仅赋予了它功能，但是到底核函数内部是什么样子呢？什么样的函数可以作为核函数呢？
定理：只要一个对称函数所对应的核矩阵是半正定的，这个对称函数就能作为核函数使用。
而且，对于一个半正定核矩阵，我们总能找到一个与之对应的映射$\phi$!!这说明，我们寻找一个合适的映射，使原始维度线性不可分，映射到高维空间线性可分，这样的映射使很难找到的。但是现在通过这个定理，我们可以先找到一个核函数，然后通过核函数找到对应的映射。
准确来说，每一个核函数都隐式的定义一个”再生核希尔伯特空间“(RKHS)。
之前我们讨论的是找到一个合适的映射，使样本在映射后的空间线性可分，现在变成找到一个合适的核函数，使样本映射到一个合适的特征空间。
下面罗列出常用的核函数：
在上述5个常用的核函数基础上，我们可以进行函数组合得到新的核函数。
-
什么时候用线性核，什么时候用高斯核呢？
当数据的特征提取比较好，所包含的信息量比较大时，很多问题是线性可分的，那么采用线性核；
若特征数较小，样本数适中，对于时间不敏感，遇到的问题是线性不可分的时候，采用高斯核。
定理：
- 若$\kappa_1$和$\kappa_2$为核函数，那么对于任意正数$\gamma_1$和$\gamma_2$，线性组合$\gamma_1\kappa_1+\gamma_2\kappa_2$也是核函数。
- 若$\kappa_1$和$\kappa_2$为核函数，则核函数的直积$\kappa_1\bigotimes\kappa_2(\textbf x,\textbf z)=\kappa_1(\textbf x,\textbf z)\kappa_2(\textbf x,\textbf z)$也是核函数。
- 若$\kappa_1$为核函数，则对于任何函数$g(x)$，$\kappa(\textbf x,\textbf z)=g(\textbf x)\kappa_1(\textbf x,\textbf z)g(\textbf z)$也是核函数。
5. 软间隔
在之前的研究中，仍然存在着一个问题：
就是合适的核函数的确定，即找到一个核函数将样本在高维空间中线性可分；而且即使找打了，也有可能是由于过拟合引起的，对于新增加的样本就不适应了。
为此，我们需要”软间隔“的方式解决这个问题。
软间隔是什么呢？我们先从硬间隔说起，因为到目前为止，我们使用的方式都是硬间隔的方式。
硬间隔指的是所有样本都必须满足公式1-4的约束，相反软间隔指的是某些样本可以不满足1-4的约束。
但是如果样本都可以不满足约束1-4，那么我们的工作就没有意义了，因此，我们要使不满足约束的样本尽可能少。带着这样的目的，我们可以从优化目标下手，将优化目标1-7转换为如下形式：
\[\min_{\textbf w,b}\frac{1}{2}{||\textbf w||^2}+C\sum_{i=1}^ml_{0/1}(y_i(\textbf w^T\textbf x+b)-1)\tag{5-1}\]上式中，$C>0$是一个常数，$l$是$0/1$损失函数：
\[l_{0/1}(z)= \begin{cases} 1, \quad if \;\; z<0\\ 0, \quad otnerwise \end{cases} \tag{5-2}\]结合公式5-2可以分析出，常数C控制着不满足约束样本的数量。原因是我们新加的后一项，代表着不满足约束样本值的和（满足约束时，0/1损失函数使得后一项为0，相当于不存在），当常数C无穷大时，那么一个不满足约束的样本也不允许存在，即公式5-1和公式1-7的意义是一样的；当常数C取一个定值时，那么这个值的大小决定了允许不满足约束的样本的数量。
但是0/1损失函数和单位阶跃函数一样，非凸且不连续，数学性质不好。因此我们需要找到一个替代损失函数，这个替代损失函数要求是凸的连续函数，且应该是0/1损失函数的上界。
下面提供几种常用的替代损失函数：
hinge损失：
\[l_{hinge}(z)=max(0,1-z) \tag{5-3}\]指数损失：
\[l_{exp}(z)=\exp(-z) \tag{5-4}\]对率损失：
\[l_{log}(z)=\log(1+\exp(-z)) \tag{5-5}\]0/1损失函数和三种替代损失函数的图像如下所示：
不管使用哪种替代损失函数代替0/1损失函数，我们都可以引入松弛变量$\xi_i \geq 0$，它的作用是获取一个样本不满足约束的度。
将公式5-1更新为：
\[\min_{\textbf w,b}\frac{1}{2}{||\textbf w||^2}+C\sum_{i=1}^m\xi_i\tag{5-6}\\ s.t. \quad y_i(\textbf w^Tx_i+b)\geq1-\xi_i\\ \quad \xi_i \geq 0,\quad i=1,2,...,m.\]上式就是完整版的软间隔支持向量机。
通过公式5-6可以发现，仍是可以用拉格朗日乘子法求解，按照之前的步骤，我们引入拉格朗日乘子$\alpha,\mu$，生成拉格朗日函数：
\[L(\textbf w,b,\bf \xi, \alpha,\mu)=\frac{1}{2}{||\textbf w||^2}+C\sum_{i=1}^m\xi_i+\sum_{i=1}^m\alpha_i(1-\xi_i-y_i(\textbf w^Tx_i+b))-\sum_{j=1}^m\mu_j\xi_j\tag{5-7}\]然后对$L(\textbf w,b,\bf \xi, \alpha,\mu)$求$\textbf w,b,\bf \xi$的偏导数，并令其等于0，可以求出以下几个公式：
\[\textbf w=\sum_{i=1}^m\alpha_iy_i\textbf x_i\\\tag{5-8} 0=\sum_{i=1}^m\alpha_iy_i\\ \frac{\partial L}{\partial \xi_i}=0+C \times 1 - \alpha_i \times 1-\mu_i \times 1 =0\Longrightarrow C=\alpha_i +\mu_i\]将5-8中的公式带入到5-7中，即可求得对偶问题：
\[\begin{aligned} \max_{\boldsymbol{\alpha}}&\sum_{i=1}^m\alpha_i-\frac {1}{2}\sum_{i=1 }^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_j\boldsymbol{x}i^T\boldsymbol{x}j \\ s.t. &\sum{i=1}^m \alpha_i y_i=0 \\ & 0 \leq\alpha_i \leq C \quad i=1,2,\dots ,m \end{aligned}\tag{5-9}\]公式5-9就是软间隔支持向量机基本型的对偶问题，跟公式2-3相比较，可以发现，仅仅是约束不同，软间隔支持向量机的对偶问题增加了对$\alpha$的约束，由$0 \leq\alpha_i$ 变成$0 \leq\alpha_i \leq C$。
同样，我们列出拉格朗日函数的KKT条件：
\[\begin{cases} \alpha_i \geq0,\quad\mu_i \geq 0,\\ y_i(\textbf w^Tx_i+b)-1+\xi_i\geq0,\\ \alpha_i(y_i(\textbf w^Tx_i+b)-1+\xi_i)=0,\\ \xi_i \geq 0,\quad \mu_i\xi_i=0. \end{cases}\tag{5-10}\]在采用了软间隔的情况下，仍然可以得出支持向量机的模型仅与支持向量有关的结论。
在上述过程中，我们使用了hinge替代损失函数，如果使用对率替代损失函数，我们几乎得到了对率回归模型(logistic regression)。
SVM和对率回归的比较：
- 优化目标相似、性能也相当。
- 对率回归的结果不仅可以分类，而且可以作为概率使用；SVM的输出不具有概率意义。
- 对率回归能直接用于多分类任务，SVM则不可以。
- 对率回归依赖更多的样本，开销更大。
通过上述对软间隔的理解，我们可以对优化目标，也就是SVM基本项写出更通用的形式：
\[\min _f \quad \Omega(f)+C\sum_{i=1}^ml(f(x_i),y_i)\tag{5-11}\]我们将5-11的公式分为两项，其中第一项描述划分超平面间隔的大小；另一项用来表示训练集上的误差。
更准确的说，第一项是”结构风险“，用来描述模型f的某些性质；第二项是经验风险，用来描述模型与训练数据的却合度；C用来对两者进行折中。
从经验风险最小化的角度来分析公式5-11，$\Omega(f)$为正则化项，$C$为正则化常数，关于正则化的相关知识将会在另一篇文章中细说。
6. 支持向量回归
一般的回归问题解决方式，都是计算模型预测值与真实值的误差，来计算损失，但是支持向量回归容忍模型预测值与真实值存在$\epsilon$的误差，即当预测值与真实值的绝对值大于$\epsilon$才计算损失。我们称支持向量回归为SVR。
如上图所示，SVR的原理类似于在SVM为中心，构建了一个宽度为2$\epsilon$的安全区，只要样本落入所示区域中，我们就认为是正确的。
根据上述描述，SVR的公式为：
\[\min _{\textbf w,b} \quad \frac{1}{2}||\textbf w||^2+C\sum_{i=1}^ml_\epsilon(f(\textbf x_i)-y_i)\tag{6-1}\]其中$l_\epsilon$为不敏感损失函数，函数图像如下所示：
引入松弛变量$\xi_i,\hat \xi_i$，可将6-1重写为：
\[\min _{\textbf w,b,\xi_i,\hat \xi_i} \quad \frac{1}{2}||\textbf w||^2+C\sum_{i=1}^m (\xi_i+\hat \xi_i)\\ \begin{aligned} s.t. \quad &f(\textbf x_i)-y_i\leq\epsilon+\xi_i,\\ &y_i-f(\textbf x_i)\leq\epsilon+\hat \xi_i,\\ &\xi_i \geq 0,\hat \xi_i \geq 0,i=1,2,...,m. \end{aligned}\tag{6-2}\]公式6-2就是SVR的优化目标。
按照之前的套路，我们先引入拉格朗日乘子，然后求解拉格朗日函数，进而拉格朗日函数对$\textbf w,b,\xi_i,\hat \xi_i$分别求导，使其等于0，将得出的结果带入拉格朗日函数中，记得可SVR优化目标的对偶问题。
具体过程省略。。。。。。
最终求得的SVR模型可表示为：
\[f(\textbf x)=\sum_{i=1}^m(\hat\alpha_i-\alpha_i)\kappa(\textbf x,\textbf x_i)+b\tag{6-3}\]$\kappa(\textbf x,\textbf x_i)$为核函数。
7. 核方法
首先介绍一下表示定理:
令$\Bbb H$表示核函数$\kappa$对应的再生核希尔伯特空间，$|h|_{\Bbb H}$表示$\Bbb H$空间中关于h的范数，对于任意单调递增函数：$\Omega:[0,\infty]\to\Bbb R$和任意非负损失函数$l$:$\Bbb R^m\to[0,\infty]$,优化问题：
\[\min _{h\in \Bbb H} F(h)=\Omega(||h||_{\Bbb H})+l(h(\textbf x_1),h(\textbf x_2),...,h(\textbf x_m))\]的解可以写为：
\[h^*(\textbf x)=\sum_{i=1}^m\alpha_i\kappa(\textbf x,\textbf x_i)\]基于核函数的强大效果，发展处一系列核方法(基于核函数的学习方法)。
最常见的是通过引入核函数，将线性学习器拓展为非线性学习器。
例如通过核函数将线性判别分析转换为非线性判别分析的过程，最终得到核线性判别分析(KLDA)。
因为内容与SVM关联不大，因此不再展开。
8. SVM代码实现
没有手动实现SVM的具体代码哈，而是调用了sklearn中SVM的库。
感兴趣的可以参考github
本篇文章主要参考西瓜书中的支持向量机一章、南瓜书公式推导。
