【机器学习】 15. SVM 支撑向量机 support vector machine，拉格朗日，软边界，核函数

SVM 支撑向量机 support vector machine，拉格朗日，软边界，核函数

• 1. 超平面边界 margin of hyperplane
• 2. 边界越大的超平面越好
• • 原因
• 3. 线性模型通过决策边界分类
• 4. SVM的问题
• 5. 拉格朗日乘子与SVM结合求最大边界
• 6. SVM软边界和硬边界
• 7. 非线性 SVM
• • 核方法 kernal trick
  • • 一些有效的核方法（符合默瑟定理）
• 8. sklearn 中的C

1. 超平面边界 margin of hyperplane

• 超平面中找决策边界，有很多。
• 支持向量是靠近决策边界的例子；删除它们将改变决策边界。
• 边缘(margin)：边界和最接近的例子之间的距离。
• 边界在边缘(margin)的中间。

2. 边界越大的超平面越好

• 具有最大边缘的超平面称为最大边缘超平面。
• 它是到训练示例的距离最大的超平面。
• SVM选择最大边缘超平面。

原因

• 如果边界很小，那么超平面或训练例子在边界上的任何轻微变化都更有可能影响分类，因为允许数据扰动的空间非常小。
• 小边界更容易过度拟合
• 另一方面，如果差距很大，就有更多的余地对数据的微小变化保持稳健。
• 可能有更好的泛化性能。
• 从统计学习理论也有理由，结构风险最小化原则。

3. 线性模型通过决策边界分类

如果x在决策边界之上：wx +b > 0 class1
如果x在决策边界以下：wx +b < 0 class2

$$sign(w\ast x+b)$$

4. SVM的问题

H1: wx +b =1 （2,3 也可以）
H2: wx +b = -1
设于H1和H2上的点为支持向量

• 根据w的方向决定H1和H2，跟w一样方向的是1
• d = 2 / ||w|| d为H的边际
• 对于任意一个样本点, 它到超平面的垂直距离为
  $$\frac{|w\ast x+b|}{||w||}$$
  代入H1-H2求两个点之间距离得到d
• 为了最大化边际d，我们需要最小化||w||
  • 这等价于最小化二次函数
    $$\frac{1}{2}||w|{|}^2$$

5. 拉格朗日乘子与SVM结合求最大边界

拉格朗日乘子法的基本原理是通过引入拉格朗日乘子(λ)将原来的约束优化问题转化为无约束的方程组问题。拉格朗日乘子法的求解过程大致分为以下步骤：

1、原问题描述：求解函数z=f(x, y)在条件φ(x, y)=0条件下的极值。

2、构造函数：F(x, y, λ) = f(x, y) + λ · φ(x, y)， 其中λ为拉格朗日乘子。

3、构造函数求偏导，列出方程组。

4、求出x, y, λ的值， 代入即可得到目标函数的极值。

我们可以使用拉格朗日乘数法将约束条件结合到目标函数中, 构造如下:
$$L(w,b,\lambda )=\frac{1}{2}||w|{|}^2-\sum _{i=1}^N{\lambda }_i[y_i(w\ast x_i+b)-1]$$
对w 和 b进行求偏导
得到
$$w=\sum _{i=1}^N{\lambda }_i{y}_i{x}_i$$
$$\sum _{i=1}^N{\lambda }_i{y}_i=0$$
代入之后得到
$$maxL(w,b,\lambda )=\sum _{i=1}^N{\lambda }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\lambda }_i{\lambda }_j{y}_i{y}_j{x}_i.x_j$$
这个公式的最大解得到最终的拉格朗日乘数λ，可以使用QP技术等。
得到λ之后就可以计算出w。
λ_i > 0 的点是支撑向量。
假设有多个样本，其中两个样本的λ大于0，其他样本都是0，那么这两个就是支撑向量。根据λ代入w的公式中，得到各自的w

6. SVM软边界和硬边界

软边际=允许在正超平面和负超平面之间存在一些样本点.

边际的距离上B1远胜B2, 但是B1中正负超平面之间存在两个错误分类的样本点。
一般情况下, 边际的距离更重要, 因为大的边际距离能够让模型更少受噪音干扰, 防止过拟合.

在硬边际分类问题中, 我们要最小化
$$||w||$$
而在软边界中，增加了一个参数C
$$||w||+C\sum {\xi }_i$$
ξ是每个样本的额外允许的误差当C变大的时候, 会使得更加注重减小分类错误, 而不是增加边际距离.

• 当C为无穷大时，为了保证目标函数取得最小值，需要要求ξ=0,即所有样本严格满足硬间隔约束条件；
• 当C取有限值时，允许部分样本不满足约束条件。

7. 非线性 SVM

解决了线形不可分的问题，数据的特征空间转换:当数据在其原始特征空间中不是线性可分的时，我们可以考虑将其转换到⼀个新的特征空间中，这样在新的空间⾥数据可能会变得线性可分。⾮线性转换到更⾼维度:通过⾮线性变换，我们可以将数据映射到⼀个更⾼的维度。在这个更⾼维度的空间中，数据有更⼤的可能性是线性可分的。想象⼀下，⼀组在⼆维平⾯上不可分的数据点，可能在三维空间中可以被⼀个平⾯完美地分隔。

• 将数据从其原始特征空间转换为一个新的空间，线性边界可以用来分离数据

• 如果转换是非线性的，并向更高的维度空间，它更有可能比线性的决策边界可以在其中找到。

• 在新特征空间中学习到的线性决策边界被映射回原始特征空间，导致原始空间中的非线性决策边界

核方法 kernal trick

能够直接计算⾼维空间中两个数据点的点积，⽽⽆需显式地将数据点映射到那个⾼维空间。

通过使⽤核函数，绕过在⾼维空间中进⾏显式计算的需求，从⽽有效地处理⾮线性问题，

避免了⾼维度带来的计算复杂性。在⽀持向量机（SVM）中，这种技巧尤为关键，因为SVM的⼯作原理是基于数据点之间的点积。

使⽤核技巧，我们可以直接计算这些点积，从⽽实现⾮线性分类，⽽不需要在⾼维空间中处理数据。

简⽽⾔之，核技巧的核⼼是利⽤核函数来“欺骗”算法，使其“认为”它在⾼维空间中⼯作，⽽实际上我们只是在原始空间中计算点积。这使得计算更加⾼效和实⽤。

1. 映射关系: 当我们想将数据从原始空间转移到⼀个⾼维空间时，通常需要定义⼀个映射函数（例如ϕ(x)这个映射函数的作⽤是将数据点从原始特征空间映射到⼀个更⾼的维度。
2. ⾼维空间中的计算: 在⾼维空间中，我们可能需要计算两个映射后的数据点的点积，即ϕ(xi)ϕ(xj) 。直接进⾏这样的计算可能会⾮常耗时，特别是当映射到的维度⾮常⾼时。
3. 核函数的作⽤: 核函数 的作⽤就是直接计算⾼维空间中的点积，⽆需显式地计算映射 。这意味着我们可以得到⾼维空间中的点积值，但不需要明确地执⾏映射过程,最终提⾼计算效率
   $$\varphi (u)\ast \varphi (v)=(u\ast v{)}^2$$
   以上这个公式简要概括了核函数的作用，不需要计算高维空间的映射ϕ，而是直接用核函数算出高维空间点积。

一些有效的核方法（符合默瑟定理）

Mercer定理：一个核函数K(u,v)如果满足特定条件, 那么这个核函数一定对应着某一个映射函数

8. sklearn 中的C

通过上述讲解，在sklearn中掉包的时候，C已经有了清晰的认知。
超参数C控制模型对误分类点的惩罚强度

• 当C很小的时候, 允许更多的点被误分类, 因此决策边界更加平滑, 接近线性, 适用于防止过拟合, 我们可以看左上角的图, 边界基本上是线性的了;
• 当C很大的时候, 模型更加关注误分类的点, 导致决策边界弯曲, 以捕捉到更多的细节, 如果数据复杂, 模型可能会过拟合。
  所以，过拟合的时候应该减小C，欠拟合的时候应该再增加C