数据挖掘——支持向量机 SVM 巩固

之前没怎么搞懂 SVM 算法的数学理论知识,比如求拉格朗日对偶这些,主要是硬件条件(智商)不够啊。所以这篇文章只是自己思路的一个记录,不会有很多的数学公式。

有新的进展后会更。

从以下方面进行笔记:

  • 支持向量机相关概念
  • 模型函数以及预测公式
  • 损失项
  • 损失函数和惩罚项
  • 硬间隔与软间隔
  • 隐藏的假设
  • 核函数
  • 总结

支持向量机相关概念

SVM

是一个二类分类模型,非常强大。

线性可分

两个类别能够被一条直线完美的分开,这样的数据就是线性可分的。

分离超平面

分离他们的直线叫做分离超平面(二维的可以交分离直线)。

一个数据点离分离直线的距离代表了模型对这一点预测结果的“自信程度”,称为「置信度」。

间隔

对于一条分离直线,定义它到某一类别的距离等于这个类别的所有点到这条直线的距离的最小值。

分离直线到每个类别的距离相等。

最大化分离直线到两个类别的距离之和,这个距离之和叫作「间隔」。

SVM 的目的就是最大化这个间隔。

支持向量

只有落在虚线上的或者两条虚线内的点,他的权重才有可能不等于 0。这样的点叫作「支持向量」。

模型函数以及预测公式

在线性可分的情况下:

1) 模型函数
$$
min\frac{1}{2}||w||^2
$$

$$
y_i(w \cdot X_i + c) \geq 1
$$

2) 预测公式
$$
\hat{y_i} = sign(\hat{w} \cdot X_i + \hat{c})
$$
$sign$ 表示当 $x > 0$ 时,$sign(x) = 1$;否则 $sign(x) = -1$。

损失项

生活中大多数情况下数据都不是完全线性可分的,不存在一个超平面使得不同类别的数据完全的分别落在平面的不同两侧。这种情况下需要加入损失项。
$$
y_i(w \cdot X_i + c) \geq 1 - \xi_i
$$
其中 $\xi_i$ 可以看作模型在数据i这一点违反自身分类原则的程度,也就是模型在这一点的损失。

所以它们的和 $\sum_i\xi_i$ 当然是越来越小,但是这个目标与模型本身的目标(最大化间隔)相矛盾,$\sum_i\xi_i$ 越来越小就会引起间隔变小;如果想间隔变大,那么 $\sum_i\xi_i$ 就会越来越大。

为了兼顾以上两个目标,改变公式,其中C > 0为模型的损失系数,是一个超参数。
$$
min\frac{1}{2}||w||^2 + C\sum_i\xi_i
$$

$$
y_i(w \cdot X_i + c) \geq 1 - \xi_i; \xi_i \geq 0
$$

损失函数与惩罚项

直接给出公式:
$$
L = \frac{1}{2}||w||^2 + C\sum_imax(0, 1 - y_i(w \cdot X_i + c))
$$
可以分为两个部分:

  • 模型的预测损失 $LL = \sum_imax(0, 1 - y_i(w \cdot X_i + c))$,学术上称这个函数为hinge loss。所以可以看出 SVM 的预测损失其实是由一个线性的损失函数外套一个非线性变换构成的。而这个非线性变化部分$f(x) = max(0 ,x)$就是所谓的线性整流函数(ReLU)。
  • 惩罚项 $\frac{1}{2}||w||^2$ 其实就是「L2 惩罚项」,它在其它模型中是为了防止出现过拟合问题,在 SVM 中是为了最大化间隔,但是某种程度上也防止了过拟合问题。并且它在 SVM 中是必不可少的。

硬间隔和软间隔

超参数C其实就是模型预测损失的权重,它的值很大表示模型更加在意分类“错误”的损失而轻视间隔的大小。

sklearn库中提供了 SVM 的两种实现方式:

  • sklearn.svm.SVC: 更加常用,可以方便的更换核函数
  • sklearn.svm.LinearSVC: 可以为线性 SVM 选择其他种类的损失函数和惩罚项

SVC中的C就是超参数C的意思。

现在来通过代码展示超参数C的影响

1
2
3
4
5
6
7
8
9
10
11
12
13
def hardSoftMargin(data):
"""
从小到大,用不同的损失系数训练模型
"""
C = []
res = []
for i in range(-1, 5):
C_ = 10 ** i
model = SVC(C=C_, kernel="linear")
model.fit(data[["x1", "x2"]], data['y'])
res.append(model)
C.append(C_)
visualize(data, C, res)

kernel="linear"表示使用的核函数是线性核函数,线性核函数表示没有做空间变换,对应着线性可分时

结果:

可以看到,随着C的增大,间隔会越来越小。

  • C比较小时,有很多点落在虚线之间,模型更注重的是靠近类别中心的数据点,这种叫做soft margin
  • C较小时,几乎没有点落在虚线之间,模型更注重的是靠近分离超平面的数据点,这种叫做hard margin

具体怎么确定这个C的大小可以有很多选择:工程化的,人为的。

隐藏的假设

每个数据点的权重不一样,越靠近分离超平面,数据的权重越大。

不同的模型对数据权重的隐含假设不一样,比如逻辑回归没有这种假设。如果希望模型对靠近分离超平面的点更加敏感,则推荐使用hard margin,如果需要综合的考虑每个点,则推荐使用soft margin或者逻辑回归。

拉格朗日对偶

通过拉格朗日对偶可以解决支持向量机的最优化问题。

等我磨透了再更这一部分

核函数

核函数是一种很重要的数据处理技巧,通过核函数,将原空间中非线性的数据映射到高维或者无限维空间中近线性的数据。然后再对数据使用线性模型分析。

不仅仅用于 SVM 中,也可以搭配其它模型。

空间变换

之前对于线性不可分的数据,使用了加入损失项的解决方案,但是这种方案对于那种完全线性不可分的数据,无法解决。这时候需要用到空间变换,将数据从非线性到线性。

具体为数学就是:

  • 假设原始数据为$\lbrace X_i, y_i \rbrace$ ,$X_i$ 是自变量,$y_i$ 是被预测量

  • 找到一个非线性的空间变换 $\phi$,将数据转换为 $\lbrace \phi(X_i), y_i \rbrace$。比如说 $X_i = (x_{1, i}, x_{2, i})$,那么可以是 $\phi(X_i) = (x^2_{1, i}, x^2_{2, i})$

  • 使用转换后的新数据训练模型,新的预测公式:
    $$
    \hat{y_i} = sign(w \cdot \phi(X_i) + c)
    $$

理论很完美,就是有了两个问题

  • 很难得到这个 $\phi$ 的具体表达式
  • 并且将数据映射到高维空间(相当于从原始数据提取更多特征)后,使用新数据训练模型,运算复杂度太高

核函数的定义:优化运算

有了核函数就可以很好的解决以上两个问题,但是核函数涉及到很多复杂的数学概念,比如「向量空间的内积」,「无限维向量空间」。

之前说借助一个非线性的空间变换 $\phi$,将数据转换为 $\lbrace \phi(X_i), y_i \rbrace$。但是 $\phi$ 非常难找,现在借助「对偶问题(就是没有搞懂的部分)」完成模型训练并不需要 $\phi$ 的具体表达式,只需要知道内积 $\phi(X_i) \cdot \phi(X_j)$。这就是所谓的核函数,记为 $K(X_i, X_j)$
$$
K(X_i, X_j) = \phi(X_i) \cdot \phi(X_j)
$$
举个例子:定义 $\phi(X_i) = (x_{1, i}^2, x_{2, i}^2, \sqrt2x_{1, i}x_{2, i})$,则可证明它的核函数如下:
$$
\phi(X_i) \cdot \phi(X_j) = x_{1, i}^2x_{1, j}^2 + x_{2, i}^2x_{2, j}^2 + 2x_{1, i}x_{2, i}x_{1, j}x_{2, j}
$$

$$
\phi(X_i) \cdot \phi(X_j) = (X_i \cdot X_j)^2 = K(X_i, X_j)
$$

优化:如果空间变换已知,那么使用核函数比直接计算向量内积更加高效。

现在就有了两个问题:

  • 不知道一个函数是否是核函数
  • 对于当前的数据,该选择哪个核函数

针对第一个问题,现在数学家们已经找到了一些适用于大多数场景的核函数;针对第二个问题,要取决于对问题的分析以及对核函数的理解。

常用的核函数

  • Linear kernel:没做任何空间变换
  • Polynomial kernel:多项式核函数
  • Sigmoid kernel:映射到无限维空间
  • Laplacian kernel:映射到无限维空间
  • RBF kernel :映射到无限维空间

具体的可以使用sklearn库完成这些调用。

Scale variant

SVM 对自变量的线性变换不稳定,自变量的线性变换(放大和缩小)都将极大的影响模型的效果。

这个时候需要将自变量做归一化处理,进而提升模型的预测效果。

总结

以上就是对 SVM 的学习整理,还有很关键的数学理论部分没有搞懂,所以还需要继续学习。