SVM理解

SVM概念

SVM(Support Vector Machine)支持向量机,它是一个二分类模型.也存在变体的SVM模型,可用于处理多分类问题

SVM擅长于处理样本数少于特征维度数的情况,应该也适用于小样本学习

从二维空间举例来说,我们存在两个点集$D_1$和$D_2$,它们是线性可分的,即可以通过一条直线将其进行完全划分.这是二维空间的情况.推广至n维空间,即存在一个超平面hyperplane可以对该特征空间下的点集进行划分

那么很明显,这样的超平面存在无数多个,于二维空间而言,我们可以找多无数多条直线来对点集进行划分.SVM所期望的超平面是最大间隔超平面

最大间隔超平面,即距离超平面最近的点的距离最大化.这些离超平面最近的点被称作支持向量

之所以以最大间隔作为期望条件,是因其:间隔越大,两个需要区分的类别差异性更大,更容易做区分

间隔的表达式

以二维空间为例,假设我们已经找到了可以将两个点集进行划分的分割线,这条分割线的超平面方程式为$w_1x_1+w_2x_2+b=0$,根据上面的概念,我们可以通过将该直线上下分别移动$C$以恰好经过一些最近的样本点(即支持向量),来找到对应的间隔上下边界,二者的式子可表示为$w_1x_1+w_2x_2+b=\pm{C}$

我们可以对间隔边界的式子进行变形以取得下式:$w_1x_1+w_2x_2+b=\pm{1}$,我们将这三个式子如下称呼:

$\begin{cases}\begin{aligned} w_1x_1+w_2x_2&=1 \quad &\text{正超平面} \\ w_1x_1+w_2x_2&=0 \quad &\text{决策超平面} \\ w_1x_1+w_2x_2&=-1 \quad &\text{负超平面} \end{aligned}\end{cases}$

若点代入式子,有:$w_1x_1+w_2x_2\ge1$,则其为正类;
若点代入式子,有:$w_1x_1+w_2x_2\le-1$,则其为负类

我们可以根据向量投影来求得间隔$L$的值,也可以通过线线距离来求得$L$的值

根据上图将m,n两点代入正负超平面,做差,而后投影,可得$L=\frac{2}{\Vert \vec{w} \Vert}$,我们欲求得$\max L$,可以转换成求其倒数的最小值,而由于对向量求范式含根号,故对其平方以去根号,因此我们的优化目标转为:$\min f(w) = \frac{1}{2}\Vert \vec{w^2} \Vert$

拉格朗日乘数法

面对存在一个或多个约束条件下,我们想求得目标函数的极值,可以使用拉格朗日乘数法
而在此题中,我们欲求得$f(w)$的最小值,则可以通过拉格朗日乘数法来求解
首先明确,我们的约束条件是:

$g_i(w,b) = y_i * (\vec{w}\vec{x_i} + b) \ge 1 \quad\quad (i=1,2,\cdots,s)$

其中$y_i$代表的是分类值,为1则为正类,为-1则为负类,$\vec{w}\vec{x}+b$则是超平面的表达式(其所处的维度空间由向量维度确定),约束条件表明正负类点集都应分布在正负超平面两侧(亦可恰好分布在正负超平面上)

对于拉格朗日乘数法,它所处理的是等式约束条件,而我们这里是不等式约束条件,可通过增加松弛变量来使得其转化为等式的约束条件,可变换成如下形式:

$g_i(w,b,p_i) = y_i * (\vec{w}\vec{x_i} + b) -1 = {p_i}^2 \quad\quad (i=1,2,\cdots,s)$

此时可以通过构造拉格朗日函数来处理极值问题,构造的函数如下:

$\begin{aligned} L(w,b,\lambda_i,p_i) &= f(w) - \sum_{i=1}^{s}\lambda_ig_i(w,b,p_i) \\ &= \frac{\Vert \vec{w^2} \Vert}{2} - \sum_{i=1}^{s}\lambda_i * (y_i * (\vec{w}\vec{x_i} + b) -1 - {p_i}^2) \quad\quad (i=1,2,\cdots,s) \end{aligned}$

此时我们可以知道,若$\lambda_i$的值为负数,则无法起到罚值作用(相关意义可以见后面软间隔部分),因此其取值应为:$\lambda_i \ge 0$

需注意,根据拉格朗日乘数法,我们需要对目标函数,拉格朗日算子以及松弛变量求偏导,且零其值为0,因此,得下式:

$\begin{cases} \Vert \vec{w} \Vert - \sum_{i=1}^{s}\lambda_i * y_i * \vec{x_i} = 0 \\ - \sum_{i=1}^{s}\lambda_i * y_i = 0 \\ y_i * (\vec{w}\vec{x_i} + b) - 1 - {p_i}^2 = 0 \\ 2\lambda_ip_i = 0 \end{cases}$

联立后两个式子(消去${p_i}^2$),我们会发现有:$\lambda_ig_i(w,b)=0$这一公式,其只有以下两种情况:

1. $\lambda_i=0,g_i(w,b)\neq0$,此刻约束条件非零,则意味着点并非落在正负超平面上,非极值,此刻$\lambda_i$必须为0;
2. $\lambda_i\neq0,g_i(w,b)=0$,此刻点落在正负超平面上,$\lambda_i$可以不为零

因此,对公式重整,我们有:

$\begin{cases} \Vert \vec{w} \Vert - \sum_{i=1}^{s}\lambda_i * y_i * \vec{x_i} = 0 \\ - \sum_{i=1}^{s}\lambda_i * y_i = 0 \\ g_i(w,b) \ge 0 \\ \lambda_i * g_i(w,b) = 0 \\ \lambda_i \ge 0 \end{cases}$

观察可知,此式现已满足KKT条件,即可对其进行求解

强对偶

为了效率及后续操作中使用kernel trick,我们可以利用强对偶性对其进行处理
暂时没看懂,后面再补

软间隔

我们知道并不是所有点都可以满足$g_i(w,b) \ge 1$,有些点会出现在我们的margin里面,那么这时候我们要么缩短margin以满足所有点都在margin两侧(hard margin),要么根据误差做罚值
根据margin的定义,margin越大越说明二者差异,越易分类.因此,不可轻易缩短margin,我们要容许部分点落在margin内,因此是对二者做的一个平衡

我们可以将罚值公式记作如下:$\epsilon_i = 1 - y_i * (\vec{w} + \vec{x_i} + b)$

因此,我们所求的$\min \frac{\Vert \vec{w^2} \Vert}{2}$需要与不同点的罚值寻找一个平衡,构建出以下公式:

$\min \frac{\Vert \vec{w^2} \Vert}{2} + \sum_{i=1}^{s}\epsilon_i$

使用以上公式,以达总体最优,再根据之前的构造出拉格朗日乘数法进行计算即可

核技巧中的核函数

我们在低维空间可能无法对点集进行线性划分,则我们可以通过将其映射到高维来处理,但映射到高维存在计算量过大的问题,而我们在通过强队偶计算的过程中发现,可以利用其中$x_ix_j$的性质来利用核函数.即:
以下是两个核函数公式:

$\text{多项式核函数} K_d(\vec{x_i},\vec{x_j}) = {(c + \vec{x_i} * \vec{x_j})}^d \\ \text{高斯核函数} K(\vec{x_i},\vec{x_j}) = e^{-\gamma {\Vert \vec{x_i}-\vec{x_j} \Vert}^2}$