svm小结

线性可分支持向量机（硬间隔）

1.函数间隔与几何间隔

$$\hat \gamma_i=y_i(wx_i + b)$$ $$\tilde \gamma_i= \frac{\hat \gamma_i}{||w||}$$

2.间隔最大化

$$\underset{w,b}{max} \frac{\hat \gamma}{||w||}$$ $$s.t. \space y_i(wx_i + b) \ge \hat \gamma,i=1,2,\cdots,N$$

函数间隔$\hat \gamma$的取值并不影响最优化问题的求解。如将$w$和$r$等比例改为$\lambda w$和$\lambda b$，这时函数间隔变为$\lambda \hat \gamma$，函数间隔这一改变对上面的不等式约束和目标函数的优化都没有影响。令$\hat \gamma=1$，问题转化为：

$$\underset{w,b}{min} \space \frac{1}{2}||w||^2 \tag {7.13}$$ $$s.t. \space y_i(wx_i + b) - 1\ge 0,i=1,2,\cdots,N \tag {7.14}$$

3.拉格朗日函数

$$L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^N(\alpha_iy_i(wx_i+b)-1)$$

原问题转化为

$$d^*=\underset{w,b}{min} \space \underset{\alpha}{max} \space L(w,b,\alpha) \\ s.t. \space a_i \ge 0,i=1,2,\cdots,N$$

为什么$\theta(w) = \max_{\alpha_i\geq 0}\mathcal{L}(w,b,\alpha)$和原问题$\frac{1}{2}||w||^2$是等价的？

容易验证，当某个约束条件不满足时，例如$y_i(w^Tx_i+b) < 1$那么我们显然有 $\theta(w)=\infty$（只要令 $\alpha_i=\infty$ 即可）。而当所有约束条件都满足时，则有 $\theta(w)=\frac{1}{2}|w|^2$ ，亦即我们最初要最小化的量。

4.对偶问题

根据拉格朗日对偶性，原问题的对偶问题是极大极小问题，用$p^*$表示。

$$p^*=\underset{\alpha}{max} \space \underset{w,b}{min} \space L(w,b,\alpha)$$ $$s.t. \space a_i \ge 0,i=1,2,\cdots,N$$

易知$d^\leq p^$，而当满足KKT条件时，二者的划等号的。因为我们有7.14的不等式约束，所以满足KKT条件（好神奇 :)）

于是就来求解对偶问题吧！

• 求$\underset{w,b}{min} \space L(w,b,\alpha)$

  $$\nabla_w L(w,b,\alpha)=w-\sum_{i=1}^w\alpha_iy_ix_i=0$$ $$\nabla_b L(w,b,\alpha)=\sum_{i=1}^w\alpha_iy_i=0$$

  得

  $$w=\sum_{i=1}^w\alpha_iy_ix_i$$ $$\sum_{i=1}^w\alpha_iy_i=0$$

  代入$L$

  $$L(w,b,\alpha)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_jy_iy_j(x_i \cdot x_j) + \sum_{i=1}^N\alpha_i$$

• 原问题就转化为，求$\underset{w,b}{min} \space L(w,b,\alpha)$对$\alpha$的极大，

  $$\underset{\alpha}{max}-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_jy_iy_j(x_i \cdot x_j) + \sum_{i=1}^N\alpha_i$$ $$\begin{align} s.t. & \space \sum_{i=1}^w\alpha_iy_i=0 \\ & a_i \ge 0,i=1,2,\cdots,N \end{align}$$

  取反

  $$\underset{\alpha}{min}\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_jy_iy_j(x_i \cdot x_j) -\sum_{i=1}^N\alpha_i \tag {7.22}$$ $$\begin{align} s.t. & \space \sum_{i=1}^w\alpha_iy_i=0 \tag{7.23}\\ & a_i \ge 0,i=1,2,\cdots,N \tag {7.24} \end{align}$$

对于线性可分训练数据集，假设对偶最优化问题（7.22）~（7.24）对$\alpha$的解为

$$\alpha^*=(\alpha^*_1,\alpha^*_2,\cdots,\alpha^*_N)^T$$

定理 7.2 存在下标$j$，使得$a_j^>0$，并可以按下式求得原始最优化问题(7.13)~(7.14)的解$w^,b^*$:

$$w=\sum_{i=1}^w\alpha_i^*y_ix_i$$

其中至少存在一个$a^*_j$>0，对此$j$有$y_j^2=1$，这也是为什么$b$是唯一的原因，于是：

$$b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i\langle x_i\cdot x_j \rangle$$

解出$\alpha$后，求出$w$和$b$即可得到模型

$$\begin{align} f(x)&=\left(\sum_{i=1}^n\alpha_i y_i x_i\right)^Tx+b \\ &= \sum_{i=1}^n\alpha_i y_i \langle x_i, x\rangle + b \end{align}$$

因为KKT条件成立，于是 $\alpha$有如下性质:

$$\begin{cases} \alpha_i \ge 0 \\[2ex] y_if(x_i)-1 \ge 0 \\[2ex] \alpha_i(y_if(x_i)-1)=0 \end{cases}$$

可以看出若$\alpha = 0$，则该样本不会出现在预测模型中，若$\alpha \gt 0$，一定有$y_if(x_i)=1$，其所对应的样本点位于最大间隔边界上，是一个支持向量。这也是svm的一个重要特性：训练完成后，大部分的训练样本都不需要保留，最终模型仅仅与支持向量有关。

核函数

现实中的样本数据往往不是线性可分的，此时超平面并不存在。对于这样的问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。

这不禁联想到三体里的高等文明，以高维空间的视角审视低维世界的生物，一览无余，骨骼、血脉等人体构造如庖丁解牛般拆分开来。最后地球遭受的二向箔降维打击，将三维空间压缩到了二维空间，人类的世界交叠在了一起，变成了油画般的平面。

如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。
令$\phi(x)$表示将$x$映射后的特征向量

原模型变为：

$$f(x) = \sum_{i=1}^n\alpha_i y_i \langle \phi(x_i), \phi(x)\rangle + b$$

由于特征空间维数可能很高，甚至无穷维，直接计算$\langle \phi(x_i), \phi(x)\rangle$通常是困难的，于是引出核函数。

$$\kappa\langle x_i,x_j \rangle=\langle \phi(x_i), \phi(x)\rangle$$

即$x_i$与$x_j$在特征空间的内积等于它们在原始样本空间中通过核函数$\kappa\langle x_i,x_j \rangle$计算的结果。这样就不用直接去计算高维甚至无穷维特征空间中的内积。

原模型变为

$$f(x) = \sum_{i=1}^n\alpha_i y_i \kappa \langle x_i, x\rangle + b$$

常用核函数及经验

Linear 线性核和radial basis function RBF 高斯核最常用

选择方法

1. 如果Feature的数量很大，跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM
2. 如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM+Gaussian Kernel
3. 如果Feature的数量比较小，而样本数量很多，需要手工添加一些feature变成第一种情况

RBF相比于Linear计算量大一些，所以当样本数很多的时候，尽量使用Linear

注意 SVM建模前需要先对数据进行归一化

软间隔

在现实中，一般不是线性可分的，而且退一步说，即便恰好找到某个核函数使训练集在特征空间线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的。

在我们原来的 SVM 模型里，outlier 的存在有可能造成很大的影响，因为超平面本身就是只有少数几个 support vector 组成的，如果这些 support vector 里又存在 outlier 的话，其影响就很大了

核函数用于解决空间不可分，软间隔主要关注异常点

对每个样本点引进松弛变量$\xi_i \ge 0$ ,约束条件变为$y_i(wx_i + b)\ge 1-\xi_i$，问题转化为：

$$\underset{w,b,\xi}{min} \frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i$$ $$\begin{align} s.t. & \space y_i(w^Tx_i + b) \ge 1-\xi_i,i=1,2,\cdots,N \\ & \xi_i \ge 0,i=1,2,\cdots,N \end{align}$$

其中 C 是一个参数，用于控制目标函数中两项（“寻找 margin 最大的超平面”和“保证数据点偏差量最小”）之间的权重。注意，其中 ξ 是需要优化的变量（之一），而 C 是一个事先确定好的常量

类比硬间隔处理方法，

$$\mathcal{L}(w,b,\xi,\alpha,r)=\frac{1}{2}\|w\|^2 + C\sum_{i=1}^n\xi_i – \sum_{i=1}^n\alpha_i \left(y_i(w^Tx_i+b)-1+\xi_i\right) – \sum_{i=1}^n r_i\xi_i \\ \begin{align} \frac{\partial \mathcal{L}}{\partial w}=0 &\Rightarrow w=\sum_{i=1}^n \alpha_i y_i x_i \\ \frac{\partial \mathcal{L}}{\partial b} = 0 &\Rightarrow \sum_{i=1}^n \alpha_i y_i = 0 \\ \frac{\partial \mathcal{L}}{\partial \xi_i} = 0 &\Rightarrow C-\alpha_i-r_i=0, \quad i=1,\ldots,n \end{align}$$

将$w$带回$\mathcal{L}$并化简，得到和原来一样的目标函数：

$$\max_\alpha \sum_{i=1}^n\alpha_i – \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_j\langle x_i,x_j\rangle$$

不过，由于我们得到$C-\alpha_i-r_i=0$,而又有$r_i\geq 0$，因此有 $\alpha_i\leq C$，所以问题转化为

$$\begin{align} \max_\alpha &\sum_{i=1}^n\alpha_i – \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_j\langle x_i,x_j\rangle \\ s.t., &0\leq \alpha_i\leq C, i=1,\ldots,n \\ &\sum_{i=1}^n\alpha_iy_i = 0 \end{align}$$

对比硬间隔，唯一的区别就是多了$C$上界。