支持向量机基本思想

在n维空间中，可以使用n-1维超平面（可用线性方程 $\mathbf{w^Tx}+b=0$ 来描述）来分类（将n维空间分为2部分），下图以二维空间为例：

图中带圆圈标记的政府样本为距离超平面最近的样本点，也称支持向量。用支持向量机分类时有以下约束条件：应尽量去找正负样本正中心的超平面，这样对样本扰动容忍性好。

机器学习方法到头来都是求解一个最优化问题（比如最小化训练误差），支持向量机也不例外，优化列示可表示为：

目标函数：最大化超平面到正负样本的间隔（$\max{2 \over{||\mathbf{w}||}}$，故可转化为最小化问题$\min{\frac{1}{2}||\mathbf{w}||^2}$）
约束条件：$y _ i(\mathbf{w}\mathbf{x} _ i+b)\ge 1$（样本到超平面距离大于等于1，取等于时为支持向量。$y _ i$为target，对于而分裂问题简化为[+1 -1]）
KKT条件：带约束的优化问题可以通过拉格朗日乘子法与KKT条件转化为对偶问题求解，原理可参考我爱智能。通过KKT条件，原优化目标转化为：
$$L(w,b,\alpha)=||\mathbf{w}||^2+\sum\limits _ {i=1}^{N}{\alpha _ i h _ i(x)}=||\mathbf{w}||^2-\sum\limits _ {i=1}^{N}{\alpha _ i {y _ i}(\mathbf{w}x+b)}-\sum\limits _ {i=1}^{N}{\alpha _ i}$$
令 $L(w,b,\alpha)$ 对 $w$ 和 $b$ 偏导为0得：
$$\frac{\partial{L}}{\partial{w}}=w-\sum\limits _ {i=1}^{N}{\alpha _ i{y _ i}{x _ i}}=0$$
$$\frac{\partial{L}}{\partial{b}}=-\sum\limits _ {i=1}^{N}{\alpha _ i{y _ i}}=0$$
带入$L(w,b,\alpha)$得：
$$L(w,b,\alpha)=\frac{1}{2}||\mathbf{w}||^2-\sum\limits _ {i=1}^{N}{\alpha _ i {y _ i}\mathbf{w}x _ i}-\sum\limits _ {i=1}^{N}{\alpha _ i {y _ i}b}-\sum\limits _ {i=1}^{N}{\alpha _ i}=\frac{1}{2}\mathbf{w}^T\sum\limits _ {i=1}^{N}{\alpha _ i {y _ i}x _ i}-\sum\limits _ {i=1}^{N}{\alpha _ i {y _ i}\mathbf{w}x _ i}+\sum\limits _ {i=1}^{N}{\alpha _ i}$$
$$=\frac{1}{2}\mathbf{w}^T\sum\limits _ {i=1}^{N}{\alpha _ i {y _ i}x _ i}-\sum\limits _ {i=1}^{N}{\alpha _ i {y _ i}\mathbf{w}x _ i}+\sum\limits _ {i=1}^{N}{\alpha _ i}=-\frac{1}{2}\mathbf{w}^T\sum\limits _ {i=1}^{N}{\alpha _ i {y _ i}x _ i}+\sum\limits _ {i=1}^{N}{\alpha _ i}$$
得到对偶问题：
$$\max W(\alpha)=\sum\limits _ {i=1}^{N}{\alpha _ i}-\frac{1}{2}(\sum\limits _ {i,j=1}^{N}{\alpha _ i{y _ i}{\alpha _ j}{y _ j}{\mathbf{x} _ i\mathbf{x} _ {j}^\mathbf{T}}})$$

$$s.t. \sum\limits _ {i=1}^{N}{\alpha _ i{y _ i}}=0$$

$$\alpha _ i{\ge}0$$
具体证明过程可参考我爱智能

核函数

上面描述的都是对于线性可分的情况，如果线性不可分，则可以使用核函数将样本从原始空间映射到高维空间。

核函数：
$$x \rightarrow \phi(x)$$
超平面为：
$$\mathbf{w}^T\phi(x)+b=0$$
对偶问题为：
$$\max W(\alpha)=\sum\limits _ {i=1}^{N}{\alpha _ i}-\frac{1}{2}(\sum\limits _ {i,j=1}^{N}{\alpha _ i{y _ i}{\alpha _ j}{y _ j}{\phi(x _ i)^\mathbf{T}\phi(x _ {j})}})$$

$$s.t. \sum\limits _ {i=1}^{N}{\alpha _ i{y _ i}}=0$$

$$\alpha _ i{\ge}0$$

$\phi(x _ i)^\mathbf{T}\phi(x _ {j})$为对应的高位空间内积，计算起来可能比较困难，于是希望有以下函数：$\kappa(x _ i,x _ j)=\phi(x _ i)^\mathbf{T}\phi(x _ {j})$，这样便不用计算高位空间的内积。

常用核函数

线性核函数

$$\kappa(x,x _ i) = x \cdot x _ i$$
线性核，主要用于线性可分的情况，我们可以看到特征空间到输入空间的维度是一样的，其参数少速度快。

多项式核函数

$$\kappa(x, x _ i) = ((x\cdot x _ i) + 1)^d$$
多项式核函数可以实现将低维的输入空间映射到高纬的特征空间，但是多项式核函数的参数多，计算较复杂。

高斯（RBF）核函数

$$\kappa(x, x _ i) = \exp(-\frac{||x - x _ i||^2}{2\delta^2})$$
高斯径向基函数是一种局部性强的核函数，其可以将一个样本映射到一个更高维的空间内，该核函数是应用最广的一个，无论大样本还是小样本都有比较好的性能，而且其相对于多项式核函数参数要少，因此大多数情况下在不知道用什么核函数的时候，优先使用高斯核函数。

sigmoid核函数

$$\kappa(x, x _ i) = tanh(\eta<x, x _ i> + \theta)$$
采用sigmoid核函数，支持向量机实现的就是一种多层神经网络。

核函数选用

可以从拟合效果与训练代价上去考虑。

处理异常点

在实际模型使用中，并不能一定找到一个合适的核函数使样本映射到高位空间线性可分，退一步说，即使找到这个核函数，也不能确保该核函数是否过拟合，因此SVM引入松弛变量( $\xi _ i\geq 0$ )这一概念，允许样本在一定程度上偏离超平面。加入松弛变量的约束条件变为：
$$y _ i(w^Tx _ i+b)\geq 1\color{red}{-\xi _ i}, \quad i=1,\ldots,n$$
目标函数加入损失项后变为：
$$\min \frac{1}{2}|w|^2\color{red}{+C\sum _ {i=1}^n \max(0,1-y _ i(w ^ T x _ i + b))}$$
其中$\sum _ {i=1}^n \max(0,1-y _ i(w ^ T x _ i + b))$称为为hinge损失。

考虑松弛变量后变为：
$$\min \frac{1}{2}|w|^2\color{red}{+C\sum _ {i=1}^n \xi _ i}$$
其中 $C$ 是一个参数，用于控制目标函数中两项（“寻找 margin 最大的超平面”和“保证数据点偏差量最小”）之间的权重。

转化为对偶规划问题：

$$\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(y _ i(w^Tx _ i+b)-1+\xi _ i)-\sum _ {i=1}^n r _ i\xi _ i$$

让 $\mathcal{L}$ 针对 $w$、$b$ 和 $\xi$ 偏导为0：

$$\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$$

将 $w$ 带回 $\mathcal{L}$ 并化简，优化问题可写为：
$$\max _ \alpha \sum _ {i=1}^n \alpha _ i-\color{red}{\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\color{red}{\leq C}, i=1,\ldots,n$$

$$\sum _ {i=1}^n\alpha _ iy _ i = 0$$

SMO

基本思想

SMO，Sequential Minimal Optimization：每次选取了两个坐标维度来进行优化，固定欲求的参数之外的所有参数。由于$\sum\limits _ {i=1}^{m}\alpha _ iy _ i = 0$。假如将$\alpha _ 3, \alpha _ 4, …, \alpha _ m$　固定，那么$\alpha _ 1, \alpha _ 2$变成一个一元二次函数，即$\alpha _ i y _ i \alpha _ j y _ j =c$，其中c为常数，此时 $α _ i$ 可以由$α _ j$和其他参数表示出来。这样回代入W中，W就只是关于$α _ j$的函数了，这时候对$α _ j$进行求导，令导数为0就可以解出这个时候最优的$α _ j$了。然后也可以得到$α _ i$。这就是一次的迭代过程，一次迭代只调整两个拉格朗日乘子$α _ i$和$α _ j$。

$α _ i$与$α _ j$的选择

使用贪心思想，每次选取最违反KTT条件的$α _ i$与$α _ j$。

停止条件

所有的样本都满足KKT条件，那么就表示迭代结束了。实际使用中，可设定一个KKT条件容许值，所用样本在容许值内即可停止迭代。

想了解更多，可参考：