SVM理论推导

本文介绍支持向量机（SVM）的理论推导。

一、SVM 的基本思想

SVM 的目标是找到一个最优超平面，将样本分为不同的类别，并最大化类别间的间隔。

1. 线性可分情况下：

在特征空间中找到一个超平面，使得：

• 样本之间的分类间隔（margin）最大。
• 分类误差最小。

超平面可以表示为：
$$w^{T}x+b=0$$
其中：

• w 是法向量，决定了超平面的方向。
• b 是偏置，决定了超平面到原点的距离。

对于任意样本$(x_i,y_i)$，其中 $y_i$ ∈{−1,1} 表示类别标签，超平面需要满足：
$$y_i(w^T{x}_i+b)\ge 1$$

1. 优化目标：

最大化间隔（margin）等价于最小化 $\frac{1}{2}\Vert \vec{w}{\Vert }^2$:
$$\underset{w,b}{\min }\frac{1}{2}\Vert \vec{w}{\Vert }^2$$
约束条件：
$$y_i(w^T{x}_i+b)>1,i=1,2,\dots ,n$$

二、线性不可分情况

在实际问题中，数据通常线性不可分，此时需要引入：

1. 松弛变量 ${\xi }_i$：

• 允许部分样本点违反约束条件。
• 目标函数变为：
  $$\underset{w,b,\xi }{\min }\frac{1}{2}\Vert \vec{w}{\Vert }^2+C\sum _{i=1}^n{\xi }_i$$
  其中 C 是惩罚参数，控制误差与间隔的权衡。

2. 核函数：

• 将低维数据映射到高维特征空间，使其线性可分。
• 核函数定义为：
  $$K(x_i,x_j)=\varphi (x_i)\cdot \varphi (x_j)$$
  常用核函数包括：
• 线性核：$K(x_i,x_j)=x_i\cdot x_j$
• 多项式核：$K(x_i,x_j)=(x_i\cdot x_j+c{)}^d$
• 高斯核（RBF 核）：$K(x_i,x_j)=exp(-\Vert x_i-x_j{\Vert }^2/(2{\sigma }^2))$
• Sigmoid 核：$K(x_i,x_j)=tanh(\alpha x_i\cdot x_j+c)$

三、SVM 的优化过程

SVM 的优化问题通常通过 拉格朗日对偶问题 解决：

1. 原始问题：

$$\begin{array}{rlrl}\underset{w,b,\xi }{\min }& \frac{1}{2}\Vert \vec{w}{\Vert }^2+C\sum _{i=1}^n{\xi }_i& & \\ s.t& y_i(w^T{x}_i+b)\ge 1-{\xi }_i,& {\xi }_i\ge 0,& i=1,2,\dots ,n\end{array}$$

实际上，引入核函数后，优化问题需要用 $\varphi (x_i)$ 代替约束条件中的 $x_i$,即原始问题变为如下：
$$\begin{array}{rl}\underset{w,b,\xi }{\min }& \frac{1}{2}\Vert \vec{w}{\Vert }^2+C\sum _{i=1}^n{\xi }_i\\ s.t& y_i(w^T\varphi (x_i)+b)\ge 1-{\xi }_i\\ & {\xi }_i\ge 0\end{array}$$

变换一下约束条件的符号，可以得到等价的标准型：
$$\begin{array}{rlr}\underset{\omega ,b,\xi }{\min }& \frac{1}{2}\Vert \vec{\omega }{\Vert }^2-C\sum _{i=1}^n{\xi }_i& \\ s.t& 1+{\xi }_i-y_i{\omega }^T\varphi (x_i)-y_{i}b\le 0& \\ & {\xi }_i\le 0,& i=1,2,\dots ,n\end{array}\text{\hspace{1em}(1)}$$

由于我们往往不知道$\varphi (x_i)$的显示表达，因此我们需要想办法把优化问题转换为没有$\varphi (x_i)$ 的等价问题，因此就引入了对偶问题。
注意：该优化问题强对偶成立，即原始问题的最优解 $p^{\ast }$ 等于对偶问题的 $d^{\ast }$。

2. 对偶问题：

将约束条件引入优化目标，得到对偶形式：
$$\begin{array}{rl}\underset{\alpha }{\max }& \sum _{i=1}^n{\alpha }_i-\frac{1}{2}\cdot \sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)\\ s.t& 0\le {\alpha }_i\le C,\sum _{i=1}^n{\alpha }_i{y}_i=0\end{array}\text{\hspace{1em}(2)}$$
其中 ${\alpha }_i$是拉格朗日乘子。

3. 优化算法：

对偶问题通常通过 SMO（序列最小优化） 或其他数值方法求解。

补充：对偶函数推导：

式（1）的拉格朗日函数为：
$$\begin{array}{rl}L(\omega ,\alpha ,\beta )=& \frac{1}{2}\Vert \vec{w}{\Vert }^2-C\sum _{i=1}^n{\xi }_i+\sum _{i=1}^n{\alpha }_i(1+{\xi }_i-y_i{\omega }^T\varphi (x_i)-y_{i}b)\\ & +\sum _{i=1}^n{\beta }_i{\xi }_i\end{array}\text{\hspace{1em}(3)}$$

在给定 $\alpha ,\beta$ 对偶函数的值，实质上就是对于多有$(\omega ,{\xi }_i,b)$ 求最小值。即对偶问题为：
$$\begin{array}{rl}\underset{\alpha ,\beta }{\max }& \theta (\alpha ,\beta )=\underset{\omega ,{\xi }_i,b}{\inf }L(\omega ,\alpha ,\beta )\\ s.t& {\alpha }_i\ge 0,{\beta }_i\ge 0,i=1,2,\dots ,n\end{array}\text{\hspace{1em}(4)}$$

其中 $inf$ 是极小化的意思。
注意：该问题没有等式约束，这里的${\alpha }_i,{\beta }_i$ 都是原始优化问题的不等式约束的拉格朗日乘子。

为了求得拉格朗日函数（式子3）的最小值，需要在对应变量求一阶偏导等于0 即可，可得：
$$\begin{array}{rl}\frac{\partial L}{\partial \omega }=0& \Rightarrow \omega =\sum _{i=1}^n{\alpha }_i{y}_i\varphi (x_i)\\ \frac{\partial L}{\partial {\xi }_i}=0& \Rightarrow {\alpha }_i+{\beta }_i=C\\ \frac{\partial L}{\partial b}=0& \Rightarrow \sum _{i=1}^n{\alpha }_i{y}_i=0\end{array}$$

可得：
$$\begin{array}{rl}\frac{1}{2}\Vert \vec{w}{\Vert }^2& =\frac{1}{2}{\omega }^T\omega \\ & =\frac{1}{2}(\sum _{i=1}^n{\alpha }_i{y}_i\varphi (x_i){)}^T(\sum _{j=1}^n{\alpha }_j{y}_j\varphi (x_j))\\ & =\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j\varphi (x_i{)}^T\varphi (x_j)\end{array}$$

又有：
$$\begin{array}{rl}-\sum _{i=1}^n{\alpha }_i{y}_i{\omega }^T\varphi (x_i)& =-\sum _{i=1}^n{\alpha }_i{y}_i(\sum _{j=1}^n{\alpha }_j{y}_j\varphi (x_j){)}^T\varphi (x_i)\\ & =-\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j\varphi (x_j{)}^T\varphi (x_i)\end{array}$$

注意红色部分可以用核函数 $K(x_i,x_j)$ 替换。（妙啊）

带入到式子（4）中，得：
$$\theta (\alpha ,\beta )=\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)$$

即推导出了对偶问题的目标函数式子（2）。

四、求解

对偶问题通常通过 SMO（序列最小优化） 或其他数值方法求解。

到这里思考一个问题：
我们的目标是求分割平面的 $\omega ,b$ ，但是求对偶问题得到的是 $\alpha$, 这要怎么办？

目前已经有对偶问题得到了其解 $\alpha$, 我们又有
$$\omega =\sum _{i=1}^n{\alpha }_i{y}_i\varphi (x_i)$$
是否可以推出 $\omega$ 呢？ 答案是否定的，因为这里又出现了一个 $\varphi (x_i)$，大前提是我们并不知道$\varphi (x_i)$ 的具体显示表达。

测试流程（a）

测试样本 $x$ 输入，有

• 若 ${\omega }^T\varphi (x)+b\ge 0$ 则 y = +1 ,属于第一类，或正例；
• 若 ${\omega }^T\varphi (x)+b<0$ 则 y = -1, 属于第二类，或负例；

对于实际场景，我们并不需要具体的 $\omega$, 如果知道 ${\omega }^T\varphi (x)+b$ 也是可以的，这样就跳过了具体的$\varphi (x)$。

那么我们继续看，上述中我们已经求得了 $\omega$的表达式， 带入可得：
$$\begin{array}{rl}{\omega }^T\varphi (x)& =(\sum _{i=1}^n{\alpha }_i{y}_i\varphi (x_i))\varphi (x)\\ & =\sum _{i=1}^n{\alpha }_i{y}_i\varphi (x_i)\varphi (x)\\ & =\sum _{i=1}^n{\alpha }_i{y}_{i}K(x_i,x)\end{array}$$

问题又来了，${\omega }^T\varphi (x)+b$ 中的 b 怎么得到？

我们继续看，回到对偶问题上，对偶问题的解一定满足 KKT 条件，而 KKT 条件中的互补松弛 条件：
$$\sum _{i=1}^n{\lambda }_i{f}_i=0,\lambda \ge 0,f_i\le 0$$

对应本示例（结合式子3）表明：
对于 $\forall i=1,2,\dots ,n$

1. 要么 ${\alpha }_i=0$，要么 $1+{\xi }_i-y_i{\omega }^T\varphi (x_i)-y_{i}b=0$
2. 要么 ${\beta }_i=0$，要么 ${\xi }_i=0$

那么我们可以取一个${\alpha }_i$ 满足 $0<{\alpha }_i<C$，则 ${\beta }_i=C-{\alpha }_i>0$，此时有:
$${\beta }_i=C-{\alpha }_i>0\Rightarrow {\xi }_i=0$$
同样的：
$${\alpha }_i\ne 0\Rightarrow 1+{\xi }_i-y_i{\omega }^T\varphi (x_i)-y_{i}b=0$$

可以得到 b 的表达式为：
$$\begin{array}{rl}b& =\frac{1-y_i{\omega }^T\varphi (x_i)}{y_i}\\ & =\frac{1-y_i\sum _{j=1}^n{\alpha }_j{y}_{j}K(x_j,x_i)}{y_i}\end{array}$$

至此 b 就算出来了。实际中可以把所有的 满足 $0<{\alpha }_i<C$ 中的 ${\alpha }_i$, 按照上面方法求出对应的 b, 然后求平均。

测试流程（b）

有了上面的推论，我们可以得到最终的测试流程：

输入测试样本 $x$,

• 若 $\sum _{i=1}^n{\alpha }_i{y}_{i}K(x_i,x)+b\ge 0$，则 y = +1
• 若 $\sum _{i=1}^n{\alpha }_i{y}_{i}K(x_i,x)+b<0$，则 y = -1

总结：整个算法学习过程和测试流程都无需知道 $\varphi (x)$, 只需要知道 $K(x_i,x_j)$ 就可以完成。

（至此，结束）