SVM 模型复习

最近根据周志华的《机器学习》复习了一下 SVM 算法,SVM 确实称得上机器学习的代表算法之一,把涉及的概念整理一下。

首先,从一个二分类器说起。SVM 实际上解决的是一个线性的模型,也就是说,假定存在这么一个表达式:

$$w^T x + b = 0$$

能够把数据恰到好处地分割为两部分。即对于样本点 $(x_i, y_i)$ ,有如下不等式成立

$$
\begin{cases}
w^T x_i + b \ge +1, & y_i=+1; \
w^T x_i + b \le -1, & y_i=-1;
\end{cases}
$$

当上述不等式的等号成立的时候,那些样本点 $(x_i, y_i)$ 称为支持向量。而分割平面到支持向量之间的距离为

$$
\gamma = \frac{2}{|| w||}
$$

所谓的“恰到好处”指的是使 $\gamma$ 最大的时候。

#损失函数

在得到了 SVM 的定义以后,可以归纳出 SVM 的优化目标将会分为两部分,即满足最大化分类间隔,以及在这个目的下约束所有分类点都应该满足分类表达式:

$$
\begin{align*}
& \max_{w,b} \quad \frac{2}{||w||} \
& \begin{array}{r@{\quad}r@{}@{\quad}} s.t. & y_i ( w^T x_i + b) \ge 1, & i=1,2,3 \end{array} .
\end{align*}
$$

上式是一个带约束的最优化问题,采用最优化理论的对偶解法。把优化式转换为

$$
L(w,b,\alpha) = \frac{1}{2}||w||^2 + \sum_{i=1}^m \alpha_i (1 - y_i (w^T x_i + b))
$$

即得到了 SVM 的损失函数

#软间隔以及正则化

但是现实世界里可能没有那么完美的分类平面,噪声的存在使得这个世界不是非黑即白。为了解决噪声,我们要允许数据犯错,则优化目标转化为

$$
\min_{w,b} \frac{1}{2}||w||^2 + C \sum_{i=1}^m \ell_{0/1}(y_i (w^T x_i + b) - 1)
$$

其中

$$
\ell_{0/1}(z) = \begin{cases} 1, & \text{if} \quad z > 0 \ 0, & \text{otherwise.} \end{cases}
$$

容易看出,当$C$ 趋近无穷大的时候,要求 $\mathcal{l}(z)=0$ 恒成立,否则将不能被优化,此时对犯错的风险降至 0 。反之, $C$ 越接近 0 则越容许分类器犯错。

然而,$\ell_{0/1}(z)$ 是一个分段函数,意味着该函数不能直接求导,因此,有很多函数试图替代这个函数,例如:

$$
\ell_{log}(z) = \log (1 + \exp(-z))
$$

当把上式替代 $\ell_{0/1}(z)$ 后,那么损失函数变为

$$
\begin{align*}
& \frac{1}{2}||w||^2 + C \sum_{i=1}^m \log(1 + \exp(1 - y_i (w^T x_i + b))) \
\rightarrow \quad & \sum_{i=1}^m \log(1 + \exp(1 - y_i (w^T x_i + b))) + C \frac{1}{2}||w||^2
\end{align*}
$$

看着是不是很像逻辑回归?比逻辑回归多的部分,就是多加了个 $w$ 项。在逻辑回归里,也可以做类似的优化,称为正则化项,依据就是当参数越少,泛化能力越好。当然,在 SVM 中,实际上就是软间隔的最大化了。由此,两个看起来不相关的模型在这里巧合地相互解释。

#结构风险与经验风险

从结构和经验两部分来看,把上述损失函数分拆,可以得到如下两部分:

$$
\underbrace{\frac{1}{2} ||w||^2} _ {结构风险} + \overbrace{C \sum_{i=1}^m \ell(y_i(w^T x_i + b) - 1)}^{经验风险}
$$

每一个机器学习的目标函数可能都会包括这两部分,即结构风险和经验风险。这两者在 SVM 上表现得尤为显著。其中,第一部分结构风险,就形象地表达了 SVM 模型的平面结构,它的最小化偏向使得分类平面向着支持向量间隔最大的方向发展。而经验风险在引入软间隔的时候就说明了,就是是否允许数据犯错,对数据噪声的容忍程度。换句话说,以多大的程度信任给定的数据。

但是为什么说是风险呢?数据挖掘的场景下,原始数据是“肮脏”的,不真实的。数据有一些偶然和随机的成分,即使是今天所谓的大数据场景下,获得的数据也是不全面的。由于仪器的误差,有些数据可能存在一些噪声,使得不是该类的样本被测得在该类下,如果一味拟合过去的数据就会误导未来的预测。这就是所谓经验风险。另一方面,模型越复杂对数据的解释能力就越强,例如二次函数生成的数据可以被四次甚至更高次的模型解释,但是两者却不会再所有点上重合。显然,二次模型产生的点应该用二次模型来解读,模型过于复杂,反而出现所谓过度解读的问题,对未出现过的点解释错误。这就是所谓的结构风险。

#核函数方法

核函数是 SVM 中的一个重要优化手段,但其他分类器也可能实现核函数的优化。核方法说的是把样本的特征提升到一定的维度上,使得在当前维不可分的点在高维空间下可分。但是 SVM 中的核函数却不是指通过该函数提升到高维空间,而是算法实现上的一个细节。

注意到损失函数中,

$$
w = \sum_{i=1}^m \alpha_i y_i x_i^T
$$

也就是说,求得的分类平面是

$$
\sum_{i=1}^m \alpha_i y_i x_i^T x + b
$$

如果通过函数 $\phi(x)$ 把 $x$ 提升到一个新的高维空间,那么,分类平面将变为

$$
\sum_{i=1}^m \alpha_i y_i \phi(x_i)^T \phi(x) + b
$$

实际上需要计算的是 $\phi(x_i)^T\phi(x)$ 而不是 $\phi(x)$,因此,核函数就是说

$$
\kappa(x, y)=\phi(x)^T \phi(y)
$$

的过程,而非把样本特征向量转换到高维的函数。