支持向量机

0.引言

本文主要参考了李航的《统计学习方法》。是本人学习支持向量机的学习笔记。
首先对支持向量机做简单介绍，然后分别介绍以下三个模型：
（1）线性可分支持向量机：又称为硬间隔支持向量机，通过硬间隔最大化来学习一个线性分类器。适合数据线性可分情况；
（2）线性支持向量机：又称为软间隔支持向量机，通过软间隔最大化来学习一个线性分类器。适合数据近似线性可分情况；
（3）非线性支持向量机：通过核技巧和软间隔最大化来学一个非线性分类器。适合数据非线性可分情况
本文将对三个模型的介绍，从原始问题导出对偶问题。得到对偶问题以后，通过SMO算法对模型参数进行求解。最后，如果有机会再介绍以下支持向量机模型参数是如何利用SMO算法学习和训练的。

1.线性可分支持向量机

1.1基本模型

两堆数据怎么样才是线性可分就不再赘述，否则请出门左拐百度“线性可分”。支持向量机学习的目的是找到一个将两类数据分离的超平面，这个超平面可以描述为：
w\cdot x+b=0
但实际上，我们通过给定的线性可分数据集能够拟合出来的模型为：
w^*\cdot x+b^*=0
其中带了星号的w^*和b^*是超平面模型的参数，表示是从数据集中学习得到的经验值或者说是估计值。与理论上的模型差别就在于这两个参数。如果数据足够多，那么经验值与理论值就近似相等了。

1.2函数间隔和几何间隔

为什么要引入间隔呢？为什么还有除了函数间隔之外还有个几何间隔？

间隔——追求分类的正确度和确信度

什么是间隔，间隔就是样本点与分离超平面之间的距离。支持向量机学习的目标就是将间隔最大化。
支持向量机在学习过程中最终目的是找到一个能将数据分离的超平面。但将数据分离完成后还不够完美，还需要使得这个分离超平面具有足够的正确性和确信度。
假设我们得到了一个超平面w\cdot x+b=0，如果有一个点x_p，则我们可以采用y(w\cdot x_p+b)来表示分类的正确性和确信度。y的正负取值描述正确性；|w\cdot x_p+b|的取值描述确信度。

函数间隔

我们用变量\hat{\gamma_i}来表示第i个样本与超平面之间的函数间隔描述式：
\hat{\gamma_i}=y_i(w \cdot x_i+b)
在定义和寻找超平面的时候就是在训练集T{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}中寻找最小的函数间隔，即:
\hat{\gamma}=\min_{i=1,...,N} \hat{\gamma}_i

几何间隔——对函数间隔加以约束

先不废话，直接给出几何间隔的描述式，然后再解释要引入几何间隔。免得看一堆字看的懵逼。
\gamma_i=y_i(\frac{w}{||w||} \cdot x_i+\frac{b}{||w||})
可以看到函数间隔和集合间隔相比，参数w和b的分母上多了个||w||，为什么要这样做呢？因为我们需要对参数w和b进行约束。如果不进行约束，求出来的超平面w\cdot x+b=0与不加约束是相同的（毕竟w和b前面的系数可以约掉），但w和b的实际可能会大个好几倍，会导致超平面的确信度|w\cdot x+b|变得十分不可靠。因此，我们对函数间隔加以约束，引入几何间隔的概念。
在定义和寻找超平面的时候就是在训练集T{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}中寻找最小的几何间隔，即:
\gamma_i=\min_{i=1,...,N}\gamma_i
函数间隔和几何间隔的关系：
\gamma=\frac{\hat{\gamma}}{||w||}

1.3线性可分支持向量机的描述——间隔最大化

支持向量机学习的目的是找到一个几何间隔最大的、能正确划分数据集T{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}的分离超平面。有目标，有约束，那么就可以表示为一个有约束的最优化问题,用几何间隔描述：
\begin{aligned} \max_{w,b} \ \ &\hat{\gamma} \\ s.t.\ \ & y_i(\frac{w}{||w||} \cdot x_i+\frac{b}{||w||}) \leqslant \gamma,\ \ i=1,2,...,N\\ \end{aligned}
用函数间隔描述：
\begin{aligned} \max_{w,b}\ \ & \frac{\hat{\gamma}}{||w||}\\ s.t.\ \ & y_i(w\cdot x+b) \leqslant \hat{\gamma}, \ \ i=1,2,...,N\\ \end{aligned}
为了方便转换为最优化问题，我们将约束项||w||保留的同时，对\frac{1}{||w||}积分得到\frac{1}{2}||w||^2，使得最大化\frac{1}{||w||}问题等价转换为最小化\frac{1}{2}||w||^2；令\hat{\gamma}=1; 利用两个数学技巧得到最终的最优化问题：
线性可分支持向量机最优化问题
\begin{aligned} \min_{w,b}\ & \ \frac{1}{2}||w||^2\\ s.t. \ & \ \ y_i(w\cdot x+b) -1 \leqslant 0,\ \ i=1,2,...,N\\ \end{aligned}
我们求出最优解w^*,b^*后，可以得到分离超平面：
w^*\cdot x+b^*=0
对新样本进行决策分类函数为：
f(x)=sign(w^*\cdot x+b^*)
决策分类函数的意思就是将新样本的特征值x带入式子w^*\cdot x+b^*中，根据得出正负取值来进行分类。
其中，sign函数：
sign(x)= \begin{cases} 0,& x<0\\ 1,& x>0\\ \end{cases}

1.4 从线性可分支持向量机的原始问题导出对偶问题

原始问题：线性可分支持向量机最优化问题
\begin{aligned} & \min_{w,b}\ \ \frac{1}{2}||w||^2\\ & s.t. \ \ \ y_i(w\cdot x+b) -1 \leqslant 0,\ \ i=1,2,...,N\\ \end{aligned}
为了导出它的对偶问题，我们构造一个拉格朗日函数：
L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^{N}\alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^{N}\alpha_i
根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题
\max_{\alpha}\min_{w,b}L(w,b,\alpha)
先求极小化问题，再求极大化问题。
(1)求极小化问题\min_{w,b}L(w,b,\alpha)：
将L(w,b,\alpha)对w和b求偏导并令其等于0
\begin{aligned} & \frac{\partial{L(w,b,\alpha)}}{\partial{{w}}}=w-\sum_{i=1}^{N}y_i\alpha_ix_i=0 \ \Rightarrow \ w=\sum_{i=1}^{N}y_i\alpha_ix_i\\ & \frac{\partial{L(w,b,\alpha)}}{\partial{{b}}}= -\sum_{i=1}^{N}y_i\alpha_i =0 \ \Rightarrow \ \sum_{i=1}^{N}y_i\alpha_i =0\\ \end{aligned}
将上面两个式子得出的结果代回到L(w,b,\alpha)：
\begin{aligned} L(w,b,\alpha) &=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}y_iy_j\alpha_i\alpha_jx_ix_j-\sum_{i=1}^{N}\alpha_iy_i\big[\sum_{j=1}^{N}y_j\alpha_jx_j\cdot x_i+b\big]+\sum_{i=1}^{N}\alpha_i\\ & =-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}y_iy_j\alpha_i\alpha_jx_ix_j+\sum_{i=1}^{N}\alpha_i\\ \end{aligned}
于是就求得：
\min_{w,b}L(w,b,\alpha)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}y_iy_j\alpha_i\alpha_jx_ix_j+\sum_{i=1}^{N}\alpha_i
(2)求极大化问题\max_{\alpha}\min_{w,b}L(w,b,\alpha)：
我们把上一步的结果带入第二步中，再加上约束条件可以得到：
\begin{aligned} \max_{\alpha}\min_{w,b}\ L(w,b,\alpha) & =\max_{\alpha}\ -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}y_iy_j\alpha_i\alpha_jx_ix_j+\sum_{i=1}^{N}\alpha_i\\ &s.t.\ \sum_{i=1}^{N}\alpha_iy_i=0\\ &\alpha_i \geqslant 0,\ \ \ i=1,...,N \end{aligned}
再把负号去掉，使得最大化问题等价转化为最小化问题
\begin{aligned} \min_{\alpha}\ \ \ &\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}y_iy_j\alpha_i\alpha_jx_ix_j+\sum_{i=1}^{N}\alpha_i\\ s.t.\ \ \ &\sum_{i=1}^{N}\alpha_iy_i=0\\ &\alpha_i \geqslant 0,\ \ \ i=1,...,N \end{aligned}
这样就得到了对偶问题的最优化问题，然后采用如SMO这种参数估计方法来对参数进行求解。
原始问题的解
假设我们求出了对偶最优化问题的解\alpha^*=(\alpha^*_1,...,\alpha^*_l)^T，则存在一个下标j使得\alpha^*_j \geqslant 0，我们就可以根据关系推导出原始最优化问题的解w^*,b^*(这是一个定理，证明请参考李航的《统计学习方法》):
\begin{aligned} \sum_{i=1}^{N}y_i\alpha_i =0 &\Rightarrow w^*=\sum_{i=1}^{N}\alpha_i^*y_ix_i\\ y_i(w\cdot x+b) -1 \leqslant 0& \Rightarrow b^*=y_i-\sum_{i=1}^{N}\alpha_i^*y_i(x_i\cdot x_j) \end{aligned}

2.线性支持向量机

2.1基本模型

正如本文开篇所说的，线性支持向量机用来解决近似线性可分的数据分类问题。我们在线性可分支持向量机的基础对数据集T{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}中的每一个样本都引入一个松弛变量\xi_i，并对目标函数引入一个惩罚项，改变原来的目标函数和约束条件，使得线性支持向量机的原始问题为：
\begin{aligned} \min_{w,b,\xi}\ \ &\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i\\ s.t.\ \ &y_i(w\cdot x_i+b) \geqslant 1-\xi_i,\ \ i=1,2,...,N\\ &\xi_i \geqslant 0,\ \ i=1,2,...,N\\ \end{aligned}

2.2从线性支持向量机的原始问题导出对偶问题

根据原始问题构造拉格朗日函数：
L(w,b,\xi,\alpha,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i-\sum_{i=1}^{N}\alpha_i\big[y_i(w\cdot x+b)-1+\xi_i\big]-\sum_{i=1}^{N}\mu_i\xi_i
根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题
\max_{\alpha}\min_{w,b,\xi}\ \ L(w,b,\xi,\alpha,\mu)
(1)求极小化问题\min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)
将L(w,b,\alpha)对w,b,\xi求偏导并令其等于0:
\begin{aligned} \frac{\partial L}{\partial w} &=w-\sum_{i=1}^{N}\alpha_iy_ix_i=0\ \Rightarrow w=\sum_{i=1}^{N}\alpha_iy_ix_i\\ \frac{\partial L}{\partial b}&=-\sum_{i=1}^{N}\ \alpha_iy_i=0 \ \Rightarrow \sum_{i=1}^{N}\ \alpha_i y_i=0\\ \frac{\partial L}{\partial \xi}&=C-\alpha_i-\mu_i=0,\ \Rightarrow C-\alpha_i-\mu_i=0 \end{aligned}
将上面的结果代回拉格朗日函数得到：
\begin{aligned} \min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)&=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jx_ix_j+C\sum_{i=1}^{N}\xi_i-\sum_{i=1}^{N}\alpha_i\big[y_i(\sum_{j=1}^{N}\alpha_jy_jx_j+b)-1+\xi_i\big]-\sum_{i=1}^{N}\mu_i\xi_i\\ &=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^{N}\xi_i(C-\alpha_i-\xi_i)+\sum_{i=1}^{N}\alpha_i\\ &=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^{N}\alpha_i\\ \end{aligned}
(2)求极大化问题\max_{\alpha}\min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)
通过上一步我们求解得到了极小化问题的表达式，接下来我们求解极大化问题：
\begin{aligned} \max_{\alpha} & \ \ -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^{N}\alpha_i\\ s.t.&\ \ \sum_{i=1}^{N}\alpha_iy_i=0\\ &\ \ C-\alpha_i-\mu_i=0\\ &\ \ \alpha_i \geqslant 0\\ &\ \ \mu_i \geqslant 0,\ \ i=1,2,...,N \end{aligned}
实际上，通过约束条件中的非零关系，可以进一步将约束条件简化为0\leqslant \alpha \leqslant C.我们可以得到最终的线性支持向量机的对偶最优化问题：
\begin{aligned} \max_{\alpha} & \ \ -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^{N}\alpha_i\\ s.t.&\ \ \sum_{i=1}^{N}\alpha_iy_i=0\\ &\ \ 0\leqslant \alpha \leqslant C,\ \ i=1,2,...,N\\ \end{aligned}
原始问题的解
原始问题的解与前面的线性可分支持向量机一样，假设我们求出了对偶最优化问题的解\alpha^*=(\alpha^*_1,...,\alpha^*_l)^T，则存在一个下标j使得0\leqslant \alpha^* \leqslant C，我们就可以根据关系推导出原始最优化问题的解w^*,b^*(这也是一个定理，证明请参考李航的《统计学习方法》):
\begin{aligned} \sum_{i=1}^{N}y_i\alpha_i =0 &\Rightarrow w^*=\sum_{i=1}^{N}\alpha_i^*y_ix_i\\ y_i(w\cdot x+b) -1+\xi_i\leqslant 0& \Rightarrow b^*=y_i-\sum_{i=1}^{N}\alpha_i^*y_i(x_i\cdot x_j) \end{aligned}
对新样本进行决策分类函数的对偶形式为：
f(x)=sign(\sum_{i=1}^{N}\alpha_i^*y_i(x_i\cdot x)+b^*)
决策分类函数的意思就是将新样本的特征值x带入式子w^*\cdot x+b^*中，根据得出正负取值来进行分类。
其中，sign函数：
sign(x)= \begin{cases} 0,& x<0\\ 1,& x>0\\ \end{cases}

3.非线性支持向量机

-------未完待续