机器学习7-支持向量机

2022-06-29 本文已影响0人只是甲

一. SVM模型的基本概念

1.1 从线性判别说起

image.png

如果需要构建一个分类器将上图中的黄点与蓝点分开，最简单的方法就是在平面中选择一条直线将二者分开，使得所有的黄点与蓝点分属直线的两侧。这样的直线有无穷多种选择，但是什么样的直线是最优的呢？

显而易见的是，中间的红色的分割线的效果会比蓝色虚线与绿色虚线的效果好。原因是，需要分类的样本点普遍距离红线比较远，因而健壮性更强。相反，蓝色虚线与绿色虚线分别距离几个样本点很近，从而在加入新的样本点后，很容易发生错误分类。

1.2 支持向量机(SVM)的基本概念

点到超平面的距离
在上述的分类任务中，为了获取稳健的线性分类器，一个很自然的想法是，找出一条分割线使得两侧样本与该分割线的平均距离足够的远。在欧式空间中，定义一个点𝒙到直线（或者高维空间中的超平面） $𝒘^𝑇 𝒙+𝑏=0$ 的距离公式是：
$𝑟(𝑥)= (|𝒘^𝑇 𝒙+𝑏|)/(||𝒘||)$
在分类问题中，如果这样的分割线或者分割平面能够准确地将样本分开，对于样本 ${𝒙_𝑖,𝑦_𝑖}∈𝐷, 𝑦_𝑖=±1$ 而言，若 $𝑦_𝑖=1$ ，则有 $𝒘^𝑇 𝒙_𝒊+𝑏≥1$ ，反之若 $𝑦_𝑖=-1$ ，则有 $𝒘^𝑇 𝒙_𝒊+𝑏≤−1.$

支持向量与间隔
对于满足 $𝒘^𝑇 𝒙_𝒊+𝑏=±1$ 的样本，它们一定落在2个超平面上。这些样本被称为“支持向量（support vector）”，这2个超平面称为最大间隔边界。分属不同类别的样本距离分割平面的距离之和为
$𝛾=2/(|\|𝑤||)$
该距离之和被称为“间隔”

image.png

二. SVM的目标函数和对偶问题

2.1 支持向量机的优化问题

因此，对于完全线性可分的样本，分类模型的任务就是找出这样的超平面，满足

image.png

等价于求解带约束的最小化问题：

image.png

2.2 优化问题的对偶问题

一般来说，求解带等式或不等式约束的优化问题时，通常使用拉格朗日乘子法将原问题转换成对偶问题。在SVM的优化问题中，相应的对偶问题为：

image.png

对𝐿(𝑤,𝑏,𝛼)求关于𝑤,𝑏,𝛼的偏导数并且令为0，有：

image.png

最终的优化问题转化成

image.png

解出𝛼后，求出𝑤,𝑏即可得到模型。一般使用SMO算法求解。

2.3 支持向量与非支持向量

注意到， $𝑦_𝑖 (𝒘^𝑇 𝒙_𝒊+𝑏)≥ 1$ 是不等式约束，因此 $𝛼_𝑖$ 需要满足 $𝛼_𝑖 (𝑦_𝑖 (𝒘^𝑇 𝒙_𝒊+𝑏)−1)=0$ （这是KKT条件中关于不等式约束的条件）。因此，满足这样的条件的样本 ${𝒙_𝒊,y_i}$ ，要么 $𝛼_𝑖=0$ , 要么 $𝑦_𝑖 (𝒘^𝑇 𝒙_𝒊+𝑏)−1$ 。因此对于SVM的训练样本来讲，
如果 $𝛼_𝑖=0$ ，则 $∑〖𝛼_𝑖−1/2 ∑∑𝛼_𝑖 𝛼_𝑗 𝑦_𝑖 𝑦_𝑗 𝒙_𝑖^𝑇 𝒙_𝒋$ 的计算中不会出现该样本
如果 $𝑦_𝑖 (𝒘^𝑇 𝒙_𝒊+𝑏)−1$ ，则该样本处于最大间隔边界上
从这一点可以看出，大部分训练样本最后都不会对模型的求解有任何影响，仅支持向量影响到模型的求解。

三. 软间隔

3.1 线性不可分

在一般的业务场景中，线性可分是可遇而不可求的。更多是线性不可分的情形，即无法找出这样的超平面可以完全正确地将两类样本分开。
为了解决这个问题，一个方法是我们允许部分样本被错误的分类（但是不能太多！）。带有错误分类的间隔，称之为“软间隔”。于是，目标函数仍然是带约束的最大化间隔，其中约束条件是，不满足 $𝑦_𝑖 (𝒘^𝑇 𝒙_𝒊+𝑏)≥ 1$ 的样本越少越好。

image.png

3.2 损失函数

基于这个思想，我们改写了优化函数

image.png

使其变为

image.png

可用的损失函数有:

image.png

3.3 松弛变量

当使用hinge loss的时候，损失函数变为

image.png

3.4 求解带松弛变量的软间隔SVM

令𝐿(𝑤,𝑏,𝛼,𝜂,𝜇)关于𝑤,𝑏, 𝜂的偏导等于0，则有：

image.png

3.5 支持向量与非支持向量

同样地，拉格朗日乘子也需满足 $𝛼_𝑖 (1−𝑦_𝑖 (𝒘^𝑇 𝒙_𝒊+𝑏)−𝜉_𝑖 )=0$ 和 $𝜇_𝑖 𝜉_𝑖=0$ 的条件。对于某样本 ${𝑥_𝑖,𝑦_𝑖}$ ,
当 $𝛼_𝑖=0$ 时，样本不会对模型有任何影响
当 $〖0<𝛼〗_𝑖<𝐶时，𝜇_𝑖>0,$ 此时有 $𝜉_𝑖=0$ ，该样本落在最大间隔边界上
当 $𝛼_𝑖=𝐶$ 时， $𝜇_𝑖=0$ 。此时若有 $𝜉_𝑖≤1$ ，该样本落在最大间隔内部，属于正确分类的情况；若有 $𝜉_𝑖>1$ ，该样本落在最大间隔之间，属于错误分类的情况。
表明在hinge loss的情况下，带软间隔的SVM模型仍然只与支持向量有关。

四. 核函数

4.1 从低维到高维

在SVM的优化目标函数 $∑𝛼_𝑖−1/2 ∑∑𝛼_𝑖 𝛼_𝑗 𝑦_𝑖 𝑦_𝑗 𝒙_𝑖^𝑇 𝒙_𝒋$ 中， ${𝛼_𝑖}$ 是参数， ${𝑦_𝑖}$ 是类别，二者的形式是固定的。但是交互项 $𝒙_𝑖^𝑇 𝒙_𝒋$ 是独立的，我们完全可以讲其进行拓展。注意到我们有两种拓展的办法：
拓展一： $𝒙_𝒋→𝝍(𝒙_𝒋)$ , 此时目标函数变为 $∑𝛼_𝑖−1/2 ∑∑𝛼_𝑖 𝛼_𝑗 𝑦_𝑖 𝑦_𝑗 𝝍(𝑥_𝑖 )^𝑇 𝝍(𝒙_𝒋)$
拓展二： $𝒙_𝑖^𝑇 𝒙_𝒋→𝝍(𝒙_𝒊,𝒙_𝒋)$ ,此时目标函数变为 $∑𝛼_𝑖−1/2 ∑∑𝛼_𝑖 𝛼_𝑗 𝑦_𝑖 𝑦_𝑗 𝝍(𝒙_𝒊,𝒙_𝒋)$
拓展一能够将𝑥映射到更高维的空间，从而将在低维不可分的情形变为在高维空间可分。这是除了软间隔之外，另一种解决线性不可分的办法。