SVM理论知识

拉格朗日对偶性

Primal

如果有如下优化问题：

$\begin{split} &min \quad f(w)\\ &s.t.\begin{cases} g_i(w)\le 0\\ h_i(w)=0 \end{cases} \end{split}$

我们可以相应的构造它的拉格朗日函数：

$L(w,\alpha,\beta)=f(w)+\sum_{i=1}^k\alpha_ig_i(w)+\sum_{i=1}^l\beta_ih_i(w)$

定义

$\theta_p(w)=max_{\alpha,\beta} \quad L(w,\alpha,\beta),\quad \alpha_i,\beta_i\ge0$

注意$\theta_p(w)$是对$L(w,\alpha,\beta)中\alpha与\beta$的优化。
如果存在$w$使得其不满足约束条件，则$\theta_p(w)$的值即为$+\infty$（因为如果存在某个$g_i(w)>0或h_i(w)\neq0$，则令$\alpha_i\rightarrow\infty或\beta_i\rightarrow\infty $，即可得到$L的最大值$）。
如果$w$都符合约束条件，则$\theta_p(w)$的值即为$f(w)$（后两项为负值，若$\alpha_i=0且\beta_i=0 $，即为$f(w)$）。

所以我们原先求取的目标函数即可变为：

$min_{w} \quad\theta_p(w)=min_{w} \quad max \ L(w,\alpha,\beta),\quad \alpha_i,\beta_i\ge0$

定义原始问题（Primal）的最优值为：

$P^*=min_{w} \quad\theta_p(w)$

Dual

定义

$\theta_D(\alpha,\beta)=min_{w} \quad L(w,\alpha,\beta),\quad \alpha_i,\beta_i\ge0$

注意$\theta_D(\alpha,\beta)$是对$L(w,\alpha,\beta)中w$的优化。

而极大化$\theta_D(\alpha,\beta)$，即为：

$max_{\alpha,\beta}\quad\theta_D(\alpha,\beta)=max_{\alpha,\beta} \quad min \ L(w,\alpha,\beta),\quad \alpha_i,\beta_i\ge0$

定义对偶问题（Dual）的最优值为：

$D^*=max_{\alpha,\beta} \quad\theta_D(\alpha,\beta)$

Primal与Daul的关系

对于原始问题与对偶问题求解得到的最优值$P^,D^$，它们有如下关系：

$P^*=min_{w} \quad\theta_p(w)\le max_{\alpha,\beta} \quad\theta_D(\alpha,\beta)=D^*$

而它们只有KKT条件下是相等的，即$P^=D^$。那么我们便可以通过求解Dual问题来求解Primal问题。

同时满足原问题与对偶问题的最优解$w^,\alpha^,\beta^$满足的*KKT条件如下：

$\begin{split} &\nabla_wL(w^*,\alpha^*,\beta^*)=0\\ &\alpha_i^*g_i(w^*)=0\\ &g_i(w^*)\le0\\ &\alpha^*\ge0 \end{split}$

通过KKT条件，我们可以求解最优解。其第二个条件需着重观察，可以发现，若数据带入$g_i(w)$中，若其不为0，则说明$\alpha_i=0$。

线性可分的SVM

在一个二维平面上，有两种类型的数据，如下图所示

我们可以很容易找到一条线将它们分开，并且这种线是有很多的。

而支持向量（support vector）的定义即是：存在一条线到a数据边界的distance与到b数据边界的distance是相同的，这条线便是支持向量决策线。

找到的支持向量便是SVM算法得到的最优解。

将两条边界上的线的距离定义为margin，而SVM则希望找一个最大的margin，所以SVM还有另外一个名字：max margin classifier。

假设现在有两个support vector，如图所示：

我们将用数学公式，对两个支持向量的距离进行推导

设边界上的两条线分别为：

$\begin{cases} w^Tx_1+b=1\\ w^Tx_2+b=-1 \end{cases}$

将两式相减便可得到：

$w^T(x_1-x_2)=2$

而$w^T$与$(x_1-x_2)$都为向量，故它们相乘实际上是做内积

故可得：

$\Vert w\Vert_2\Vert x_1-x_2\Vert_2\cos\theta=2$

则便可得：

$d_1+d_2=\Vert x_1-x_2\Vert_2\cos\theta=\frac{2}{\Vert w\Vert_2}\\ d_1=d_2=\frac{1}{2}\Vert x_1-x_2\Vert_2\cos\theta=\frac{1}{\Vert w\Vert_2}$

上面提到SVM的目标就是max-margin，而$margin=\frac{2}{\Vert w\Vert_2}$，故可以得到SVM的数学模型：

$\begin{split} &min \quad \frac{1}{2}\Vert w\Vert^2\\ &s.t. \quad y^{(i)}(wx^{i}+b)\geqslant1 \end{split}$

上面的目标函数并不难理解，对原距离求其分母的最小值，便是求远距离的最大值。

而约束条件的意思即：有这样的一个vector $w$与bias $b$，对空间中任意一点$x^i$，带入$wx+b$中，再乘以$y^{i}$（数据的标签，可为1或-1），都是大于等于1的。我理解的意思便是：数据都被较好的分类，即1类数据都在1类的平面里，-1类的数据都在-1类的平面里。

我们可以将上式改写为如下形式：

$g_i(w,b)=-y^{(i)}(wx^{i}+b)+1\leqslant0$

将其拉格朗日化可得：

$L(w,b,\alpha)=\frac{1}{2}\Vert w\Vert^2-\sum_{i=1}^n\alpha_i[y^{(i)}(wx^{i}+b)-1]$

则由KKT条件可得：

$\begin{cases} \nabla_wL=w-\sum_{i=1}^n\alpha_iy^{(i)}x^i=0\\ \nabla_bL=-\sum_{i=1}^n\alpha_iy^{(i)}=0 \end{cases}$

带入原式可得：

$L(\alpha)=\sum_i^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^ny^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)}$

上述经过KKT条件的带入，已对$w,b$进行了优化，得到的$L(\alpha)$即上文Dual问题中的$\theta_D$。而现在便可将其转换为Dual问题：

$\begin{split} &max \quad L(\alpha)=\sum_i^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^ny^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)}\\ &s.t.\begin{cases} \alpha_i\geq0\\ \sum_{i=1}^n\alpha_iy^{(i)}=0 \end{cases} \end{split}$

通过构造Dual问题，进行求解得到$\alpha$的值。

而SVM的决策子如下：

$w^Tx+b=(\sum_{i=1}^n\alpha_iy^{(i)}x^i)^Tx+b=\sum_{i=1}^n\alpha_iy^{(i)}\lang x^i,x\rang+b$

因为$\alpha_iy^{(i)}$为常数，故$(x^i)^Tx=\lang x^i,x\rang$做内积。

但这样可以发现，当输入值$x$时，需要与所有的训练数据进行内积并求和。如果数据过大，则每次输入$x$时，太过花费时间与内存。

但为什么SVM会很流行呢？因为根据KKT条件，我们会发现这个规则：

$\alpha_i^*g_i(w^*)=0$

而在这里$g_i(w,b)=-y^{(i)}(wx^{i}+b)+1\leqslant0$

也就是说，如果$g_i(w)$带入的数据$(x^i,y^{(i)})$并不等于0，那么其对应的$\alpha_i=0$。而事实上较多的训练数据带入约束函数中并不等0，故其相应的$\alpha_i$等于0，于是SVM决策子便会大大简单。当输入$x$后，也并不会与以往所有的数据做一次内积求和。事实上真正保留下来的$\alpha_i$为数据正好为支持向量，其所对应的$\alpha_i$。

带松弛变量的SVM

上文为标准的支持向量机模型。但在实际情况中，其往往会出现一些问题。

当我们的数据有一些异常值的时候，如下所示：

如果按照SVM标准模型，则支持向量决策线为图中的虚线，但我们可以看出，蓝色点有一个异常值，如果不管那个异常值，则支持向量决策线应为上图中的蓝色线。

而对于这种情况，我们可以通过放松限制来解决：

以下为带松弛变量的SVM模型：

$\mbox{Primal问题:}\begin{split} &min \quad \frac{1}{2}\Vert w\Vert^2+C\sum_{i=1}^n\zeta_i\\ &s.t. \begin{cases} y^{(i)}(wx^{i}+b)\geqslant1-\zeta_i, \ i=1,2,\dots,n\\ \zeta_i\ge0 \end{cases} \end{split}$

可以发现，引入的$\zeta_i$即为松弛变量，这样我们可以使异常值也可以满足限制条件。但我们不能使$\zeta_i$过大，因为这样的话限制条件便没有作用了，于是我们在目标函数中加入$C\sum_{i=1}^n\zeta_i$，以使它放松并不能太大。而参数$C$是需要我们自己进行调参的，通过调节$C$，可以控制$\zeta_i$的大小。

而其Dual问题为：

$\begin{split} &max \quad L(\alpha)=\sum_i^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^ny^{(i)}y^{(j)}\alpha_i\alpha_j\lang x^{(i)},x^{(j)}\rang\\ &s.t.\begin{cases} 0\leq\alpha_i\leq C\\ \sum_{i=1}^n\alpha_iy^{(i)}=0 \end{cases} \end{split}$

在这里$y^{(i)}y^{(j)}$为不同数据的标签，可以发现如果类别相同，则其为正数，而类别不同，则其为负数。所以类别相同，其值增加；类别不同，其值减少。而对于$\lang x^{(i)},x^{(j)}\rang$，则是两个数据作内积，其衡量两个数据之间的相似性。

对于$\sum_{i=1}^n\alpha_iy^{(i)}=0$而言，其表示不同数据点的权重是不相同的，即每个数据的看重程度是不同的。由于$y^{(i)}$的取值为-1或1，则为使其和为0，则不同类别的数据其权重应该是相同的。

而KKT条件也发生了一些变化：

而除了用上述最小化问题或Dual问题来理解，我们也可以用Hinge Loss来理解。

Hinge Loss(合页损失函数)

根据上述最小化问题的约束，

$y^{(i)}(wx^{i}+b)\geqslant1-\zeta_i, \ i=1,2,\dots,n\\ \zeta_i\ge0$

可以得到：

$\zeta_i\geqslant1-y^{(i)}(wx^{i}+b)\\ \zeta_i\geq0$

则以上两个式子即为：

$\zeta_i= max(0,1-y^{(i)}(wx^i+b))$

而化成这样的好处是，它是一个可求导的函数，这样我们便可使用SGD进行优化，利用PyTorch的Auto grading进行自动求梯度。

带kernel的SVM

使用核函数：

$\begin{split} &max \quad L(\alpha)=\sum_i^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^ny^{(i)}y^{(j)}\alpha_i\alpha_jk(x^{(i)},x^{(j)})\\ &s.t.\begin{cases} 0\leq\alpha_i\leq C\\ \sum_{i=1}^n\alpha_iy^{(i)}=0 \end{cases} \end{split}$

对于上节的SVM模型，其改变的地方仅从目标函数由$\lang x^{(i)},x^{(j)}\rang$变为$k(x^{(i)},x^{(j)})$，其中$k(x^{(i)},x^{(j)})$即称为核函数。

核函数定义如下：

$K(x^i,x^j)=\lang \varPhi(x^i),\varPhi(x^j)\rang$

其做了两步操作：

首先使用$\varPhi(x)$函数对数据进行高维投影
然后对其求内积

这里要说明的是，使用kernel函数与只内积，它们所求得的$\alpha$都是相同的。也是因为这样，使用kernel trick才是有意义的。

而使用核函数后，其预测公式为：

$w^T\varPhi(x)+b=\sum_{i=1}^n\alpha_iy^{(i)}k(x^i,x)+b$

只有当$x_i$为支持向量的时候，$\alpha_i>0$。

为什么使用核函数

那么我们为什么要使用核函数呢?观察下图

对于上图中的数据，其使用传统的SVM模型是无法进行分类的。而使用核函数的原因就是处理线性不可分。

那么kernel为什么可以处理线性不可分呢?

当一维数据$x$经过函数$\varPhi(x)$处理后，数据升维。之前线性不可分的数据经过升维后就可以线性可分了。

例如输入数据有两个feature$[x_{i1},x_{i2}]$，经过升维后，它就变为$[x_{i1},x_{i2},x_{i1}x_{i2},x_{i1}^2,x_{i2}^2]$，可以发现其feature是变多了。

那么既然通过升维可以使线性不可分变为线性可分，那所有的数据我们都来升维？但如果当一条数据的feature特别多时，升维后，其feature将变得非常多，可能不利于我们计算。（计算量与数据量和每一条数据的维度呈正相关）

成为kernel的条件

即由kernel形成的矩阵$G_{ij}$，其需要满足两个条件：

为对称矩阵
为半正定矩阵，$z^TGz\geq 0,z\in R^n$。

常用的kernel

多项式核（Polynomial Kernel）

$K(x_i,x_j)=(\lang x_i,x_j\rang+c)^d$

$c\ge0$控制低阶项的强度
特殊情况，当$c=0,d=1$成为线性核（Linear kernel），相当于无核SVM一样。

下面可以通过一个例子来理解：

这里的polynomial kernel中$c=0,d=2$。

高斯核（Gaussian Kernel或Radial Basis Function-RBF Kernel）

$K(x_i,x_j)=exp(-\frac{\| x_i-x_j\|_2^2}{2\sigma^2})$

当$x_i$=$x_j$时，其值为1。当$x_i$与$x_j$的距离增加，其值倾向于0。但当使用高斯核之前需要将其特征做标准化。因为不同特征之间其值变化范围可能不一样。

下面是随着$\sigma^2$值的变化，高斯核的变化。

下面看一个高斯核的例子：

Sigmoid Kernel

$K(x_i,x_j)=\tanh (\beta x_i^Tx_j+c)$

tanh为双曲正切函数，由$\sinh=\frac{e^x-e^{-x}}{2}$与$\cosh=\frac{e^x+e^{-x}}{2}$得到，即为$\frac{e^x-e^{-x}}{e^x+e^{-x}}$。

Cosine Similarly Kernel

$K(x_i,x_j)=\frac{x_i^Tx_j}{\|x_i\|_2\|x_j\|_2}$

常用于衡量两段文字的相似性。
相当于衡量两个向量的余弦相似度（向量夹角的余弦值）

Chi Squared Kernel

$K(x_i,x_j)=\frac{x_i^Tx_j}{\|x_i+x_j\|_{L1}}$

常用于计算机视觉
衡量两个概率分布的相似性
输入数据必须是非负的，且必须使用L1归一化。

其中L1归一化公式为：
$y_i=\frac{x_i}{\sum_{i=1}^nx_i}$
L2归一化公式为：
$y_i=\frac{x_i}{\sqrt{\sum_{i=1}^nx_i^2}}$

SMO算法

对于已经建立好的SVM数学模型：

我们一般采用SMO算法对其求解，SMO算法一般有下面两个步骤：

重复直到收敛：
1. 选择下一步需要优化的$\alpha_i$与$\alpha_j$，使用启发式的方式优化$\alpha_i$与$\alpha_j$，使目标函数向着最大值的进发最快。
2. 保持其他的$\alpha$值不变，仅仅通过一次改变一组$\alpha_i$与$\alpha_j$来优化$L(\alpha)$。（为什么SMO一次需要选择两个参数进行优化？因为如果每次只选择一个参数进行优化，固定其他参数。那么它会不满足数学模型的第二条约束条件。
使用KKT条件判断是否收敛。

我们可以通过以下例子来理解：