支持向量机(SVM)

引入

对于上一篇提到的风险（Risk）：

$$R(w)\leq R_{emp}(w)+\epsilon(N,p^*,h)$$

其中$N$是训练数据量，$p^*$是到达边界的概率，$h$是VC维度。

为了最小化风险，经典的机器学习算法是：

固定$\epsilon(…)$，最小化经验风险$R_{emp}$
其中$\epsilon(…)$是通过保证一些模型参数不变以固定的，比如说神经网络的隐藏层数量。

支持向量机（SVM）的做法则是：

保证$R_{emp}(w)$固定以最小化$\epsilon$
当数据可分时，$R_{emp}(w)=0$。
通过改变VC维度以控制$\epsilon$。

支持向量机一般分为三类：

1. 线性可分支持向量机（linear support vector machine in linearly separable case ），采用的方法是硬间隔最大化（hard margin maximization）
2. 线性支持向量机（linear supportvector machine），是指训练数据近似线性可分时，采用的方法是软间隔最大化（soft margin maximization）
3. 非线性支持向量机（non-linear support vector machine），是指训练数据线性不可分时，采用核技巧（kernel trick）及软间隔最大化

对于二分类问题：

输入空间：欧式空间或离散集合
特征空间：欧式空间或希尔伯特空间

线性可分支持向量机、线性支持向量机：

假设这两个空间的元素一一对应，并将输入空间中的输入映射为特征空间中的特征向量；

非线性支持向量机：

利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量；

支持向量机的学习是在特征空间进行的。

（这篇会有不少补充推导，这些过程其实看不看都没事，不想看的话就直接记结论。看了，能减少学习过程中的疑惑，不看，也不会对SVM的理解产生大的影响）

线性SVM

硬间隔最大化

直白地说，就是找一个（超）平面，使其距离最近数据点的距离最大，就是最大化下图这个$margin$。

为了最大化这个margin，我们首先要找到一个超平面，使数据得到线性分离：

$$y_i(\pmb{w}^T\pmb{x}_i+b)\ge1 \quad \forall i$$

并且让至少一个点满足$y_i(\pmb{w}^T\pmb{x}_i+b)=1$。
然后这个间隔就是$\frac{1}{||w||}$。

———————————————————————————————————————

补充1

上面的（不）等式怎么来的，这里的1又是什么，为什么间隔会是这个？
我们要找到最大间隔分类器，就是要找一个合适的参数$w,b$，使其满足：

$$\max margin(w,b)$$ $$s.t.\quad y_i(\pmb{w}^T\pmb{x}_i+b)>0$$

稍微解释一下这个约束条件：这里有个前提是我们已经把数据分类好了，因为线性可分，其经验风险为0，$y_i$与括号里的式子同号，相乘大于0。
再多说一点，点到超平面的距离表示分类预测的确信程度，$w^Tx+b$与标签符号是否一致表示分类的准确性，所以$y(w^Tx+b)$表示分类的正确性和确信度。
这里定义一下这个$margin$函数如下：

$$margin(w,b)=\min\limits_{w,b,x_i,i=1...N} distant(w,b,x_i)$$

也就是说我们要找到距离（超）平面最近的那个点所对应的距离。
然后点到（超）平面的距离为（距离公式之前那篇分类问题里有用到）：

$$distant=\frac{1}{||\pmb{w}||}|\pmb{w}^Tx_i+b|$$

也就是说，间隔公式可以写为：

$$margin(w,b)=\min\limits_{w,b,x_i,i=1...N} \frac{1}{||\pmb{w}||}|\pmb{w}^Tx_i+b|$$

即是说，最上面我们要处理的问题就变为：

$$\max\limits_{w,b} \min\limits_{x_i,i=1...N}\frac{1}{||\pmb{w}||}|\pmb{w}^Tx_i+b|$$ $$s.t.\quad y_i(\pmb{w}^T\pmb{x}_i+b)>0$$

因为绝对值符号有点碍眼，根据其约束条件我们可以将其改写成：

$$\max\limits_{w,b} \min\limits_{x_i,i=1...N}\frac{1}{||\pmb{w}||}y_i(\pmb{w}^Tx_i+b)$$

因为我们要求的是最大值对应的参数，所以这里加个系数也无所谓（或许这里写成$argmax$之类的会更好理解？）。
继续改写！
前面那个$\frac{1}{||\pmb{w}||}$跟$\min$无关，所以可以前移，然后对于约束条件，因为左式大于0，所以我们肯定能找到一个$\gamma$，使左式最小值等于$\gamma$，即是：

$$\max\limits_{w,b} \frac{1}{||\pmb{w}||}\min\limits_{x_i,i=1...N}y_i(\pmb{w}^Tx_i+b)$$ $$s.t.\quad \exists \gamma \min\limits_{x_i,y_i,i=1,...,N} y_i(\pmb{w}^T\pmb{x}_i+b)=\gamma$$

令$\gamma=1$，将约束条件带入我们要处理的式子，就可以写成：

$$\max\limits_{w,b} \frac{1}{||\pmb{w}||}$$ $$s.t.\quad \min\limits_{x_i,y_i,i=1,...,N} y_i(\pmb{w}^T\pmb{x}_i+b)=1$$

为什么这里可以让$\gamma=1$呢？因为这相当于超平面的等比例缩放，取1只是为了方便计算而已，要有闲情逸致的话，取个3.1415926都行。
继续改写约束条件!
这个最小值的等式我们可以用不等式代替，然后这个求最大值的我们也可以用最小值代替，分子分母换位而已，即：

$$arg\min\limits_{w,b} \frac{1}{2}w^Tw$$ $$s.t.\quad y_i(\pmb{w}^T\pmb{x}_i+b)\ge1 \quad for \quad \forall i=1,...,N$$

这里乘上$\frac{1}{2}$，又把根号去掉，只是为了方便后面计算，毕竟我们要的是$w,b$，不要求计算实际最大值，所以这无所谓。这是一个典型的凸二次规划问题：有$N$个约束条件，目标函数是二次的。
至此，我们就知道上面的1和（不）等式是什么东西，以及间隔为什么会是$\frac{1}{||w||}$了。

——————————————————————————————————————

支持向量（Support vectors）：

所有位于边缘的点，即满足：$y_i(\pmb{w}^T\pmb{x}_i+b)=1$的点。
现在计算以下优化问题(写法上跟上面补充内容有一丁点不一样，但意思是一样的)：

$$arg\min\limits_{w,b} \frac{1}{2}||w||^2$$ $$s.t. \quad y_i(\pmb{w}^T\pmb{x}_i+b)-1\ge0 \quad \forall i$$

带约束条件的优化问题依旧是拉格朗日,如下：

要最小化上面这个$L(w,b,\alpha)$，即是要同时对$b,w$求偏导并令偏导等于0，如下：

现在还剩个$\alpha_i$。
在这里，只有在边缘点$\alpha_i$是不为0的，其余点的$\alpha_i$都等于0，比如下面这张图：

只有圈出的那三个点的$\alpha_i$是有意义的。所以SVM是一个稀疏（sparse）的学习机，分类只取决于少数的点。
要求解这个$\alpha_i$，我们就要引进这个问题的对偶问题。

———————————————————————————————————————

补充2——拉格朗日对偶

在约束最优化问题中，常常利用拉格朗日对偶性(Lagrange duality)将原始问题转换为对偶问题，通过解对偶问题得到原始问题的解。
比如说，现有原始问题：
设$f(x),c(x),h(x)$是定义在$\mathcal{R}^n$上的连续可微函数：

$$\min\limits_{x\in \mathcal{R}^n}f(x)$$ $$s.t. \quad c_i(x)\leq0,\quad i=1,...,k$$ $$h_j(x)=0,\quad j=1,...,l$$

引入拉格朗日函数$\alpha_i,\beta_j$为乘子$\alpha_i\ge0$:

$$L(x,\alpha,\beta)=f(x)+\sum_{i=1}^{k}\alpha_ic_i(x)+\sum_{j=1}^{l}\beta_jh_j(x)$$

考虑$x$的函数，$P$为原始问题：

$$\theta_P(x)=\max\limits_{\alpha,\beta,\alpha_i\ge0}L(x,\alpha,\beta)$$

假定给定一个$x$，如果$x$违反约束条件，即：

$$c_i(x)>0\quad h_j(x)\ne0$$

则

$$\theta_P(x)=\max\limits_{\alpha,\beta,\alpha_i\ge0}[f(x)+\sum_{i=1}^{k}\alpha_ic_i(x)+\sum_{j=1}^{l}\beta_jh_j(x)]=+\infty$$

即（这个结论下面需要用到）：

考虑极小问题：

$$\min\limits_{x}\theta_P(x)=\min\limits_{x}\max\limits_{\alpha,\beta,\alpha_i\ge0}L(x,\alpha,\beta)$$

这个极小问题与原始的最优化问题等价

$$p^*=\min\limits_{x}\theta_P(x)$$

原始问题变为：

$$\min\limits_{x}\theta_P(x)=\min\limits_{x}\max\limits_{\alpha,\beta,\alpha_i\ge0}L(x,\alpha,\beta)$$

称为广义拉格朗日函数的极小极大问题，定义最优解为$p^*=\min\limits_{x}\theta_P(x)$。

对偶问题为：
定义：$\theta_D(\alpha,\beta)=\min L(x,\alpha,\beta)$
所以：

$$\max\limits_{\alpha,\beta,\alpha_i\ge0}\theta_D(\alpha,\beta)=\max\limits_{\alpha,\beta,\alpha_i\ge0}\min\limits_xL(x,\alpha,\beta)$$

称为广义拉格朗日函数的极大极小问题，约束条件为$\alpha_i\ge0,i=1,…,k$，这个称为原始问题的对偶问题，对偶问题的最优值为：

$$d^*=\max\limits_{\alpha,\beta,\alpha_i\ge0}\theta_D(\alpha,\beta)$$

若原始问题和对偶问题都有最优值，则：

$$d^*=\max\limits_{\alpha,\beta,\alpha_i\ge0}\min\limits_xL(x,\alpha,\beta)\leq \min\limits_{x}\max\limits_{\alpha,\beta,\alpha_i\ge0}L(x,\alpha,\beta)=p^*$$

在SVM这里，对偶问题其实就可以表示为很直接的一个式子：

$$\max\min f(x)\leq \min\max f(x)$$

这个式子直观上就能理解，所以这里不解释。
这个不等式称为弱对偶关系，但在SVM我们要强对偶关系，也就是：

$$\max\min f(x)=\min\max f(x)$$

而凸优化的二次规划问题恰恰就满足强对偶条件。

————————————————————————————————————————

也就是说，现在问题变成求以下优化问题：

$$\max\limits_{\alpha}\min\limits_{w,b}L(w,b,\alpha)$$ $$s.t. \quad \alpha\ge0$$

现在问题就好算了。
在继续往下之前先对上面做个总结（上面的看着挺乱）：

1. 首先我们要求解以下这个优化问题：

   $$arg \min\limits_{w,b}\frac{1}{2}w^Tw$$ $$s.t. \quad y_i(\pmb{w}^T\pmb{x}_i+b)\ge1 \quad for \quad \forall i=1,...,N$$

2. 用拉格朗日法进行去约束，变为：

   $$\min\limits_{w,b}\max\limits_{\alpha}L(w,b,\alpha)$$

$$s.t. \quad \alpha\ge0$$

这里再简单说一下，这个优化跟$w,b$已经无关了（这么说好像不太准确。。。），就是说，如果$y_i(\pmb{w}^T\pmb{x}_i+b)<1$的话，根据上面补充（关于$+\infty$）的内容，值是等于$+\infty$的，再根据前面的最小约束，怎么都取不到这个值，所以不管$w,b$的值怎么取，结果都是等价于是在约束$y_i(\pmb{w}^T\pmb{x}_i+b)\ge1$里取，这是被上面拉格朗日的方程限制死的，所以我们不再需要考虑上面的约束了。

1. 根据强对偶关系，优化问题等价于：

$$\max\limits_{\alpha}\min\limits_{w,b}L(w,b,\alpha)$$ $$s.t. \quad \alpha\ge0$$

总结结束，继续!
对于这个优化问题就很容易求了，两次求导即可。上面我们已经有过一次求导了，把上面的结论写下来即是：

将其带入下面这个最开始的拉格朗日方程里：

得到下面这个式子：

这就是拉格朗日方程的最小值，再由于：

继续改写成如下的式子

这就是我们要最大化的东西。
这里我们要这么大费周章地推导求解对偶问题，主要是因为：

1. 对偶问题往往更容易求解；
2. 引入核函数，即为非线性SVM做准备。

软间隔最大化

软间隔最大化问题跟硬间隔的差不多，只是训练集中会有一些异常点（outlier）不能满足约束条件$y_i(\pmb{w}^T\pmb{x}_i+b)\ge1$。如下图：

一个简单的思路就是，将这些数据点映射到新的特征空间，然后就可以线性区分了，比如用小半径的RBF核函数（这在下面非线性SVM会介绍）。
但这会产生一个问题，就是$VC$维度特别大，可能会导致过拟合。

另一种解决方法是：选择性地忽略一些点。对每个样本点$(x_i,y_i)$引进一个松弛变量（slack variables）$\xi_i\ge0$，使：

函数间隔加上松弛变量大于等于1，即约束条件变为：

$$y_i(\pmb{w}^T\pmb{x}_i+b)\ge1-\xi_i$$

目标函数就变为：

$$\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i$$

其中$C>0$为惩罚参数。
由此可得，线性不可分的线性支持向量机的学习问题为：

其中$w$的解是唯一的，$b$不是（不作证明）。

最大化边际（margin），同时最小化所有不在边际之外的数据点的惩罚权重 C 允许我们指定权衡。 通常通过交叉验证确定, 即使数据是可分离的，最好允许偶尔的惩罚（penalty）。

剩下的解优化问题跟硬间隔几乎是一模一样了，不过还是再过一遍吧。
回到我们上面的学习问题，带约束的优化，用拉格朗日函数如下：

$$L(w,b,\xi,\alpha,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i-\sum_{i=1}^{N}\alpha_i(y_i(wx_i+b)-1+\xi_i)-\sum_{i=1}^{N}\mu_i\xi_i$$

其中: $\alpha_i\ge 0,\mu_i\ge0$。对偶问题是这个函数的极大极小问题，首先求$L(w,b,\xi,\alpha,\mu)$对$w,b,\xi$的极小，即是求导等于0，得：

即是说，极小值为：

再对$\alpha$求极大：

这里$alpha_i\leq C$称为box constraint(箱体约束)。

设$\alpha^=(\alpha_1^,…,\alpha_N^)^T$是上面对偶问题的一个解，若存在$\alpha$的一个分量$\alpha_j$，$0<\alpha_j^<C$，则原始问题的解$w,b$为：

$$w^*=\sum_{i=1}^{N_s}\alpha_i^*y_ix_i$$ $$b^*=y_j-\sum_{i=1}^{N_s}y_i\alpha_i^*(x_ix_j)$$

(注：在硬间隔中求出的$\alpha$也是一个向量。)

———————————————————————————————————————

补充3——合页损失函数（hinge loss function）

线性支持向量机学习还有另一种解释，就是最小化下面这个目标函数：

$$\sum_{i=1}^{N}[1-y_i(wx_i+b)]_++\lambda||w||^2$$

第一项：$L(y(wx+b))=[1-y(wx+b)]_+$就称为合页损失函数，其中：

$$[z]_+=z,\quad z>0$$ $$[z]_+=0,\quad z\le0$$

最优化问题就可以等价为：

———————————————————————————————————————

非线性SVM

然而很多时候我们得到的数据并不是直接用硬或者软间隔进行线性分类的，比如下面这个：

明显，不管怎么画直线都没办法把这两类分开，这时候我们可以增加一个维度，从二维变三维，变成下面这种情况：

这个就可以用（超）平面进行线性划分了。记住一点：相对于低维，高维更可能可以用线性进行分类。
也就是说在这里，数据的输入空间不再直接充当特征空间，我们要新构造一个特征空间，就跟之前的线性回归那里的思想是一样的。
我们的输入是$\pmb{x}$，然后就要找到一个非线性变换$\phi$，将输入空间映射到特征空间（但这个映射也不能太过分了，不然容易过拟合）。
现在回顾上面的对偶形式：

通过非线性变换，可以得到下面的方程：

这个式子可以看出，当两个特征空间的元素$\phi(x_i)$和$\phi(x_j)$内积时，就会产生一个标量。
再看判别函数：

$$y(x)=w^T\phi(x)+b$$

由于

$$w=\sum_{i=1}^{N_s}\alpha_iy_i\phi(x_i)$$

则非线性判别函数可以写为：

$$y(x)=\sum_{i=1}^{N_s}\alpha_iy_i\phi(x_i)^T\phi(x)+b$$

其中$N_s$是支持向量的数目。
又发现，判别函数也可以只用非线性特征的标量积来表示。
但是我们想直接计算它们内积是不太可能的，因为这个非线性转换可能会出现无限维的情况。
这就引出了核技巧（Kernel Trick），即使用核函数取代每一个标量积：

$$K(x_i,x_j)=\phi(x_i)^T\phi(x_j)$$

如果我们能找到这么一个核函数，那就可以避免高维空间的映射，转而直接计算这个标量积。
但该怎么判断是否存在这样的核函数呢？

多项式核（Polynomial Kernel）

以以下二阶核为例：

$$K(x,y)=(x^Ty)^2$$

等同于点积：

$$K(x,y)=(x^Ty)^2=x_1^2y_1^2+2x_1x-2y_1y_2+y_1^2y_2^2$$

对应的非线性转换为：

以这个为例，核方法的一个优点是核计算量的简便，比如这里的计算数为：3（$x,y$的点积）+1（结果的平方）=4
另外需要注意，一个核函数的非线性变换不是唯一的，比如上面这个核函数，其对应的变换还可能是：

转换空间维度以及VC维度的确定
令$C_d(x)$为将一个向量映射到所有阶数为$d$的有序单项式空间的变换。

$$K(x,y)=(x^Ty)^d=C_d(x)^TC_d(y)$$

转换空间$H$的维度为：$C_{d+N-1}^{d}$。
比如说：

$$N=16\times 16=256 \quad d=4$$

则转换空间维度为：

$$dim(H)=183181376$$

该分类器的$VC$维度为：$dim(H)+1$。

径向基函数（Radial Basis Functions）

径向基函数（RBF），通常定义为空间任一点到某一中心的$y$的欧氏距离的单调函数，最常用的是高斯核函数，定义为：

$$K(x,y)=\exp(-\frac{||x-y||^2}{2\sigma^2})$$

换种说法的话，这个核函数可以衡量$x$和$y$的相似度的。其对应的变换空间是无限维的，所以其VC维度也是无限维的。当$x$和$y$很接近时值为1，很远时值为0，$\sigma$为函数的宽度参数，控制函数的径向作用范围。
用这个核函数的效果如下：

Mercer’s Condition

既然核函数能极大地简便我们的计算量，那现在就有个问题，我们该如何判断给定的一个函数$K$是一个有效的核函数呢，或者说，我们如何判断这个$K$能够替代$\phi(x_i)^T\phi(x_j)$？
这就引出了Mercer定理。

Mercer定理：
如果函数$K$是$R^n\times R^n\rightarrow R$上的映射（也就是从两个$n$维向量映射到实数域），当且仅当对于任意训练样例$[x_1,…,x_n]$，其相应的核函数矩阵是对称半正定的话，则$K$是一个有效核函数（也称为Mercer核函数）。

——————————————————————————————————————

补充4——正定与半正定矩阵

正定矩阵
给定一个大小为 $n\times n$的实对称矩阵 $A$ ，若对于任意长度为 $n$ 的非零向量 $x$ ，有$x^TAx>0$ 恒成立，则矩阵 $A$ 是一个正定矩阵。
正定矩阵的特征值都大于0。

半正定矩阵
给定一个大小为 $n\times n$的实对称矩阵 $A$ ，若对于任意长度为 $n$ 的非零向量 $x$ ，有$x^TAx\ge0$ 恒成立，则矩阵 $A$ 是一个半正定矩阵。
也就是说，半正定包含正定，其特征值均为非负，主子式大于等于0。

———————————————————————————————————————

也就是说，为了证明$K$是有效核函数，我们不需要去找相应的映射函数$\phi$，只需要在训练集上求出各个$K_ij$，判断其是否为半正定即可。
上面的Mercer定理用数学表达的话可以写为：

对于满足$\int g(x)^2dx<0$的$g(x)$，若$K(x,y)$满足$\int \int K(x,y)g(x)g(y)dxdy\ge0$，则$K(x,y)$是一个有效核函数。

判断一个函数是否满足Mercer定理并不容易，但我们可以根据现有的有效核函数构造出新的，也就是说，如果$K_1(x,y),K_2(x,y)$是有效核函数，则下面这些也是：

$$cK_1(x,y)\\K_1(x,y)+K_2(x,y)\\K_1(x,y)K_2(x,y)\\f(x)K_1(x,y)f(y)\\...$$

相关补充

除了上面的，非齐次多项式核函数也可以用来表示$d$阶多项式，形式如下：

$$K(\pmb{x},\pmb{y})=(\pmb{x}^T\pmb{y}+c)^d$$

除了Gaussian RBF 核函数：

$$K(\pmb{x},\pmb{y})=\exp(-\frac{||\pmb{x}-\pmb{y}||^2}{2\sigma^2})$$

还有其它比如Hyperbolic tangent核函数：

$$K(\pmb{x},\pmb{y})=tahn(a\pmb{x}^T\pmb{y}+b)$$