稀疏核机:支持向量机

支持向量机的想法是,从正确分类中找到最好的那个。同时,由于支持向量机由于其样本的稀疏性和采用了核函数,因此又被称为稀疏核机。大部分文献表示,在朴素分类器中,支持向量机有最好的分类效果(神经网络需要设计架构)。

1.函数间隔和几何间隔

回想一下感知机的判别函数:

我们将

一个二分类问题的类别定义为$y \in \{ 1, -1 \}$。显然,我们能得出以下结论:

对于分类问题,我们当然希望分类正确的样本越多越好,这样就得出了感知机的损失函数:

但是这样的效果并不好,原因在于这个损失函数同等看待各个样本点。例如,有两个样本点A、B,其中$y_A(\omega ^\top x_A + b) = 1000$, $y_B(\omega ^\top x_B + b) = 0.1$;在这种情况下,$loss = 1000.1$看起来结果好像很好,然而真的是这样的吗?

对于分类问题,相较于99%的置信度的样本,我们更关注那些置信度在50%附近的样本。因为如果一个样本有99%的置信度,那么这个样本基本上不会被误判;但是对于那些在分类边界线游离的样本而言,很有可能就会被误判。因此,我们要减少这类样本的数量,最大化最靠近分类边界线的样本的置信度。将这个目标写作优化函数:

其中,$\hat \gamma_i$被称为函数间隔

但是,我们又发现了问题。我们对感知机的判别函数乘以一个正常数:

显然,$\omega ^\top x + b$的符号不受影响,分类结果也不受影响,这个过程只是把这个分类超平面进行了缩放。但是,函数间隔受到了影响。显然,当$N > 1$时,$ \min Ny(\omega ^\top x + b) > \min y(\omega ^\top x + b)$,函数间隔变大了。这就不好办了,因为我们下一步要最大化函数间隔,如果不解决这个问题,对于任意一个超平面,我们不需要修改超平面方程,只需要简单的在前面乘以一个非常大的$N$,就可以使得函数间隔变大。而乘以正常数的操作不会对分类结果产生影响,因此以最大化函数间隔作为优化目标无法收敛。

那怎么办呢?很简单,我们所需要关注的不是超平面的大小,而是超平面的方向,我们只需要对超平面的参数取模就可以了:

其中,$\gamma_i$被称为几何间隔。为什么称为几何间隔呢?因为这个函数正好表示样本点到分类超平面的几何距离。

Figure 1

2.硬间隔支持向量机

假设:

我们写出最大化几何间隔的优化函数:

由于分类超平面的缩放并不影响分类结果,所以不失一般性($w.l.o.g.$),我们假设:

即最小的几何间隔假设为1,这样优化函数就可以写成:

其中:

所以,优化函数为:

显然,优化函数是一个凸函数,这是一个二次规划问题(QP问题)。在样本不多且维度不高的情况下,可以求出解析解。但是如果样本数量大且维度高的情况下,求解析解通常是不可能的,于是我们采用对偶解法。

拉格朗日对偶性(Lagrange duality):

我们先写出拉格朗日函数:

通常假设$\lambda\geq 0$,发现有如下性质:

于是原优化问题可以转变为:

求解这个优化问题一般考虑采用求解该问题的对偶问题

所有对偶问题都满足弱对偶性:

其中一种理解方法是所有最小值中的最大值,要小于所有最大值中的最小值。鹤群再矮也比鸡高,哈哈哈。

我们希望这两个凸二次优化问题形成强对偶关系,即:

这时候就需要满足KKT条件

现在求解对偶问题$ \max_\lambda \min_{\omega,b} \cal{L}(\omega,b,\lambda)$:

$\min_{\omega,b} \cal{L}(\omega,b,\lambda)$部分的求解:

带入$\cal{L}(\omega,b,\lambda)$得:

则:

带入$\cal{L}(\omega,b,\lambda):$

其中$x_i$是一个$vetor$,$y_i$是一个数,因此$(x_iy_i)^\top = y_i^\top x_i^\top = y_i x_i ^\top$。

这样,我们的优化问题就变成了:

这就支持向量机的优化形式。

求解:

注意KKT条件中的松弛互补条件:$\lambda_i(1-y_i(\omega^\top x_i + b)) = 0$,这里只有两种可能:$\lambda_i = 0$或者$1-y_i(\omega^\top x_i + b)=0$。若$\lambda_i = 0$,那么优化函数就直接等于0了,因此$\lambda_i \neq 0$且$ 1-y_i(\omega^\top x_i + b) = 0$。满足$ 1-y_i(\omega^\top x_i + b) = 0$的点处于几何间隔上。意思就是,只有处于几何间隔上的点才对模型有影响,其他点对模型没有影响。整个模型参数是由极少数处于几何间隔上的样本点所支撑起来的,这些点被称为支持向量(Support Vector)。由于支持向量机只由少部分样本确定参数,因此支持向量机具有$稀疏性$。

Figure 2

现在通过松弛互补条件求解$b:$

上面已经得到了:$\hat \omega = \sum_{i=1} ^N \lambda_i y_i x_i$,带入得:

只需要将$\omega$和$b$带入分类超平面方程$f(x) = sign(\omega^\top x + b)$即可。

3.软间隔支持向量机

采用$f(x) = sign(\omega^\top x + b)$这样硬间隔的分类超平面会使得模型的容错性不高。由于样本存在随机噪声,总会有一些处于分类超平面附近的样本被错误分类。如果我们要求把所有样本都分类正确,模型往往会过拟合。所以,我们希望模型能包容一点点错误:

Figure 3

很自然的,我们希望定义损失为:分类正确的样本没有损失,分类错误的样本离几何间隔越远,损失越大。我们引入合页损失函数(hinge loss function):

Figure 4

于是:

令$1-y_i(\omega^\top x_i + b)= \xi_i \ge 0$,则优化函数为:

对偶优化函数为:

4.核方法

支持向量机的分类超平面是线性的。对于非线性超平面,通常做法是采用核函数$\kappa(x_1,x_2) = \phi(x_1)^\top \phi(x_2)$将样本的内积映射入高维空间。

采用核方法后的支持向量机的优化函数为:

参考文献

  1. 《统计学习方法》李航
  2. Pattern Recognition and Machine Learning
  3. CS229 Lecture notes 3

评论