ML学习笔记(一.一)

SVM基础2

Posted by QIY on September 24, 2020

Machine Learning 的学习需稳扎稳打

#引言

  • 什么是SVM?SVM干嘛用? SVM是什么:(Support Vectors)支持向量机;

SVM干嘛: 通过寻找最优超平面函数,对数据二分类

支持向量(Support Vectors):划分数据并且两平面之间没有数据点,该两平面(后续记H1/H2)上的数据点集

最优超平面:H1/H2间距离最大化,中间平面函数。

本章主要内容:

1几何推导

  • 目的:寻找最大间隔就是寻找最优超平面
  • 思路(线性可分情况)
    • 1)读取你的数据集。
    • 2)找到两个平行超平面,可以划分数据并且两平面之间没有数据点
    • 3)最大化上述两个超平面间隔
  • 结果:约束条件为,𝑦𝑖(𝐰,𝐱-.−𝑏)≥1(对于𝑖=1,…,𝑛),的情况下找到‖w‖最小的w,𝑏, 不等式约束的最小化问题。

    1.1 步骤1

    读取数据集 数据D集 是n个元素 对组成的集合。yi代表元素属于类(-1)或类(+1)。

    1.2 步骤2

    找到两个平行超平面,可以划分数据并 且两平面之间没有数据点 超平面H0划分数据集并且满足: H1: H2: 这里等比例,我们索性让 等于1,它们之间没有任何的数据点。我们只选择那些符合以下两个约束的超平面: 可化简:𝑦(𝐰⋅𝐱𝐢−𝑏)≥1for all1≤𝑖≤𝑛。

    1.3步骤3

    两个超平面之间的距离最大化 H0/H1间隔m,向量k方向为w,即: ,z0=x0+k 。z0在H1上,带入H1有:w(x0+k)+b=1. 最大化间隔也就是: 约束条件为,𝑦𝑖(𝐰,𝐱-.−𝑏)≥1(对于𝑖=1,…,𝑛)的情况下找到‖w‖最小的w,𝑏, 不等式约束的最小化问题。

    2.优化方法

    这种式子通常我们用拉格朗日乘数法来求解,即: f(x)是我们需要最小化的目标函数,g(x)是不等式约束条件,即前面的 , α 是对应的约束系数,也叫拉格朗日乘子。为了使得拉格朗日函数得到最优化解,我们需要加入能使该函数有最优化解法的KKT条件,或者叫最优化条件、充要条件。 以上的KKT条件 表示,只有距离最优超平面的支持向量(xi,yi)对应的α非零,其他所有点集的α等于零。综上所述,引入拉格朗日乘子以后,我们的目标变为: 即先求得α的极大值,再求w和b的极小值。 对偶法: 即先求得w和b的极小值,在求α的极大值。用L(w,b,α)对ww和b分别求偏导,并令其等于0: 得: 把该式代入原来的的拉格朗日式子可得(推导过程省略): 通过SMO方法求a,后求w,b。

    3 非线性可分

    现实世界的许多问题并不都是线性可分的,尤其存在许多复杂的非线性可分的情形。 要解决这些不可分问题,一般有两种方法。第一种是放宽过于严格的间隔,构造软间隔。另一种是运用核函数把这些数据映射到另一个维度空间去解决非线性问题。

    3.1 软间隔

    同样拉格朗日,对偶,kkt条件得: 可以看到,松驰变量ξi没有出现在W(α)中,线性可分与不可分的差异体现在约束αi⩾0被替换成了约束0⩽αi⩽C。但是,这两种情况下求解ww和bb是非常相似的,对于支持向量的定义也都是一致的。
    在不可分情况下,对应的KKT条件为:

    3.2 核方法

    核函数能够恰当的计算给定数据的内积,将数据从输入空间的非线性转变到特征空间,特征空间具有更高甚至无限的维度,从而使得数据在该空间中被转换成线性可分的。如下图所示,我们把二维平面的一组数据,通过核函数映射到了一个三维空间中,这样,我们的超平面就面成了一个平面(在二维空间中是一条直线),这个平面就可以准确的把数据划分开了。 核函数有Sigmoid核、线性核、多项式核和高斯核等,其中高斯核和多项式核比较常用,两种核函数均可以把低维数据映射到高维数据。高斯核的公式如下,σ是达到率,即函数值跌落到0的速度参数: 多项式核函数的公式如下,R为实数,d为低维空间的维数: 应用于我们的上个例子,我们先定义,用ϕ:x→H表示从输入空间x⊂Rn到特征空间H的一个非线性变换。假设在特征空间中的问题是线性可分的,那么对应的最优超平面为: 通过拉格朗日函数我们推导出: 带入上式得特征空间的最优超平面为: 这里的ϕT(xi)ϕ(x)表示内积,用核函数代替内积则为:

    3.3 核函数解释

    假设有两个输入样本,它们均为二维行向量x1=[x1,x2]x1=[x1,x2]他们的内积为: 这样我们就把二维数据映射成了三维数据,对于高斯核的映射,会用到泰勒级数展开式,读者可以自行推导一下。

    4 SMO算法

    SMO算法的目标是求出一系列α,一旦求出了这些α,就很容易计算出权重向量w和b,并得到分隔超平面。
    SMO算法的工作原理是:每次循环中选择两个α进行优化处理。一旦找到一对合适的α,那么就增大其中一个同时减小另一个。这里所谓的“合适”就是指两个α必须要符合一定的条件,条件之一就是这两个α必须要在间隔边界之外,而其第二个条件则是这两个α还没有进行过区间化处理或者不在边界上。